Re:Optimizing Open Addressing
by utopcell on Sunday April 02, 2023 @02:48PM
(#35413810)
Reads like a great summary for the hash map ideas that work in practice. I would have loved to see flat_hash_map<> thrown into the benchmark mix.
[ Parent
| on HN ]
I just benchmarked absl::flat_hash_map and got results comparable to Robin Hood with a load factor between 75% and 90%, which makes sense. It's also faster for looking up missing keys, so seems like a good option. I didn't benchmark the maximum probe lengths, though, so not sure on that front.
I tied adding the maps to the [1] benchmark, but I wasn't able to, since they aren't type generic yet. You may want to benchmark against [2], and [3] which are the best performing ones in the above benchmark.
[1] https://github.com/martinus/map_benchmark/
[2] https://github.com/martinus/unordered_dense/blob/main/includ...
[3] https://github.com/ktprime/emhash
Edit: I had the wrong link for [2] and [3], somehow...