lib/int_sqrt: Fix, optimize and document

Hi,

Here are a few patches that should improve things lib/int_sqrt. As stated elsewhere; I'm looking at using int_sqrt() to calculate the stdev on a normal distribution and am expecting the input values to be smallish.

In any case, these optimizations should work fine for large numbers too. And if you have a find-last-set or count-leading-zeros instruction they rock ;-)

I can post the tool used to generate the numbers or do a patch to add it to tools/testing/ if people care. The cold numbers are fairly sensitive to code layout (GCC version, random changes etc..), so I expect the branch predictor of my SKL is only partially confused or there's other things at play. However the general trend in the numbers seems fairly stable.

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.

---
 lib/int_sqrt.c |    3 +++
 1 file changed, 3 insertions(+)

@@ -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;

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.

---
 lib/int_sqrt.c |    6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

@@ -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;

Ack. You have numbers, it's all good.

Except I'd still want you to comment on why you cared and about which piece of your upcoming code this is going to matter for, ok?

Linus

Thanks!

I did an RFC here:

https://lkml.kernel.org/r/[email protected]

And that is the patch that, through Thomas asking me about our sqrt(), kick started these here patches.

There are a few more sites that would need similar treatment, but I've not gone through the entire idle predictor yet.

Basically the observation is that, for performance, we seem to pick too deep an idle state. The result is that the exit latency from this state is higher than we'd like and performance hurts because of that.

The thinking is that if you estimate the average idle duration, you'll be too long 50% of the time -- that is after all a fundamental part of being the average. My proposed solution in that patch is computing the value for which we're too long less than n%, in statistic speak:

P(X < x)

Which is given by the CDF(x). In any case, assuming a normal distribution, you end up with something like:

avg - Z * stdev

Where Z depends on our cut-off and is basically a table lookup. The whole sqrt() comes from having to compute the stdev, as that is the square root of the variance.

Christ Peter.

I meant add the explanation to the commit log, to explain *why* you care about this function that nobody has ever cared about before.

Please. Document your patches. Don't make people ask for explanations.

I've asked now *three* times about this, and still the patch submission had no explanation at all about why this mattered.

How many times do people have to ask before you start saying "oh, maybe I should explain why.." in your patch.

Linus

Yes, I _am_ a tad dense these days.. Let me go do that.

Hi Peter,

The hardware fls version works nicely for arm64, where it can be implemented using the clz instruction (via the __builtin_clzl intrinsic).

Cheers,

Will

Our current int_sqrt() is not rough nor any approximation; it calculates the exact value of: floor(sqrt()). Document this.

---
 lib/int_sqrt.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

@@ -10,10 +10,10 @@
 #include <linux/bitops.h>
 
 /**
- * int_sqrt - rough approximation to sqrt
+ * int_sqrt - computes the integer square root
  * @x: integer of which to calculate the sqrt
  *
- * A very rough approximation to the sqrt() function.
+ * Computes: floor(sqrt(x))
  */
 unsigned long int_sqrt(unsigned long x)
 {

Thanks Peter.