efficient approach to check a set bit

[Ian Collins]

There's a mult in the unoptimized version, but surprisingly no div.
My x86-fu is weak, so I can't really decode it, but I know there are no
DIVs in there. Lotsa moves, a mult, four shifts, two adds, and two
subtracts.

Sun CC does much the same.

Most fun is the use of the constant 0xBACF914D in the mod calculation.
They multiply that by the value to lookup, and discard the low 32-bits
of the result. Then from that they subtract the value to lookup, and
shift the result right by one. From there, things start to get strange,
until, 11 instructions later, they magically end up with an index into
the lookup table.

Yes, same constant, similar jiggery pokery.

In short, I'm very glad that people specialize in exactly this thing.

!

 

[James Dow Allen]

From the evil tricks department, assuming you really do have exactly
one bit set: the values 1, 2, 4, ..., 1<<31 are all distinct modulo
37, so simply reduce modulo 37 and then use a lookup table.

This is shown (in a slightly disguised form) in
Bit Twiddling Hacks
By Sean Eron Anderson
Anderson discovered it but "found it was invented earlier
by Reiser, according to Hacker's Delight."

Anderson also shows another way using multiply instead
of divide, though *not* the replace-divide-with-multiply
mentioned downthread.

Speaking of that replace-divide-with-multiply; it
doesn't work when the divisor is variable, but
what if it's variable at compile-time
but fixed early during initialization? Is any
comp.programmer as masochisticly perfectionistic
as I might once have been to handle *those* cases
with optimized constant division?

James Dow Allen

 

[bartc]

Relative runtimes on a quick-and-dirty benchmark on my Athlon64 (I'm
presuming the LUT was cached):

unoptimized -O2
Ben: 1.0 1.0
Mod37: 1.4 0.7

Looking at the assembly, gcc replaced the mod 37 with some hacker
goodies (not a div).

gcc is always giving problems when trying to benchmark things. Sometimes it
optimises out the very thing you're trying to measure the speed of.

In my own tests I had to discard the results that gave Ben's code a runtime
of 0.

I think if there exists some code that does the equivalent of the Mod37
method, but is faster, then perhaps that should become the evil trick
instead.

 

[James Dow Allen]

gcc is always giving problems when trying to benchmark things. Sometimes it
optimises out the very thing you're trying to measure the speed of.

But if there's a way to speed up mod 37, isn't that what
you'd want to measure the speed of?

Anyway, it's often not hard to defeat gcc's optimizations, either
by changing -O level, or just making a constancy less visible.

As I posted in this thread an hour ago, Anderson *does*
offer an alternative to the mod 37 trick; I don't know
about relative speed.

James

 

[Mark Dickinson]

Most fun is the use of the constant 0xBACF914D in the mod calculation.
They multiply that by the value to lookup, and discard the low 32-bits
of the result.  Then from that they subtract the value to lookup, and
shift the result right by one.  From there, things start to get strange,
until, 11 instructions later, they magically end up with an index into
the lookup table.

Very interesting. My first guess was that 0xBACF914D gives the most
significant 32 bits of the reciprocal of 37, so that the division by
37 can be replaced with a multiplication by its reciprocal. But it
turns out to be more interesting than that: the constant is ceiling
(2^32 * 27 / 37). With gcc-4.2 -O3 on x86-64, I get the following.
(The original value, call it 'x', starts out in register edi.)

movl $-1160801971, %edx
movl %edi, %eax
mull %edx

edx now contains something close to (x*2^32*27/37) >> 32 = x * 27 /
32. (-1160801971 + 2^32 = 0xBACF914D.)

movl %edi, %eax
subl %edx, %eax
shrl %eax
addl %eax, %edx
shrl $5, %edx

Put x - x*27/37 = x*10/37 in eax; shift 1 to get x*5/37; add to the
original x*27/37 to get x*32/37; shift 5 places to get x/37. There
seems to be a possibility that the result is out by 1 or 2 by this
stage; presumably a careful analysis would show that this always
works out exactly. We've now got the quotient floor(x/37) in edx.

leal (%rdx,%rdx,8), %eax
leal (%rdx,%rax,4), %eax
subl %eax, %edi

Addition chain to multiply the quotient by 37 (1st step puts 9*edx in
eax; second step puts edx + 4*eax = 37*edx in eax.) Then subtract to
get remainder in edi: x%37 = x-37*floor(x/37).

leaq _dlog(%rip), %rax
movzbl (%rdi,%rax), %eax

Do the lookup.

In short, I'm very glad that people specialize in exactly this thing.

Me too!

 

[Mark Dickinson]

This is shown (in a slightly disguised form) in
   Bit Twiddling Hacks
   By Sean Eron Anderson
Anderson discovered it but "found it was invented earlier
by Reiser, according to Hacker's Delight."

