• Peter Zijlstra's avatar
    lib/int_sqrt: optimize small argument · aab86217
    Peter Zijlstra authored
    commit 3f329570 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: 30493cc9 ("lib/int_sqrt.c: optimize square root algorithm")
    Signed-off-by: 's avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Suggested-by: 's avatarAnshul Garg <aksgarg1989@gmail.com>
    Acked-by: 's 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: 's avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: 's avatarLinus Torvalds <torvalds@linux-foundation.org>
    Signed-off-by: 's avatarArnd Bergmann <arnd@arndb.de>
    Signed-off-by: 's avatarGreg Kroah-Hartman <gregkh@linuxfoundation.org>
    aab86217
Name
Last commit
Last update
Documentation Loading commit data...
arch Loading commit data...
block Loading commit data...
certs Loading commit data...
crypto Loading commit data...
drivers Loading commit data...
firmware Loading commit data...
fs Loading commit data...
include Loading commit data...
init Loading commit data...
ipc Loading commit data...
kernel Loading commit data...
lib Loading commit data...
mm Loading commit data...
net Loading commit data...
samples Loading commit data...
scripts Loading commit data...
security Loading commit data...
sound Loading commit data...
tools Loading commit data...
usr Loading commit data...
virt Loading commit data...
.cocciconfig Loading commit data...
.get_maintainer.ignore Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
.mailmap Loading commit data...
COPYING Loading commit data...
CREDITS Loading commit data...
Kbuild Loading commit data...
Kconfig Loading commit data...
MAINTAINERS Loading commit data...
Makefile Loading commit data...
README Loading commit data...