3 ms·
Certainly, if you are hashing a large amount of data then a single modulo operation isn't going to cost a lot. But if you're just hashing an English word, possi
by Jabbles 14y ago
Certainly, if you are hashing a large amount of data then a single modulo operation isn't going to cost a lot. But if you're just hashing an English word, possibly even a URL, I'm not so sure.
You could shift or mask the result (as described above) to use a table size of any power of 2 to avoid the modulo.
- mseebach 14y agoDoing constant modulo on an integer is very fast - we're talking a few CPU operations.
- dchest 14y agoYes, but bitwise AND is faster.
- sukuriant 14y agoCross that bridge when you get there. If you're really finding that your hash function is the slowest piece of code in a tightly bound for-loop, and it's not all the collisions you're having (from having a bad hashing function), then look into alternatives. Before that, you're doing premature optimization.
- dchest 14y agoPlease read the whole thread before replying with the "premature optimization" thing. We are talking about hash table optimizations; this commenter -- http://news.ycombinator.com/item?id=4037320 http://news.ycombinator.com/item?id=4037320 -- is asking about the cost of modulo operation.
- deleted 14y ago[deleted]
- haberman 14y agoIt won't be a compile-time constant unless your hash table is incapable of resizing. And modulo arithmetic on arbitrary values is slow (20-94 cycles of latency on Sandy Bridge).
- mseebach 14y agoHmm, good point. Is that also true for JIT compilers?
- terangdom 14y agoIIrc changing a modulo to an and roughly doubled the performance of my hashtable.