Messages in this thread | | | Date | 28 Apr 2016 15:15:51 -0400 | From | "George Spelvin" <> | Subject | Re: [patch V3] lib: GCD: add binary GCD algorithm |
| |
> 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.
| |