Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1695651

Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute

Show all headers | View raw

Hi Peter,

On Mon, Jul 24, 2017 at 05:16:32PM +0200, Peter Zijlstra wrote:
> 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; the linear search is near to worst case, while the binary
> search of __fls() is a constant 6 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.

The hardware fls version works nicely for arm64, where it can be implemented
using the clz instruction (via the __builtin_clzl intrinsic).

Acked-by: Will Deacon <will.deacon@arm.com>

Cheers,

Will

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 0/3] lib/int_sqrt: Fix, optimize and document Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
    Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-24 19:40 +0200
      Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-25 10:20 +0200
        Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-25 17:50 +0200
          Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Peter Zijlstra <peterz@infradead.org> - 2017-07-25 18:10 +0200
    Re: [PATCH 2/3] lib/int_sqrt: Optimize initial value compute Will Deacon <will.deacon@arm.com> - 2017-07-25 14:00 +0200
  [PATCH 1/3] lib/int_sqrt: Optimize small argument Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  [PATCH 3/3] lib/int_sqrt: Adjust comments Peter Zijlstra <peterz@infradead.org> - 2017-07-24 17:40 +0200
  Re: [PATCH 0/3] lib/int_sqrt: Fix, optimize and document Joe Perches <joe@perches.com> - 2017-07-24 17:50 +0200

csiph-web