Hash Table Benchmark - 字符串插入和构造

这一篇测试字符串 key 下的插入和构造性能。

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

这一篇测试构造哈希表所花的时间。构造通过 insert( const value_type& value ) 操作完成。测试分两种情况：插入前调用 reserve，以及不调用 reserve。reserve 本身花的时间不计入总时间。

测试中，哈希表会被多次构造，吞吐测试记录的是总插入时间。

字符串的长度与 std::string::length() 一致，也就是说还需要额外一个字节来保存结尾的空字符。

插入字符串 key 的代价比插入整数更高，因为每次插入都要多做三件整数不用做的事：对整个 key 的字节序列做哈希、冲突时比较整个字符串，以及为超过小字符串优化（SSO）阈值的 key 分配堆内存来存放字符。在这里使用的 libstdc++/libc++ 实现中，长度不超过 15 的 std::string 会把字节内联存放在控制块里（不分配内存），所以 12 字节的 key 是纯 SSO、完全不碰分配器；而 24 字节和 64 字节的 key 会落到堆上，每次插入还要付一次 malloc。下面不同字符串长度变体之间的差异，主要就来自 SSO 与堆分配的区别。

这里也先说明一下 perfect hash table 的预期表现。fph::DynamicFphMap 和 fph::MetaFphMap 查询极快，因为它们构建了一个（近似）perfect hash，查询时无需探测，但正是这个构造过程让它们的插入很慢：随着表的增长，它们会周期性地重建 perfect hash。所以在这个插入/构造测试里，fph 系的表始终是最慢的，这个前提对理解插入结果很重要。

吞吐

预留空间后插入

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

提前调用 reserve 后，容量在插入前就固定下来，因此这里看到的基本就是单次插入本身的代价（哈希、探测、分配、存储），不涉及 rehash。在 Xeon 上，定长 64 字节 key 的结果里，xxHash_xxh3 ——它本就是为处理原始字节流而设计的——几乎在每个表上都是最佳哈希函数，几个领先的表也挨得很近： absl::flat_hash_map、ankerl::unordered_dense_map 和 robin_hood::unordered_flat_map 在 1024 个元素时都在 24-26 ns 左右，到 10^7 时收敛到约 118-119 ns，此时单次插入的代价主要来自 64 字节字符串的 malloc 和 cache miss，而不是哈希表算法。std::unordered_map 比 flat 表慢约 2 倍（小规模约 48 ns，10^7 时 250 ns），因为它在字符串分配之外，还要为每个元素分配一个节点。

fph 系的表在这里慢得多：在 Xeon 上，fph::MetaFphMap 和 fph::DynamicFphMap 在 10^7 时分别达到约 2390 ns 和 2471 ns——大约比 std::unordered_map 慢 10 倍、比最快的几个 flat 表慢 20 倍——因为 perfect hash 的构建代价随表增长。（注意它们在 N=1024 处的数据点，约 198 和 178 ns，来自对一个很小的表反复构建 perfect hash 的开销；它们在 32768 处反而相对更好，之后构建代价又重新占主导。）在 M1 Max 上排名相同，但差距更小：fph 系的表在 10^7 时落在约 950 ns，而最快的几个 flat 表约为 100-120 ns。

下面的 24 字节和 12 字节变体排名相同，只是随着字符串变短而整体更快：在 10^7 时，最快的几个 flat 表从约 118 ns（64 字节）降到约 92-112 ns（24 字节），再到约 50-63 ns（12 字节），最后这一档是因为 12 字节的 key 是纯 SSO、完全跳过了分配器。“max length N”变体和对应的“fixed length N”差不多，或者略快一点，因为随机生成的 key 平均长度短于上限，要哈希、比较和拷贝的内容更少；不过长度不一也会让每个 key 的代价不那么均匀。

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

不预留空间直接插入

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

不调用 reserve 时，每个表在填充过程中还要处理扩容和 rehash，这大致让单次插入的时间整体翻倍。在 Xeon 上，定长 64 字节 key 的结果里，absl::flat_hash_map 搭配 xxHash_xxh3 在大规模下最快（10^7 时约 191 ns），因为它扩容开销小，rehash 时重排的是 metadata 数组，而不是再次搬动整条记录；ankerl::unordered_dense_map 紧随其后（约 178 ns），因为它只需要扩展一个紧凑的数组。重探测的表受 rehash 影响更大：ska::flat_hash_map 在 10^7 时爬到约 465 ns，是 absl 的两倍多，因为每次扩容都要把每个元素重新沿探测序列插入一遍。

fph 系的表在这里慢得多。不调用 reserve 时，每次扩容都会触发一次全新的 perfect hash 构建，所以在 Xeon 上 fph::MetaFphMap/fph::DynamicFphMap 在 10^7 时达到约 3800 和 4180 ns ——约为最快的几个 flat 表的 10 倍，也明显比它们调用 reserve 时的数值更差，因为后者至少只在最终大小上构建一次 perfect hash。这正说明 fph 是拿构造速度换查询速度。

下面更小的 key 和“max length”变体保持同样的排名；12 字节的 SSO key 再次最快（absl 在 10^7 时约 64 ns），因为它们从不调用分配器，只剩下表本身的扩容和探测代价。

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

延迟

单次插入的 P99 延迟只在 Xeon E-2388G 上测试。从长尾来看，结论也是一样的：常规的 flat 表能把长尾限制住，而 perfect hash table 每次重建时都会出现尖峰。

预留空间后插入

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

提前 reserve 的情况下，定长 64 字节 key 下几个 flat 表的 P99 都收得很紧： absl::node_hash_map、ankerl::unordered_dense_map 和 absl::flat_hash_map 在 10^7 时都在 490-530 ns 左右，std::unordered_map 约 880 ns。64 字节字符串的内存分配为所有这些表都设了一个下限。fph 系的表又一次格外突出：在 10^7 时 fph::DynamicFphMap 爬到约 12660 ns，fph::MetaFphMap 约 12420 ns，差了一个数量级以上，因为即便预留了容量，perfect hash 的构造也会偶尔出现非常耗时的步骤，主导了 99 分位。对 12 字节的 SSO key，下限降低了（flat 表在 10^7 时约 460-490 ns），因为没有分配，但 fph 的长尾仍然很高（fph::DynamicFphMap 约 11780 ns）。

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

不预留空间直接插入

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

不提前 reserve 时，常规表的 P99 和 reserve 的情况相差不大——相对于插入次数，一次大到能落进 99 分位的 rehash 是很罕见的——所以对 12 字节的 key，absl::flat_hash_map 在 10^7 时仍约为 442 ns，std::unordered_map 约 850 ns。相比之下，fph 系的表急剧恶化：不 reserve 时它们每次扩容都重建 perfect hash，所以 fph::DynamicFphMap 和 fph::MetaFphMap 在 10^7 时大约达到 20400 和 20360 ns，几乎是它们 reserve 时长尾的两倍。如果在意插入延迟的稳定性，就应该提前 reserve，并在构造阶段避开 perfect hash table。其余字符串变体遵循同样的规律。

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