Hash Table Benchmark - 24 byte 字符串查询

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

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

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

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

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

24 字节的 key 已经越过了小字符串优化（SSO）的边界：这个长度的 std::string 不再能内联存放（libstdc++ 最多内联 15 字节），所以定长 24 字节的 key 全部分配在堆上，查询必须先解引用一个指针才能取到 key 的字节，再去做哈希或比较。这在 12-byte 那篇讨论过的“哈希 + 比较”代价之上，又让每个 key 几乎必然多一次 cache miss，也让定长和变长两个变体表现得相当不同：在变长 24 字节的情况下，很多 key 短到能内联，从而省掉这次额外的间接访问。这里测试的哈希函数仍是 std::hash、absl::Hash、robin_hood::hash 和 xxHash_xxh3；由于每个 key 要处理的字节更多，针对字节优化的 xxh3 现在几乎对每个表都胜出。每张图显示每个表最优的哈希；吞吐图同时给出 Xeon E-2388G 和 M1 Max 的结果，延迟只在 Xeon 上测试。

吞吐

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

使用默认 max_load_factor

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

和 12-byte 测试相比，有两点值得注意。第一，在 Xeon 上 xxHash_xxh3 现在几乎是每个表的最佳哈希函数，因为 key 更长，哈希在整体工作中占的比重更大，xxh3 在字节吞吐上的优势就显出来了。第二，所有表都更慢，彼此也挤得更近：由于每个定长 24 字节的 key 都在堆上，一次命中既要对 24 字节做哈希，又要追一个指针去取存储的字符来做比较。在 Xeon 上，robin hood 风格的 ska::flat_hash_map 和 tsl::robin_map（xxh3）在大规模下领先，10^7 时约 115 ns，其余 flat 表与它们相差 15-20 ns 以内；std::unordered_map 是主要的例外，达到 192 ns。在 cache 内（1,024 个元素），fph::DynamicFphMap 和 ankerl::unordered_dense_map 最快，约 11.5-12 ns，在访存流量主导之前，perfect hash table 又一次得益于它的单次探测保证。

M1 Max 把各个表区分得更清楚：perfect hash 的 fph::DynamicFphMap 和 fph::MetaFphMap （xxh3）在中等规模领先（32,768 时为 15.5 和 16.9 ns），并一直保持在前列直到 10^7 （125.7 和 139.0 ns），这得益于 M1 的大 cache 让它们更稀疏的数组驻留得更久。 std::unordered_map 再次垫底（10^7 时 208 ns）。

下面的变长（max length）变体明显更快，小规模下往往只要一半左右的时间（比如 Xeon 上 tsl::robin_map 在 1,024 时约 6.8 ns，而定长是 18.6 ns），正是因为大多数变长 24 字节的 key 都短到能内联，省掉了堆上的解引用。较大 max_load_factor 的图排名不变，只是排得更密一些。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

和 12 字节时一样，未命中代价更低，而 fph::MetaFphMap 领先，因为它的 metadata 能在不解引用堆指针、也不比较任何字节的情况下排除一个不存在的 key。在 Xeon 上，它在 1,024 时回答一次定长 24 字节的未命中约 6 ns，32,768 时为 10.6 ns，领先于 SwissTable 系的表（absl::flat_hash_map 11.6 ns，absl::node_hash_map 12.0 ns），并一直到 10^7 都最快（69.8 ns）。robin hood 系的表在中等规模再次落后（32,768 时 tsl::robin_map 24.6 ns，ska::flat_hash_map 25.1 ns），原因是它们的探测串更长。在 M1 Max 上这个 metadata 优势更大：fph::MetaFphMap 一直到 200,000 个元素都能在 4.7-9.5 ns 内回答未命中， 10^7 时也只有 40.5 ns，远远甩开其他表。

变长（max length）变体排名一致，只是绝对数值更小，因为很多 key 留在内联；在 M1 Max 上，fph::MetaFphMap 一直到 1.2M 个元素都低到只有 9-11 ns。较大 max_load_factor 的图同样符合这一规律。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

混合 workload 落在两者之间：在 Xeon 上，SwissTable 系的 absl::flat_hash_map 和 r_h::unordered_flat_map（xxh3）以及 fph::MetaFphMap 都在第一梯队，1,024 时约 8.6-10.2 ns，10^7 时大约 105-117 ns，std::unordered_map 落后到 187 ns。由于有一半查询是未命中、根本不会碰堆上存储的字节，依赖 metadata 的表在这里比纯命中时表现更好。M1 Max 上仍是同一批 flat 表在前列，曲线照例更平。变长变体和较大 max_load_factor 的附录图遵循同样的规律。

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

使用较大 max_load_factor

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

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

延迟

P99 延迟图（仅 Xeon）刻画的是最慢的 1% 查询。24 字节的堆布局让这些长尾比 12 字节时更重，因为一次慢查询可能同时在 slot 数组、堆上存储的 key 字节，以及页表上都发生 cache miss。

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

使用默认 max_load_factor

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

对定长 24 字节的命中，长尾陡升并收敛：到 10^7 时每个 flat 表都落在 750-830 ns 这一带，其中 r_h::unordered_flat_map（xxh3）最好，750 ns，std::unordered_map 最差， 930 ns。从 cache 内区间跳上来的幅度很大，长尾从 1,024 时约 50 ns，到 32,768 时就已经升到几百纳秒，因为此时最坏情况的查询必然会在堆上存储的 key 上 cache miss。变长（max length）变体的长尾明显更低（比如 10^7 时大约 535-695 ns），因为内联的短 key 为这些查询省掉了那次额外的堆 miss。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

在未命中路径上，基于 metadata 的表在 cache 内长尾最低：fph::MetaFphMap 和 ankerl::unordered_dense_map 一直到 32,768 都保持在约 22-51 ns，而 robin hood 系的表在那里就已经飙过 145 ns。到 10^7 时，各表长尾再次汇合到 600-700 ns 区间。更说明问题的是变长 24 字节变体：那里长尾在很长一段范围内都保持很低（即使在 200,000 个元素时，领先者也接近 130 ns）才开始上升，因为大多数不存在的 key 都能从内联数据里被排除，不必碰堆。这说明延迟长尾不只取决于哈希表算法，也取决于 SSO 边界。

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

使用较大 max_load_factor

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

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

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

使用默认 max_load_factor

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

由于有一半查询命中，长尾由更费时的命中路径决定，定长 24 字节的曲线在 10^7 时收敛到 740-980 ns 这一带，r_h::unordered_flat_map 最好，745 ns，std::unordered_map 最差，980 ns。fph::MetaFphMap 在纯未命中时享有的 metadata 优势在这里被稀释了，因为命中的那一半仍要付出堆解引用和逐字节比较的代价。和之前一样，变长变体和较大 max_load_factor 的附录图遵循同样的规律。

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

使用较大 max_load_factor

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

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

← 返回 Hash Table Benchmark 目录