From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755413AbdGXPi7 (ORCPT ); Mon, 24 Jul 2017 11:38:59 -0400 Received: from merlin.infradead.org ([205.233.59.134]:51108 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752826AbdGXPij (ORCPT ); Mon, 24 Jul 2017 11:38:39 -0400 Message-Id: <20170724153455.710696863@infradead.org> User-Agent: quilt/0.61-1 Date: Mon, 24 Jul 2017 17:16:32 +0200 From: Peter Zijlstra To: torvalds@linux-foundation.org, akpm@linux-foundation.org Cc: dave@stgolabs.net, aksgarg1989@gmail.com, tglx@linutronix.de, mingo@kernel.org, will.deacon@arm.com, joe@perches.com, peterz@infradead.org, linux-kernel@vger.kernel.org Subject: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute References: <20170724151630.447009076@infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline; filename=peterz-int_sqrt-opt-2.patch Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The initial value (@m) compute is: m = 1UL << (BITS_PER_LONG - 2); while (m > x) m >>= 2; Which is a linear search for the highest even bit smaller or equal to @x We can implement this using a binary search using __fls() (or better when its hardware implemented). m = 1UL << (__fls(x) & ~1UL); Especially for small values of @x; which are the more common arguments; the linear search is near to worst case, while the binary search of __fls() is a constant 6 branches. cycles: branches: branch-misses: PRE: hot: 43.633557 +- 0.034373 45.333132 +- 0.002277 0.023529 +- 0.000681 cold: 207.438411 +- 0.125840 45.333132 +- 0.002277 6.976486 +- 0.004219 SOFTWARE FLS: hot: 29.576176 +- 0.028850 26.666730 +- 0.004511 0.019463 +- 0.000663 cold: 165.947136 +- 0.188406 26.666746 +- 0.004511 6.133897 +- 0.004386 HARDWARE FLS: hot: 24.720922 +- 0.025161 20.666784 +- 0.004509 0.020836 +- 0.000677 cold: 132.777197 +- 0.127471 20.666776 +- 0.004509 5.080285 +- 0.003874 Averages computed over all values <128k using a LFSR to generate order. Cold numbers have a LFSR based branch trace buffer 'confuser' ran between each int_sqrt() invocation. Signed-off-by: Peter Zijlstra (Intel) --- lib/int_sqrt.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -7,6 +7,7 @@ #include #include +#include /** * int_sqrt - rough approximation to sqrt @@ -21,10 +22,7 @@ unsigned long int_sqrt(unsigned long x) if (x <= 1) return x; - m = 1UL << (BITS_PER_LONG - 2); - while (m > x) - m >>= 2; - + m = 1UL << (__fls(x) & ~1UL); while (m != 0) { b = y + m; y >>= 1;