A C++ implementation of a fast hash map and hash set using hopscotch hashing
1–10 of 26 posts
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#2How does it compare to boost unordered flat map?
Looks like the benchmarks were last updated in 2019.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#3How does it compare to boost unordered flat map? Looks like the benchmarks were last updated in 2019.
https://tessil.github.io/2016/08/29/benchmark-hopscotch-map....
Has some older benchmarks, including those two.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#4How does it compare to boost unordered flat map? Looks like the benchmarks were last updated in 2019.
https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, including those two.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/
However, it lacks the newer Boost stuff which is very fast.
The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#5Earlier quoted context omitted.
https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, including those two.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ However, it lacks the newer Boost stuff which is very fast. The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Is there something better than Swiss tables ?.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#6Earlier quoted context omitted.
https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, including those two.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ However, it lacks the newer Boost stuff which is very fast. The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Abseil Swiss Tables carefully avoids intermediate allocations/copy constructor calls.[1] I'd be wary about inferring underlying algorithm performance from benchmarks that don't explicitly control for these optimisations. (Or maybe everyone is using them and I'm out of touch.)
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#7Earlier quoted context omitted.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ However, it lacks the newer Boost stuff which is very fast. The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Is there something better than Swiss tables ?.
No. Fundamentally it's not possible to be faster.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#8Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#9Earlier quoted context omitted.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ However, it lacks the newer Boost stuff which is very fast. The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Is there something better than Swiss tables ?.
On modern super wide znver5 or SBSA with full-clock scalar 256 or 512 ALUs / SIMD lanes deep pipelines hight BTB pressure eyc. it's just really difficult to make a priori statements about performance for a given workload.
absl::flat_hash_map (or folly::F14) are great defaults if you can eat the invalidation semantics.
But if it's really hot you measure by workload and have infrastructure to flag the right ones in.
This seems promising. I'll start benching it alongside the other likely lads.
Re: A C++ implementation of a fast hash map and hash set using hopscotch hashing
#10Earlier quoted context omitted.
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ However, it lacks the newer Boost stuff which is very fast. The Hopscotch map was interesting at the time but due to unfortunate timing was immediately outshone by absl::unordered_flat_map A.K.A. "Swiss tables", and there's been even more water under the bridge since then.
Abseil Swiss Tables carefully avoids intermediate allocations/copy constructor calls.[1] I'd be wary about inferring underlying algorithm performance from benchmarks that don't explicitly control for these optimisations. (Or maybe everyone is using them and I'm out of touch.) [1] https://abseil.io/about/design/swisstables
Algorithmically hopscotch has a better strict worst case whereas swiss tables have a degenerate O(N) lookup. But there are a lot of maps like that. robin_hood::flat_hash_map is very fast but I can create insert sequences under which it will call std::abort, which I feel is ridiculous. But if your hash map isn't exposed to hostile inputs then you might not be concerned.