Re: [PATCH] lib/int_sqrt.c: Optimize square root function

From	Peter Zijlstra <peterz@infradead.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH] lib/int_sqrt.c: Optimize square root function
Date	2017-07-21 15:30 +0200
Message-ID	<u5Gae-5lR-7@gated-at.bofh.it> (permalink)
References	(5 earlier) <u5owG-2Da-19@gated-at.bofh.it> <u5sgW-4Zm-21@gated-at.bofh.it> <u5t3j-5yN-3@gated-at.bofh.it> <u5EBs-4jK-31@gated-at.bofh.it> <u5F4u-4Ir-7@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

On Fri, Jul 21, 2017 at 05:15:10AM -0700, Joe Perches wrote:
> On Fri, 2017-07-21 at 13:40 +0200, Peter Zijlstra wrote:
> > @@ -21,7 +22,11 @@ unsigned long int_sqrt(unsigned long x)
> >  	if (x <= 1)
> >  		return x;
> >  
> > -	m = 1UL << (BITS_PER_LONG - 2);
> > +	m = 1UL << (__fls(x) & ~1U);
> > +
> > +	while (m > x)
> > +		m >>= 2;
> 
> while (m > x) ?
> 
> Belt and suspenders if __fls is broken?

Hmm... you're right, that should not happen. It is a remnant from when I
rounded up, like:

	m = 1UL << ((__fls(x) + 1) & ~1UL);

Because I worried about the case where m == x, which is not included in
the loop above (but works when you look at the actual computation loop
and passes VALIDATE=1).


But check this... I cannot explain :/

When I remove that loop, we, as fully expected, loose 1 branch, but the
cycle count for the branch-cold case shoots up. Must be something GCC
does.


EVENT=0 -DNEW=1 -DFLS=1
event: 19.626050 +- 0.038995
EVENT=0 -DNEW=1 -DFLS=1 -DWIPE_BTB=1
event: 109.610670 +- 0.425667

EVENT=0 -DNEW=1 -DFLS=1 -DANSHUL=1
event: 21.445680 +- 0.043782
EVENT=0 -DNEW=1 -DFLS=1 -DANSHUL=1 -DWIPE_BTB=1
event: 83.590420 +- 0.142126


EVENT=4 -DNEW=1 -DFLS=1
event: 20.252330 +- 0.005265
EVENT=4 -DNEW=1 -DFLS=1 -DWIPE_BTB=1
event: 20.252340 +- 0.005265

EVENT=4 -DNEW=1 -DFLS=1 -DANSHUL=1
event: 21.252300 +- 0.005266
EVENT=4 -DNEW=1 -DFLS=1 -DANSHUL=1 -DWIPE_BTB=1
event: 21.252300 +- 0.005266


EVENT=5 -DNEW=1 -DFLS=1
event: 0.019370 +- 0.000732
EVENT=5 -DNEW=1 -DFLS=1 -DWIPE_BTB=1
event: 3.665240 +- 0.005309

EVENT=5 -DNEW=1 -DFLS=1 -DANSHUL=1
event: 0.020150 +- 0.000755
EVENT=5 -DNEW=1 -DFLS=1 -DANSHUL=1 -DWIPE_BTB=1
event: 2.225330 +- 0.004875


Let me dig out another GCC version current:

  gcc (Debian 6.3.0-18) 6.3.0 20170516

Thread

Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-20 13:30 +0200
  Re: [PATCH] lib/int_sqrt.c: Optimize square root function Joe Perches <joe@perches.com> - 2017-07-20 14:00 +0200
    Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-20 16:20 +0200
  Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-20 17:30 +0200
  Re: [PATCH] lib/int_sqrt.c: Optimize square root function Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-20 20:40 +0200
    Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-21 00:40 +0200
      Re: [PATCH] lib/int_sqrt.c: Optimize square root function Linus Torvalds <torvalds@linux-foundation.org> - 2017-07-21 01:30 +0200
        Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-21 13:50 +0200
          Re: [PATCH] lib/int_sqrt.c: Optimize square root function Joe Perches <joe@perches.com> - 2017-07-21 14:20 +0200
            Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-21 15:30 +0200
              Re: [PATCH] lib/int_sqrt.c: Optimize square root function Peter Zijlstra <peterz@infradead.org> - 2017-07-21 15:40 +0200

csiph-web