2 ms·
> The advantage of using power-of-two is that we don't > need to look for prime numbers, and we don't need to > do an expensive modulo operation (we just need a
by munificent 10y ago
> The advantage of using power-of-two is that we don't
> need to look for prime numbers, and we don't need to
> do an expensive modulo operation (we just need a
> dirt-cheap bit mask).
I'd heard that point about using a mask instead of modulo to fit the hash into the table range before, but never paid much attention to it. I figured with all of the other work going on in a hash table, the difference between one of two arithmetic operations would be negligible.
Right now, I'm working on a book on programming language interpreters. That includes implementing a hash table from scratch. I used "%" because I felt it made the behavior easier for readers to understand.
After I got it all up and running, I discovered that in some microbenchmarks were spending something like 10% of the total execution time on that "%". I changed it to use a mask and "&" and it made a dramatic performance difference.
So I think I'll be explaining both approaches in the book. The former for clarity and the latter as an example of an optimization.