Hash Table Benchmark - 内存占用和 load factor

这篇讨论哈希表的内存占用和 load_factor。

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

在前面的测试中，我们记录了堆内存占用和 load_factor。堆内存占用是通过自定义 Allocator 统计的，也就是在 allocate() 调用时记录分配的字节数。不过这个数字是否准确，取决于哈希表容器是否正确使用了 Allocator；也就是说，所有内存分配都必须经过这个 allocator。有些哈希表，比如 emhash::HashMap7，并非所有堆内存分配都会经过 Allocator，所以这里拿不到准确的内存数据。

C++ 里一个比较麻烦的设计是，使用不同 Allocator template 参数的类属于不同类型（std::pmr container 试图解决的就是这个问题）。例如，使用 std::allocator 的 std::basic_string 和使用自定义 allocator 的 std::basic_string 是两种类型，而 std::hash 之类的哈希函数通常只兼容使用 std::allocator 的 std::string。因此，这些哈希函数不能直接用于使用其他 allocator 的字符串；我们统计堆内存占用的方法也就统计不到字符串自己的堆内存。因此这里仅统计 key 和 value 都是整数类型的情况。

还需要说明一点：如果关心的不是总堆内存占用，而是与查询速度相关的 warm memory size，那么这个测试里的数据不能准确反映哈希表查询时实际需要用到多少 cache。有些哈希表会为了非查询操作（比如插入）保留额外空间，而这部分内存在查询时并不会访问。

这个测试使用的元素数量集合和其他测试项目不同。为了考察哈希表在不同 load_factor 下的表现，元素数量选择为 2 的幂的 0.4 倍或 0.6 倍，例如 0.4 x 2^10, 0.6 x 2^10, 0.4 x 2^11, 0.6 x 2^11, ...。

与查询相关的 cache 占用分析

哈希表占用多少堆内存、运行在什么 load_factor，会直接影响查询速度。原因是这两者共同决定了一次查询需要经过多少内存，也决定了 working set 会在多大规模时超出每一级 cache。较低的 load_factor 会浪费更多 slot，但 probe chain 通常更短；单元素占用越小，同样大小的 cache 里能放下的元素就越多。查询吞吐 测试中看到的几个 cache 分界点，本质上就是哈希表内存占用超过 L1、L2、L3 容量的位置。所以下面两组图正好能解释那些性能拐点的成因。

这些图主要描述的是数据结构本身，而不是处理器，所以堆内存数字大体上不依赖 CPU。不过 STL 实现和 allocator 不同，具体数字仍然可能有差异。下面的内存图因此把 Intel 和 M1 Max 的实测值分开展示；这些数字主要由数据结构决定，但也会受具体实现影响。

堆内存占用

使用默认 max_load_factor 时的内存占用

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

从内存占用上看，几类哈希表分得比较清楚。SwissTable 风格的 absl::flat_hash_map 和 ska::bytell_hash_map 每个 slot 只多花一个 metadata byte，是最紧凑的一档，在 10^7 个整数 pair 时大约占 272 MB。node-based 的 std::unordered_map 和 absl::node_hash_map 次之（大约 308 MB 和 297 MB），主要开销来自每个元素单独分配 node 以及指针。perfect hash table fph::DynamicFphMap 和 fph::MetaFphMap 大约是最紧凑表的两倍（约 556-572 MB），这是为了加速查询而额外使用 index 和 metadata 的代价。占用最大的是 ska::flat_hash_map 和 tsl::robin_map，大约 768 MB，因为它们使用较低的 max_load_factor，并且每个 slot 里存的都是完整的、经过对齐填充的 value type。emhash::hash_map7 显示为 0，是因为它并没有把所有分配都交给自定义计数 allocator，所以这里无法测出它的内存。

使用较大 max_load_factor 时的内存占用

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

load factor

使用默认 max_load_factor 时的 load_factor

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

load_factor 图解释了上面一部分内存差异。大多数 open-addressing 哈希表按翻倍方式扩容，所以 load_factor 会呈锯齿状变化：刚扩容后大约在 0.4 左右，下一次扩容前会到 0.75-0.9。这个测试采样的是 2 的幂的 0.4 倍和 0.6 倍，所以图上的值主要集中在 0.5-0.76。使用 robin_hood::hash 的 ska::flat_hash_map 和 tsl::robin_map 会落在最低的一档，大规模时约为 0.29-0.30，也就是用更多内存换更短的 probe chain；这也是它们查询快的原因之一。另一端是 std::unordered_map，它的 load_factor 接近 1.0，因为每个元素本来就单独分配 node，不需要像 flat table 那样留出空 slot；它的内存开销主要花在 node 和指针上，而不是空 slot 上。提高 max_load_factor 会让 flat table 填得更满。比如 10^7 个元素时，ska::flat_hash_map 的 load_factor 会从大约 0.30 提高到大约 0.60，空 slot 差不多少了一半；代价则是 probe sequence 变长、查询变慢，这个 tradeoff 会在查询测试中体现出来。

使用较大 max_load_factor 时的 load_factor

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

← 返回 Hash Table Benchmark 目录