std持续发展：unordered_map 实现的最新技术

科技 06-20 来源：飞鱼在浪屿

更多互联网精彩资讯、工作效率提升关注【飞鱼在浪屿】（日更新）

几位Boost作者开始了一个项目（

https://pdimov.github.io/articles/unordered_dev_plan.html），提高Boost.Unordered（std::unordered_map，以及multimap，set和multiset的替代品）的性能，提供基于开放寻址的更快，非标准替代方案。

该项目的第一个目标已完成Boost 1.80（将于2022年8月发布）。这里描述的boost::unordered_map中引入的技术创新，使其成为市场上std::unordered_map的最快实现。

封闭式寻址与开放式寻址

hash冲突上，哈希表实现有两种办法：

封闭寻址Closed addressing（也称为单独链接，separate chaining）依赖于一个存储桶数组，每个存储桶都指向属于它的元素列表。当新元素转到已占用的存储桶时，它只是链接到该元素列表。该图描述了封闭寻址的教科书式实现，可以说是这种类型的哈希表最简单的布局，也是最快的布局之一。

开放寻址Open addressing (封闭式哈希，closed hashing）在每个存储桶中最多存储一个元素（有时称为槽）。当元素进入已占用的插槽时，使用某种探测机制来定位可用插槽，最好靠近原始插槽。

最新的高性能哈希表使用开放式寻址，并利用其固有的更好的缓存位置和广泛可用的（ SIMD ，单指令多数据）操作。但是，封闭寻址仍有一些功能优势，也是 std::unodered_map.的实现。

对std::unordered_map实现的限制

C++无序关联容器的标准化基于Matt Austern的2003年N1456论文。

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html

过去，开放式寻址方法被认为不够成熟，因此封闭式寻址被视为安全的实现。尽管C++标准没有明确要求必须使用闭式寻址，但这种假设会让std::unordered_map:

提供了存储桶 API。
指针稳定性意味着容器是基于节点的。在 C++17 中，随着extract功能的引入，这一含义得到了明确体现。
用户可以控制hash桶装载因子。
对哈希函数的要求非常宽松（开放式寻址依赖于高质量的哈希函数，这些哈希函数能够在 std::size_t 值大小的空间中广泛分布键)。

因此，所有标准库实现都对其 std::unordered_map（以及相关容器）的内部结构使用某种形式的闭式寻址。

而困难是，有两个复杂性要求：

迭代器增量必须是（摊销的）常量时间，
erase必须是平均的恒定时间，

排除了封闭寻址的教科书实现（有关详细信息，请参阅N2023，https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf）。为了解决这个问题，标准库以引入速度和内存损失的方式偏离了教科书布局：例如，这就是libstdc++-v3和libc++布局的样子：

为了提供恒定的迭代器增量，所有节点都链接在一起，这反过来又会强制对数据结构进行两次调整：

存储桶指向存储桶中第一个节点之前的节点，以便保留恒定时间擦除。
要检测存储桶的末尾，需要将元素哈希值添加为节点本身的数据成员（在某些情况下，libstdc++-v3 会选择动态哈希计算）。

Visual Studio标准库（以前来自Dinkumware）使用完全不同的方法来规避这个问题，但一般的结果是，生成的数据结构在速度、内存消耗或两者方面的表现明显不如教科书布局。

Boost.无序 1.80 数据布局

Boost.Unordered使用的新数据布局可以追溯到教科书式的方法：

与其他标准库实现不同，节点不是跨容器链接的，而是仅在每个存储桶内链接的。这使得常数时间erase可以简单实现，但常数时间迭代器增量的问题却没有得到解决：为了实现它，引入了所谓的桶组（图的顶部）。每个存储桶组由一个 32/64 位存储桶占用掩码以及将非空存储桶组链接在一起next和prev指针组成。跨存储桶的迭代采用位掩码上的位操作操作的组合，以及通过next个指针进行组遍历的组合，这不仅是恒定时间，而且在执行时间和内存开销（每个存储桶 4 位）方面也非常轻量级。

快速模数

插入或查找元素时，哈希表实现需要将元素哈希值映射到存储桶数组（或打开寻址情况下的插槽）中。通常有两种常用方法：

桶数组大小遵循素数 p 序列，映射的形式为 h → h mod p.
存储桶数组大小遵循二次幂序列 2n，映射从 h 获取 n 位。通常，它是使用的n个最低有效位，但在某些情况下，例如，当h被后处理以提高其均匀性时，通过乘以精心选择的常数m（例如由斐波那契散列定义），最好取n个最重要的位，即h→（h × m）>>（N − n），其中 N 是 std::size_t 的位宽，>>是右移操作C++常用的位宽。

通过素数方法使用模，因为即使哈希值分布不均匀，它也能产生非常好的传播。然而，在现代CPU中，模是一种涉及整数除法的昂贵操作。另一方面，编译器知道如何更有效地通过常量执行模，因此一种可能的优化是保留一个指向函数fp的指针表：h→h mod p。这种技术用表跳转加上乘以常数的模运算取代了昂贵的模计算。

在Boost.Unordered 1.80中，更进一步优化。丹尼尔·勒迈尔等展示如何将 h mod p 计算为一个操作，涉及一些移位和乘以 p 以及一个预先计算的 c 值，作为 p 的倒数。已经使用这项工作实现了h→fastmod（h，p，c）的哈希映射（省略了一些细节）。注意，尽管 fastmod 通常比模数快一个常数，但大多数性能提升实际上来自这样一个事实，即消除了选择 fp 所需的表跳转，这阻止了代码内联。

Boost 1.80 的时间和内存性能boost::unordered_map

针对 libstdc++-v3、libc++ 和 Visual Studio 标准库提供了一些针对插入、查找和擦除方案的 boost::unordered_map 基准测试结果。boost::unordered_map总体上更快，在某些情况下甚至更快。有三个因素促成了这种性能优势：

非常减少的内存占用提高了缓存利用率，
使用快速模
新布局比 libstdc++-v3 和 libc++ 少产生一个指针间接寻址来访问存储桶的元素。

至于内存消耗，设 N 是具有 B 存储桶的容器中的元素数：64 位架构上不同实现的内存开销（即分配的内存减去严格用于元素本身的内存）为：

实现	内存开销（字节）
libstdc++-v3	16 N + 8 B（哈希缓存) 8 N + 8 B（无哈希缓存）
libc++	16 N + 8 B
Visual Studio （Dinkumware）	16 N + 16 B
Boost.Unordered	8 N + 8.5 B

选择哪个哈希容器

选择闭式寻址（在C++领域，这几乎是使用std::unordered_map实现的同义词）或选择面向速度的开放式寻址容器实际上不是一个明确的决定。列出了一些有利于一种或另一种选择的因素：

std::unordered_map该代码使用其API的某些特定部分，例如节点提取，存储桶接口或设置最大负载因子的能力，这些在开放寻址容器中通常不可用。所需值的指针稳定性和/或不可移动性（尽管一些开放寻址替代方案支持这些选项，但代价是性能降低）。需要恒定时间迭代器增量。使用的哈希函数只是中等质量的（开放寻址要求哈希函数具有非常好的密钥传播属性）。等效键支持，即。unordered_multimap/unordered_multiset。我们不知道有任何开放寻址容器支持等效密钥。
开放寻址容器性能是主要关注点。现有的代码可以适应基本上更严格的API和对元素类型（如可移动性）的更苛刻的要求。哈希函数具有良好的质量（或者使用容器提供程序中的默认函数）。