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

Groups > linux.kernel > #1322582

Re: [PATCH] Optimize int_sqrt for small values for faster idle

Show all headers | View raw

Hello,

 > -	m = 1UL << (BITS_PER_LONG - 2);
 > +	if (x <= 0xffff) {
 > +		if (m <= 0xff)
 > +			m = 1UL << (8 - 2);
 > +		else
 > +			m = 1UL << (16 - 2);
 > +	} else if (x <= 0xffffffff)
 > +		m = 1UL << (32 - 2);
 > +	else
 > +		m = 1UL << (BITS_PER_LONG - 2);
 >   	while (m != 0) {
 >   		b = y + m;
 >   		y >>= 1;
 >


I think, m can be initialized with

1 << (greatest multiple of 2 less than or equal to (position of most significant bit of x))

i.e. 1 << ((position of most significant bit of x) & 62)

without changing the outcome of the original algorithm (as long as x<m the loop does just m >>= 2).

I believe, that for (position of most significant bit of x) there is an efficient macro, and
some processors directly have an instruction for it. So this would probably be faster than your suggestion
for an initial starting value and give an even better starting value (cutting in some cases further on the number of
while loop interations).

If one just wants to achieve a result with a certain relative error in terms of the fraction of the input, one can
probably only look at the most significant bit and a few following bits of x.

Sincerely,

Thomas

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

Thread

[PATCH] Optimize int_sqrt for small values for faster idle Andi Kleen <andi@firstfloor.org> - 2016-01-28 22:50 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle kbuild test robot <lkp@intel.com> - 2016-01-28 23:10 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Joe Perches <joe@perches.com> - 2016-01-28 23:20 +0100
    Re: [PATCH] Optimize int_sqrt for small values for faster idle Andi Kleen <andi@firstfloor.org> - 2016-01-28 23:50 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle kbuild test robot <lkp@intel.com> - 2016-01-28 23:20 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Joe Perches <joe@perches.com> - 2016-01-28 23:30 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Andi Kleen <andi@firstfloor.org> - 2016-01-28 23:40 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Eric Dumazet <eric.dumazet@gmail.com> - 2016-01-28 23:40 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle "Rafael J. Wysocki" <rjw@rjwysocki.net> - 2016-01-29 05:00 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Thomas Rohwer <trohwer85@gmail.com> - 2016-01-31 08:30 +0100
  Re: [PATCH] Optimize int_sqrt for small values for faster idle Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-02-01 22:30 +0100
    Re: [PATCH] Optimize int_sqrt for small values for faster idle Andi Kleen <ak@linux.intel.com> - 2016-02-01 22:40 +0100
      Re: [PATCH] Optimize int_sqrt for small values for faster idle Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-02-02 00:10 +0100
        Re: [PATCH] Optimize int_sqrt for small values for faster idle Andi Kleen <ak@linux.intel.com> - 2016-02-02 01:10 +0100
        Re: [PATCH] Optimize int_sqrt for small values for faster idle Eric Dumazet <eric.dumazet@gmail.com> - 2016-02-02 01:40 +0100
          Re: [PATCH] Optimize int_sqrt for small values for faster idle Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-02-02 21:50 +0100
            Re: [PATCH] Optimize int_sqrt for small values for faster idle Eric Dumazet <eric.dumazet@gmail.com> - 2016-02-02 22:40 +0100
      Re: [PATCH] Optimize int_sqrt for small values for faster idle Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2016-02-07 22:40 +0100

csiph-web