• Peter Zijlstra's avatar
    lib/int_sqrt: optimize small argument · 3f329570
    Peter Zijlstra authored
    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: 30493cc9 ("lib/int_sqrt.c: optimize square root algorithm")
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Suggested-by: default avatarAnshul Garg <aksgarg1989@gmail.com>
    Acked-by: default avatarLinus 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: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    3f329570
int_sqrt.c 715 Bytes