3 ms·

https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, inc

https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, including those two.

jeffbee 3mo ago
A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ 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.
- quadrature 3mo ago
  Is there something better than Swiss tables ?.
  - szmarczak 3mo ago
    No. Fundamentally it's not possible to be faster.
    - infamouscow 3mo ago
      This is not true. It is fast as a general purpose hash table, but claiming it's the fastest across all datasets and workloads is silly.
      - szmarczak 3mo ago
        > claiming it's the fastest across all datasets I never claimed so. Please stop stating I said something when I didn't. > as a general purpose hash table That's what I claimed. The question IS about hash tables. If you want a hash table of any content, it's impossible to get faster. Unless you check all possible keys at once - only this will get you faster.
  - reinitctxoffset 3mo ago
    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.
- RossBencina 3mo ago
  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 https://abseil.io/about/design/swisstables
  - jeffbee 3mo ago
    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.
- utopcell 3mo ago
  You probably mean absl::flat_hash_map<>.
  - jeffbee 3mo ago
    Yeah. I typed the comments on my phone without bothering with the docs. I probably got all the other classes wrong, too.
mgaunard 3mo ago
boost unordered flat map didn't exist in 2016 (nor 2019).

https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... Has some older benchmarks, including those two.

jeffbee 3mo ago

A more recent benchmark is https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ 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.

quadrature 3mo ago
Is there something better than Swiss tables ?.
- szmarczak 3mo ago
  No. Fundamentally it's not possible to be faster.
  - infamouscow 3mo ago
    This is not true. It is fast as a general purpose hash table, but claiming it's the fastest across all datasets and workloads is silly.
    - szmarczak 3mo ago
      > claiming it's the fastest across all datasets I never claimed so. Please stop stating I said something when I didn't. > as a general purpose hash table That's what I claimed. The question IS about hash tables. If you want a hash table of any content, it's impossible to get faster. Unless you check all possible keys at once - only this will get you faster.
- reinitctxoffset 3mo ago
  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.
RossBencina 3mo ago
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 https://abseil.io/about/design/swisstables
- jeffbee 3mo ago
  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.
utopcell 3mo ago
You probably mean absl::flat_hash_map<>.
- jeffbee 3mo ago
  Yeah. I typed the comments on my phone without bothering with the docs. I probably got all the other classes wrong, too.

mgaunard 3mo ago

boost unordered flat map didn't exist in 2016 (nor 2019).