mold 内置 TBB：concurrent_unordered_multiset 的并行迭代接口（range）与 ContainerRange 实现解析

mold 内置 TBBconcurrent_unordered_multiset 的并行迭代接口range与 ContainerRange 实现解析【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 mold 仓库内置的 TBB 组件中 parallel_iteration.rst 规范文档为主体系统讲解concurrent_unordered_multiset容器用于并行算法遍历的range_type/const_range_type成员类型与range()成员函数的语义、约束与契约并结合 TBB 源码中的实现与测试用例说明其拆分splitting机制帮助读者掌握如何把并发容器安全地喂给parallel_for等并行原语这一实战方案。一、为什么并发容器需要专门的并行迭代接口concurrent_unordered_multiset是一个允许多线程并发插入、查找的哈希容器multiset 即允许重复键。它不能像std::unordered_set那样简单地边遍历边处理遍历期间其他线程可能正在插入或删除节点。TBB 的解决方案是提供一类满足ContainerRange要求的 range 对象——它本质上是一段可递归二分的工作区间而不是传统意义上的迭代器区间。这样parallel_for、parallel_reduce等算法可以不断地调用拆分构造器把区间切成两半直到每一块小到适合串行执行从而在不加全局锁的情况下实现安全的并行遍历。这一点在规范中直接写明ContainerRange对象可以用于parallel_for等并行算法中遍历容器参见 ContainerRange 需求文档。二、成员类型range_type 与 const_range_type原文档的核心内容是对两个成员类型的界定成员类型concurrent_unordered_multiset::range_type和concurrent_unordered_multiset::const_range_type满足ContainerRange要求这两种类型唯一的区别在于const_range_type的边界bounds类型是concurrent_unordered_multiset::const_iterator而range_type的边界类型是concurrent_unordered_multiset::iterator。即二者功能完全一致只是返回的可变/只读迭代器不同。容器侧的配套迭代器接口定义在同章节的 iterators.rstiterator与const_iterator满足 ISO C 标准[forward.iterators]的 ForwardIterator 要求并提供begin()/cbegin()指向第一个元素与end()/cend()指向尾后位置。三、range() 成员函数原文档给出的接口签名与语义range_type range(); // 非 const 容器上调用 const_range_type range() const; // const 容器上调用Returns返回一个表示容器内全部元素的 range 对象。也就是说拿到容器的完整并行迭代入口只需要一行对非 const 容器调用range()得到range_type对 const 容器得到const_range_type。返回的 range 对象覆盖容器当前时刻的全部元素可被反复拆分。四、ContainerRange 契约range 对象必须满足哪些要求ContainerRange 需求文档需求编号req.container_range规定了满足该契约的类型必须同时满足两部分要求。4.1 必须满足 Range 要求首先它要满足 Range 要求req.range一个 range 可以被递归二分为两部分拆分通过调用其拆分构造器完成。Range 要求包括R::R( const R ); // 拷贝构造 bool empty() const; // 区间是否为空 bool is_divisible() const; // 是否可以再拆分为两个子区间 R::R( R r, split ); // 基本拆分构造器把 r 拆成两个子区间 R::R( R r, proportional_split ); // 可选按给定比例拆分规范还约定了拆分的方向性若值集合存在方向拆分构造器应构造区间的后半部分并更新入参为前半部分这样parallel_for/parallel_reduce/parallel_scan在退化为串行执行时会按递增顺序处理区间与普通顺序循环的行为一致。4.2 必须提供的成员类型与函数在此之上ContainerRange还要求提供成员说明CR::value_type区间内元素的类型CR::reference区间内元素的引用类型CR::const_reference区间内元素的 const 引用类型CR::iterator用于遍历区间的迭代器类型CR::size_type无符号整型用于获取 grain size粒度CR::difference_type两个迭代器之差的类型iterator CR::begin()返回指向区间起始的迭代器iterator CR::end()返回指向区间尾后位置的迭代器size_type CR::grainsize() const返回区间的粒度大小对concurrent_unordered_multiset的两种 range 类型而言这些成员在iterator一项上体现为上文提到的唯一差异range_type::iterator是iteratorconst_range_type::iterator是const_iterator。五、源码实现解析range 对象如何被拆分规范只描述契约真正的实现在 TBB 容器基类头文件 中concurrent_unordered_set与concurrent_unordered_multiset都继承自concurrent_unordered_base后者携带allow_multimapping true的特征参数见 concurrent_unordered_set.h。5.1 const_range_type持有区间边界与中点源码中const_range_type的核心成员变量是四个节点指针const concurrent_unordered_base my_instance; // 所属容器 node_ptr my_begin_node; // 区间起点 node_ptr my_end_node; // 区间终点尾后 mutable node_ptr my_midpoint_node; // 预计算的中点用于下次拆分它对外提供的接口与契约一一对应empty()my_begin_node my_end_node时为空is_divisible()my_midpoint_node ! my_end_node时仍可以再拆分grainsize()直接返回1即最小工作单元是单个元素begin()/end()从边界节点取出第一个值节点first_value_node包装成迭代器返回。5.2 拆分构造器O(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; // 原对象收缩到原中点 ... set_midpoint(); range.set_midpoint(); }由于中点在区间创建/上一次拆分时已预先计算好每次拆分本身是 O(1) 的指针操作。5.3 中点如何找到借助段表与 reverse_bitsconcurrent_unordered_base内部采用哈希段表segment table组织节点。set_midpoint()的思路是取my_begin_node与my_end_node的order_key()节点在段表中的有序键计算二者的中点键值对mid_bucket键执行reverse_bits按位反转后对当前桶数取模定位一个候选段表桶若该桶为空则通过get_parent(mid_bucket)向上回溯到最近非空祖先若反转后的桶号确实落在 begin 与 end 的 order_key 之间说明区间内部存在一个dummy 节点段表占位节点于是取该段第一个值节点作为中点否则区间内没有可切分点中点退化为my_end_node表示该区间不可再拆。可以推断这一设计利用了哈希容器的段表结构dummy 节点把整个键空间划分成连续段按中点键在段表中定位就能以接近 O(1) 的成本获得大约一半的切分位置而不必真的数出元素个数——这正是并发容器无法随时安全地全量遍历计数能做到高效递归拆分的根本原因。5.4 range_type继承并只改迭代器类型range_type 的完整定义只有 8 行它继承const_range_type复用拷贝构造与拆分构造器using const_range_type::const_range_type;仅重写begin()/end()把底层的const_iterator适配成iterator。这与规范两种类型仅边界迭代器类型不同的描述完全一致。容器侧的range()两个重载分别返回range_type(*this)与const_range_type(*this)源码。六、实战用法与测试验证6.1 与 parallel_for 配合遍历range 对象的标准用法是作为parallel_for的第一个参数lambda 捕获容器或 range后按迭代器遍历子区间#include oneapi/tbb/concurrent_unordered_set.h #include oneapi/tbb/parallel_for.h tbb::concurrent_unordered_multisetint table; // ... 多线程并发插入若干元素 ... // 并行遍历range 可被算法不断拆分为更小的子区间 tbb::parallel_for( table.range(), []( tbb::concurrent_unordered_multisetint::range_type r ) { for (auto it r.begin(); it ! r.end(); it) { // 处理元素 *it此处可只读访问元素 } } );测试代码中即有完全相同形态的用例concurrent_associative_common.h 同时对可变容器c与 const 容器constC的range()执行tbb::parallel_for分别验证可变与只读两条路径。6.2 测试用例对契约的逐条验证TBB 的公共测试头 concurrent_associative_common.h 对 range 契约做了系统断言空容器的 range 行为L428-L436空容器上range()得到的区间必须empty()、!is_divisible()且r.begin() r.end()、r.begin() cont.begin()递归拆分完整性L644-L649向容器插入 256 个元素后CheckRecursiveRange对range()递归二分直至不可拆累加各叶子区间的元素数应恰好等于 256可变迭代器与 const 迭代器两条路径分别验证同时断言grainsize() 0。这组断言恰好覆盖第四节列出的契约要点空语义、可分性、迭代器边界、grainsize 与递归拆分的完备性不重不漏。七、要点回顾concurrent_unordered_multiset提供range_type range()与const_range_type range() const两个重载返回表示容器全部元素的可递归拆分区间二者唯一区别是边界迭代器类型iteratorvsconst_iteratorrange 对象满足ContainerRange契约在Range要求empty/is_divisible/split拆分构造器之上额外提供value_type、reference、iterator、size_type、begin()/end()/grainsize()等成员实现上中点借助哈希段表与reverse_bits中点键定位使每次拆分接近 O(1)且区间不可再拆时is_divisible()返回 false保证算法可安全终止实战中把cont.range()直接传给tbb::parallel_for或其 const 版本即可完成并发遍历仓库测试已按契约对空容器、递归拆分完整性等场景做了覆盖可作为编写自定义 range 时的参照。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考