* + lib-int_sqrt-optimize-initial-value-compute.patch added to -mm tree
@ 2017-10-20 22:18 akpm
0 siblings, 0 replies; only message in thread
From: akpm @ 2017-10-20 22:18 UTC (permalink / raw)
To: peterz, aksgarg1989, davem, dave, joe, keescook, mawilcox, md,
mingo, tglx, torvalds, will.deacon, mm-commits
The patch titled
Subject: lib/int_sqrt: optimize initial value compute
has been added to the -mm tree. Its filename is
lib-int_sqrt-optimize-initial-value-compute.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/lib-int_sqrt-optimize-initial-value-compute.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/lib-int_sqrt-optimize-initial-value-compute.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Peter Zijlstra <peterz@infradead.org>
Subject: lib/int_sqrt: optimize initial value compute
The initial value (@m) compute is:
m = 1UL << (BITS_PER_LONG - 2);
while (m > x)
m >>= 2;
Which is a linear search for the highest even bit smaller or equal to @x
We can implement this using a binary search using __fls() (or better when
its hardware implemented).
m = 1UL << (__fls(x) & ~1UL);
Especially for small values of @x; which are the more common arguments
when doing a CDF on idle times; the linear search is near to worst case,
while the binary search of __fls() is a constant 6 (or 5 on 32bit)
branches.
cycles: branches: branch-misses:
PRE:
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
SOFTWARE FLS:
hot: 29.576176 +- 0.028850 26.666730 +- 0.004511 0.019463 +- 0.000663
cold: 165.947136 +- 0.188406 26.666746 +- 0.004511 6.133897 +- 0.004386
HARDWARE FLS:
hot: 24.720922 +- 0.025161 20.666784 +- 0.004509 0.020836 +- 0.000677
cold: 132.777197 +- 0.127471 20.666776 +- 0.004509 5.080285 +- 0.003874
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.936577234@infradead.org
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Suggested-by: Joe Perches <joe@perches.com>
Acked-by: Will Deacon <will.deacon@arm.com>
Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Anshul Garg <aksgarg1989@gmail.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: David Miller <davem@davemloft.net>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Kees Cook <keescook@chromium.org>
Cc: Matthew Wilcox <mawilcox@microsoft.com>
Cc: Michael Davidson <md@google.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/int_sqrt.c | 6 ++----
1 file changed, 2 insertions(+), 4 deletions(-)
diff -puN lib/int_sqrt.c~lib-int_sqrt-optimize-initial-value-compute lib/int_sqrt.c
--- a/lib/int_sqrt.c~lib-int_sqrt-optimize-initial-value-compute
+++ a/lib/int_sqrt.c
@@ -7,6 +7,7 @@
#include <linux/kernel.h>
#include <linux/export.h>
+#include <linux/bitops.h>
/**
* int_sqrt - rough approximation to sqrt
@@ -21,10 +22,7 @@ unsigned long int_sqrt(unsigned long x)
if (x <= 1)
return x;
- m = 1UL << (BITS_PER_LONG - 2);
- while (m > x)
- m >>= 2;
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2017-10-20 22:18 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-10-20 22:18 + lib-int_sqrt-optimize-initial-value-compute.patch added to -mm tree akpm
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).