3 ms·
Integer modulus is one of the slowest CPU operations, especially on modern CPUs (since most other operations have been heavily optimized, and there are many exe
by titzer 10y ago
Integer modulus is one of the slowest CPU operations, especially on modern CPUs (since most other operations have been heavily optimized, and there are many execution units available for them). IDIV on Nehalem can literally take up to 100 cycles (http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf), and it varies _a lot_.
Power of 2 hashtables are so much faster because indexing uses a mask. The problem is that, as others have mentioned, powers of 2 suffer a lot with bad hash functions, and people tend to write pretty bad ones, so it's generally a good idea to salt or rehash hashcodes before dropping the upper bits with a mask.
In fact it looks like the results from the author's bear that out, as the flat_hashmap_powers_of_two is almost always the fastest.
- deleted 10y ago[deleted]