Hash Table Benchmark - 整数插入和构造

这一篇测试整数 key 下插入并构造哈希表的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试测量的是构造哈希表所花的时间。构造时使用 emplace( const value_type& value )。测试分为插入前先 reserve 和不提前 reserve 两种情况，reserve 自己花的时间不计入总时间。

最早测试时用的是 insert( const value_type &value) 来构造哈希表，但后来发现有些哈希表并不使用 std::pair<const Key, T> 作为自己的 value_type（也就是 STL container 使用的类型），因此没法对所有被测哈希表统一使用 insert。

测试中，每种哈希表都会被构造很多次，吞吐测试记录的是总插入时间。

吞吐

y 轴是平均单次操作耗时，计算方式是 time/op = sum{construct time} / (number of construct * number of elements)。

<K,V>: <uint64_t with several split bits masked, uint64_t>

预留空间后插入

分析 reserve 之后的插入性能时，首先能看到有些哈希表并不适合搭配 std::hash 使用，比如 emhash::hash_map7、tsl::robin_map、absl::node_hash_map 和 absl::flat_hash_map。这些表需要质量更好的哈希函数。当然，也有一些哈希表在插入测试中还没有暴露这个问题，但后面的查询测试会看得更清楚。

如果把这些没有使用合适哈希函数的组合先隐藏掉（可以点击图例里的标签隐藏对应数据线），最慢的是 perfect hash table fph::DynamicFphMap 和 fph::MetaFphMap，而且差距很大。这正是它们为快速查询付出的代价：构造 perfect hash 本身很慢，而且元素越多越慢。Xeon E-2388G 上，1024 个元素时 fph 表已经需要 37 到 51 ns 每次插入；作为对比，std::unordered_map 大约 20 ns，最快的 flat table 只有 4 到 6 ns。元素数量继续增加后，差距会更大：10^7 个元素时，Intel CPU 上 fph 的插入时间大约 1450 到 1900 ns，约为 std::unordered_map（约 125 ns）的 12 到 15 倍；Apple M1 Max 上也有约 11 到 12 倍，fph 接近 1550 ns，std::unordered_map 约 134 ns。

另外，在 M1 Max 上，std::unordered_map 搭配 std::hash 在部分数据点上异常慢。进一步看会发现，这些数据点的元素数量刚好是 2 的幂：1024 个元素时每次插入约 165 ns，2048 时约 311 ns，8192 时暴涨到约 2500 ns；而附近非 2 的幂规模（例如 800、1500、3000、6000）基本在 20 到 32 ns。这里推测原因出在 M1 上 clang 所用的 libc++ unordered_map 实现：它用 hash value 对 bucket 数取模来得到 slot index。当 bucket 数刚好是 2 的幂时，这个取模等价于只保留 hash 的低位，丢掉高位。而对整数来说 std::hash 又是 identity function，所以一旦 key 的信息主要集中在高位，就会在这些 2 的幂规模上产生大量冲突。

单看插入最快的哈希表，x86-64 和 arm64 的结果就有些不同。

在 Intel Rocket Lake 上，小规模时几个 flat table 性能基本相当：emhash::hash_map7 搭配 absl::Hash、ska::flat_hash_map 搭配 std::hash、以及 ankerl::unordered_dense_map 在元素数量不超过几千时每次插入都在 4 到 5 ns 左右。中等规模下，absl::flat_hash_map 搭配 absl::Hash 最稳定，从 6000 到约 800,000 个元素基本保持在 6 到 12 ns，而其他 flat table 会更早上升。最大规模时结果又发生变化，而且不是单调的。tsl::robin_map 搭配 robin_hood::hash 在 10^7 个元素时反而最快，大约 25 ns；ankerl::unordered_dense_map 和 ska::flat_hash_map 也很接近，大约 27 到 28 ns。但同一个组合在 200,000 到 1,200,000 这一段会掉下去，升到大约 30 到 42 ns 后又恢复。这种非单调更可能是 robin_hood::hash 在这段 masked-bit key 上分布质量较差导致的，而不是单纯的 cache 层级变化。另一方面，robin_hood::unordered_flat_map 没有受到这个 hash quality 问题的明显影响：不管搭配 absl::Hash 还是 robin_hood::hash 都有竞争力。这说明它虽然需要好的哈希函数，但不像 absl::flat_hash_map 等表那样强依赖 hash quality。

Apple M1 Max 上情况略有不同。元素数量不超过约 6000 时，ska::flat_hash_map 搭配 std::hash 最快，每次插入能低于 4 ns。超过 6000 后，absl::flat_hash_map 搭配 absl::Hash 领先，并且直到约 1,200,000 个元素都保持在 4.5 到 10 ns 左右。接近 10^7 个元素时，几个 flat map 的差距缩小，收敛到约 20 到 22 ns。这是因为元素很多后，working set 已经放不进 cache。这个现象在 <K,V>: <uint64_t with several split bits masked, 56 bytes struct> 中更明显，因为那种情况下 cache 压力更大。

不预留空间直接插入

不提前 reserve 时，哈希表之间的排名又会变化。

在 Intel Rocket Lake 上，absl::flat_hash_map 搭配 absl::Hash 几乎在所有规模下都是最快的一组，大约 16 到 44 ns；emhash::hash_map7 和 ankerl::unordered_dense_map 紧随其后。小规模时，tsl::robin_map 和 ska::flat_hash_map 也几乎同样快，但规模变大后会落后，因为它们更激进的增长策略会触发更多 rehash。

