Hash Table Benchmark - 整数查询吞吐

这一篇测试整数 key 下的查询吞吐。

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

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

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

查询性能与内存层级的关系

在深入查询速度的细节之前，需要先注意一点：哈希表的查询速度和 cache 命中率高度相关。对于整数的 key-value，哈希表的查询操作主要就是从内存里加载数据，这一部分占据了大部分时间。

现代计算机系统采用分层的内存设计。比如 Intel Rocket Lake 有寄存器、L1 cache、L2 cache、L3 cache 和 DRAM，速度依次递减。M1 Max 则有 L1 cache、L2 cache、SLC cache 和 DRAM。

当某一层 cache 的 miss 率上升时，整体查询时间就会被下一层更慢的存储硬件速度所限制。除了 cache miss，TLB miss 同样会带来时间惩罚。下面这张 Xeon E-2388G 上命中查询的 P50（中位数）延迟图，可以帮助说明这一点。要看清其中的结构，最简单的办法是只保留一个开放寻址的表，比如 ska::flat_hash_map 搭配 std::hash（点击图例中的其他项把它们隐藏掉）。对这样的表，中位数的查询经过一次 key 比较就能成功，所以 P50 基本反映了一次访存加载的延迟，能比较紧密地跟随内存层级。

从上图可以看到，在 Intel Rocket Lake 架构上，查询性能按元素数量分成四个层级：

1. 元素能完全放进 L1 cache。在 value_type 大小为 16 字节、L1 数据 cache 为 48 KB 时，大约能放下 3,072 个元素。由于 ska::flat_hash_map 默认的 load factor 通常小于 0.5，这一段在图中对应 32 到 1,024。
2. 元素能完全放进 L2 cache。在 value_type 大小为 16 字节、L2 cache 为 512 KB 时，大约能放下 32,768 个元素。在本测试中，ska::flat_hash_map 对应的范围是 1,500 到 8,192。
3. 元素能完全放进 L3 cache。在 value_type 大小为 16 字节、L3 cache 为 16 MB 时，大约能放下 1,048,576 个元素。在本测试中，ska::flat_hash_map 对应的范围是 12,000 到 400,000。
4. 不得不从 RAM 读取的情况。这通常发生在 L3 cache 放不下所有元素时，一般是元素数量超过 1,048,576 的时候。

除了 cache miss，TLB miss 对哈希表查询速度也有显著影响。Rocket Lake 有 64 个 L1 DTLB 表项（4KB 模式下；2MB 模式下为 32 个）和 1536 个 STLB 表项。因此，在 4KB 页下，元素数量超过 16,384 时就会出现相当多的 L1 TLB miss，超过 393,216 时则会出现 L2 TLB miss。使用大页（huge page）可以大幅减少 TLB miss。M1 Max 上的 macOS 默认使用 16 KB 页，因此 TLB miss 带来的惩罚比 Rocket Lake 平台默认的 4 KB 页要小得多。在 P50 曲线上，当工作集把页表撑到超出 L2 TLB 的覆盖范围时，这个 TLB miss 惩罚会在前面提到的 cache 层级台阶之上再多出一级。

M1 Max 每个线程可以使用 128KB L1 数据 cache、12MB L2 cache 和 48MB SLC cache，因此 cache 命中率更高，在哈希表测试的大多数数据规模下性能也更好。

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

使用默认 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

大致来说，哈希表的查询时间可以拆成四部分：

1. 哈希函数计算 hash value 的时间。
2. 把 hash value 映射到具体内存地址的时间。
3. 从给定内存地址加载数据的时间。
4. 把加载到的数据和目标 key 比较的时间；如果比较不相等，还要加上额外的惩罚时间。

当元素数量较少时，CPU cache 往往能放下所有元素。此时第三步相对较快，另外三部分就变得重要。第一步和第二步之间存在权衡：一步多做，另一步就能少做。如果第一步的哈希函数没有把元素均匀地分布到 hash 空间，第二步就需要额外的计算，把这些不均匀的 hash value 分散到底层的 slot 数组里。如果第一步用的是高质量的哈希函数、能均匀分布 hash value，那么第二步通常只需要一条快速的按位与指令做截断（在 slot 数量为 2 的幂时）。

