mold 仓库中的 oneTBB `concurrent_hash_map`：并发哈希容器规范与源码级解析

mold 仓库中的 oneTBBconcurrent_hash_map并发哈希容器规范与源码级解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldconcurrent_hash_map是 oneTBBoneAPI Threading Building Blocks提供的一个无顺序关联容器类模板用于存放键唯一的键值对并支持线程安全的插入、查找与删除。本文以 mold 仓库内随附的 oneTBB 规范文档concurrent_hash_map_cls.rst为骨架结合仓库内真实头文件实现concurrent_hash_map.h完整讲解该容器的类模板概要、accessor 访问器机制、构造/复制语义、并发安全操作与迭代方式并给出可编译的代码示例。读完本文你将能正确选用concurrent_hash_map的各个成员函数、理解其 accessor 读锁/写锁语义并掌握它在多线程场景下的安全使用边界。一、容器定位与类模板概要规范文档将concurrent_hash_map定义为键唯一、支持并发插入、查找与删除的无顺序关联容器。它定义在头文件oneapi/tbb/concurrent_hash_map.h中属于oneapi::tbb命名空间类模板签名如下template typename Key, typename T, typename HashCompare tbb_hash_compareKey, typename Allocator tbb_allocatorstd::pairconst Key, T class concurrent_hash_map;四个模板参数的语义模板参数默认值作用Key—键类型T—映射值mapped value类型HashComparetbb_hash_compareKey用于计算哈希码并比较键相等性的函数对象Allocatortbb_allocatorstd::pairconst Key, T内存分配器HashCompare必须满足规范的 HashCompare 要求文档引用自 oneTBB 命名需求章节它同时承担哈希与相等比较两项职责Allocator必须满足 ISO C 标准 [allocator.requirements] 中的Allocator要求。此外规范还要求表达式std::allocator_typeAllocator::destroy(m, val)良构well-formed即分配器需能正确销毁元素。类内定义了一组与标准无序容器对应的类型别名using key_type Key; using mapped_type T; using value_type std::pairconst Key, T; // 注意键是 const 的 using reference value_type; using const_reference const value_type; using pointer typename std::allocator_traitsAllocator::pointer; using const_pointer typename std::allocator_traitsAllocator::const_pointer; using hash_compare_type HashCompare; using allocator_type Allocator; using size_type implementation-defined unsigned integer type; using difference_type implementation-defined signed integer type; using iterator implementation-defined ForwardIterator; using const_iterator implementation-defined constant ForwardIterator; using range_type implementation-defined ContainerRange; using const_range_type implementation-defined constant ContainerRange; class accessor; class const_accessor;其中iterator与const_iterator满足 ISO C [forward.iterators] 的ForwardIterator要求range_type与const_range_type满足 oneTBB 的 ContainerRange 命名需求。accessor/const_accessor是本容器并发语义的核心成员类将在下一节专门展开。二、并发访问的核心accessor 与 const_accessor普通std::unordered_map的operator[]在并发环境下无法安全使用因为读后写不是一个原子动作。concurrent_hash_map的解法是访问器accessor把定位元素和持锁访问绑定在一起由访问器在存续期间对元素持有读锁或写锁。规范文档在 accessors.rst 中给出两个成员类的完整定义template typename Key, typename T, typename HashCompare, typename Allocator class concurrent_hash_mapKey, T, HashCompare, Allocator::accessor { using value_type std::pairconst Key, T; accessor(); ~accessor(); bool empty() const; value_type operator*() const; value_type* operator-() const; void release(); }; template typename Key, typename T, typename HashCompare, typename Allocator class concurrent_hash_mapKey, T, HashCompare, Allocator::const_accessor { using value_type const std::pairconst Key, T; const_accessor(); ~const_accessor(); bool empty() const; value_type operator*() const; value_type* operator-() const; void release(); };两者的差别在于accessor对元素提供读写访问value_type为std::pairconst Key, Tconst_accessor提供只读访问value_type为const std::pairconst Key, T。成员函数语义构造/析构默认构造函数构造一个空empty访问器即不指向任何元素析构函数在访问器非空时自动释放对元素的持有权因此访问器是典型的 RAII 对象。empty()返回true表示访问器为空、不指向任何元素。operator*()/operator-()返回访问器所指向键值对的引用/指针当访问器为空时行为未定义undefined behavior。release()若访问器非空释放对元素的持有权此后访问器变为空。从源码看这个持有权对应头文件 concurrent_hash_map.h 中的锁模型容器采用分段桶segments of buckets 每桶一把读写锁的结构——bucket内含有mutex_type mutex与原子指针std::atomicnode_base* node_list每个哈希节点hash_map_node_base也内嵌一把mutex_type mutex默认即spin_rw_mutex的 scoped_lock 语义头文件通过#include spin_rw_mutex.h引入。访问器存续期间即相当于持有一把 scoped 读写锁因此可以安全地跨多条语句反复读写同一个元素而无需担心其他线程并发修改。三、构造、析构与复制语义规范在 construct_destroy_copy.rst 中按六类逐一规定1. 空容器构造concurrent_hash_map(); // 初始桶数未指定 explicit concurrent_hash_map(const hash_compare_type compare, const allocator_type alloc allocator_type()); explicit concurrent_hash_map(const allocator_type alloc); concurrent_hash_map(size_type n, const hash_compare_type compare, const allocator_type alloc allocator_type()); concurrent_hash_map(size_type n, const allocator_type alloc allocator_type());前三个构造空容器初始桶数由实现决定后两个构造空容器并预分配n个桶适合已知元素规模、希望避免后续扩容的场景。可选的compare用于计算哈希码和比较键相等性alloc用于内存分配。2. 从元素序列构造template typename InputIterator concurrent_hash_map(InputIterator first, InputIterator last, const hash_compare_type compare, const allocator_type alloc allocator_type()); template typename InputIterator concurrent_hash_map(InputIterator first, InputIterator last, const allocator_type alloc allocator_type()); concurrent_hash_map(std::initializer_listvalue_type init, const hash_compare_type compare hash_compare_type(), const allocator_type alloc allocator_type()); concurrent_hash_map(std::initializer_listvalue_type init, const allocator_type alloc);容器内容为半开区间[first, last)中的元素若区间内存在多个键相等的元素最终插入哪一个未指定。InputIterator需满足 [input.iterators] 要求初始化列表版本等价于concurrent_hash_map(init.begin(), init.end(), ...)。3. 拷贝构造concurrent_hash_map(const concurrent_hash_map other)及其带分配器版本。不带分配器参数时分配器通过std::allocator_traitsallocator_type::select_on_container_copy_construction(other.get_allocator())取得。若对other存在并发操作行为未定义——拷贝是串行操作。4. 移动构造concurrent_hash_map(concurrent_hash_map other)及其带分配器版本。移动后other处于有效但未指定状态分配器通过std::move(other.get_allocator())取得同样禁止与other并发操作。5. 析构~concurrent_hash_map()调用所有存储元素的析构函数并释放存储空间期间禁止对*this的并发操作。6. 赋值运算符concurrent_hash_map operator(const concurrent_hash_map other); // 拷贝赋值 concurrent_hash_map operator(concurrent_hash_map other); // 移动赋值 concurrent_hash_map operator(std::initializer_listvalue_type init);拷贝/移动赋值会替换*this的全部元素并依据std::allocator_traitsallocator_type::propagate_on_container_copy_assignment / move_assignment::value决定是否传播分配器赋值期间对*this或other的并发操作均为未定义行为。7.get_allocator()返回与容器关联的分配器副本。并发边界小结上述构造/复制/析构族接口全部属于串行操作。并发安全接口仅限后面两节查找、并发安全修改器。四、查找操作find 与 count规范文档 lookup.rst 明确本节所有方法可以彼此并发执行也可以与并发安全修改器并发执行。bool find(const_accessor result, const key_type key) const; bool find(accessor result, const key_type key); template typename K bool find(const_accessor result, const K key) const; template typename K bool find(accessor result, const K key); size_type count(const key_type key) const; template typename K size_type count(const K key) const;find的语义要点若传入的result访问器非空先释放它若容器中存在与key等价的元素则将result设置为指向该元素返回true表示找到false表示未找到。选择accessor还是const_accessor决定了后续对该元素的访问是读写还是只读——这是实现读多写少场景的最佳实践查找用const_accessor避免不必要的写锁开销。模板化重载const K key支持透明哈希比较只有当hash_compare_type::is_transparent有效并指明一个类型时该重载才参与重载决议从而允许用与key_type不同类型的键进行查找例如用std::string_view查找std::string键避免不必要的键构造。count的语义与std::unordered_map不同由于键唯一它返回1存在或0不存在而不是元素个数。典型用法oneapi::tbb::concurrent_hash_mapint, std::string chm; oneapi::tbb::concurrent_hash_mapint, std::string::const_accessor acc; if (chm.find(acc, 42)) { // 持读锁安全读取 acc-second std::cout acc-second \n; } // acc 析构时自动释放读锁五、并发安全修改器insert / emplace / erase规范文档 modifiers.rst 声明本节所有方法可以彼此并发执行也可以与查找方法并发执行。5.1 插入insertinsert家族按是否返回访问器分为两组带访问器参数的重载推荐bool insert(const_accessor result, const key_type key); bool insert(accessor result, const key_type key); bool insert(const_accessor result, const value_type value); bool insert(accessor result, const value_type value); bool insert(const_accessor result, value_type value); bool insert(accessor result, value_type value);语义若result非空先释放然后尝试插入由key构造mapped_type()或给定value组成的元素result最终指向插入的新元素或指向已存在的同键元素返回true表示确实由本线程插入false表示键已存在。这种一次调用同时完成查找与插入并持锁返回的语义正是并发容器最常用的模式避免了先 find 再 insert的竞态窗口。不带访问器的重载bool insert(const value_type value); bool insert(value_type value);仅尝试插入返回是否插入成功不返回元素访问权。批量插入template typename InputIterator void insert(InputIterator first, InputIterator last); void insert(std::initializer_listvalue_type init);后者等价于insert(init.begin(), init.end())区间内键重复时插入哪个元素未指定。5.2 就地构造emplacetemplate typename... Args bool emplace(const_accessor result, Args... args); template typename... Args bool emplace(accessor result, Args... args); template typename... Args bool emplace(Args... args);与insert的区别是元素由args就地构造EmplaceConstructible避免构造临时value_type带访问器版本同样在返回时持锁。5.3 删除erasebool erase(const key_type key); template typename K bool erase(const K key); bool erase(const_accessor item_accessor); bool erase(accessor item_accessor);按键删除存在等价键则移除返回true否则返回false。模板重载同样受is_transparent约束。按访问器删除移除item_accessor所拥有的元素要求访问器非空。返回值值得注意true表示当前线程完成了删除false表示其他线程先删除了该元素——这是并发删除时的正常竞争结果并非错误。5.4 类型要求速查操作关键要求insert(accessor, key)value_type满足 EmplaceConstructiblemapped_type满足 DefaultConstructibleinsert(accessor, const value_type)value_type满足 CopyInsertableinsert(accessor, value_type)value_type满足 MoveInsertable移动后原值有效但未指定emplacevalue_type满足 EmplaceConstructible六、大小、容量与哈希策略6.1 大小与容量规范文档 size_and_capacity.rst 规定bool empty() const; // 容器是否为空 size_type size() const; // 容器内元素个数 size_type max_size() const; // 容器可容纳的最大元素个数一个易被忽视的细节empty()与size()的返回值在存在未完成的并发插入/删除时可能与容器实际状态不一致。这是因为并发容器无法在读取计数的同时冻结所有桶的修改——它们提供的是近似一致的快照语义不应依赖其做精确统计或作为同步手段。6.2 哈希策略规范文档 hash_policy.rst 定义了重哈希接口void rehash(size_type n 0); // 若 n 0将桶数调整为不小于 n 的值 size_type bucket_count() const; // 返回当前桶数rehash(0)是 no-op不改变桶数rehash(n)用于提前扩容把桶数设置为不小于n的值避免后续插入时频繁触发自动重哈希。bucket_count()返回容器当前桶数。从源码实现看桶的扩展采用**分段segmented**策略hash_map_base中定义了embedded_block 1、first_block 8含内嵌块配合桶大小 16 使分配量对齐到 4096 的幂、pointers_per_table sizeof(segment_index_type) * 8每比特对应一个段通过my_mask初始为embedded_buckets - 1对哈希码取模定位桶并在必要时以 2 的幂方式扩展现有段——这种设计把并发扩容的锁竞争分散到段级别。七、并发不安全操作clear 与 swap规范文档 unsafe_modifiers.rst 特别强调本节所有成员函数只能串行执行若与任何其他方法包括并发安全方法并发执行行为未定义。void clear(); // 移除容器中所有元素 void swap(concurrent_hash_map other); // 交换两个容器的内容swap还有分配器约束若std::allocator_traitsallocator_type::propagate_on_container_swap::value为true则交换分配器否则当get_allocator() ! other.get_allocator()时行为未定义。八、迭代器与并行迭代8.1 迭代器串行使用规范文档 iterators.rst 规定iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; std::pairiterator, iterator equal_range(const key_type key); std::pairconst_iterator, const_iterator equal_range(const key_type key) const; // 以及受 is_transparent 约束的模板重载begin()/cbegin()返回指向首元素的迭代器end()/cend()返回尾后迭代器。equal_range(key)返回包含与key等价的元素的范围由于键唯一范围长度最多为 1若不存在则返回{end(), end()}。关键约束本节所有成员函数只能串行执行与任何其他方法含并发安全方法并发执行均属未定义行为。也就是说遍历容器时不能同时执行insert/erase/find等操作——如需并发遍历应使用下面的range()并行迭代而不是手写迭代器循环。8.2 并行迭代range规范文档 parallel_iteration.rst 定义range_type range(std::size_t grainsize 1); const_range_type range(std::size_t grainsize 1) const;range()返回表示容器全部元素的 range 对象grainsize为粒度参数默认 1。range_type与const_range_type仅边界迭代器类型不同iteratorvsconst_iterator二者都满足 oneTBB 的 ContainerRange 命名需求可直接配合oneapi::tbb::parallel_for使用把整个容器切分成多个子范围交给不同线程并行处理oneapi::tbb::parallel_for(chm.range(), { for (auto kv : r) { // 只读遍历 kv.first / kv.second线程安全 } });同样地规范强调遍历concurrent_hash_map本身不是线程安全的——在遍历 range 期间并发执行任何成员函数行为未定义。因此并行迭代的正确姿势是先并发修改再并行只读遍历或者对每个子范围内部自行加锁。九、C17 推导指南CTAD规范文档 deduction_guides.rst 说明自 C17 起concurrent_hash_map的构造支持类模板实参推导CTAD。除拷贝/移动构造含显式分配器参数版本提供隐式推导指南外还显式提供了四组指南覆盖迭代器区间 比较器/分配器与初始化列表 比较器/分配器两种形态并配套定义了iterator_key_t、iterator_mapped_t、iterator_alloc_value_t三个辅助类型别名用于从迭代器/初始化列表的元素类型中提取键、值与分配器类型。官方示例文档原文可直接编译验证#include oneapi/tbb/concurrent_hash_map.h #include vector int main() { std::vectorstd::pairconst int, float v; // Deduces chmap1 as oneapi::tbb::concurrent_hash_mapint, float oneapi::tbb::concurrent_hash_map chmap1(v.begin(), v.end()); std::allocatorstd::pairconst int, float alloc; // Deduces chmap2 as oneapi::tbb::concurrent_hash_mapint, float, // tbb_hash_compareint, // std::allocatorstd::pairconst int, float oneapi::tbb::concurrent_hash_map chmap2(v.begin(), v.end(), alloc); }参与重载决议的前提是InputIterator满足 [input.iterators] 要求、Allocator满足 [allocator.requirements] 要求、且HashCompare不满足Allocator要求用于区分第三个参数到底是比较器还是分配器。十、非成员函数比较与交换规范文档 concurrent_hash_map_cls.rst 及 non_member_binary_comparisons.rst 声明了三个非成员函数template typename Key, typename T, typename HashCompare, typename Allocator bool operator(const concurrent_hash_map... lhs, const concurrent_hash_map... rhs); template typename Key, typename T, typename HashCompare, typename Allocator bool operator!(const concurrent_hash_map... lhs, const concurrent_hash_map... rhs); template typename Key, typename T, typename HashCompare, typename Allocator void swap(concurrent_hash_map... lhs, concurrent_hash_map... rhs);两个concurrent_hash_map相等当且仅当元素个数相等且一个容器中的每个元素在另一个容器中也存在注意这是集合意义上的相等与桶布局无关。operator!等价于!(lhs rhs)。这些函数的具体定义命名空间未指定可通过参数依赖查找ADL使用。十一、源码佐证分段桶与每桶读写锁回到仓库中的真实实现 concurrent_hash_map.h可以印证规范中接口设计背后的并发策略节点基类hash_map_node_baseMutexType内嵌next指针与mutex_type mutex即链式桶 每节点一把锁桶结构bucket内含mutex_type mutex与原子指针std::atomicnode_base* node_list桶本身还挂一把锁容器基类hash_map_baseAllocator, MutexType以**段表segments table**管理桶数组my_mask负责哈希取模my_size维护近似元素计数头文件通过#include spin_rw_mutex.h引入读写锁默认MutexType即spin_rw_mutex与规范中accessor 存续期间持有读/写锁的语义一一对应。这意味着const_accessor底层持有一把读锁允许多线程同时只读访问同一元素accessor持有一把写锁独占该元素这正是查找用const_accessor、修改用accessor这一最佳实践的性能依据。规范文档concurrent_hash_map_cls/目录下全部小节与头文件声明保持一致仓库中的测试用例third-party/tbb/test/目录也可作为进一步验证各接口并发行为的第一手资料。十二、使用边界与最佳实践小结综合规范文档与源码实现归纳concurrent_hash_map的并发安全矩阵操作类别成员并发安全性查找find、count✅ 可彼此并发且可与并发安全修改器并发修改insert、emplace、erase并发安全重载✅ 可彼此并发且可与查找并发迭代begin/end/cbegin/cend、equal_range❌ 只能串行遍历range()parallel_for⚠️ 遍历期间禁止并发执行任何成员函数容量clear、swap❌ 只能串行构造/复制/析构全部构造、赋值、析构❌ 只能串行统计size()、empty()⚠️ 并发下结果为近似值实践建议读多写少优先const_accessorfind避免持有写锁最大化读并发查无则插用带 accessor 的insert/emplace一次调用原子完成检查与插入杜绝竞态窗口并发删除用按访问器erase注意返回false可能是其他线程已删除属正常竞争遍历与修改严格分离先完成所有并发修改再串行遍历或parallel_for并行只读遍历对计数不要精确依赖size()/empty()在并发写入期间只是近似值需要透明查找/删除让HashCompare提供is_transparent类型并启用模板重载可避免为临时键做昂贵构造。如需继续深入可在仓库中查阅规范原文 concurrent_hash_map_cls.rst 及其子章节accessor、构造复制、查找、修改器、迭代器、并行迭代、推导指南、非成员比较或直接阅读实现头文件 concurrent_hash_map.h 与随附测试用例。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考