在 Apple Silicon 上，最小规模时 ska::flat_hash_map 搭配 std::hash 最快，1024 个元素时约 14 ns。元素数量超过几千后，absl::flat_hash_map 搭配 absl::Hash 又成为最快，并且在后面的范围里基本保持在 20 到 32 ns。emhash::hash_map7 搭配 absl::Hash 稍微落后一些。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

预留空间后插入

key 的模式和 <K,V>: <uint64_t with several split bits masked, uint64_t> 一样。区别在于 pair 的大小变成原来的 4 倍：每个元素 64 bytes，而不是原来的 16 bytes。因此 working set 会更早超出 cache。

在 Intel Rocket Lake 上，小规模时 ankerl::unordered_dense_map、ska::flat_hash_map 搭配 std::hash、以及 absl::flat_hash_map 搭配 absl::Hash 都很接近，大约 5 到 8 ns。中等规模下，absl::flat_hash_map 搭配 absl::Hash 最快，直到约 200,000 个元素都保持在 10 到 15 ns 左右。但最大规模时 absl::flat_hash_map 会落后：10^7 时约 65 ns，而 ska::flat_hash_map（约 43 ns）和 tsl::robin_map 搭配 absl::Hash（约 40 ns）明显更快。原因是 absl::flat_hash_map 把 metadata 和 slot 存在两个不同数组中，一旦 working set 放不进 cache，每次 probe 就可能付出两次内存访问；元素为 64 字节时，这个代价会更明显。

Apple Silicon 上，元素数量较小（不超过约 6000）时，ska::flat_hash_map 搭配 std::hash 最快。中大规模下，absl::flat_hash_map 搭配 absl::Hash 领先，并保持到约 1,200,000 个元素。再往后，ska::flat_hash_map 又会和 absl::flat_hash_map 接近，甚至反超。原因是这个规模下 M1 Max 也已经放不下 working set，而 absl::flat_hash_map 比较依赖 cache 才能获得好的性能。它的 metadata 和 slot 在两个数组里，而 ska::flat_hash_map 只有一个 slot array。所以即使发生 cache miss，ska::flat_hash_map 通常也只需要从 RAM 取一次数据。

不预留空间直接插入

不提前 reserve 时，结果和 <uint64_t, uint64_t> 数据比较相似。这可能是因为大部分时间都花在内存分配和释放上。

有一个区别是：absl::node_hash_map 的排名比在 <uint64_t, uint64_t> 数据中更好。这说明当 sizeof(value_type) 较大，或者 value_type 构造本身比较耗时时，absl::node_hash_map 有一定优势，因为它不需要在 slot 之间移动 value。

延迟

<K,V>: <uint64_t with several split bits masked, uint64_t>

预留空间后插入延迟

不预留空间直接插入延迟

从结果看，即使插入前没有 reserve，insert 操作的 P99 latency 也基本和提前 reserve 后处在同一水平。不过从理论上说，如果不提前 reserve，insert 的最坏时间复杂度是 O(n)，因为哈希表可能需要扩容。如果提前 reserve，则插入过程中通常可以避免 rehash。

因此可以再看 P100 latency，也就是 max latency。下面两张图分别是提前 reserve 和不提前 reserve 时的插入 P100 latency。

可以看到，提前 reserve 后，只有 fph 系列哈希表和 robin_hood::unordered_flat_map 会出现很大的最大插入延迟。fph 表在 10^7 个元素时会达到几千万 ns，原因是要重建 perfect hash；robin_hood::unordered_flat_map 也会超过一百万 ns。从实验数据看，其他哈希表在提前 reserve 后，插入的 worst-case time complexity 看起来不像 O(n)。即使元素数量达到 10^7，ska::flat_hash_map 和 ska::bytell_hash_map 的 P100 插入延迟也只有大约 760 到 830 ns，这是很好的结果。

不提前 reserve 时，insert 的 P100 latency 更能反映哈希表插入操作的最坏时间复杂度：O(n)。最大插入延迟和元素数量成比例，flat table 在 10^7 个元素时会达到 10^8 ns 量级。相对来说，absl::flat_hash_map、robin_hood::unordered_flat_map 以及 ankerl::unordered_dense_map 在扩容时的最大延迟更小。

如果希望插入时间稳定，就应该提前 reserve，这样大多数哈希表都可以避免插入过程中的 rehash。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

预留空间后插入延迟

不预留空间直接插入延迟

当 value_type 是 64 bytes 时，排名和 <uint64_t, uint64_t> 很接近。

吞吐附录

<K,V>: <uint64_t with high position bits masked, uint64_t>

预留空间后插入

不预留空间直接插入

<K,V>: <uint64_t with low position bits masked, uint64_t>

预留空间后插入

不预留空间直接插入

<K,V>: <uint64_t uniformly distributed, uint64_t>

预留空间后插入

不预留空间直接插入

延迟附录

<K,V>: <uint64_t with high position bits masked, uint64_t>

预留空间后插入延迟

不预留空间直接插入延迟

<K,V>: <uint64_t with low position bits masked, uint64_t>

预留空间后插入延迟

不预留空间直接插入延迟

<K,V>: <uint64_t uniformly distributed, uint64_t>

预留空间后插入延迟

不预留空间直接插入延迟

← 返回 Hash Table Benchmark 目录