On Mon, 2019-04-01 at 19:01 +0200, Greg Kroah-Hartman wrote: > 4.4-stable review patch. If anyone has any objections, please let me know.
If this is to be ported just for an optimization (which I think is dubious as it's not a bug fix), why not port the __fls optimization too? __fls has a bigger effect on performance. ------------------ > > From: Peter Zijlstra <[email protected]> > > commit 3f3295709edea6268ff1609855f498035286af73 upstream. > > The current int_sqrt() computation is sub-optimal for the case of small > @x. Which is the interesting case when we're going to do cumulative > distribution functions on idle times, which we assume to be a random > variable, where the target residency of the deepest idle state gives an > upper bound on the variable (5e6ns on recent Intel chips). > > In the case of small @x, 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. > > Link: http://lkml.kernel.org/r/[email protected] > Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm") > Signed-off-by: Peter Zijlstra (Intel) <[email protected]> > Suggested-by: Anshul Garg <[email protected]> > Acked-by: Linus Torvalds <[email protected]> > Cc: Davidlohr Bueso <[email protected]> > Cc: Thomas Gleixner <[email protected]> > Cc: Ingo Molnar <[email protected]> > Cc: Will Deacon <[email protected]> > Cc: Joe Perches <[email protected]> > Cc: David Miller <[email protected]> > Cc: Matthew Wilcox <[email protected]> > Cc: Kees Cook <[email protected]> > Cc: Michael Davidson <[email protected]> > Signed-off-by: Andrew Morton <[email protected]> > Signed-off-by: Linus Torvalds <[email protected]> > Signed-off-by: Arnd Bergmann <[email protected]> > Signed-off-by: Greg Kroah-Hartman <[email protected]> > > --- > 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; > >
