Hash Table Benchmark - 整数遍历

这一篇测试整数 key 下遍历哈希表的性能。

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

这个测试测量的是遍历整个哈希表的性能。

遍历和查询、插入不太一样，它的速度几乎完全取决于哈希表在内存中如何存储元素，而几乎与哈希函数无关。这里测试的哈希表大致可以分成三类：

• Dense array storage. ankerl::unordered_dense_map 和 emhash::hash_map7 会把所有 key-value pair 紧密地存到一段连续数组里，hash slot 中只保存 index 或少量 metadata。遍历时只需要线性扫描 dense array，所以单元素成本很低，而且重要的是，这个成本基本不受 load_factor 影响。
• Inline open addressing. ska::flat_hash_map、ska::bytell_hash_map、tsl::robin_map、absl::flat_hash_map、fph::* 和 robin_hood::unordered_flat_map 会把元素直接存到稀疏的 slot array 里。遍历时必须走完整个 slot array，并跳过空 slot。因此表越空、slot array 越大，单元素遍历成本就越高；当 slot array 超出 cache 后，这个问题会更明显。
• Node-based storage. std::unordered_map 和 absl::node_hash_map 会为每个元素单独分配 node。遍历时要在可能分散在 heap 上的 node 之间追指针。node 还在 cache 里时问题不大，一旦落到 DRAM，性能会明显下降。

吞吐

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

图中的结果和上面的分析一致。在两个平台上，ankerl::unordered_dense_map 都明显最快，并且在整个数据规模范围内基本是一条平线：Xeon E-2388G 上约 0.22 ns 每元素，M1 Max 上约 2.0 ns。原因是它始终遍历一段紧密排列的数组，不需要关心哈希表本身有多少 slot。emhash::hash_map7 排在第二，也有类似的平坦曲线，Xeon 上约 0.6 ns，M1 上约 2.6 ns。

每一种 inline open-addressing table 的表现都会随元素数量变化：slot array 超出 cache 后，单元素成本开始上升。比如 ska::flat_hash_map 在小规模时约 1 ns，到 10^7 个元素时，Xeon 上会升到大约 9-10 ns，因为这时大部分时间都花在从内存里读取空 slot 上。node-based 的 std::unordered_map 在大规模时最慢，10^7 个元素时 Xeon 上约 35 ns 每元素，M1 上约 22 ns，因为遍历 node list 基本变成了一串 cache miss 的 pointer dereference。

有几组组合的曲线在中等规模之后就中断了。absl::flat_hash_map 和 absl::node_hash_map 假设 hash value 分布得比较好，但整数上的 std::hash 是 identity function；在 masked-bit key 上会产生大量冲突，所以构造在大规模时 timeout，这些数据点被记为 0，也不会画出来。

下面的其他整数分布和 56-byte value 类型给出的排名基本相同。dense-storage table 仍然平坦且最快；56-byte slot 的主要影响是让 open-addressing table 更早受到内存带宽限制，因为它们现在每个 slot 需要移动 64 bytes。

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

<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>

延迟

单次 iterator step 的 P99 latency 从尾部延迟角度说明了同样的问题（latency 只在 x86-64 平台上测试）。ankerl::unordered_dense_map 不随规模变化，基本维持在约 1.6 ns，因为在 dense array 上推进 iterator 不太会遇到远距离的 cache miss。inline table 和 node-based table 在底层存储超过 cache 后，tail latency 会逐渐变长：10^7 个元素时，open-addressing table 的 P99 step 会到几十 ns，node-based 的 std::unordered_map 和 absl::node_hash_map 会到几百 ns，分别约 374 ns 和 439 ns。这些尖峰对应的，通常就是下一次访问 slot 或 node 时遇到的 cache miss。

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

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

<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 目录