这一点可以从上面的图里看出来。libc++ 和 libstdc++ 对 std::hash 的实现，对 uint64_t 都使用 identity hash，所以第一步极快。但如果第二步直接用一条按位与指令取 slot 数组下标，就会产生很多冲突，导致第四步出现多余的比较。那些第二步处理很简单的哈希表，比如 absl::flat_hash_map、absl::node_hash_map、emhash::hash_map7 和 tsl::robin_map，都需要高质量的哈希函数，光靠 std::hash 是不够的。 robin_hood::unordered_flat_map 在第二步多做了一点工作，但搭配 std::hash 仍达不到最优性能。libc++ 的 std::unordered_map 在使用 std::hash 且元素数量为 2 的幂时，性能也很差。robin_hood::hash 对大多数要求好哈希函数的哈希表来说质量不够，但对 robin_hood::unordered_flat_map 已经足够，这一点在 100,000 到 3,100,000 这段数据点上可以看到。

相反，那些在第二步多做工作的哈希表，即使第一步用最简单的 identity hash，也仍能取得不错的性能，比如 ska::flat_hash_map、ska::bytell_hash_map、 fph::DynamicFphMap、fph::MetaFphMap 以及 libstdc++ 的 std::unordered_map。这里推荐了解一下 ska::flat_hash_map 在第二步用到的巧妙技巧——Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)。这个方法用到一次 64 位乘法和一条右移指令。由于哈希函数本身（identity hash）不涉及任何算术指令，这两条基本就是 CPU 的 ALU 需要处理的全部算术指令。

另一方面，对于需要“好”哈希函数、第二步只用一条按位与指令的哈希表，据我所知，还没有哪个哈希函数能既把代价控制在这两条指令以内，又在大多数数据分布上保持足够好的哈希质量。

正因为如此，在 Intel Rocket Lake 上当所有数据都能放进 L2 cache（或 M1 Max 上的 L1 cache）时，ska::flat_hash_map 搭配 std::hash 目前是最快的组合。其他几乎所有组合，在第一步和第二步加起来都需要更多指令。在这段数据范围内，Rocket Lake 上第二快的是 tsl::robin_map 搭配 absl::hash，差距非常小。在 M1 Max 上，fph::DynamicFphMap 搭配 std::hash 也几乎一样快，每次操作只差不到 0.1 纳秒。

不过，当 L2 cache 放不下所有元素、但 L3 cache 还放得下时，ska::flat_hash_map 就不再是第一了。在 Intel Rocket Lake 上，fph::DynamicFphMap 搭配 std::hash 在 8,192 到 3,100,000 个元素的范围内是最快的（不过在 400,000 个元素处， absl::flat_hash_map 搭配 absl::hash 略快一点）。在 M1 Max 上，这个组合在元素数量处于 8,192 到 1,200,000 时也表现突出，fph::MetaFphMap 在这一范围内排第二。考虑到 ska::flat_hash_map 和 tsl::robin_map 都采用激进的扩容策略，导致 load factor 偏低、更早出现 cache miss，而 fph::DynamicFphMap 使用 perfect hash（即没有冲突），这些结果就不难理解了。

当数据放不进 L3 cache 时，ska::flat_hash_map 搭配 std::hash 又重新成为最快的组合。tsl::robin_map 搭配 absl::hash 紧随其后——相比 cache miss 的开销，一两条指令的差距几乎可以忽略。即使在元素数量极大时，这两者依然最快，部分原因是很多其他哈希表会用辅助数组来存放额外信息。例如 absl::flat_hash_map 使用了一个 metadata 数组，在处理大数据时，它的 cache miss 率可能很高、代价也很大。相比之下， ska::flat_hash_map 和 tsl::robin_map 只用一个 slot 数组存放 key-value 数据，一次从内存到 cache line 的加载就足够了。

