lkml.org 
[lkml]   [2018]   [Feb]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Date
    Subject[PATCH 3.16 094/136] lib/int_sqrt: optimize small argument
    3.16.54-rc1 review patch.  If anyone has any objections, please let me know.

    ------------------

    From: Peter Zijlstra <peterz@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.876503355@infradead.org
    Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm")
    Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
    Suggested-by: Anshul Garg <aksgarg1989@gmail.com>
    Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Davidlohr Bueso <dave@stgolabs.net>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: Ingo Molnar <mingo@kernel.org>
    Cc: Will Deacon <will.deacon@arm.com>
    Cc: Joe Perches <joe@perches.com>
    Cc: David Miller <davem@davemloft.net>
    Cc: Matthew Wilcox <mawilcox@microsoft.com>
    Cc: Kees Cook <keescook@chromium.org>
    Cc: Michael Davidson <md@google.com>
    Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
    Signed-off-by: Ben Hutchings <ben@decadent.org.uk>
    ---
    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;
    \
     
     \ /
      Last update: 2018-02-11 05:47    [W:4.090 / U:0.164 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site