From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753375AbcA2D6W (ORCPT ); Thu, 28 Jan 2016 22:58:22 -0500 Received: from v094114.home.net.pl ([79.96.170.134]:58921 "HELO v094114.home.net.pl" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1751784AbcA2D6V (ORCPT ); Thu, 28 Jan 2016 22:58:21 -0500 From: "Rafael J. Wysocki" To: Andi Kleen Cc: akpm@linux-foundation.org, linux-kernel@vger.kernel.org, davidlohr.bueso@hp.com, rafael.j.wysocki@intel.com, lenb@kernel.org, Andi Kleen Subject: Re: [PATCH] Optimize int_sqrt for small values for faster idle Date: Fri, 29 Jan 2016 04:59:16 +0100 Message-ID: <2197456.e7XNAplqRP@vostro.rjw.lan> User-Agent: KMail/4.11.5 (Linux/4.5.0-rc1+; KDE/4.11.5; x86_64; ; ) In-Reply-To: <1454017365-8509-1-git-send-email-andi@firstfloor.org> References: <1454017365-8509-1-git-send-email-andi@firstfloor.org> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="utf-8" Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thursday, January 28, 2016 01:42:45 PM 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. > > I instrumented the function on my workstation and most values are > 16bit only and most others 32bit (50% percentile is 122094, > 75% is 3699533). > > sqrt is implemented by starting with an initial estimation, > and then iterating. int_sqrt currently only uses a fixed > estimating which is good for 64bits worth of input. > > This patch adds some checks at the beginning to start with > a better estimate for values fitting in 8, 16bit and 32bit. > This makes int_sqrt between 60+% faster for values in 16bit, > and still somewhat faster (between 10 and 30%) for larger values > upto 32bit. Full 64bit is slightly slower. > > This optimizes the short idle calls and does not hurt the > long sleep (which probably do not care) much. > > An alternative would be a full table drive approach, or > trying some inverted sqrt optimization, but this simple change > already seems to have a good payoff. I'm wondering if you have any numbers on how much of a difference this makes in practice in terms of energy consumption, performance, latency etc. Thanks, Rafael