从 range() 到 Split-Ordered Listmold 所携 TBB concurrent_unordered_set 的并行迭代机制详解【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldoneapi::tbb::concurrent_unordered_set是 TBBThread Building Blocks以第三方组件形式随 mold 仓库携带于 third-party/tbb 目录中支持并发插入、查找与遍历的无序集合容器。它的并行迭代能力通过range()成员函数暴露返回值是一个满足 ContainerRange 命名要求的可分裂区间对象可直接喂给parallel_for/parallel_reduce等 TBB 并行算法让多线程按“分治”方式遍历整个容器。本文以仓库中的规范文档与头文件实现为证据完整讲解range_type/const_range_type的类型契约、range()的语义并深入到 split-ordered list 上“二分点”查找算法的源码级原理最后给出可运行的并行迭代示例与测试验证路径。1. 并行迭代容器规范中的定位规范文档 parallel_iteration.rst 给出的核心事实非常凝练成员类型concurrent_unordered_set::range_type与concurrent_unordered_set::const_range_type满足 ContainerRange 要求两种类型唯一的区别在于边界迭代器的类型const_range_type的边界是concurrent_unordered_set::const_iterator而range_type的边界是concurrent_unordered_set::iteratorrange()成员函数返回一个“代表容器中所有元素”的 range 对象。结合容器总览页 concurrent_unordered_set_cls.rst 的描述concurrent_unordered_set“支持并发插入、查找与遍历但不支持并发擦除”supports concurrent insertion, lookup, and traversal, but does not support concurrent erasure——因此并行迭代期间的并发安全性边界是可以与insert/find等并发安全操作同时进行不可以与clear()/unsafe_erase()等“并发不安全修改器”同时进行。range()在类总览中的声明见 concurrent_unordered_set_cls.rst 的 “Parallel iteration” 小节// Parallel iteration range_type range(); const_range_type range() const;两个重载与规范一致Returns: a range object representing all elements in the container返回代表容器全部元素的 range 对象。2. ContainerRange 与 Rangerange 类型必须满足的契约2.1 ContainerRange 要求按 container_range.rst 的定义ContainerRange是“表示并发容器或其一部分的 range”用于parallel_for等并行算法遍历容器。类型CR满足ContainerRange要求需同时满足两点满足 Range 要求提供如下成员类型与成员函数成员含义CR::value_typerange 中元素的类型CR::reference指向 range 中元素的引用类型CR::const_reference指向 range 中元素的 const 引用类型CR::iterator用于遍历 range 的迭代器类型CR::size_type用于获取 grain size 的无符号整数类型CR::difference_type两个迭代器之差的类型iterator CR::begin()返回指向 range 起始位置的迭代器iterator CR::end()返回指向最后一个元素之后位置的迭代器size_type CR::grainsize() const返回该 range 的 grain size2.2 Range 要求可递归二分的核心Range 要求 规定 Range 必须可以被递归地切分成两部分切分通过调用 Range 的*分裂构造器splitting constructor*完成R::R( const R ); // 拷贝构造器 bool R::empty() const; // range 是否为空 bool R::is_divisible() const; // 是否还能切分为两个子 range R::R( R r, split ); // 基本分裂构造器把 r 切成两个子 range R::R( R r, proportional_split proportion ); // 可选按比例分裂关键约定若值集合有“方向”语义分裂构造器应当让新构造对象表示第二部分、并把入参r更新为第一部分从而保证parallel_for等算法在串行运行时按递增顺序处理元素与普通顺序循环一致。理想情况下range 应一直可分裂到“串行执行比继续分裂更高效”为止——这正是grainsize()的意义。3. 源码走读const_range_type 与 range_type 的定义上述规范类型在仓库头文件 _concurrent_unordered_base.h 中以嵌套类形式实现concurrent_unordered_set与concurrent_unordered_multiset共用该基类见 concurrent_unordered_set.hclass const_range_type { private: const concurrent_unordered_base my_instance; node_ptr my_begin_node; // 可能为 nullptr node_ptr my_end_node; // nullptr 表示“列表末尾” mutable node_ptr my_midpoint_node; public: using size_type typename concurrent_unordered_base::size_type; using value_type typename concurrent_unordered_base::value_type; using reference typename concurrent_unordered_base::reference; using difference_type typename concurrent_unordered_base::difference_type; using iterator typename concurrent_unordered_base::const_iterator; // const 边界 bool empty() const { return my_begin_node my_end_node; } bool is_divisible() const { return my_midpoint_node ! my_end_node; } size_type grainsize() const { return 1; } const_range_type( const_range_type range, split ) : my_instance(range.my_instance), my_begin_node(range.my_midpoint_node), my_end_node(range.my_end_node) { range.my_end_node my_begin_node; // 原 range 收缩为 [begin, mid) __TBB_ASSERT(!empty(), Splitting despite the range is not divisible); __TBB_ASSERT(!range.empty(), Splitting despite the range is not divisible); set_midpoint(); // 新 range 计算自己的中点 range.set_midpoint(); // 原 range 重新计算中点 } iterator begin() const { return iterator(my_instance.first_value_node(my_begin_node)); } iterator end() const { return iterator(my_instance.first_value_node(my_end_node)); } private: void set_midpoint() const; /* 见第 4 节 */ }; // class const_range_type class range_type : public const_range_type { public: using iterator typename concurrent_unordered_base::iterator; // 非 const 边界 using const_range_type::const_range_type; // 复用父类构造器 iterator begin() const { return iterator(const_range_type::begin().get_node_ptr()); } iterator end() const { return iterator(const_range_type::end().get_node_ptr()); } }; // class range_type // Parallel iteration range_type range() { return range_type(*this); } const_range_type range() const { return const_range_type(*this); }这段实现把规范逐条落实值得注意的细节有两种 range 类型的差异确实只有迭代器range_type通过公有继承const_range_type复用其全部构造逻辑与中点算法仅把iterator别名从const_iterator换回iterator并重写begin()/end()剥掉 const 属性——与规范“两种类型仅边界迭代器类型不同”的描述完全吻合。grainsize()恒返回 1每个元素即一份不可再分的工作粒度。这与同仓库 conformance_concurrent_hash_map.cpp 中CHECK(v.range().grainsize() 1)的断言一致。分裂构造器遵循了 Range 要求的“第二部分给新对象、第一部分留给自己”约定new.my_begin_node 旧中点同时旧.my_end_node 中点原 range 因此收缩为前半段[begin, mid)。两个__TBB_ASSERT在调试期拦截“对不可分裂的 range 调用分裂”的误用。empty()用节点指针相等判断my_begin_node my_end_nodeis_divisible()则是“已算出的中点是否不等于终点”中点在构造时即由set_midpoint()一次性算好并缓存因此is_divisible()本身是 O(1) 的。4. 中点查找算法 set_midpoint()哈希容器如何“对半切”对有序容器二分点显而易见但concurrent_unordered_set内部是一条全局唯一的 split-ordered list分裂有序链表元素按“分裂顺序键order key”单调排列中点怎么找答案在 _concurrent_unordered_base.h 第 741–763 行 的set_midpoint()void set_midpoint() const { if (empty()) { my_midpoint_node my_end_node; } else { sokey_type invalid_key ~sokey_type(0); sokey_type begin_key my_begin_node ! nullptr ? my_begin_node-order_key() : invalid_key; sokey_type end_key my_end_node ! nullptr ? my_end_node-order_key() : invalid_key; size_type mid_bucket reverse_bits(begin_key (end_key - begin_key) / 2) % my_instance.my_bucket_count.load(std::memory_order_relaxed); while( my_instance.my_segments[mid_bucket].load(std::memory_order_relaxed) nullptr) { mid_bucket my_instance.get_parent(mid_bucket); } if (reverse_bits(mid_bucket) begin_key) { // 在 begin 与 end 之间找到了一个 dummy 节点 my_midpoint_node my_instance.first_value_node( my_instance.my_segments[mid_bucket].load(std::memory_order_relaxed)); } else { // 没有找到中点即终点range 不可再分 my_midpoint_node my_end_node; } } }要读懂这段算法需要先理解底层的三个结构件均可在同一头文件中找到order key 与 reverse_bits元素节点value node的 order key 是reverse_bits(hash) | 0x1最低位为 1桶的哑节点dummy node的 order key 是reverse_bits(hash) ~1最低位为 0见 split_order_key_regular / split_order_key_dummy 与list_node::is_dummy()第 142–145 行 通过最低位区分两类节点。位反转使得哈希值相近的元素在链表中彼此邻近从而把“按哈希定位”转化为“按顺序扫描”。segment 表桶表my_segments是一张从桶号映射到该桶 dummy 节点指针的分段表容器初始桶数为 8、初始max_load_factor为 4第 787–788 行负载超过阈值时桶数翻倍adjust_table_size。每个桶对应链表中一个 dummy 节点dummy 节点天然是“链表的切分点”——这正是哈希表能够做等值分裂的原因。父桶回退 get_parent(bucket)取桶号清除其最高有效位第 1455–1460 行沿“桶号树”向上爬。从源码结构看该回退保证while循环必然终止桶 0 的入口节点my_head在容器构造时即已存在构造函数初始化列表中my_head(sokey_type(0))第 244–251 行。于是set_midpoint()的逻辑可以概括为四步取键空间的中点(begin_key (end_key - begin_key) / 2)是[begin, end)键区间的中值空 range 或my_end_node nullptr时用全 1 的invalid_key表示“链尾”反变换回桶号reverse_bits(mid_key) % bucket_count得到中值哈希对应的桶向上找已占用的桶若该桶尚无 dummy 节点沿get_parent回溯到最近的祖先桶——该桶的 dummy 节点是键区间内可用的最“靠后”的切分锚点判断锚点是否落在区间内若reverse_bits(mid_bucket) begin_key说明找到了 begin 与 end 之间的 dummy 节点中点取该 dummy 节点之后的第一个 value 节点first_value_node会跳过所有 dummy 节点第 1149–1154 行否则把中点设为终点is_divisible()返回 falserange 不再可分。从源码结构看这一设计把“等分工作”转化为“在桶键空间中找中点”单次set_midpoint()的开销近似 O(log 桶数) 且只读原子指针因此分裂过程不会与并发插入互相阻塞——这与容器整体“无锁wait-free 风格”的实现取向一致unordered_segment_table中allow_table_extending false桶表本身不再增长见 第 802–804 行。5. 实战用 parallel_for / parallel_reduce 并行遍历集合把range()的产物直接作为 TBB 并行算法的范围参数即可。以下示例演示两种典型写法代码为标准 TBB 用法基于本文第 2、3 节确认的 API 形态5.1 递归分治式求和并行 reduce#include oneapi/tbb/concurrent_unordered_set.h #include oneapi/tbb/parallel_reduce.h using set_type tbb::concurrent_unordered_setint; using range_type set_type::range_type; long long reduce_range(const range_type r) { if (r.empty()) { return 0; } if (!r.is_divisible()) { // 不可再分串行处理这一小段 long long sum 0; for (auto it r.begin(); it ! r.end(); it) { sum *it; } return sum; } range_type second(r, tbb::split()); // second 后半段r 收缩为前半段 return reduce_range(second) reduce_range(r); } int main() { set_type set; for (int i 0; i 1000000; i) { set.insert(i); // 并发安全可与其他线程的 insert 同时进行 } long long total tbb::parallel_reduce(set.range(), reduce_range, [](long long a, long long b) { return a b; }); (void)total; }range_type second(r, tbb::split())调用的正是第 3 节的分裂构造器由于新对象承接后半段、r保留前半段递归天然按递增顺序处理元素符合 Range 要求的串行顺序约定。5.2 parallel_for 只读扫描#include oneapi/tbb/concurrent_unordered_set.h #include oneapi/tbb/parallel_for.h tbb::parallel_for(set.range(), [](auto subrange) { for (auto it subrange.begin(); it ! subrange.end(); it) { // 只读处理每个元素校验、统计需按线程隔离累加、序列化等 } });const 对象上调用range()得到const_range_type其begin()/end()返回const_iterator适合纯只读场景两个版本的 range 都可以与insert、find等并发安全操作并行这正是 ContainerRange 规范 中“range 可用于parallel_for等并行算法遍历容器”的语义前提。并发安全边界与规范一致务必遵守迭代期间可并发执行insert/find/count等操作clear()、unsafe_erase()、unsafe_extract()、swap()、merge()等被规范归类为“Concurrently unsafe modifiers”不得与正在进行的迭代并发执行否则行为未定义。6. 测试验证与仓库索引仓库中的 TBB 测试套件对上述机制有直接的覆盖conformance_concurrent_unordered_set.cpp 是针对[containers.concurrent_unordered_set / concurrent_unordered_multiset]规范的符合性测试静态断言了hasher、key_equal、allocator_type等默认模板参数并复用了通用测试设施 concurrent_unordered_common.h共享的关联容器测试设施 concurrent_associative_common.h 对 range 做了递归分裂深度与 grain size 的验证CheckRecursiveRange递归到 256 层、grainsize() 0并在 第 1160–1163 行 用tbb::parallel_for(c.range(), ...)实际并行遍历容器验证并行迭代期间元素可见性功能级测试入口为 test_concurrent_unordered_set.cpp多集合并行读写场景由测试线程池驱动间接覆盖了“迭代 并发插入”组合下的正确性。与本文主题直接相关的仓库文件索引内容路径并行迭代规范页本文核心文档parallel_iteration.rst容器类总览与成员函数清单concurrent_unordered_set_cls.rstContainerRange 命名要求container_range.rstRange 分裂语义range.rstrange 类型与range()实现_concurrent_unordered_base.h容器类定义set / multisetconcurrent_unordered_set.h符合性测试conformance_concurrent_unordered_set.cpp7. 小结concurrent_unordered_set的并行迭代表面上只是一对range()重载实则建立在一套清晰的契约与机制之上range 类型满足 ContainerRange/Range 双重要求grainsize() 1把每个元素定义为最小工作单元range_type与const_range_type仅以边界迭代器的 const 属性区分而分裂的可行性完全取决于底层 split-ordered list 中 dummy 节点桶锚点的分布——set_midpoint()通过“键空间中点 → 桶号 → 父桶回退”三步在几乎无锁的前提下给出切分点。理解这一机制后读者即可放心地在parallel_for/parallel_reduce中并发遍历该容器同时严守“迭代期禁止并发擦除”的安全性边界。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考