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 <pet...@infradead.org>
>
> 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/20171020164644.876503...@infradead.org
> Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm")
> Signed-off-by: Peter Zijlstra (Intel) <pet...@infradead.org>
> Suggested-by: Anshul Garg <aksgarg1...@gmail.com>
> Acked-by: Linus Torvalds <torva...@linux-foundation.org>
> Cc: Davidlohr Bueso <d...@stgolabs.net>
> Cc: Thomas Gleixner <t...@linutronix.de>
> Cc: Ingo Molnar <mi...@kernel.org>
> Cc: Will Deacon <will.dea...@arm.com>
> Cc: Joe Perches <j...@perches.com>
> Cc: David Miller <da...@davemloft.net>
> Cc: Matthew Wilcox <mawil...@microsoft.com>
> Cc: Kees Cook <keesc...@chromium.org>
> Cc: Michael Davidson <m...@google.com>
> Signed-off-by: Andrew Morton <a...@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torva...@linux-foundation.org>
> Signed-off-by: Arnd Bergmann <a...@arndb.de>
> Signed-off-by: Greg Kroah-Hartman <gre...@linuxfoundation.org>
>
> ---
> 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;
>
>
