Hash Table Benchmark - 12 byte 字符串查询

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

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

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

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

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

和整数测试不同，字符串 key 的查询会把很大一部分时间花在哈希函数和 key 比较上：整个字节序列都要算一遍哈希，命中时还要把候选 slot 里的字节和查询的 key 逐字节比较。这让哈希函数的选择比在整数测试中重要得多。这里测试了四个哈希函数：std::hash、 absl::Hash、robin_hood::hash 和 xxHash_xxh3；其中 xxh3 专为字节序列设计，所以对那些查询开销主要花在哈希函数上的表，它往往最快。第二个字符串特有的因素是小字符串优化（SSO）：12 字节的 std::string 会内联存放在字符串对象内部，因此没有单独的堆分配，访问这些字符也不需要解引用指针。定长变体让每个 key 恰好 12 字节，而变长（max length）变体下 key 长度在 12 字节以内浮动，这也会触发哈希和比较代码里依赖长度的分支。下面每张图默认显示每个表最快的那个哈希函数（点击图例可以展开其余）；吞吐图同时给出 Xeon E-2388G 和 M1 Max 的结果，延迟只在 Xeon 上测试。

吞吐

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

使用默认 max_load_factor

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

命中查询时，表需要计算 hash、找到 slot，然后真正把查询的 12 个字节和存储的 key 比较，所以每个表都要付出完整的“哈希 + 比较”代价。在 Xeon E-2388G 上，只要工作集还在 cache 里，perfect hash 的 fph::DynamicFphMap 最快：搭配 xxHash_xxh3，它在 1,024 个元素时一次命中约 6.5 ns，32,768 时约 8.4 ns，领先于所有常规的表。这正是 fph 发挥优势的区间，因为它的最小 perfect hash 保证 key 在第一次探测就落到自己的 slot 上，唯一的一次访存就是它读取的那个 slot。当表的大小超过 L3 cache 后，情况反转：一旦查询变成访存受限，反而是那些探测序列短、访问局部性好的表占优。在 10^7 个元素时， tsl::robin_map 和 ska::flat_hash_map（都搭配 xxh3）以约 42 ns 领先，而 fph::DynamicFphMap 慢到 57 ns，metadata 更重的 fph::MetaFphMap 慢到 64 ns，因为 perfect hash table 把元素铺在更稀疏的数组上，规模一大就更容易 cache miss。

这里哈希函数的选择最为关键。对大多数开放寻址和 perfect hash 的表，xxHash_xxh3 是最佳哈希函数，因为它们的查询循环主要被对 12 字节做哈希所主导；而 SwissTable 风格的 emhash::hash_map7 和 ska::bytell_hash_map 反而和 absl::Hash 搭配最好。基于节点的表一旦离开 cache 就明显落后：在 10^7 时，absl::node_hash_map 达到 107 ns， std::unordered_map 达到 118 ns，每次查询在哈希之外还要追一个堆上节点的指针。

M1 Max 上的情况类似，但曲线更平。由于 cache 更大，SwissTable 家族的表在大规模下领先（在 10^7 时，emhash::hash_map7 和 ska::bytell_hash_map 约为 60-66 ns）；而且在这个平台上，好几个表最优的哈希是 absl::Hash 而不是 xxh3，这反映了它针对 Arm 做了调优。基于节点的表依然垫底（std::unordered_map 在 10^7 时约 200 ns）。

下面的变长（max length）变体表现几乎一样：所有 key 仍然都满足 SSO、上限是 12 字节，长度变化几乎不改变哈希和比较的代价，所以排名和数值都和定长情况吻合。较大 max_load_factor 的图把元素排得更密，这在大规模下对 cache 驻留略有帮助，但会拉长探测序列，整体排名不变。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

未命中比命中代价更低，因为大多数表只靠 metadata 就能排除查询，根本不用比较那 12 个字节。这正是 fph::MetaFphMap 明显领先的地方：它每个 slot 的 metadata 让它只需一次 metadata 检查就能回答“不存在”，所以在 Xeon 上，它在 1,024 个元素时一次未命中约 3.6 ns，并且一直到 1.2M 个元素都保持在 10 ns 以内（9.65 ns），远远甩开其他表。即使在 10^7 时它变成 DRAM 受限、上升到 30.7 ns，也仍能和最好的 SwissTable 表竞争（absl::flat_hash_map 为 25.1 ns，r_h::unordered_flat_map 为 29.0 ns）。robin hood 风格的 tsl::robin_map 和 ska::flat_hash_map 在 cache 区间则慢得多（32,768 到 200,000 时为 16-26 ns），因为它们的回移（backward-shift）探测必须走过一连串 slot，才能断定 key 不存在。

