From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751170AbcBAXIv (ORCPT ); Mon, 1 Feb 2016 18:08:51 -0500 Received: from mail-wm0-f41.google.com ([74.125.82.41]:35126 "EHLO mail-wm0-f41.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750743AbcBAXIt (ORCPT ); Mon, 1 Feb 2016 18:08:49 -0500 From: Rasmus Villemoes To: Andi Kleen Cc: Andi Kleen , akpm@linux-foundation.org, linux-kernel@vger.kernel.org, davidlohr.bueso@hp.com, rafael.j.wysocki@intel.com, lenb@kernel.org Subject: Re: [PATCH] Optimize int_sqrt for small values for faster idle Organization: D03 References: <1454017365-8509-1-git-send-email-andi@firstfloor.org> <87y4b4azsy.fsf@rasmusvillemoes.dk> <20160201213622.GA15302@tassilo.jf.intel.com> X-Hashcash: 1:20:160201:ak@linux.intel.com::9Z5nzxyT8nxjs4UK:00000000000000000000000000000000000000000001Sxz X-Hashcash: 1:20:160201:lenb@kernel.org::o89FihPoCpKGNVeK:0014uj X-Hashcash: 1:20:160201:akpm@linux-foundation.org::DFFej2IeFVJGi5KV:0000000000000000000000000000000000001SB6 X-Hashcash: 1:20:160201:linux-kernel@vger.kernel.org::+DwD+39q6WuN2lX4:0000000000000000000000000000000002PMt X-Hashcash: 1:20:160201:rafael.j.wysocki@intel.com::Quz8itFQC0O0krrY:000000000000000000000000000000000005YXf X-Hashcash: 1:20:160201:davidlohr.bueso@hp.com::jzjNQmmpks0HQTbj:0000000000000000000000000000000000000006v5t X-Hashcash: 1:20:160201:andi@firstfloor.org::YYzBuIXJZDnfuXcX:0000000000000000000000000000000000000000007VxD Date: Tue, 02 Feb 2016 00:08:46 +0100 In-Reply-To: <20160201213622.GA15302@tassilo.jf.intel.com> (Andi Kleen's message of "Mon, 1 Feb 2016 13:36:22 -0800") Message-ID: <87powgav0h.fsf@rasmusvillemoes.dk> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Feb 01 2016, Andi Kleen wrote: > On Mon, Feb 01, 2016 at 10:25:17PM +0100, Rasmus Villemoes wrote: >> On Thu, Jan 28 2016, Andi Kleen wrote: >> >> > From: Andi Kleen >> > >> > The menu cpuidle governor does at least two int_sqrt() each time >> > we go into idle in get_typical_interval to compute stddev >> > >> > int_sqrts take 100-120 cycles each. Short idle latency is important >> > for many workloads. >> > >> >> If you want to optimize get_typical_interval(), why not just take the >> square root out of the equation (literally)? >> >> Something like > > Looks good. Yes that's a better fix. > Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?) While there and doing the math, I noticed that the variance computation may _theoretically_ overflow (if half the observations are 0, half C, the variance before the division should be around INTERVALS*C^2/4, which is around 2^65 for C=UINT_MAX and INTERVALS=8). I have no idea if it actually matters, but it can be fixed by lowering the initial threshold from UINT_MAX to sqrt(4*U64_MAX/INTERVALS) ~~ 3e9. However, this would make it possible that all observations are larger than the initial threshold, so we'd have to protect against a division by zero... Rasmus