Hash Table Benchmark - 字符串遍历

这一篇测试字符串 key 下遍历哈希表的性能。

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

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

遍历这种操作几乎不受 key 类型影响。遍历时既不会重新计算 key 的 hash，也不会比较两个字符串；它只是推进 iterator，并读出每个已经存好的 entry。因此，和查询或插入不同，字符串长度和哈希函数选择在这里几乎没有影响。真正起决定作用的是哈希表在内存中如何组织元素，这一点和 整数 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 超出 cache 越多，单元素成本就越高。
• Node-based storage. std::unordered_map 和 absl::node_hash_map 会为每个元素单独分配 node，遍历时需要在这些 node 之间追指针。

字符串这里还有一点要注意：存储的 entry 是 std::pair<std::string, uint64_t>。不管字符串本身是 12、24 还是 64 个字符，这个 entry 的固定部分大小都一样，都是一个 32-byte 的 std::string control block 加上 value。较长字符串实际的字符内容会放在别处的堆内存上，但遍历时并不会碰这些字符内容，因为这里只推进 iterator，不读取字符串本身。这也是为什么六种字符串数据的遍历结果几乎一样。

吞吐

<K,V>: <string with a fixed length of 64, uint64_t>

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

各种 inline open-addressing table 的单元素成本会随元素数量上升，因为 slot array 逐渐超过 cache。比如 ska::flat_hash_map 在 1024 个元素时不到 1 ns，到 10^7 个元素时，Xeon 上升到大约 12.4 ns，这时大部分时间都花在从内存里读取空 slot 上。node-based 的 std::unordered_map 在大规模时最慢，10^7 个元素时 Xeon 上约 48 ns 每元素，M1 上约 25 ns，因为遍历 node list 基本变成了一串 cache miss 的 pointer dereference。

perfect hash table 在 open-addressing table 中处于中间位置，这里并不领先：10^7 个元素时，Xeon 上 fph::MetaFphMap 大约 7.4 ns，fph::DynamicFphMap 大约 10.8 ns。perfect hash 能换来很快的 lookup，但遍历还是要走稀疏的 slot array，所以对 fph 没有优势；而 fph::DynamicFphMap 的 slot array 相对更稀疏，因此反而成了扫描最慢的几个 flat table 之一。

下面五种字符串数据给出的结果几乎一样，连小数点后的数值都几乎一致。遍历不关心 key 的具体内容，所以 fixed/max length 以及 12/24/64-byte 的区别在这里看不出明显影响。

<K,V>: <string with a max length of 64, uint64_t>

<K,V>: <string with a fixed length of 24, uint64_t>

<K,V>: <string with a max length of 24, uint64_t>

<K,V>: <string with a fixed length of 12, uint64_t>

<K,V>: <string with a max length of 12, uint64_t>

延迟

单次 iterator step 的 P99 latency 从尾部延迟角度说明了同样的问题（latency 只在 Xeon E-2388G 上测试）。ankerl::unordered_dense_map 不随规模变化，基本维持在约 0.94 ns，因为在 dense array 上推进 iterator 不太会遇到远距离的 cache miss。inline table 和 node-based table 在底层存储超过 cache 后，tail latency 会逐渐变长：10^7 个元素时，ska::bytell_hash_map 的 P99 step 大约 84 ns，ska::flat_hash_map 大约 110 ns，tsl::robin_map 大约 103 ns；node-based 的 std::unordered_map 和 absl::node_hash_map 会到几百 ns，分别约 406 ns 和 444 ns。这些尖峰对应的，通常就是下一次访问 slot 或 node 时遇到的 cache miss。第一个点（N=1024）里 ankerl 的 3.13 ns 是一个小异常点，应该是 cold-start artifact，之后就稳定在约 0.94 ns。其他五种字符串数据也有同样模式。

<K,V>: <string with a fixed length of 64, uint64_t>

<K,V>: <string with a max length of 64, uint64_t>

<K,V>: <string with a fixed length of 24, uint64_t>

<K,V>: <string with a max length of 24, uint64_t>

<K,V>: <string with a fixed length of 12, uint64_t>

<K,V>: <string with a max length of 12, uint64_t>

← 返回 Hash Table Benchmark 目录