4 ms·
It's fairly common to keep array sizes bounded at a power of two, because when you take a hash you can use bitwise shifting instead of a modulus to determine th
by AlisdairO 14y ago
It's fairly common to keep array sizes bounded at a power of two, because when you take a hash you can use bitwise shifting instead of a modulus to determine the hash bucket to use. Depending on the performance of your hash function it can have a noticeable impact, although you're right that it's probably not a matter of 'much' faster.
- paul 14y agoI bet that there's no measurable difference in this code. It just bugs me to see so much unnecessary complication based on blindly imitating an optimization that maybe made sense 20 years ago.
- deleted 14y ago[deleted]
- fizx 14y agoI've noticed the difference between modulo and bitshift in java code written in the last five years. If it's getting 99.9+% cache hits, being used in an innermost loop, and jdk7 hasn't gotten around to JITing special cases in modulo, this could absolutely matter.
- spullara 14y agoIt was 10% faster to switch from modulo to & on a recent real world problem for me.
- brlewis 14y agoI believe you. There are two reasons I think paul's right in the context of hash tables. 1. If you're using a non-trivial hash function, one more modulo calculation at the end to get the actual memory address is not a big difference. 2. If you're using a trivial hash function, I bet for a lot of data sets you'll get fewer collisions with a hash table whose size is a prime number, canceling out any benefit from calculating the address slightly faster.
- eridius 14y agoUsing a modulo with a non-power-of-2 is going to introduce modulo bias.