[PATCH 1/3] lib/int_sqrt: Optimize small argument

From: Peter Zijlstra
Date: Mon Jul 24 2017 - 11:39:39 EST


The current int_sqrt() computation is sub-optimal for the case of
small @x.

In this case, the compute loop:

while (m != 0) {
b = y + m;
y >>= 1;

if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}

can be reduced to:

while (m > x)
m >>= 2;

Because y==0, b==m and until x>=m y will remain 0.

And while this is computationally equivalent, it runs much faster
because there's less code, in particular less branches.

cycles: branches: branch-misses:

OLD:

hot: 45.109444 +- 0.044117 44.333392 +- 0.002254 0.018723 +- 0.000593
cold: 187.737379 +- 0.156678 44.333407 +- 0.002254 6.272844 +- 0.004305

PRE:

hot: 67.937492 +- 0.064124 66.999535 +- 0.000488 0.066720 +- 0.001113
cold: 232.004379 +- 0.332811 66.999527 +- 0.000488 6.914634 +- 0.006568

POST:

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

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.

Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm")
Suggested-by: Anshul Garg <aksgarg1989@xxxxxxxxx>
Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
---
lib/int_sqrt.c | 3 +++
1 file changed, 3 insertions(+)

--- a/lib/int_sqrt.c
+++ b/lib/int_sqrt.c
@@ -22,6 +22,9 @@ unsigned long int_sqrt(unsigned long x)
return x;

m = 1UL << (BITS_PER_LONG - 2);
+ while (m > x)
+ m >>= 2;
+
while (m != 0) {
b = y + m;
y >>= 1;