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

Groups > linux.kernel > #1390471

Re: [patch V3] lib: GCD: add binary GCD algorithm

Show all headers | View raw

> How does a CPU lack an efficient ffs/ctz anyway? There are all sorts
> of ways to implement it without a native insn, some of which are
> almost or just as fast as the native insn on cpus that have the
> latter. On anything with a fast multiply, the de Bruijn sequence
> approach is near-optimal, and otherwise one of the binary-search type
> approaches (possibly branchless) can be used. If the compiler doesn't
> generate an appropriate one for __builtin_ctz, that's arguably a
> compiler bug.

What's wanted here is something faster than any of those.
Yes, there's a simple constant-time branch-free implementation:

unsigned inline __attribute__((const))
hweight32(uint32_t x)
{
	x -= (x >> 1) & 0x55555555;
	x  = ((x >> 2) & 0x33333333) + (x & 0x33333333);
	x += x >> 4;
	x &= 0x0f0f0f0f;
	x += x >> 8;
	x += x >> 16;
	return x & 63;
}

unsigned inline __attribute__((const))
__ffs32(uint32_t x)
{
	return hweight(~x & (x-1));
}

but if you work it through, that's about 19 instructions; a few more on
platforms without 32-bit immediates.  The shift itself makes an even 20,
and there are a lot of sequential dependencies (I count a 17-op chain
including the shift) limiting execution time.

The de Bruijn hack reduces the length but adds a memory access for
the table lookup.  (http://supertech.csail.mit.edu/papers/debruijn.pdf)

In the GCD code, the number to normalize is basically random, so the
normalization loop shifts an average of 1 bit.  One bit half the time,
a second bit 1/4 of the time, etc.

(The posted code in the FAST_FFS case omits one guaranteed shift at the
end of the loop because the normalization code is constant-time.)

So "fast __ffs" basically means faster than *one* iteration of
"while (!(x & 1)) x >>= 1;".

In this case "fast" means cheaper than *one* unpredictable branch, which
is a very small handful of instructions.

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

Thread

[patch V3] lib: GCD: add binary GCD algorithm zengzhaoxiu@163.com - 2016-04-28 14:00 +0200
  Re: [patch V3] lib: GCD: add binary GCD algorithm Josh Juran <jjuran@gmail.com> - 2016-04-28 19:20 +0200
  Re: [patch V3] lib: GCD: add binary GCD algorithm "George Spelvin" <linux@horizon.com> - 2016-04-28 19:20 +0200
    Re: [patch V3] lib: GCD: add binary GCD algorithm Geert Uytterhoeven <geert@linux-m68k.org> - 2016-04-28 20:00 +0200
      Re: [patch V3] lib: GCD: add binary GCD algorithm Rich Felker <dalias@libc.org> - 2016-04-28 20:10 +0200
        Re: [patch V3] lib: GCD: add binary GCD algorithm Geert Uytterhoeven <geert@linux-m68k.org> - 2016-04-28 20:20 +0200
        Re: [patch V3] lib: GCD: add binary GCD algorithm "George Spelvin" <linux@horizon.com> - 2016-04-28 21:20 +0200
    Re: [patch V3] lib: GCD: add binary GCD algorithm Sam Ravnborg <sam@ravnborg.org> - 2016-04-28 22:00 +0200
  Re: [patch V3] lib: GCD: add binary GCD algorithm James Bottomley <James.Bottomley@HansenPartnership.com> - 2016-04-28 19:30 +0200

csiph-web