综合上面这些现象可以看出，高性能的哈希表在查询的第四步里失败比较都很少（要么像 ska::flat_hash_map 那样限制了失败次数，要么像 fph::DynamicFphMap 这样的 perfect hash table 根本不会失败）。

在这个前提下，当数据小到能完全装进 cache 时，第三步从内存加载的代价就变得很小。这一阶段，第一步和第二步指令的数量少、足够简单，对速度至关重要。能做到这一点的哈希表与哈希函数组合（ska::flat_hash_map 搭配 std::hash）就是最快的。

当数据量略微增加、冲突变得更频繁时，能避免冲突的哈希表就能占到优势，比如 fph::DynamicFphMap。absl::flat_hash_map 在一定程度上用 SIMD 来处理冲突，在某些数据规模下也能保持优势。

当数据量继续增加，到了任何一次访存都会 cache miss 的程度时，访存次数最少的哈希表就变成最快的。这要求冲突更少，同时也凸显出：在这一阶段，任何 metadata 都会增加访存次数。此时 ska::flat_hash_map 和 tsl::robin_map 是最快的选择。

总而言之，高性能的哈希表与哈希函数组合取决于多个因素。当数据完全装进 cache 时， ska::flat_hash_map 搭配 std::hash 表现最好，因为前两步所需的指令最少。随着数据规模增大，能有效避免冲突、或用 SIMD 解决冲突的哈希表会占优，比如 fph::DynamicFphMap 和 absl::flat_hash_map。最后，当数据规模超过 cache 容量时，访存次数最少的哈希表会胜出，比如 ska::flat_hash_map 和 tsl::robin_map。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

当 value_type 的大小扩大到 64 字节时，cache 能容纳的元素更少。而且一条 cache line 只能放下一个元素，哈希表的冲突代价也就更高。不过现代 CPU 强大的预取能力，通常能让使用线性探测或二次探测的哈希表把这部分代价压得很低。

总体来看，各哈希表之间的性能关系和 <uint64_t, uint64_t> 的情况大体一致。数据量较少或较多时，ska::flat_hash_map 搭配 std::hash 最快；而在中等数据量时， fph::DynamicFphMap 搭配 std::hash 更胜一筹。

使用较大 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

前面的测试都使用默认 load factor。但不同哈希表常常使用不同的 load factor，因为内存占用需求不同，性能上也会有差异。

哈希表对提高最大 load factor 的反应各不相同。更大的 load factor 能减少内存占用、降低潜在的 cache miss 率，从而提升性能，但同时也会增加哈希表的冲突，拖慢查询速度。

因此，如果某个哈希表的性能对 load factor 和冲突概率比较敏感，更大的 load factor 反而会让它变慢，比如 ska::flat_hash_map 和 tsl::robin_map。而对那些受 load factor 影响较小的表，比如 fph::DynamicFphMap 和 absl::flat_hash_map，性能则保持稳定，甚至随着 load factor 增大而提升。

把较大的 max_load_factor 和默认值对比一下，可以印证这些观察。

元素较少时，ska::flat_hash_map 搭配 std::hash 仍是最快的组合。随着元素数量上升，ska::flat_hash_map 和 tsl::robin_map 的性能下降，而 fph::DynamicFphMap 和 fph::MetaFphMap 的性能总体上升，其他哈希表则变化不大。因此在较大的数据规模下， fph::DynamicFphMap 搭配 std::hash 查询最快，其次是 fph::MetaFphMap 搭配 std::hash，以及 absl::flat_hash_map 搭配 absl::hash。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

当 value_type 大小为 64 字节时，提高 max_load_factor 得到的结果和 <uint64_t, uint64_t> 类似。元素较少时 ska::flat_hash_map 搭配 std::hash 最快，而元素较多时 fph::DynamicFphMap 搭配 std::hash 领先。

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

使用默认 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

