Hash Table Benchmark - 64 byte 字符串查询

这一篇测试 64 byte 字符串 key 下的查询性能。

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

这一篇测试三种情况下哈希表的查询性能：

1. 查询表中存在的 key（命中，successful find）。
2. 查询表中不存在的 key（未命中，unsuccessful find）。
3. 查询有 50% 概率在表中的 key。

测试里有两种 key：定长 64 byte 的字符串，以及最长 64 byte 的变长字符串。

64 字节时，每个定长 key 都远远超过了小字符串优化（SSO）的上限，所以它们全都存放在堆上，查询必须先解引用一个指针才能取到字符，再去做哈希或比较。现在一个 key 就有四条 cache line 那么大，这使得哈希函数的开销在整个查询中占了主导：把完整的 64 字节算一遍哈希，比 slot 的下标运算耗时得多。因此，针对字节吞吐做了优化的 xxHash_xxh3，在本测试中几乎都是两台机器上各个表的最佳哈希函数；而各种表布局之间的差距也缩小了，因为它们都要付出同样大的哈希和指针追逐代价。定长 64 字节和变长 64 字节两个变体的区别仍然在于：变长 key 里包含许多短的、可以走 SSO 的字符串，能省掉堆上的间接访问。吞吐图同时给出 Xeon E-2388G 和 M1 Max 的结果；延迟只在 Xeon 上测试。

吞吐

查询表中存在的 key（命中）

使用默认 max_load_factor

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

由于对 64 字节做哈希占了主导，整个梯队比短 key 测试时更挤在一起，但排名仍然有参考价值。在 Xeon 上，perfect hash 的 fph::DynamicFphMap 和 fph::MetaFphMap（xxh3）在 cache 内最快（1,024 时约 16.4 和 16.8 ns，32,768 时 54.6 和 56.5 ns），靠的是它们的单次探测保证——即便哈希开销很大，这一点依然重要。在 10^7 时它们仍处于前列（152.7 和 163.5 ns），但探测串短的 robin hood 系 tsl::robin_map 和 ska::flat_hash_map 追了上来（151.7 和 152.2 ns）。这里每个表最优的哈希都是 xxh3。基于节点的 std::unordered_map 明显落后， 246.7 ns，在本就开销很大的 key 解引用之上，还要再多一次对堆上节点的解引用。

M1 Max 上 perfect hash table 领先得更明显，fph::DynamicFphMap 在整个范围内都最快（32,768 时 15.5 ns，10^7 时 112.7 ns），这得益于 M1 的大 cache 让它稀疏的数组驻留得更久。 std::unordered_map 再次垫底，184.5 ns。

下面的变长（max length）变体明显更快，比如 tsl::robin_map 在 1,024 时一次命中约 9.9 ns，而定长 64 字节是 18.4 ns，因为可走 SSO 的短 key 既避开了堆解引用，也省掉了对完整 64 字节做哈希的代价。较大 max_load_factor 的图排名不变，只是排得更密。

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

使用较大 max_load_factor

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

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

查询表中不存在的 key（未命中）

使用默认 max_load_factor

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

未命中又一次是 fph::MetaFphMap 脱颖而出的场景：它的 metadata 让它在不解引用堆上存储的字符、也不比较任何字节的情况下就排除一个不存在的 key，所以在 Xeon 上，它在 1,024 时领先（8.2 ns），32,768 时 16.9 ns，并一直到 10^7 都最快（95.5 ns）。SwissTable 系的 absl::flat_hash_map 和 ankerl::unordered_dense_map 紧随其后，而 robin hood 系的 tsl::robin_map 和 ska::flat_hash_map 在中等规模因探测串更长而落后（32,768 时 41.6 和 43.1 ns）。在这里，避免完整的 64 字节比较非常重要，所以那些靠一个 tag 字节就能短路的 metadata 和 SwissTable 方案明显领先。M1 Max 放大了这个 metadata 优势： fph::MetaFphMap 一直到 200,000 个元素都能在 5.9-18 ns 内回答未命中，10^7 时也只有 54.2 ns。std::unordered_map 在两台机器的大规模下都最慢（10^7 时 Xeon 231 ns，M1 125 ns）。

