深入理解 TBB Range 概念mold 中 parallel_for / parallel_reduce 的分治基石【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldRange 是 oneAPI Threading Building BlocksTBB算法库的核心抽象它定义了一类可以递归二分的值区间parallel_for、parallel_reduce、parallel_scan等模板算法正是通过反复调用 Range 的分裂构造函数把大任务拆成可并行执行的小块。本文以 TBB 规范中的 Range 命名要求 为主体结合本仓库 third-party/tbb 下的真实源码与 mold 链接器对 TBB 的实际使用完整讲解 Range 的两种分裂构造函数、五大必备成员、grainsize 粒度控制以及如何自己动手实现一个满足 Range 要求的类型。读完本文你将掌握 TBB 并行算法的分治模型并能写出可被parallel_for/parallel_reduce直接消费的自定义 Range。说明本文讲解的 TBB 源码位于仓库 third-party/tbb 目录mold 链接器内置的第三方依赖mold 主程序在 src/passes.cc 等文件中大量使用tbb::parallel_for与tbb::parallel_for_each加速链接过程。Range 是什么可递归二分的工作区间Range 是一种概念concept/ 命名要求named requirement而不是某个具体类。一个类型R只要满足一组约定好的成员函数签名与语义就被认为符合 Range。规范原文range.rst给出的定义是ARangecan be recursively subdivided into two parts. Subdivision is done by callingsplitting constructorof aRange.也就是说Range 描述的不是一整块数据而是一棵动态生成的递归分割树算法拿到初始 Range 后不断用分裂构造函数把它一分为二直到每个子块足够小、串行执行比继续切分更划算为止。这种先切分、后执行的模型是 TBB 工作窃取work stealing调度得以运转的前提——每个线程都可以从任务队列里抢一块子 Range 来执行而 Range 本身只负责描述这块区间是什么。具体到 mold 项目链接器在 src/passes.cc 中把扫描所有输入目标文件合并符号表重定位计算等步骤实现为对ctx.objs、ctx.merged_sections、ctx.chunks等容器的大规模并行遍历例如tbb::parallel_for((i64)0, (i64)ctx.objs.size(), ...)见 src/passes.cc底层正是依赖 TBB 将整数区间递归切分到各个线程。两种分裂构造函数规范把分裂构造函数分成两类这是 Range 概念最核心的内容构造函数是否可选语义R::R(R r, split)基本分裂构造函数必选把r一分为二建议尽量均分不强制R::R(R r, proportional_split proportion)比例分裂构造函数可选按proportion给定的比例切分r必要时四舍五入到最近整数基本分裂文档强调均分通常能获得最好的并行度因为各子块工作量均衡线程不容易出现负载不均但规范并不强制均分只要语义上是分成两个子区间即可。比例分裂适用于已知任务一头重一头轻的场景。比如某个循环里前 20% 的迭代耗时占 80%用proportional_split(1, 4)让切分点偏向工作量大的一侧可以显著减少负载不均衡。由于它是可选的不实现比例分裂构造函数的类型仍然是合法 Range——算法会退化为普通均分源码中的range_split_object_provider专门处理这一回退见下文。分裂何时停止grainsize 的语义Range 的理想分裂终点是子块代表的工作串行执行比继续切分更高效。但多大算大通常取决于调用场景因此一个合格的 Range 类型应当提供控制分裂程度的手段。规范原文点名了模板类blocked_range的grainsize参数For example, the template classblocked_rangehas thegrainsizeparameter that specifies the biggest range considered indivisible.grainsize 就是不可再分的阈值当区间大小size()大于grainsize时可分裂小于等于则不可分裂。在 blocked_range.h 中这一语义直接落在代码里// third-party/tbb/include/oneapi/tbb/blocked_range.h bool empty() const { return !(my_beginmy_end); } // L81 bool is_divisible() const { return my_grainsizesize(); } // L85blocked_range(Value begin_, Value end_, size_type grainsize_1)blocked_range.h默认 grainsize 为 1且构造时断言grainsize 0。grainsize 越大任务切分越粗、调度开销越低但并行度也越低实践中常取单次迭代平均耗时 × 目标调度开销来估算mold 中把目标文件扫描等大批量、短迭代的循环交给 TBB 处理正是希望用足够细的 grainsize 摊满所有核心。迭代方向约定让并行循环看起来像串行循环规范中还规定了一条重要的方向约定If the set of values has a sense of direction, by convention the splitting constructor should construct the second part of the range and update its argument to be the first part of the range.即分裂构造函数应当新构造的对象代表后半段而参数r被更新为前半段。这样parallel_for、parallel_reduce、parallel_scan在顺序执行时会按递增顺序遍历整个区间行为与普通 for 循环一致——这对依赖确定性遍历顺序的 reduce/scan 结果、以及调试时的可复现性都至关重要。看 blocked_range.h 的基本分裂实现就能验证这个约定// third-party/tbb/include/oneapi/tbb/blocked_range.h L118-L124 static Value do_split( blocked_range r, split ) { __TBB_ASSERT( r.is_divisible(), cannot split blocked_range that is not divisible ); Value middle r.my_begin (r.my_end - r.my_begin) / 2u; r.my_end middle; // 原对象 r 被截为前半段 [begin, middle) return middle; // 新对象从 middle 开始即后半段 [middle, end) }而blocked_range的分裂构造函数正是my_begin(do_split(r, split()))新对象的my_end继承原r.my_endmy_begin取切分点于是新对象 后半段、r 前半段与规范约定完全一致。比例分裂同样遵循该约定其切分点的计算blocked_range.h为size_type right_part size_type(float(r.size()) * float(proportion.right()) / float(proportion.left() proportion.right()) 0.5f); return r.my_end Value(r.my_end - right_part);源码注释还特别说明了一个工程细节用 32 位浮点运算处理超过 2^24 次迭代的区间会有精度损失但即使在 2^64 次迭代规模下计算误差也仅约 0.000001%对均匀切分的影响可以忽略追求精确切分的场景可参考其test_partitioner_whitebox测试中的精确算法。默认构造函数不会被自动生成Range 概念有一个容易被忽略的连带约束Because aRangedeclares splitting and copy constructors, the default constructor for it is not generated automatically. You need to explicitly define the default constructor or add any other constructor to create an instance of aRangetype in the program.C 规则一旦类声明了任何构造函数包括复制构造函数和分裂构造函数编译器就不再隐式生成默认构造函数。因此一个自定义 Range 类型若想被R r;这样实例化必须显式定义默认构造函数或提供任意其他可用构造函数。实践中blocked_range的做法是提供三参构造函数blocked_range(begin, end, grainsize1)靠默认参数兼作默认构造入口。Range 要求的完整清单Pseudo-Signature 与语义规范用一张伪签名表给出类型R满足 Range 所需的全部成员。这张表是判断我的类型是不是 Range的逐项对照清单伪签名语义R::R( const R )复制构造函数。Range 会被反复拷贝分发到各线程必须可拷贝R::~R()析构函数bool R::empty() const区间为空则返回 truebool R::is_divisible() const区间可被分成两个子区间则返回 trueR::R( R r, split )基本分裂构造函数把r分成两个子区间R::R( R r, proportional_split proportion )可选比例分裂构造函数按proportion切分r注意两点参数必须是R非 const 引用分裂构造函数要原地修改r把它改成前半段所以不能接受 const 引用也正是这一点让编译器能区分分裂构造与复制构造——split/proportional_split只是起标记作用的 tag 类型。empty()与is_divisible()必须为 const 成员调度器在只读视角下就能判断是否继续切分。规范同时把这些成员对应的运行时行为定义为empty()即无任何元素is_divisible()为 true 意味着调用分裂构造函数不会产生空子区间。在 blocked_range.h 中两个分裂构造函数体内都有__TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly )断言Debug 构建下可即时发现错误切分。分裂 tagsplit 与 proportional_split两个分裂 tag 类型的定义位于 detail/_range_common.h// third-party/tbb/include/oneapi/tbb/detail/_range_common.h L36 class split {}; // 空 tag用于把分裂构造函数与复制构造函数区分开 // L43-L55 class proportional_split : no_assign { public: proportional_split(size_t _left 1, size_t _right 1) : my_left(_left), my_right(_right) { } size_t left() const { return my_left; } size_t right() const { return my_right; } // used when range does not support proportional split explicit operator split() const { return split(); } private: size_t my_left, my_right; };关键点split是空类纯粹作为重载标记与 STL 中std::piecewise_construct_t的思路一致proportional_split携带左、右两个权重系数left()/right()供 Range 计算切分点它提供explicit operator split()从而对不支持比例分裂的 Range 自动降级为普通分裂。降级机制由 detail/_range_common.h 的range_split_object_provider实现通过std::is_constructibleRange, Range, proportional_split做 SFINAE 检测——若 Range 实现了比例分裂构造函数就把proportional_split原样传给分裂构造函数否则退化为splittemplate typename Range, typename void struct range_split_object_provider { template typename PartitionerSplitType static split get( PartitionerSplitType ) { return split(); } }; template typename Range struct range_split_object_providerRange, typename std::enable_ifstd::is_constructibleRange, Range, proportional_split::value::type { template typename PartitionerSplitType static PartitionerSplitType get( PartitionerSplitType split_obj ) { return split_obj; } };此外detail/_range_common.h 在 C20 环境下还给出了形式化的 concept 定义可视为对规范表格的可编译版本template typename T concept splittable std::constructible_fromT, T, tbb::detail::split; template typename Range concept tbb_range std::copy_constructibleRange splittableRange requires( const std::remove_reference_tRange range ) { { range.empty() } - relaxed_convertible_tobool; { range.is_divisible() } - relaxed_convertible_tobool; };官方 Range 家族从一维到 N 维规范在 See also 中列出了 TBB 提供的标准 Range 类型它们全部满足上述要求是学习自定义 Range 的最佳参照物blocked_range一维半开区间[begin, end)带 grainsizesize() end() - begin()is_divisible()即size() grainsize()blocked_range2d / blocked_range3d二维/三维迭代空间行与列可有不同的 Value 类型和 grainsizeblocked_nd_rangeN 维推广templatetypename Value, unsigned int N所有维度必须是同一 Value 类型并附带丰富的推导指引deduction guides。多维 Range 的分裂策略值得单独一提。以 blocked_range2d.h 为例它的do_split并不固定切行或切列而是比较两个维度的大小 / grainsize比值优先切分更稀疏比值更大的那个维度if ( my_rows.size()*double(my_cols.grainsize()) my_cols.size()*double(my_rows.grainsize()) ) { my_cols.my_begin col_range_type::do_split(r.my_cols, split_obj); } else { my_rows.my_begin row_range_type::do_split(r.my_rows, split_obj); }blocked_nd_range_cls.rst 中的规范说明同样建议沿 size-to-grainsize 比值最大的维度切分使得反复切分后子块趋向近正方形/立方体从而改善缓存局部性。这是多维 Range 相对一维 Range 最重要的行为差异。使用示例从规范文档直接可用的代码blocked_range_cls.rst 给出了可直接验证的语义示例均与 blocked_range.h 的实现一一对应blocked_rangeint r(5, 14, 2); // 表示 [5, 14)含 5..13grainsize 2 // r.begin() 5, r.end() 14 blocked_rangeint s(r, split); // 基本分裂后 // r 表示 [5, 9)s 表示 [9, 14)grainsize 均为 2 blocked_rangeint t(r, proportional_split(2, 3)); // 比例分裂后 // r 表示 [5, 52*(9-5)/5)t 表示 [52*(9-5)/5, 9)规范还特别解释了const_iterator这个命名它不一定是真正的 STL 迭代器只需满足 BlockedRangeValue 要求但命名为const_iterator后若 Value 恰好是迭代器类型blocked_range就能像只读 STL 容器一样使用。调度器如何消费 Range以 parallel_for 为例Range 不是孤立存在的它的价值在于被算法模板消费。在 parallel_for.h 中start_for任务类型的分裂构造函数直接调用了 Range 的分裂构造函数// third-party/tbb/include/oneapi/tbb/parallel_for.h L82-L87 start_for( start_for parent_, typename Partitioner::split_type split_obj, small_object_allocator alloc ) : my_range(parent_.my_range, get_range_split_objectRange(split_obj)), my_body(parent_.my_body), my_parent(nullptr), my_partition(parent_.my_partition, split_obj), my_allocator(alloc) {}这里my_range(parent_.my_range, get_range_split_objectRange(split_obj))就是整个并行模型的心脏调度器把一个start_for任务分裂成两个子任务时同时用split/proportional_splittag 调用 Range 的分裂构造函数把区间切成左右两半。get_range_split_objectRange正是前文提到的比例分裂降级检测函数。换句话说Range 概念的全部要求可拷贝、可判空、可判可分、可分裂都是为这条调用链服务的。parallel_reduce、parallel_scan的start_reduce/start_scan任务内部采用同样的模式。mold 中的真实调用mold 链接器把 TBB 作为内建并行运行时在 src/passes.cc 中几乎每个对全部目标文件/输出段做一遍处理的 pass 都用了tbb::parallel_for_each或tbb::parallel_for。例如符号表扫描、段成员收集、ctx.chunks的逐块处理等都以ctx.objs、ctx.merged_sections、ctx.osec_pool、ctx.chunks等容器为 Range 来源。这些调用的背后正是本文介绍的 split 语义在支撑一个大任务被递归切成几百个小任务、分发给所有工作线程的执行模型——链接一个大型 C 程序时动辄上百万次重定位的并行计算都依赖这一层 Range 抽象保持正确、均衡且可预测。动手实现一个自定义 Range综合规范表格与源码实现一个满足 Range 要求的类型只需五个成员外加可选的第六个。最小可用模板如下#include oneapi/tbb/blocked_range.h template typename T class my_range { T my_begin, my_end; std::size_t my_grainsize; public: // 1. 显式提供构造函数Range 声明了分裂/复制构造默认构造不会自动生成 my_range(T begin, T end, std::size_t grainsize 1) : my_begin(begin), my_end(end), my_grainsize(grainsize) {} // 2. 复制构造 析构可省略声明编译器默认生成即可 // 3. 判空 bool empty() const { return !(my_begin my_end); } // 4. 判可分大小超过 grainsize bool is_divisible() const { return my_grainsize size(); } // 5. 基本分裂构造新对象为后半段r 更新为前半段 my_range(my_range r, tbb::split) : my_begin(r.my_begin (r.my_end - r.my_begin) / 2), my_end(r.my_end), my_grainsize(r.my_grainsize) { r.my_end my_begin; } // 6.可选比例分裂构造按 left:right 切分 my_range(my_range r, tbb::proportional_split proportion) : my_begin(r.my_begin (r.my_end - r.my_begin) * proportion.left() / (proportion.left() proportion.right())), my_end(r.my_end), my_grainsize(r.my_grainsize) { r.my_end my_begin; } std::size_t size() const { return std::size_t(my_end - my_begin); } T begin() const { return my_begin; } T end() const { return my_end; } };实现时请对照规范逐条自检分裂构造函数参数必须是R且修改原对象新对象代表后半段方向约定保证顺序遍历递增必须显式定义默认构造函数或可用构造否则无法实例化规范明确要求empty()/is_divisible()必须是 const 成员建议提供 grainsize 之类的分裂度控制否则任务可能被切到过细调度开销反而拖慢整体性能若实现了比例分裂构造函数调度器会自动用proportional_split调用它detail/_range_common.h 的 SFINAE 检测保证不实现也不会编译失败只是退化为均分。写完的类型即可直接传给tbb::parallel_for(my_rangeT(...), body)或tbb::parallel_reduce由调度器自动完成递归分裂 → 工作窃取 → 子块执行的完整流程。小结Range 是 TBB 并行算法与用户数据之间唯一的契约一个可拷贝、可判空、可判可分、可递归二分可选项按比例二分的轻量描述对象。它通过split/proportional_split两个 tag 与复制构造函数区分开通过 grainsize 之类的参数控制分裂粒度并通过新对象为后半段的方向约定保证顺序执行时的遍历次序与普通循环一致。理解这份规范range.rst再对照 blocked_range.h 与 parallel_for.h 的源码就能既写出正确的自定义 Range也看懂 mold 这类大型程序如何借 TBB 的分治模型榨干多核性能。延伸阅读仓库内文档blocked_range 类规范blocked_nd_range 类规范split 类规范proportional_split 类规范mold 并行 pass 实现【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
深入理解 TBB Range 概念：mold 中 parallel_for / parallel_reduce 的分治基石
深入理解 TBB Range 概念mold 中 parallel_for / parallel_reduce 的分治基石【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldRange 是 oneAPI Threading Building BlocksTBB算法库的核心抽象它定义了一类可以递归二分的值区间parallel_for、parallel_reduce、parallel_scan等模板算法正是通过反复调用 Range 的分裂构造函数把大任务拆成可并行执行的小块。本文以 TBB 规范中的 Range 命名要求 为主体结合本仓库 third-party/tbb 下的真实源码与 mold 链接器对 TBB 的实际使用完整讲解 Range 的两种分裂构造函数、五大必备成员、grainsize 粒度控制以及如何自己动手实现一个满足 Range 要求的类型。读完本文你将掌握 TBB 并行算法的分治模型并能写出可被parallel_for/parallel_reduce直接消费的自定义 Range。说明本文讲解的 TBB 源码位于仓库 third-party/tbb 目录mold 链接器内置的第三方依赖mold 主程序在 src/passes.cc 等文件中大量使用tbb::parallel_for与tbb::parallel_for_each加速链接过程。Range 是什么可递归二分的工作区间Range 是一种概念concept/ 命名要求named requirement而不是某个具体类。一个类型R只要满足一组约定好的成员函数签名与语义就被认为符合 Range。规范原文range.rst给出的定义是ARangecan be recursively subdivided into two parts. Subdivision is done by callingsplitting constructorof aRange.也就是说Range 描述的不是一整块数据而是一棵动态生成的递归分割树算法拿到初始 Range 后不断用分裂构造函数把它一分为二直到每个子块足够小、串行执行比继续切分更划算为止。这种先切分、后执行的模型是 TBB 工作窃取work stealing调度得以运转的前提——每个线程都可以从任务队列里抢一块子 Range 来执行而 Range 本身只负责描述这块区间是什么。具体到 mold 项目链接器在 src/passes.cc 中把扫描所有输入目标文件合并符号表重定位计算等步骤实现为对ctx.objs、ctx.merged_sections、ctx.chunks等容器的大规模并行遍历例如tbb::parallel_for((i64)0, (i64)ctx.objs.size(), ...)见 src/passes.cc底层正是依赖 TBB 将整数区间递归切分到各个线程。两种分裂构造函数规范把分裂构造函数分成两类这是 Range 概念最核心的内容构造函数是否可选语义R::R(R r, split)基本分裂构造函数必选把r一分为二建议尽量均分不强制R::R(R r, proportional_split proportion)比例分裂构造函数可选按proportion给定的比例切分r必要时四舍五入到最近整数基本分裂文档强调均分通常能获得最好的并行度因为各子块工作量均衡线程不容易出现负载不均但规范并不强制均分只要语义上是分成两个子区间即可。比例分裂适用于已知任务一头重一头轻的场景。比如某个循环里前 20% 的迭代耗时占 80%用proportional_split(1, 4)让切分点偏向工作量大的一侧可以显著减少负载不均衡。由于它是可选的不实现比例分裂构造函数的类型仍然是合法 Range——算法会退化为普通均分源码中的range_split_object_provider专门处理这一回退见下文。分裂何时停止grainsize 的语义Range 的理想分裂终点是子块代表的工作串行执行比继续切分更高效。但多大算大通常取决于调用场景因此一个合格的 Range 类型应当提供控制分裂程度的手段。规范原文点名了模板类blocked_range的grainsize参数For example, the template classblocked_rangehas thegrainsizeparameter that specifies the biggest range considered indivisible.grainsize 就是不可再分的阈值当区间大小size()大于grainsize时可分裂小于等于则不可分裂。在 blocked_range.h 中这一语义直接落在代码里// third-party/tbb/include/oneapi/tbb/blocked_range.h bool empty() const { return !(my_beginmy_end); } // L81 bool is_divisible() const { return my_grainsizesize(); } // L85blocked_range(Value begin_, Value end_, size_type grainsize_1)blocked_range.h默认 grainsize 为 1且构造时断言grainsize 0。grainsize 越大任务切分越粗、调度开销越低但并行度也越低实践中常取单次迭代平均耗时 × 目标调度开销来估算mold 中把目标文件扫描等大批量、短迭代的循环交给 TBB 处理正是希望用足够细的 grainsize 摊满所有核心。迭代方向约定让并行循环看起来像串行循环规范中还规定了一条重要的方向约定If the set of values has a sense of direction, by convention the splitting constructor should construct the second part of the range and update its argument to be the first part of the range.即分裂构造函数应当新构造的对象代表后半段而参数r被更新为前半段。这样parallel_for、parallel_reduce、parallel_scan在顺序执行时会按递增顺序遍历整个区间行为与普通 for 循环一致——这对依赖确定性遍历顺序的 reduce/scan 结果、以及调试时的可复现性都至关重要。看 blocked_range.h 的基本分裂实现就能验证这个约定// third-party/tbb/include/oneapi/tbb/blocked_range.h L118-L124 static Value do_split( blocked_range r, split ) { __TBB_ASSERT( r.is_divisible(), cannot split blocked_range that is not divisible ); Value middle r.my_begin (r.my_end - r.my_begin) / 2u; r.my_end middle; // 原对象 r 被截为前半段 [begin, middle) return middle; // 新对象从 middle 开始即后半段 [middle, end) }而blocked_range的分裂构造函数正是my_begin(do_split(r, split()))新对象的my_end继承原r.my_endmy_begin取切分点于是新对象 后半段、r 前半段与规范约定完全一致。比例分裂同样遵循该约定其切分点的计算blocked_range.h为size_type right_part size_type(float(r.size()) * float(proportion.right()) / float(proportion.left() proportion.right()) 0.5f); return r.my_end Value(r.my_end - right_part);源码注释还特别说明了一个工程细节用 32 位浮点运算处理超过 2^24 次迭代的区间会有精度损失但即使在 2^64 次迭代规模下计算误差也仅约 0.000001%对均匀切分的影响可以忽略追求精确切分的场景可参考其test_partitioner_whitebox测试中的精确算法。默认构造函数不会被自动生成Range 概念有一个容易被忽略的连带约束Because aRangedeclares splitting and copy constructors, the default constructor for it is not generated automatically. You need to explicitly define the default constructor or add any other constructor to create an instance of aRangetype in the program.C 规则一旦类声明了任何构造函数包括复制构造函数和分裂构造函数编译器就不再隐式生成默认构造函数。因此一个自定义 Range 类型若想被R r;这样实例化必须显式定义默认构造函数或提供任意其他可用构造函数。实践中blocked_range的做法是提供三参构造函数blocked_range(begin, end, grainsize1)靠默认参数兼作默认构造入口。Range 要求的完整清单Pseudo-Signature 与语义规范用一张伪签名表给出类型R满足 Range 所需的全部成员。这张表是判断我的类型是不是 Range的逐项对照清单伪签名语义R::R( const R )复制构造函数。Range 会被反复拷贝分发到各线程必须可拷贝R::~R()析构函数bool R::empty() const区间为空则返回 truebool R::is_divisible() const区间可被分成两个子区间则返回 trueR::R( R r, split )基本分裂构造函数把r分成两个子区间R::R( R r, proportional_split proportion )可选比例分裂构造函数按proportion切分r注意两点参数必须是R非 const 引用分裂构造函数要原地修改r把它改成前半段所以不能接受 const 引用也正是这一点让编译器能区分分裂构造与复制构造——split/proportional_split只是起标记作用的 tag 类型。empty()与is_divisible()必须为 const 成员调度器在只读视角下就能判断是否继续切分。规范同时把这些成员对应的运行时行为定义为empty()即无任何元素is_divisible()为 true 意味着调用分裂构造函数不会产生空子区间。在 blocked_range.h 中两个分裂构造函数体内都有__TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly )断言Debug 构建下可即时发现错误切分。分裂 tagsplit 与 proportional_split两个分裂 tag 类型的定义位于 detail/_range_common.h// third-party/tbb/include/oneapi/tbb/detail/_range_common.h L36 class split {}; // 空 tag用于把分裂构造函数与复制构造函数区分开 // L43-L55 class proportional_split : no_assign { public: proportional_split(size_t _left 1, size_t _right 1) : my_left(_left), my_right(_right) { } size_t left() const { return my_left; } size_t right() const { return my_right; } // used when range does not support proportional split explicit operator split() const { return split(); } private: size_t my_left, my_right; };关键点split是空类纯粹作为重载标记与 STL 中std::piecewise_construct_t的思路一致proportional_split携带左、右两个权重系数left()/right()供 Range 计算切分点它提供explicit operator split()从而对不支持比例分裂的 Range 自动降级为普通分裂。降级机制由 detail/_range_common.h 的range_split_object_provider实现通过std::is_constructibleRange, Range, proportional_split做 SFINAE 检测——若 Range 实现了比例分裂构造函数就把proportional_split原样传给分裂构造函数否则退化为splittemplate typename Range, typename void struct range_split_object_provider { template typename PartitionerSplitType static split get( PartitionerSplitType ) { return split(); } }; template typename Range struct range_split_object_providerRange, typename std::enable_ifstd::is_constructibleRange, Range, proportional_split::value::type { template typename PartitionerSplitType static PartitionerSplitType get( PartitionerSplitType split_obj ) { return split_obj; } };此外detail/_range_common.h 在 C20 环境下还给出了形式化的 concept 定义可视为对规范表格的可编译版本template typename T concept splittable std::constructible_fromT, T, tbb::detail::split; template typename Range concept tbb_range std::copy_constructibleRange splittableRange requires( const std::remove_reference_tRange range ) { { range.empty() } - relaxed_convertible_tobool; { range.is_divisible() } - relaxed_convertible_tobool; };官方 Range 家族从一维到 N 维规范在 See also 中列出了 TBB 提供的标准 Range 类型它们全部满足上述要求是学习自定义 Range 的最佳参照物blocked_range一维半开区间[begin, end)带 grainsizesize() end() - begin()is_divisible()即size() grainsize()blocked_range2d / blocked_range3d二维/三维迭代空间行与列可有不同的 Value 类型和 grainsizeblocked_nd_rangeN 维推广templatetypename Value, unsigned int N所有维度必须是同一 Value 类型并附带丰富的推导指引deduction guides。多维 Range 的分裂策略值得单独一提。以 blocked_range2d.h 为例它的do_split并不固定切行或切列而是比较两个维度的大小 / grainsize比值优先切分更稀疏比值更大的那个维度if ( my_rows.size()*double(my_cols.grainsize()) my_cols.size()*double(my_rows.grainsize()) ) { my_cols.my_begin col_range_type::do_split(r.my_cols, split_obj); } else { my_rows.my_begin row_range_type::do_split(r.my_rows, split_obj); }blocked_nd_range_cls.rst 中的规范说明同样建议沿 size-to-grainsize 比值最大的维度切分使得反复切分后子块趋向近正方形/立方体从而改善缓存局部性。这是多维 Range 相对一维 Range 最重要的行为差异。使用示例从规范文档直接可用的代码blocked_range_cls.rst 给出了可直接验证的语义示例均与 blocked_range.h 的实现一一对应blocked_rangeint r(5, 14, 2); // 表示 [5, 14)含 5..13grainsize 2 // r.begin() 5, r.end() 14 blocked_rangeint s(r, split); // 基本分裂后 // r 表示 [5, 9)s 表示 [9, 14)grainsize 均为 2 blocked_rangeint t(r, proportional_split(2, 3)); // 比例分裂后 // r 表示 [5, 52*(9-5)/5)t 表示 [52*(9-5)/5, 9)规范还特别解释了const_iterator这个命名它不一定是真正的 STL 迭代器只需满足 BlockedRangeValue 要求但命名为const_iterator后若 Value 恰好是迭代器类型blocked_range就能像只读 STL 容器一样使用。调度器如何消费 Range以 parallel_for 为例Range 不是孤立存在的它的价值在于被算法模板消费。在 parallel_for.h 中start_for任务类型的分裂构造函数直接调用了 Range 的分裂构造函数// third-party/tbb/include/oneapi/tbb/parallel_for.h L82-L87 start_for( start_for parent_, typename Partitioner::split_type split_obj, small_object_allocator alloc ) : my_range(parent_.my_range, get_range_split_objectRange(split_obj)), my_body(parent_.my_body), my_parent(nullptr), my_partition(parent_.my_partition, split_obj), my_allocator(alloc) {}这里my_range(parent_.my_range, get_range_split_objectRange(split_obj))就是整个并行模型的心脏调度器把一个start_for任务分裂成两个子任务时同时用split/proportional_splittag 调用 Range 的分裂构造函数把区间切成左右两半。get_range_split_objectRange正是前文提到的比例分裂降级检测函数。换句话说Range 概念的全部要求可拷贝、可判空、可判可分、可分裂都是为这条调用链服务的。parallel_reduce、parallel_scan的start_reduce/start_scan任务内部采用同样的模式。mold 中的真实调用mold 链接器把 TBB 作为内建并行运行时在 src/passes.cc 中几乎每个对全部目标文件/输出段做一遍处理的 pass 都用了tbb::parallel_for_each或tbb::parallel_for。例如符号表扫描、段成员收集、ctx.chunks的逐块处理等都以ctx.objs、ctx.merged_sections、ctx.osec_pool、ctx.chunks等容器为 Range 来源。这些调用的背后正是本文介绍的 split 语义在支撑一个大任务被递归切成几百个小任务、分发给所有工作线程的执行模型——链接一个大型 C 程序时动辄上百万次重定位的并行计算都依赖这一层 Range 抽象保持正确、均衡且可预测。动手实现一个自定义 Range综合规范表格与源码实现一个满足 Range 要求的类型只需五个成员外加可选的第六个。最小可用模板如下#include oneapi/tbb/blocked_range.h template typename T class my_range { T my_begin, my_end; std::size_t my_grainsize; public: // 1. 显式提供构造函数Range 声明了分裂/复制构造默认构造不会自动生成 my_range(T begin, T end, std::size_t grainsize 1) : my_begin(begin), my_end(end), my_grainsize(grainsize) {} // 2. 复制构造 析构可省略声明编译器默认生成即可 // 3. 判空 bool empty() const { return !(my_begin my_end); } // 4. 判可分大小超过 grainsize bool is_divisible() const { return my_grainsize size(); } // 5. 基本分裂构造新对象为后半段r 更新为前半段 my_range(my_range r, tbb::split) : my_begin(r.my_begin (r.my_end - r.my_begin) / 2), my_end(r.my_end), my_grainsize(r.my_grainsize) { r.my_end my_begin; } // 6.可选比例分裂构造按 left:right 切分 my_range(my_range r, tbb::proportional_split proportion) : my_begin(r.my_begin (r.my_end - r.my_begin) * proportion.left() / (proportion.left() proportion.right())), my_end(r.my_end), my_grainsize(r.my_grainsize) { r.my_end my_begin; } std::size_t size() const { return std::size_t(my_end - my_begin); } T begin() const { return my_begin; } T end() const { return my_end; } };实现时请对照规范逐条自检分裂构造函数参数必须是R且修改原对象新对象代表后半段方向约定保证顺序遍历递增必须显式定义默认构造函数或可用构造否则无法实例化规范明确要求empty()/is_divisible()必须是 const 成员建议提供 grainsize 之类的分裂度控制否则任务可能被切到过细调度开销反而拖慢整体性能若实现了比例分裂构造函数调度器会自动用proportional_split调用它detail/_range_common.h 的 SFINAE 检测保证不实现也不会编译失败只是退化为均分。写完的类型即可直接传给tbb::parallel_for(my_rangeT(...), body)或tbb::parallel_reduce由调度器自动完成递归分裂 → 工作窃取 → 子块执行的完整流程。小结Range 是 TBB 并行算法与用户数据之间唯一的契约一个可拷贝、可判空、可判可分、可递归二分可选项按比例二分的轻量描述对象。它通过split/proportional_split两个 tag 与复制构造函数区分开通过 grainsize 之类的参数控制分裂粒度并通过新对象为后半段的方向约定保证顺序执行时的遍历次序与普通循环一致。理解这份规范range.rst再对照 blocked_range.h 与 parallel_for.h 的源码就能既写出正确的自定义 Range也看懂 mold 这类大型程序如何借 TBB 的分治模型榨干多核性能。延伸阅读仓库内文档blocked_range 类规范blocked_nd_range 类规范split 类规范proportional_split 类规范mold 并行 pass 实现【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
