mold 第三方 TBB 中 concurrent_set 的并行迭代range()、ContainerRange 需求与跳表分裂实现【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文为 TBBoneTBBmold 仓库以third-party/tbb形式内置的concurrent_set容器撰写聚焦其并行迭代接口range()成员函数与range_type/const_range_type两个成员类型。读完本篇你将理解这两个类型如何满足 TBB 规范中的ContainerRange需求、跳表skip list底层是如何实现分裂的以及如何把range()的结果直接喂给parallel_for等并行算法。1. 并行迭代的两个成员类型TBB 规范文档parallel_iteration.rst对concurrent_set的并行迭代给出了如下定义concurrent_set::range_type与concurrent_set::const_range_type这两个成员类型满足ContainerRange需求规范条目[req.container_range]见 container_range.rst。两种类型唯一的区别在于边界bounds类型const_range_type的边界是concurrent_set::const_iteratorrange_type的边界是concurrent_set::iterator。ContainerRange 的定位是一个可以整体或部分表示并发容器concurrent container的 range 对象可用于parallel_for之类的并行算法中遍历容器原文表述TheContainerRangeobject can be used to traverse the container in parallel algorithms likeparallel_for.。2. range() 成员函数规范给出的成员函数签名只有一个range_type range(); const_range_type range() const;返回值一个表示容器中全部元素的 range 对象。也就是说任何线程都可以调用range()获取一个描述当前整个容器的迭代范围对象再将其交给并行算法递归切分。在 mold 仓库内置的 TBB 源码中这两个重载位于基类concurrent_skip_listconcurrent_set/concurrent_multiset的共同基类// third-party/tbb/include/oneapi/tbb/detail/_concurrent_skip_list.h, L777-L778 range_type range() { return range_type(*this); } const_range_type range() const { return const_range_type(*this); }由于concurrent_set直接继承自concurrent_skip_list见 concurrent_set.h 第 55–56 行base_type即concurrent_skip_listset_traits..., geometric_level_generator32, Allocator, falserange()、range_type、const_range_type对concurrent_set而言都是继承而来的公开接口。3. ContainerRange 需求逐项拆解根据 container_range.rst类型CR要满足ContainerRange需同时满足两部分条件3.1 先满足 Range 需求CR必须满足 Range 需求。Range 的核心是可递归二分Range 可以通过调用其分裂构造器splitting constructor递归地切分为两部分分为两类基本分裂构造器必选R::R( const R )之外的R::R( R r, split)将r一分为二规范要求尽量均分均分通常能带来最好的并行度但不强制比例分裂构造器可选R::R( R r, proportional_split proportion)按给定比例切分必要时四舍五入到最近整数。理想的 Range 可以一直切分直到子部分小得串行执行比继续切分更高效为止。由于切分粒度与上层语境相关典型 Range 类型会提供控制切分程度的手段——例如blocked_range模板类的grainsize参数指定被认为不可再分的最大范围。方向约定若取值集合有方向感分裂构造器按惯例应让实参变为前半段、新对象成为后半段这样parallel_for、parallel_reduce、parallel_scan在顺序运行时能按递增顺序处理符合普通顺序循环的习惯。因为声明了分裂构造器与拷贝构造器Range 不会自动生成默认构造器需要显式定义默认构造器或任意其他构造器来创建实例。Range 需求汇总伪签名 / 语义伪签名语义R::R( const R )拷贝构造器R::~R()析构函数bool R::empty() const范围为空时返回 truebool R::is_divisible() const范围可否切分为两个子范围R::R( R r, split )基本分裂构造器把r切成两部分R::R( R r, proportional_split proportion )可选。按proportion比例切分3.2 再提供成员类型与成员函数ContainerRange在此基础上要求CR提供成员语义CR::value_type范围内元素的类型CR::reference指向范围内元素的引用类型CR::const_reference指向范围内元素的常量引用类型CR::iterator用于遍历范围的迭代器类型CR::size_type用于获取 grain size 的无符号整数类型CR::difference_type两个迭代器之差的类型iterator CR::begin()返回范围起点的迭代器iterator CR::end()返回最后一个元素之后位置的迭代器size_type CR::grainsize() const返回范围的 grain size这正是concurrent_set::range_type/const_range_type所满足的契约两个类型都提供上述全部成员差异仅落在iterator是concurrent_set::iterator还是concurrent_set::const_iterator。4. 源码实现跳表上的 range 类型规范中抽象的empty()/is_divisible()/ 分裂构造器 /grainsize()在仓库内的具体实现见 _concurrent_skip_list.h。实现分为两层const_range_type基类持有状态并实现分裂逻辑range_type派生自它、只改写返回的迭代器类型——这与规范两类型仅边界类型不同的表述一一对应。4.1 状态与可观测成员// _concurrent_skip_list.h, L709-L755节选 class const_range_type { public: using size_type typename concurrent_skip_list::size_type; using difference_type typename concurrent_skip_list::difference_type; using iterator typename concurrent_skip_list::const_iterator; // 边界是 const_iterator using value_type typename iterator::value_type; using reference typename iterator::reference; bool empty() const { return my_begin.my_node_ptr ? (my_begin.my_node_ptr-next(0) my_end.my_node_ptr) : true; } bool is_divisible() const { return my_begin.my_node_ptr my_level ! 0 ? my_begin.my_node_ptr-next(my_level - 1) ! my_end.my_node_ptr : false; } size_type size() const { return std::distance(my_begin, my_end); } // ... iterator begin() const { return my_begin; } iterator end() const { return my_end; } size_type grainsize() const { return 1; } private: const_iterator my_end; const_iterator my_begin; size_type my_level; }; // class const_range_type逐条对照规范empty()起点节点为空或起点的第 0 层后继恰好就是终点即范围内只剩或没有一个节点返回 trueis_divisible()起点存在、且当前切分层级my_level ! 0、且起点在第my_level - 1层还有不是终点的后继时才返回 true。从源码结构看这保证了只有当子范围内至少有两个节点时才继续分裂避免了对单元素范围的无效切分size()用std::distance(my_begin, my_end)线性距离计算元素数规范未强制此成员属于实现附赠的可观测接口grainsize()恒返回1。结合第 3.1 节 grainsize 的语义被视为不可再分的最小范围可以推断concurrent_set的 range 允许被切分到一个元素为止是否在此时停手由parallel_for等算法自身的调度策略决定。4.2 分裂构造器利用跳表高层指针跳跃式对半切实现中最值得玩味的是分裂构造器// _concurrent_skip_list.h, L730-L745 const_range_type( const_range_type r, split) : my_end(r.my_end) { if (r.empty()) { __TBB_ASSERT(my_end.my_node_ptr nullptr, nullptr); my_begin my_end; my_level 0; } else { my_begin iterator(r.my_begin.my_node_ptr-next(r.my_level - 1)); my_level my_begin.my_node_ptr-height(); } r.my_end my_begin; } const_range_type( const concurrent_skip_list l) : my_end(l.end()), my_begin(l.begin()), my_level(my_begin.my_node_ptr ? my_begin.my_node_ptr-height() : 0) {}其工作方式结合跳表结构可以推断如下从容器构造 rangerange()内部走的构造器起点取begin()、终点取end()my_level初始化为起点节点的高度——即后续分裂都从该节点参与的最高层索引开始分裂时把原范围r的终点作为新对象的终点新对象不取r的起点本身而是取r起点节点在第my_level - 1层的后继作为自己的起点——在跳表中高层链接跳过的是整段连续的底层节点因此一次next(level)就能把剩余区间切出一大块而无需线性扫描原范围r的终点被更新为新的my_begin于是r变成前半段、新对象是后半段与第 3.1 节的方向约定一致顺序执行时按递增顺序处理新对象的my_level设为新起点自身节点的高度下一轮分裂从新起点能触及的最高层继续跳跃。从源码结构看这套机制让每次分裂的代价与该层索引距离相关而非元素个数这正是推荐尽量均分的规范要求在跳表场景下的落点高层指针天然把区间切成大致相近的两段。4.3 range_type仅替换边界迭代器类型// _concurrent_skip_list.h, L757-L775 class range_type : public const_range_type { public: using iterator typename concurrent_skip_list::iterator; // 边界是 iterator using value_type typename iterator::value_type; using reference typename iterator::reference; range_type(range_type r, split) : const_range_type(r, split()) {} range_type(const concurrent_skip_list l) : const_range_type(l) {} iterator begin() const { /* 把基类 const_iterator 重新解释为 iterator */ } iterator end() const { /* 同上 */ } }; // class range_type可以看到range_type完全复用基类的empty()/is_divisible()/ 分裂逻辑仅将begin()/end()的返回类型提升为非 const 的iterator。这与规范文档对两类型差异的表述严格吻合也解释了为何const_range_type::iterator定义为concurrent_skip_list::const_iteratorL713而range_type::iterator重新别名为concurrent_skip_list::iteratorL759。5. 实战用法把 range 交给 parallel_for按 ContainerRange 的规范用途可用于parallel_for之类的并行算法遍历容器一个典型用法骨架如下#include oneapi/tbb/concurrent_set.h #include oneapi/tbb/parallel_for.h tbb::concurrent_setint data{1, 2, 3, 4, 5, 6, 7, 8}; // 非 const 对象调用非 const 版 range()得到 range_type tbb::parallel_for( data.range(), { for (auto it r.begin(); it ! r.end(); it) { // 对每个元素做并行处理例如 *it *it * 2 之外的无共享状态计算 } }); // 只有 const 对象或只读需求时使用 const_range_type const auto cdata data; tbb::parallel_for( cdata.range(), { for (auto it r.begin(); it ! r.end(); it) { /* 只读遍历 */ } });要点说明data.range()返回的对象是range_type非 const 成员函数版本cdata.range()返回const_range_type——与第 2 节的两个重载一一对应parallel_for内部正是通过is_divisible()判断能否继续切分、通过分裂构造器R(R r, split)递归对半这与第 4.2 节的实现相互印证规范同时提醒Range 需求一节声明了分裂与拷贝构造器的 Range 不会自动生成默认构造器。本仓库实现中const_range_type未显式声明默认构造器因此 range 对象应通过range()或分裂构造器获取这与需要显式定义默认构造器或任意其他构造器来创建实例的要求是一致的此点为对源码结构的阅读推断。6. 适用前提与限制本节所述接口来自 mold 仓库内置的 TBB 实现third-party/tbbconcurrent_set/concurrent_multiset均经由共同基类concurrent_skip_list获得range()与 range 类型concurrent_multiset允许重复键其 range 语义与concurrent_set相同。grainsize()恒为 1意味着规范语义下不可再分的最小粒度是一个元素具体何时停止切分由并行算法自身策略决定。迭代器满足 ForwardIterator 需求见 iterators.rst 对concurrent_set::iterator/const_iterator的说明单个迭代器只应由一个线程使用并行场景下由parallel_for保证各线程持有不相交的子范围。规范对range()的表述是表示调用时刻容器中全部元素的 range 对象。在迭代期间若其他线程并发修改容器行为以 TBB 规范的并发容器语义为准本文不对此展开额外推断。相关规范与实现入口索引parallel_iteration.rst本文主题规范、container_range.rstContainerRange 需求、range.rstRange 需求、concurrent_set.h容器公开接口、_concurrent_skip_list.hrange 类型实现。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考