变长（max length）变体排名一致，只是数值更小；较大 max_load_factor 的图也符合这一规律。

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

使用较大 max_load_factor

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

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

查询有 50% 概率在表中的 key

使用默认 max_load_factor

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

混合 workload 介于两者之间。在 Xeon 上，absl::flat_hash_map、 r_h::unordered_flat_map 和 fph::MetaFphMap（都用 xxh3）都在第一梯队，1,024 时约 11.7-12 ns，10^7 时 137-148 ns，std::unordered_map 落后到 235 ns。在 M1 Max 上， fph::MetaFphMap 在大多数规模下最快（32,768 时 22.8 ns，10^7 时 104.2 ns），因为 workload 里未命中的那一半正好发挥了它 metadata 的长处，而命中的那一半仍然受益于它的单次探测布局。变长变体和较大 max_load_factor 的附录图遵循同样的规律。

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

使用较大 max_load_factor

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

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

延迟

P99 延迟图（仅 Xeon）展示长尾。64 字节的 key 分配在堆上，一次最坏情况的查询可能在 slot 数组、key 的堆缓冲区和页表上都 cache miss，所以这里的长尾是三个字符串测试中最重的。

查询表中存在的 key（命中）

使用默认 max_load_factor

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

对定长 64 字节的命中，长尾急剧收敛：从 1,024 时约 67-92 ns，到 32,768 时就跳到 550-620 ns，再到 10^7 时画出来的表大约落在 830-955 ns，其中 r_h::unordered_flat_map （xxh3）排在最前，830 ns，absl::node_hash_map 是它们中最慢的，955 ns。 std::unordered_map 还要更慢，但它的长尾超出了图表 1,000 ns 的显示上限（10^7 时约 1,025 ns），所以没有画在这里。早期那段陡升，反映的是一旦缓冲区放不进 cache，对 key 字节的堆访问就必然 miss。变长（max length）变体的长尾更低（领先的表在 32,768 时大约 290-330 ns，而定长是 550 以上），因为内联的短 key 为许多未命中的查询省掉了这次访问。

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

使用较大 max_load_factor

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

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

查询表中不存在的 key（未命中）

使用默认 max_load_factor

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

在未命中路径上，fph::MetaFphMap 在 cache 内保持最低的长尾（1,024 时 24.8 ns，32,768 时 105.6 ns），因为它的 metadata 不必碰堆上存储的 key 字节就能定下未命中， ankerl::unordered_dense_map 次之。robin hood 系的表最早急剧上升，32,768 时就超过 400 ns。变长 64 字节变体把长尾飙升的拐点大幅推后，领先者在 32,768 时仍保持在 52-62 ns 左右，因为大多数不存在的 key 都短到能从内联数据里被排除。和 24 字节时一样，这说明 SSO 边界对延迟长尾的影响不亚于哈希表算法本身。

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

使用较大 max_load_factor

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

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

查询有 50% 概率在表中的 key

使用默认 max_load_factor

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

由于有一半查询命中，长尾由更费时的命中路径主导，定长 64 字节的大多数曲线在 10^7 时聚在 805-890 ns 这一带（许多表集中在 805-845 ns 附近，其中 fph::MetaFphMap 最高，约 890 ns）；std::unordered_map 又一次超出图表 1,000 ns 的显示上限（约 1,065 ns），没有画出。fph::MetaFphMap 在纯未命中时享有的 metadata 优势在这里被稀释了，因为命中的那一半仍然需要堆解引用和 64 字节比较。变长变体和较大 max_load_factor 的附录图遵循同样的规律。

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

使用较大 max_load_factor

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

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

← 返回 Hash Table Benchmark 目录