[PATCH -v2 2/3] lib/int_sqrt: Optimize initial value compute

From: Peter Zijlstra
Date: Fri Oct 20 2017 - 12:48:59 EST


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
when doing a CDF on idle times; the linear search is near to worst
case, while the binary search of __fls() is a constant 6 (or 5 on
32bit) 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.

Acked-by: Will Deacon <will.deacon@xxxxxxx>
Suggested-by: Joe Perches <joe@xxxxxxxxxxx>
Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
---
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 <linux/kernel.h>
#include <linux/export.h>
+#include <linux/bitops.h>

/**
* 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;