Thanks for the reference. I have no memory of where I got this from,
but I guess it must have been some source derived from one of the
above. I just know that the constant '37' has long been embedded
somewhere in my brain for this purpose.

[...]

Speaking of that replace-divide-with-multiply; it
doesn't work when the divisor is variable, but
what if it's variable at compile-time
but fixed early during initialization?  Is any
comp.programmer as masochisticly perfectionistic
as I might once have been to handle *those* cases
with optimized constant division?

I believe GMP does something a bit like this: precalculating inverses
(at runtime) for divisors that are likely to be used more than once.
It makes sense for multi-limb divisions, where you end up repeatedly
dividing by (something related to) the top limb of the divisor.

 

[Willem]

James Dow Allen wrote:
)> > Looking at the assembly, gcc replaced the mod 37 with some hacker
)> > goodies (not a div).
)>
)> gcc is always giving problems when trying to benchmark things. Sometimes it
)> optimises out the very thing you're trying to measure the speed of.
)
) But if there's a way to speed up mod 37, isn't that what
) you'd want to measure the speed of?

If the mod37 gets sped up to some weird combination of unsigned multiply
and some shifts and adds, perhaps there is a way to do it with just the
unsigned multiply ? Perhaps there is some multiplication factor f and
constant m so that ((2^x)*f (mod 2^m)) is distinct for x from 0 to 32 ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Mark Dickinson]

Anderson also shows another way using multiply instead
of divide, though *not* the replace-divide-with-multiply
mentioned downthread.

I just checked this out: it's *much* nicer (simpler, faster,
neater, more satisfying) than the mod 37 hack!

http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

It seems to depend only on the observation that in the 32-bit
binary number:

x = 00000111011111001011010100110001

the 32 5-bit cyclic subsequences are all distinct, so the
top 5 bits of x << i are different for each i in the range
0 <= i < 32.

 

[Phil Carmody]

That's a _very_ evil trick. I like it.

If you use it, try to use a variation which avoids UB.

Reduction modulo 37 may not be a fast operation, so a
multiply and shift version may be better. A 5-bit LFSR
is your friend.

Phil

 

[Phil Carmody]

Ben Bacarisse wrote:
) And, as it happens, if you need to do the same for 64 bits, the
) smallest modulus is 67 -- the 7 making both 37 and 67 reasonably easy
) to remember.

Question for the mathematically inclined: Does it work iff the
modulus has no factors smaller than the number of bits you need ?

No.

Phil

 

[Kaz Kylheku]

gcc is always giving problems when trying to benchmark things. Sometimes it
optimises out the very thing you're trying to measure the speed of.

So what is exactly that you are trying to benchmark? Your CPU's
instructions for computing a quotient and remainder?

If that's what you are after, then C is the wrong interface,
don't you think. Write the exact instructions you want and
benchmark that.

Write down a specification which describes as precisely as possible the
entity that you are trying to benchmark, and then ensure that the
benchmark program actually measures that entity.

 

[Ian Collins]

If you use it, try to use a variation which avoids UB.

Reduction modulo 37 may not be a fast operation, so a
multiply and shift version may be better. A 5-bit LFSR
is your friend.

or an optimiser that does the trick for you.

 

[bartc]

So what is exactly that you are trying to benchmark? Your CPU's
instructions for computing a quotient and remainder?

In this case, whether a solution involving a mod operation and a table
lookup is, in general, faster or slower than one using a bunch of shifts and
masks.

I want to find out the efficiency of my C compiler in generating code for
mods, lookups, shifts and masks, not how clever it is in eliminating those
operations!

Since a simple benchmark often involves repeating a simple operation
millions of times, gcc especially tries to avoid those millions of
iterations, often resulting in zero runtimes.

Sure I can turn off optimisation completely, but that gives misleading
results too.

(I work on my own language projects and I spend a lot of time comparing
runtimes against C. If I have a recursive benchmark, I want to see how my
call/return code stacks up the call/return code that a good C compiler will
generate. Having the C compiler remove call/return operations is not really
very helpful. So it does tail recursion elimination; I could do that too,
but that's not what I'm testing...)

If that's what you are after, then C is the wrong interface,
don't you think. Write the exact instructions you want and
benchmark that.

On my cpu, there's an instruction BSF that does exactly this task, return
the bit index of the only (or lowest) set bit.

A good test is how well these C routines compare against that.

Using a benchmark which finds the set bit for 1,2,4,8,,,,42949672296 in
turn, executing the inner loop body ten times to reduce the effect of loop
overheads, and doing the whole thing 10 million times, took 670ms using
inline assembler.

Using C compilers other than gcc, took various times from 3500ms to 6600ms
(using the mask/shift code).

gcc 3.4.5 with -O0 took 7100ms.

With -O1, -O2 and -O3 it took just 62ms. That's incredible! gcc even
with -O1 outperforming tight inline assembler by ten to one. And an
optimiser which speeds things up by over 100 times!