由于未命中省掉了完整的逐字节比较，哈希函数在这里的影响略小一些，很多表的最佳选择变成了 absl::Hash 而不是 xxh3。基于节点的 std::unordered_map 在大规模下仍然最慢（10^7 时 110 ns），因为即使是未命中也要先哈希，再遍历一个 bucket 的节点链。在 M1 Max 上排名一致，只是绝对数值更小：fph::MetaFphMap 一直到 1.2M 个元素都能在 4-6 ns 内回答未命中，10^7 时也只有 18.6 ns，曲线也最稳定。

变长（max length）变体和较大 max_load_factor 的图重复了同样的规律；唯一能看出的变化是：更密的大 load factor 让 robin hood 的探测串略微变长，使它们与基于 metadata 和 SwissTable 的表之间的差距进一步拉大。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

50% 命中的 workload 把命中和未命中混在一起，所以它介于前两种情况之间，排名也随之变化。在 Xeon 上，SwissTable 风格的 absl::flat_hash_map 和 r_h::unordered_flat_map （都搭配 xxh3）现在在中小规模领先，1,024 时约 6 ns，32,768 时约 13-14 ns， fph::MetaFphMap 紧贴其后；perfect hash table 不再像纯命中时那样在 cache 区间占据压倒性优势，因为有一半查询是未命中，而基于 metadata 的表能用很低的代价处理这些查询。在 10^7 时，robin hood 系的表又凭借访存局部性领先（tsl::robin_map 43.5 ns，ska::flat_hash_map 44.4 ns），而 std::unordered_map 落后到 119.5 ns。

M1 Max 上，r_h::unordered_flat_map 和 absl::flat_hash_map 在大多数规模下排第一，曲线照例更平；各表最优的哈希是 xxh3 和 absl::Hash 混合。和之前一样，变长变体和较大 max_load_factor 的图遵循同样的规律，没有定性变化。

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

使用较大 max_load_factor

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

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

延迟

P99 延迟图（仅 Xeon）展示的是查询时间分布的长尾：单次查询的 99 分位，它主要由探测路径上最坏的 cache miss 和 TLB miss 决定。当工作集超过 L3 cache 后，每个表的长尾都会跳到几百纳秒，因为最慢的那 1% 查询现在要走一次完整的 DRAM 往返。

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

使用默认 max_load_factor

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

命中时，长尾取决于最坏情况下探测序列要碰多少条 cache line。在 cache 内， fph::DynamicFphMap 和 fph::MetaFphMap 的长尾最低（1,024 时约 21 ns，32,768 时约 36-37 ns），因为它们的单次探测保证把最坏情况限得很紧。一旦表溢出到 DRAM，几个 flat 表的长尾收敛到 460-560 ns 这一带，其中 r_h::unordered_flat_map 和 absl::flat_hash_map 在 10^7 时最好（约 527 和 557 ns）。基于节点的表自始至终长尾最重（10^7 时 absl::node_hash_map 680 ns，std::unordered_map 795 ns），因为一次查询既可能在 bucket 数组上 cache miss，又可能在它指向的节点上再次 miss。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

未命中的长尾最能体现 fph::MetaFphMap 的 metadata 优势：它的 P99 极其平坦，从 1,024 到 200,000 个元素只有 16-35 ns，1.2M 时也只有 59.5 ns，而此时其他每个表都已经爬到几百纳秒。由于未命中靠一次 metadata 读取就能定论，最坏情况很少需要第二条 cache line，所以直到表大到连 DRAM 中常驻的页都放不下，长尾才会飙升（10^7 时 482 ns）。robin hood 系的 tsl::robin_map 和 ska::flat_hash_map 则相反，在 200,000 个元素时就已经跳到约 412 ns，因为一次最坏未命中要走过很长的探测串。std::unordered_map 的长尾再次最重（10^7 时 905 ns）。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

由于有一半查询命中，长尾由更费时的命中路径主导：flat 的 SwissTable 表 r_h::unordered_flat_map 和 absl::flat_hash_map 保持最好的 P99（1,024 时约 23 和 22 ns，10^7 时升到 527 和 534 ns）。fph::MetaFphMap 不再有它在纯未命中时那种平坦的优势，因为这个 workload 里命中的那一半仍然需要逐字节比较，还可能多读一条 cache line。基于节点的 std::unordered_map 的长尾又一次最重（10^7 时 850 ns）。变长变体和较大 max_load_factor 的附录图遵循同样的规律。

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

使用较大 max_load_factor

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