在哈希表里查找不存在的元素，和查找已有元素不一样。要确认目标 key 和存储的 key 相等，必须做完整比较；但要证明两个 key 不同，hash value 不同就够了。因此，存储了 hash value 或部分 hash 的哈希表可以加快这件事。特别是用部分 hash value（比如 1 字节）作为 metadata 时，它占用的 cache 空间比完整的 key 更少。

虽然 absl::flat_hash_map、r_h::unordered_flat_map 和 fph::MetaFphMap 这类哈希表用部分 hash 作为 metadata，但在小规模查询时它们并不总是最快，因为额外的指令开销可能盖过 cache 节省带来的好处。不过一旦 L1 cache 不够用，这种做法的优势就显现出来了。

在 Intel Rocket Lake 上，元素数量超过 6,000 后，fph::MetaFphMap 搭配 std::hash 最快，并且几乎一路领先；只有在最大的规模（约一千万）附近，absl::flat_hash_map 搭配 absl::Hash 才稍稍反超。在 M1 Max 上，不到 3,000 个元素时 ska::flat_hash_map 最快，fph::DynamicFphMap 紧随其后；6,000 到 150,000 个元素时 fph::DynamicFphMap 领先，而超过 200,000 个元素后 fph::MetaFphMap 胜出。M1 Max 更大的 cache 容量很可能影响了这种变化，使得基于 metadata 的方法在更大的元素数量下才占到优势。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

使用 64 字节的 value_type 时，整体情况和 <uint64_t, uint64_t> 类似。在 M1 Max 上，fph::MetaFphMap 从 45,000 个元素开始占据主导。这一变化是因为 cache 能容纳的元素数量变少了。

使用较大 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

设置更大的最大 load factor 后，整体排名和默认 load factor 时一致。ska::flat_hash_map 领先的范围有所缩小，因为它的性能对 load factor 比较敏感。在 Intel Rocket Lake 上，元素数量不超过 1024 时 ska::flat_hash_map 搭配 std::hash 最快；元素更多时则是 fph::MetaFphMap 搭配 std::hash 更快。在 M1 Max 上，ska::flat_hash_map 领先的范围同样更小了。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

和上面一样，整体的相对速度关系与使用默认 load factor 时类似。

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

使用默认 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

当查询的 key 有 50% 概率在表中时，由于分支预测失败的惩罚拉长了查询时间，吞吐会下降，各哈希表之间的查询时间差距也随之缩小。为了让图更清晰、更易读，默认只显示每个哈希表最快的那个哈希函数。

从上面的图可以看到，除了 std::unordered_map，各哈希表的性能可以说非常接近。

元素数量相对较少时，ska::flat_hash_map 搭配 std::hash 在大多数数据点上仍是最快的。

在 Intel Rocket Lake 上，元素数量在 25,000 到 2,200,000 之间时，fph::MetaFphMap 和 fph::DynamicFphMap 搭配 std::hash 最快，absl::flat_hash_map 和 ska::flat_hash_map 在某些数据点上也很接近。元素数量在 2,200,000 到 6,000,000 之间时，absl::flat_hash_map 搭配 absl::hash 是最快的组合。元素数量不少于 6,000,000 时，ska::flat_hash_map 搭配 std::hash 又回到第一。差距非常小，领先的表也会随元素数量变化。

在 M1 Max 上，元素数量大于 32,768 时，fph::MetaFphMap 和 absl::flat_hash_map 是最快的哈希表。absl::flat_hash_map 的性能随元素数量波动，而 fph::MetaFphMap 相对稳定。元素数量极大时，ska::flat_hash_map 又回到第一。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

使用较大 max_load_factor

<K,V>: <uint64_t with several split bits masked, uint64_t>

<K,V>: <uint64_t with several split bits masked, 56 bytes struct>

命中附录

使用默认 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

使用较大 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

未命中附录

使用默认 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

使用较大 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

50% 命中附录

使用默认 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

使用较大 max_load_factor

<K,V>: <uint64_t with high position bits masked, uint64_t>

<K,V>: <uint64_t with low position bits masked, uint64_t>

<K,V>: <uint64_t uniformly distributed, uint64_t>

← 返回 Hash Table Benchmark 目录