Hash Table Benchmark - 整数删除和插入

这一篇测试整数 key 下反复删除和插入的性能。

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

这个测试先构造一个大小为 N 的哈希表，然后重复执行 M 次下面的操作：

1. 向哈希表中插入一个新元素
2. 从哈希表中随机删除一个元素

这个测试结果同样和数据分布高度相关，尤其和“被删除的数据”和“新插入的数据”之间的关系有关。这里删除元素时是等概率随机选择的。真实场景里，元素未必会等概率地被删除；比如最可能被删除的元素也许正是最近插入的元素。

吞吐

这里记录的是整个过程的耗时，包括 insert 和 erase 两部分。

y 轴是平均单次操作耗时，计算方式是 time/op = (time for insert + time for erase) / (2 * M)，也就是 insert 和 erase 的平均耗时。这个数字反映的是对哈希表做修改的效率。

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

在 Intel Rocket Lake 上，ska::flat_hash_map 搭配 std::hash 在几乎整个范围内都是最快或接近最快的一组，大约 5 到 37 ns 每操作。中等规模下，emhash::hash_map7 搭配 absl::Hash、以及 absl::flat_hash_map 搭配 absl::Hash 也比较接近。tsl::robin_map 在小规模和很大规模时都不慢，10^7 个元素时大约 39 ns，但在中间规模会变慢，在 400,000 到 800,000 附近升到 60-90 ns。这和 robin_hood::hash 在这些 key pattern 上分布较差有关。

在 Apple M1 Max 上，ska::flat_hash_map 和 std::hash 的组合在几乎所有数据规模下都有相对优势，大约 6 到 33 ns。

另外值得注意的是，M1 Max 上 absl::node_hash_map 有一段明显的性能下降，在大约 45,000 到 100,000 个元素之间出现一段很明显的凸起，最高接近 135 ns。std::unordered_map 也有类似退化，随着规模增长一路升高，在 100,000 到 300,000 个元素附近达到峰值，最高约 600 ns。这个现象的原因还不清楚，可能与系统的内存分配策略有关，因为这两种哈希表在每次插入和删除时都需要做内存分配和回收。这个现象在 <uint64_t, 56 bytes> 数据上更明显。

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

在 Intel Rocket Lake 上，排名和前面的 <K,V>: <uint64_t with several split bits masked, uint64_t> 类似：ska::flat_hash_map 搭配 std::hash 仍然有比较明显的领先优势，大约 8 到 59 ns；absl::flat_hash_map 是最接近的一组。

在 M1 Max 上，当元素数量大约在 32,768 到 1,200,000 之间时，absl::flat_hash_map 和 emhash::hash_map7 的相对表现会好一些，其中 emhash::hash_map7 搭配 absl::Hash 在几个点上会略快于 ska::flat_hash_map。

延迟

这里把插入和删除的延迟分开记录。注意，这里的插入延迟和“插入和构造”测试中的插入延迟不一样：构造测试中的延迟统计的是从大小 0 一直插入到大小 N 的整个过程，而本测试中哈希表的大小始终保持在 N 或 N + 1 附近。

插入（删除之后）

<K,V>: <uint64_t with several split bits masked, uint64_t> 插入延迟

先看 P50 latency。数据规模较小时，ska::flat_hash_map 搭配 std::hash 和 tsl::robin_map 搭配 absl::Hash 属于第一梯队，大约 7 到 9 ns。元素数量变大后，absl::flat_hash_map 和 absl::node_hash_map 搭配 absl::Hash 更有优势：大约 300,000 个元素之后，ska/tsl 系列会跳到 50 ns 以上，而 absl 系列仍然在 24 到 28 ns 左右。接近 10^7 个元素时，大多数 open-addressed 哈希表的 median latency 又会重新接近，约 92 到 99 ns。

P99 latency 上，小中规模时 emhash::hash_map7 搭配 absl::Hash 的 tail latency 最小，小规模约 31 ns，并且直到约 200,000 个元素之前都保持领先。再往后则是 absl::flat_hash_map 更好。

说到 open-addressed 哈希表的修改，就绕不开 tombstone 机制。有些哈希表执行 delete 时，会在被删除元素所在 slot 放一个特殊标记，也就是 tombstone。tombstone 和 empty marker 不一样。如果 tombstone 太多，lookup 性能会受影响。因此一些哈希表会在 tombstone 数量达到一定比例时 rehash。这会让与删除交替进行的插入操作出现很高的最大延迟。P100 latency 可以显示这一点。

除了元素数量为 2 的幂时第一次插入可能触发扩容外，有些哈希表在部分数据点上的 P100 latency 会和元素数量成比例。在 absl 系列哈希表和 robin_hood::unordered_flat_map 上都能观察到这个现象。如果应用对修改操作的最大延迟有严格要求，就不应该选择这些哈希表。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct> 插入延迟

当 value_type 变成 64 bytes 时，小数据规模下 ska::flat_hash_map 搭配 std::hash 相比 tsl::robin_map 的优势会变大。P50 上最小规模时大约是 8 ns 对 11 ns。

P99 latency 上，小规模时 tail latency 最小的是 absl::flat_hash_map 搭配 absl::Hash，大约 33 ns，领先于 ska::flat_hash_map 和 emhash::hash_map7。

删除

<K,V>: <uint64_t with several split bits masked, uint64_t> 删除延迟

P50 latency 上，ska::flat_hash_map 搭配 std::hash 几乎总是最小，只有大约 300,000 到 800,000 个元素之间例外。在这一段里，ska::flat_hash_map 会跳高到大约 100 到 160 ns，因为它更激进的扩容和较低的 load_factor 让底层存储落到了更慢的内存层级；而 absl::flat_hash_map 和 robin_hood::unordered_flat_map 仍然较低，大约 45 到 120 ns，相对表现更好。超过 1,200,000 个元素后，各表又会重新接近。

P99 latency 上，元素数量较小时 emhash::hash_map7 搭配 absl::Hash 最快，约 19 ns，并且领先到大约 3,000 个元素。中等规模下，absl::flat_hash_map 搭配 absl::Hash 的 tail latency 更小，大约从 8,000 到 200,000 个元素都是如此。元素数量再变大后，很多哈希表的表现会接近。

<K,V>: <uint64_t with several split bits masked, 56 bytes struct> 删除延迟

当 value_type 是 64 bytes 时，整体情况和 <uint64_t, uint64_t> 基本一致。

吞吐附录

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

延迟附录

插入（删除之后）

<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> 插入延迟

删除

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