bucket count

[gf777]

Hello @greg7mdp
as always many thanks for this very useful tool.
I have a question about the internal bucket counts that relates to efficiency. It is my understanding that if the number of buckets is a prime number, even with bad hash function, one can get a very good/near perfect distribution in the buckets. This is especially useful when the inputs are unpredictable.
However, apparently it is impossible to set the number of buckets to achieve this very useful feature in unordered_map (and therefore I guess in parallel-hashmap) because we can only set the minimum number of buckets with rehash: https://cplusplus.com/reference/unordered_map/unordered_map/rehash/
Is there a reason for this? It sounds like have a defined number of buckets that allows this trick with prime numbers would allow for significant improvements in efficiency.
Thanks!

[greg7mdp]

Hi @gf777 ,

You are right that for traditional hash maps using closed addressing, the bucket count is usually a prime number, and collisions are addressed by storing multiple values in each bucket (sometimes using a linked list).

The phmap tables use open addressing, where collisions are resolved by probing for an empty slot. This is much more efficient as it ensures memory locality, and avoids memory allocations. These tables are often dimensioned to a power of two size, so the number of slots doubles on each resize (and obviously is not a prime number).

Still, to benefit from the good distribution that prime number modulo provides, especially when the hash function is poor, the phmap tables implement fibonacci hashing, see phmap_mix.

So the optimization that you consider above is implemented in phmap. Because it has a small overhead, It sometimes provides slower results in micro-benchmarks when a good hash function is used, but I have found that in real world usage, it is better to perform well consistently, than to optimize for micro-benchmarks, and have the performance drop inexplicably in some cases.

[gf777]

Very interesting reading, thank you so much for sharing Greg!
Giulio