5 ms·
The modolo function is pretty much required unless you have 2^32 bytes of RAM available for each hashtable. Modolo is also ridiculously cheap, especially compar
by viggity 14y ago
The modolo function is pretty much required unless you have 2^32 bytes of RAM available for each hashtable. Modolo is also ridiculously cheap, especially compared to the hashing function.
- Jabbles 14y agoCertainly, 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.