Why Num&sizeMinusOne faster than num&(size-1)

I've been told that when I have a hash table of size `m` and `m=2^k`, I can use the `&` operator as `num & (size-1)` instead of `num % size`, to fit the hashCode to my table size.

I've also been told that the the command Num&sizeMinusOne is more than twice faster than `num & (size-1)`.

My question is, why?

And isn't the operation of creating a variable called SizeMinusOne takes time too?

• Whoever told you it's faster, ignore them. There are other things to be concerned about long before trying to save nanoseconds. That was bad advice. – david.pfx Apr 14 '14 at 5:24
• Unless of course it was good advice. (You never know another's use case unless they explicitly explain it.) – Thomas Eding Apr 14 '14 at 20:49

Regarding `% 2**k` vs. `& 2**k-1`: This is a micro optimization, but a feasible one. The compiler can't prove that `size` is always a power of two (as it's variable and possibly modified by code in different translation units), so it can't perform the optimization itself. Integer division has significantly worse throughput and latency than bitwise operations on virtually every architecture. To a degree, this can even be justified with complexity theory: Bitwise operations require linear time/circuit size, while the best known divison/modulo operations require super-linear time/circuit size. This effect is actually measurable on contemporary machines too (I know this because I didn't believe it and tried it).

Regarding `size-1` versus `sizeMinusOne`: The idea is to store `sizeMinusOne` (I've seen the name `mask` for this) instead of `size`, to reduce redundancy. In a very local, short-sighted machine model, `num & sizeMinusOne` is (pseudo-RISC)

``````and r3, r1, r2
``````

while `num & (size - 1)` is

``````sub r3, r2, #1
and r3, r1, r3
``````

with otherwise identical setup and surrounding code. Since bitwise and arithmetic operations are typically equally fast (single ALU cycle, optimal latency) one could indeed argue that the first takes half the resources of the second.

But that ignores the fact that the surrounding code will take much longer, a hundred cycles overall being a very optimistic estimate. In that context, a single cycle is not just peanuts, it's a measurement error, simply noise. Don't lose sleep over it. What's more, depending on the surrounding code it may not even be a single cycle: An out-of-order CPU (such as most contemporary x86 cores) might very well squeeze the subtraction somewhere into the scheduling while an ALU is idle and be done with it before it even finished calculating `num`.

There are, however, other reasons to store `mask` instead of `size`. Usually the former is used more often than the latter, so by preferring `mask` you simplify the code.

• Note that the question as it stands now is about implementing power-of-two modulo by either `and` masking or the generic `%` modulo operator. You seem to have at this time described the difference between two `and` calls. – Lars Viklund Apr 14 '14 at 7:39
• @LarsViklund It was about both, I just overlooked the other part because it accounted for about 1/4th of the text. I added something about that. – user7043 Apr 14 '14 at 14:16