That's why care has to be taken especially with gcc which can be too clever
for it's own good.

 

[bartc]

On my cpu, there's an instruction BSF that does exactly this task, return
the bit index of the only (or lowest) set bit.

A good test is how well these C routines compare against that.

Using a benchmark which finds the set bit for 1,2,4,8,,,,42949672296 in
turn, executing the inner loop body ten times to reduce the effect of loop
overheads, and doing the whole thing 10 million times, took 670ms using
inline assembler.

I meant just one million times; my machine is certainly not that fast.

Using C compilers other than gcc, took various times from 3500ms to 6600ms
(using the mask/shift code).

(I have an interpreted language which has a built-in operator .firstbit. The
same test took 4000ms, comparable with a normal C compiler. This shows the
advantage of having these kinds of ops built-in and known to the
language/compiler. The implementation uses, of course, the x86 BSF
instruction.)

 

[Beej Jorgensen]

gcc is always giving problems when trying to benchmark things.
Sometimes it optimises out the very thing you're trying to measure the
speed of.

Yeah--I defeated this by feeding an accumulated summary value out of the
program at the end of the run; I also checked the assembly output to
make the code was still there.

But it's hard to get C to give a legit benchmark of some approach or
another which I why I labeled it "quick and dirty". As usual, the best
you can really take away from those numbers is that "sometimes
source-level C optimizations don't work out the way you think they
will."

-Beej

 

[Nick]

There's a mult in the unoptimized version, but surprisingly no div.
My x86-fu is weak, so I can't really decode it, but I know there are no
DIVs in there. Lotsa moves, a mult, four shifts, two adds, and two
subtracts.

Most fun is the use of the constant 0xBACF914D in the mod calculation.
They multiply that by the value to lookup, and discard the low 32-bits
of the result. Then from that they subtract the value to lookup, and
shift the result right by one. From there, things start to get strange,
until, 11 instructions later, they magically end up with an index into
the lookup table.

In short, I'm very glad that people specialize in exactly this thing.

So we have an arcane arithmetical hack at source code level which is
optimised by the compiler into a different and equally arcane hack at
machine code level.

Wonderful!

 

[Phil Carmody]

or an optimiser that does the trick for you.

Oh, I don't mean reduction modulo 37 using a multiply, I mean a
completely different { 2^i: i \in 0..32 } -> { 0 .. 31 } mapping.

For example, taking an 8-bit example, multiply by a magic constant
like 0b0001110100, which has every single possible 3-bit subsequence,
which can be extracted from a fixed location after the multiplication.

Phil

 

[Ben Bacarisse]

Oh, I don't mean reduction modulo 37 using a multiply, I mean a
completely different { 2^i: i \in 0..32 } -> { 0 .. 31 } mapping.

I think you mean i \in 0..31.

For example, taking an 8-bit example, multiply by a magic constant
like 0b0001110100, which has every single possible 3-bit subsequence,
which can be extracted from a fixed location after the
multiplication.

A solution using such a de Bruijn sequence has already been posted[1].
On my x86_64 machine it is the fastest solution so far:

mine & and shift: 84ns
mod 37 + lookup: 43ns
de Bruijn multiply plus lookup: 19ns

All are compiler with optimisation (the function ended up inlined and
%37 was done as previouslt descibed).

The de Bruijn method omits the x & -x from the bithacks site since we
don't need it here:

int bit_set_4(uint32_t x)
{
static const int MultiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return MultiplyDeBruijnBitPosition[x * 0x077CB531U >> 27];
}

[1] http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

 

[Thad Smith]

The de Bruijn method omits the x & -x from the bithacks site since we
don't need it here:

int bit_set_4(uint32_t x)
{
static const int MultiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return MultiplyDeBruijnBitPosition[x * 0x077CB531U >> 27];
}

Portable version, probably same size on common processors:

return MultiplyDeBruijnBitPosition[(x * 0x077CB531U & 0xffffffffU)

>> 27];

 

[bartc]

A solution using such a de Bruijn sequence has already been posted[1].
On my x86_64 machine it is the fastest solution so far:

mine & and shift: 84ns
mod 37 + lookup: 43ns
de Bruijn multiply plus lookup: 19ns

All are compiler with optimisation (the function ended up inlined and
%37 was done as previouslt descibed).

The de Bruijn method omits the x & -x from the bithacks site since we
don't need it here:

int bit_set_4(uint32_t x)
{
static const int MultiplyDeBruijnBitPosition[32] = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return MultiplyDeBruijnBitPosition[x * 0x077CB531U >> 27];
}

That's pretty good, about as fast (on my machine) as a function containing
just a single BSF inline instruction.

But it might be worth pointing out that this code I think only works
properly if there is one and only one bit set. For x==0, it gives the same
result as x==1, and for x's with extra bits set, it seems to go wrong.

BSF (find lowest set bit) also doesn't deal with x = 0, but gives expected
results on the rest.