尧图网页设计 
mold 中的 TBB Splittable 概念拆分构造函数与并行任务划分原理详解【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldmold 是一个采用多线程并行设计的高速链接器其链接流程大量依赖 TBBoneAPI Threading Building Blocks的并行算法如parallel_for、parallel_for_each、parallel_reduce来并行处理对象文件与输入节。所有并行循环之所以能够把工作递归划分到多核上执行底层都依赖一个核心概念——Splittable可拆分。本篇文章以 TBB 官方规范文档 Splittable 命名需求 为骨架结合本仓库third-party/tbb中的真实源码系统讲解 Splittable 的语义、split/proportional_split两个标签类型、blocked_range的拆分实现以及在 mold 链接器中的实际应用场景帮助读者理解并行算法如何将一个 Range变成可被多核并发处理的许多子任务。一、什么是 Splittable在 TBB 的并行算法体系里工作不是以裸循环的形式交给线程池的而是被包装成Range范围对象。并行算法如parallel_for、parallel_reduce、parallel_scan拿到一个 Range 后会把它递归地一分为二、二分为四最终将大量小子任务分发给各个工作线程。这个把一个实例拆成两半的能力就是 Splittable 要描述的语义。规范文档 splittable.rst 给出了精确定义一个类型是 splittable 的如果它拥有一个splitting constructor拆分构造函数允许把一个实例拆成两个部分。关键点在于这个构造函数的形式它接收两个参数——对原对象的引用以及一个库定义的哑类型dummy typesplit的实参。这个哑参的作用是让编译器能够区分拆分构造与拷贝构造两者都接收一个同类对象的引用但签名不同重载决议由此分流。构造函数执行完毕后x被引用的原对象和新建的对象共同代表原x被拆开后的两个部分。规范文档明确指出库在两种语境下使用拆分构造函数Partitioning把一个 Range 划分成两个可以并发处理的子 RangeForking把一个 body函数对象复制成两份可以并发运行的 body例如parallel_reduce中的归并体。二、Splittable 需求的形式化定义规范文档以伪签名形式给出了 Splittable 唯一一条硬性需求X::X(X x, split)语义把x拆分成x与新建对象两部分。这里的要点是第一个参数是非 const 左值引用X——拆分是原地修改原对象的拆分后原对象代表前一半新对象代表后一半第二个参数split是库定义的空标签类型见 split_cls.rst。它本身不含任何数据纯粹用于触发重载因为拆分构造函数与拷贝构造函数参数个数相同一个X引用的变体split参数的存在避免了二者混淆。在 C20 环境下TBB 直接把这个需求编码成了一个 concept。在 _range_common.h 中有template typename T concept splittable std::constructible_fromT, T, tbb::detail::split;即只要T可以从T和tbb::detail::split构造出来就认为它满足 splittable。这个 concept 又被组合进tbb_range第 97-103 行与empty()、is_divisible()一起构成 TBB 对 Range 类型的完整约束。三、split 与 proportional_split两个拆分标签3.1 split基本的拆分标签split是库提供的空类型定义在 _range_common.h//! Dummy type that distinguishes splitting constructor from copy constructor. class split {};规范文档 split_cls.rst 说明它定义于oneapi/tbb/blocked_range.h、oneapi/tbb/blocked_range2d.h、oneapi/tbb/blocked_range3d.h、oneapi/tbb/blocked_nd_range.h、oneapi/tbb/partitioner.h、oneapi/tbb/parallel_for.h、oneapi/tbb/parallel_reduce.h、oneapi/tbb/parallel_scan.h等多个头文件中实际均转发自公共内部头文件并在公开命名空间以using暴露// blocked_range.h 末尾 inline namespace v1 { using detail::d1::blocked_range; // Split types using detail::split; using detail::proportional_split; } // namespace v13.2 proportional_split按比例拆分的标签对于满足 Range 需求的类型规范还允许可选地提供一个proportional splitting constructor比例拆分构造函数其区分参数类型为proportional_split。文档 proportional_split_cls.rst 给出了完整的类接口namespace oneapi { namespace tbb { class proportional_split { public: proportional_split(std::size_t _left 1, std::size_t _right 1); std::size_t left() const; std::size_t right() const; explicit operator split() const; }; } }各成员的含义proportional_split(_left, _right)以系数_left与_right构造一个比例默认(1, 1)即对半left()返回比例中左部分的系数right()返回比例中右部分的系数explicit operator split()把proportional_split显式转换为split供不支持比例拆分的 Range 使用——当 partitioner 想按比例拆分、而 Range 只实现了基本拆分构造函数时TBB 就通过这个转换退化到普通拆分。proportional_split的实际实现位于 _range_common.h并继承自no_assign禁止赋值内部保存my_left、my_right两个size_t。关键机制TBB 用 SFINAE 特性探测一个 Range 是否实现了比例拆分构造函数见 _range_common.htemplate 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; } };若Range可用(Range, proportional_split)构造则原样传递proportional_split启用比例拆分否则退化为返回split走基本拆分路径。这一探测在并行算法内部通过get_range_split_object第 70-74 行调用正是partitioners 向 Range 传递拆分比例这一机制代码注释原话Type enables transmission of splitting proportion from partitioners to range objects的落地实现。四、经典实现blocked_range 的拆分blocked_range是本仓库 TBB 中最典型的 Splittable 类型也是 mold 链接器实际使用的类型。它在 blocked_range.h 中实现了两个拆分构造函数//! Split range. blocked_range( blocked_range r, split ) : my_end(r.my_end), my_begin(do_split(r, split())), my_grainsize(r.my_grainsize) { } //! Split range. blocked_range( blocked_range r, proportional_split proportion ) : my_end(r.my_end), my_begin(do_split(r, proportion)), my_grainsize(r.my_grainsize) { }注意源码中的一条重要注释第 112 行my_end必须在my_begin之前声明否则拆分构造函数会出错——因为do_split会修改r.my_end而my_end的初始化表达式依赖r.my_end声明顺序决定了初始化求值顺序。4.1 基本拆分取中点基本拆分的核心逻辑在私有静态函数do_split(blocked_range, split)第 118-124 行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; return middle; }它的效果是设原范围[i, j)则新对象代表[i(j-i)/2, j)后半段原对象被更新为[i, i(j-i)/2)前半段。这正是规范文档在 Range 需求中提到的约定——新建对象构造原范围的第二部分原对象更新为第一部分从而保证parallel_for、parallel_reduce、parallel_scan在顺序执行时按递增方向遍历范围行为与普通顺序循环一致见 range.rst 的说明。4.2 比例拆分按系数划分比例拆分的实现第 126-139 行用浮点运算计算右半部分大小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);即右部分 ≈size * right / (left right)四舍五入到整数。源码注释第 130-135 行诚实指出了精度限制32 位浮点算术无法精确处理超过2^24次迭代的范围但对2^64量级的范围计算误差约为0.000001%对均匀分布影响很小若需要精确拆分算法可参考test_partitioner_whitebox测试。规范文档 blocked_range_cls.rst 给出了一个直观示例blocked_rangeint r(5, 14, 2); // [5, 14)grainsize2 blocked_rangeint s(r, proportional_split(2, 3));执行后r表示[5, 52*9/5)即[5, 8)s表示[8, 14)二者比例约为2:3且 grainsize 均保持为 2。4.3 可拆分性的判据grainsizeblocked_range的is_divisible()第 85 行定义了何时可以继续拆bool is_divisible() const { return my_grainsizesize(); }即只有范围大小size() grainsize时才允许继续拆分。grainsize是构造时指定的视为不可再分的最小工作单元blocked_range.h 要求必须为正调试版本会断言。理想情况下Range 应一直递归拆分到串行执行比继续拆分更高效的程度而具体阈值取决于上层上下文所以blocked_range把控制权通过 grainsize 暴露给用户range.rst 中明确提到这一点。五、如何编写一个满足 Splittable 的自定义 RangeTBB 规范文档在examples目录下给出了一个最小可编译示例 range_concept.h完整演示了一个自定义 Range 需要具备的全部要素#include oneapi/tbb/tbb_stddef.h // for split tags struct TrivialNaturalRange { // restore the default constructor TrivialNaturalRange() {} size_t lower; size_t upper; bool empty() const { return lower upper; } bool is_divisible() const { return upper lower 1; } // basic splitting constructor TrivialNaturalRange(TrivialNaturalRange r, oneapi::tbb::split) { size_t m r.lower (r.upper - r.lower) / 2; upper r.upper; r.upper lower m; } // optional proportional splitting constructor TrivialNaturalRange(TrivialNaturalRange r, oneapi::tbb::proportional_split p) { size_t m r.lower ((r.upper - r.lower) * p.left()) / (p.left() p.right()); if (m r.lower) m; else if (m r.upper) m--; upper r.upper; r.upper lower m; } // optional trait that enables proportional split static const bool is_splittable_in_proportion true; };对照这个示例可以提炼出编写自定义 Splittable Range 的完整清单恢复默认构造函数因为声明了拷贝构造函数和拆分构造函数编译器不再自动生成默认构造函数必须显式定义规范文档 range.rst 特别强调了这一点实现empty()与is_divisible()两个 const 查询函数实现基本拆分构造函数X(X r, split)——取中点拆分为前后两半新对象为后半原对象更新为前半可选实现比例拆分构造函数X(X r, proportional_split p)——按p.left() : p.right()的比例拆分并对中点做边界修正防止m lower或m upper导致空切片可选定义is_splittable_in_proportion true特征常量启用比例拆分路径。主函数 range_concept.cpp 演示了它的基本用法构造TrivialNaturalRange r设置upper1, lower0然后调用r.empty()。六、Splittable 在 mold 链接器中的实际应用Splittable 概念不是纸面规范——mold 的并行链接流程正是通过tbb::blocked_range与tbb::parallel_for/parallel_for_each/parallel_reduce的组合来驱动。搜索src/目录可以发现大量直接调用gc-sections.cc垃圾回收阶段用tbb::parallel_for_each(ctx.objs, ...)并行遍历所有对象文件扫描引用关系icf.ccICFIdentical Code Folding相同代码折叠阶段用tbb::parallel_for((i64)0, (i64)ctx.objs.size(), ...)并行处理对象文件与节哈希arch-arm32.ccARM32 架构的松弛relaxation与重定位阶段用tbb::parallel_for/parallel_for_each并行处理条目gdb-index.ccGDB 索引生成阶段使用tbb::blocked_rangei64构造 Range 并配合tbb::parallel_reducescan函数对象带一个累加状态PoolSize做并行归约扫描。其中 gdb-index.cc 的用法最能体现本文主题——它显式创建了tbb::blocked_rangei64(0, data.entries.size())这正是构造一个 Range → 并行算法递归拆分Splittable→ 分发给工作线程的完整链条auto scan - PoolSize { // 对 range 内的条目做归约扫描 }; tbb::parallel_reduce( tbb::blocked_rangei64(0, data.entries.size()), PoolSize{}, scan, /* join */);工作过程如下parallel_reduce拿到blocked_rangei64(0, N)后若N grainsize则调用拆分构造函数递归切分每次调用blocked_range(blocked_range, split)取中点直到子范围不可再分为止每个工作线程通过工作窃取work stealing拿到子范围后执行scan回调最后各线程的部分结果通过 join 归并。整个过程完全建立在 Splittable 需求之上——blocked_range正是因为满足X::X(X, split)这一条需求才能被 TBB 的并行算法所接受。七、与 Partitioners 的协作拆分过程由库的partitioner划分器驱动。规范文档 auto_partitioner.rst 描述了默认auto_partitioner的行为初始只把范围拆成约S个子范围S与global_control或task_arena指定的线程数成正比每个子范围只有在被空闲线程窃取时才进一步拆分因此auto_partitioner只做足以均衡负载的拆分而不一定拆分到Range::is_divisible()允许的最细粒度使用auto_partitioner时 body 收到的子范围可能大于 grainsize不能假设 grainsize 是上界需要上界保证时应改用simple_partitioner。这也解释了 Splittable 需求设计上的精妙之处Range 负责声明我能怎么拆拆分构造函数 is_divisiblePartitioner 负责决定实际怎么拆、拆多少二者通过split/proportional_split标签解耦。八、小结与自检清单回顾本篇文章的核心内容Splittable 的本质一个类型拥有X::X(X, split)形式的拆分构造函数即可把一个实例原地拆成前后两个部分splittable.rst两个标签类型split空类型区分拆分/拷贝构造与proportional_split携带left()/right()比例系数可显式转换回split实现降级定义见 _range_common.h典型实现blocked_range通过取中点实现基本拆分、通过浮点比例计算实现比例拆分并以grainsize控制可拆分性blocked_range.h自定义方法显式恢复默认构造函数、实现empty()/is_divisible()/拆分构造函数参考 range_concept.hmold 中的应用parallel_for/parallel_reduce配合tbb::blocked_rangei64在 gc-sections、icf、gdb-index、arch-arm32 等模块中并行处理见 gdb-index.cc。如果要在自己的代码里使用 TBB 并行算法并让它们正确高效地工作请对照这份清单检查你的 Range 类型是否显式恢复了默认构造函数empty()/is_divisible()是否语义正确is_divisible返回 true 时empty()必须为 false基本拆分构造函数是否满足新对象为后半、原对象为前半的约定以保持顺序遍历方向拆分后两个子范围是否恰好覆盖原范围、无重叠无遗漏是否需要比例拆分如果需要是否实现了X(X, proportional_split)并处理了边界取整问题【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 mold 中的 TBB Splittable 概念：拆分构造函数与并行任务划分原理详解
mold 中的 TBB Splittable 概念拆分构造函数与并行任务划分原理详解【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldmold 是一个采用多线程并行设计的高速链接器其链接流程大量依赖 TBBoneAPI Threading Building Blocks的并行算法如parallel_for、parallel_for_each、parallel_reduce来并行处理对象文件与输入节。所有并行循环之所以能够把工作递归划分到多核上执行底层都依赖一个核心概念——Splittable可拆分。本篇文章以 TBB 官方规范文档 Splittable 命名需求 为骨架结合本仓库third-party/tbb中的真实源码系统讲解 Splittable 的语义、split/proportional_split两个标签类型、blocked_range的拆分实现以及在 mold 链接器中的实际应用场景帮助读者理解并行算法如何将一个 Range变成可被多核并发处理的许多子任务。一、什么是 Splittable在 TBB 的并行算法体系里工作不是以裸循环的形式交给线程池的而是被包装成Range范围对象。并行算法如parallel_for、parallel_reduce、parallel_scan拿到一个 Range 后会把它递归地一分为二、二分为四最终将大量小子任务分发给各个工作线程。这个把一个实例拆成两半的能力就是 Splittable 要描述的语义。规范文档 splittable.rst 给出了精确定义一个类型是 splittable 的如果它拥有一个splitting constructor拆分构造函数允许把一个实例拆成两个部分。关键点在于这个构造函数的形式它接收两个参数——对原对象的引用以及一个库定义的哑类型dummy typesplit的实参。这个哑参的作用是让编译器能够区分拆分构造与拷贝构造两者都接收一个同类对象的引用但签名不同重载决议由此分流。构造函数执行完毕后x被引用的原对象和新建的对象共同代表原x被拆开后的两个部分。规范文档明确指出库在两种语境下使用拆分构造函数Partitioning把一个 Range 划分成两个可以并发处理的子 RangeForking把一个 body函数对象复制成两份可以并发运行的 body例如parallel_reduce中的归并体。二、Splittable 需求的形式化定义规范文档以伪签名形式给出了 Splittable 唯一一条硬性需求X::X(X x, split)语义把x拆分成x与新建对象两部分。这里的要点是第一个参数是非 const 左值引用X——拆分是原地修改原对象的拆分后原对象代表前一半新对象代表后一半第二个参数split是库定义的空标签类型见 split_cls.rst。它本身不含任何数据纯粹用于触发重载因为拆分构造函数与拷贝构造函数参数个数相同一个X引用的变体split参数的存在避免了二者混淆。在 C20 环境下TBB 直接把这个需求编码成了一个 concept。在 _range_common.h 中有template typename T concept splittable std::constructible_fromT, T, tbb::detail::split;即只要T可以从T和tbb::detail::split构造出来就认为它满足 splittable。这个 concept 又被组合进tbb_range第 97-103 行与empty()、is_divisible()一起构成 TBB 对 Range 类型的完整约束。三、split 与 proportional_split两个拆分标签3.1 split基本的拆分标签split是库提供的空类型定义在 _range_common.h//! Dummy type that distinguishes splitting constructor from copy constructor. class split {};规范文档 split_cls.rst 说明它定义于oneapi/tbb/blocked_range.h、oneapi/tbb/blocked_range2d.h、oneapi/tbb/blocked_range3d.h、oneapi/tbb/blocked_nd_range.h、oneapi/tbb/partitioner.h、oneapi/tbb/parallel_for.h、oneapi/tbb/parallel_reduce.h、oneapi/tbb/parallel_scan.h等多个头文件中实际均转发自公共内部头文件并在公开命名空间以using暴露// blocked_range.h 末尾 inline namespace v1 { using detail::d1::blocked_range; // Split types using detail::split; using detail::proportional_split; } // namespace v13.2 proportional_split按比例拆分的标签对于满足 Range 需求的类型规范还允许可选地提供一个proportional splitting constructor比例拆分构造函数其区分参数类型为proportional_split。文档 proportional_split_cls.rst 给出了完整的类接口namespace oneapi { namespace tbb { class proportional_split { public: proportional_split(std::size_t _left 1, std::size_t _right 1); std::size_t left() const; std::size_t right() const; explicit operator split() const; }; } }各成员的含义proportional_split(_left, _right)以系数_left与_right构造一个比例默认(1, 1)即对半left()返回比例中左部分的系数right()返回比例中右部分的系数explicit operator split()把proportional_split显式转换为split供不支持比例拆分的 Range 使用——当 partitioner 想按比例拆分、而 Range 只实现了基本拆分构造函数时TBB 就通过这个转换退化到普通拆分。proportional_split的实际实现位于 _range_common.h并继承自no_assign禁止赋值内部保存my_left、my_right两个size_t。关键机制TBB 用 SFINAE 特性探测一个 Range 是否实现了比例拆分构造函数见 _range_common.htemplate 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; } };若Range可用(Range, proportional_split)构造则原样传递proportional_split启用比例拆分否则退化为返回split走基本拆分路径。这一探测在并行算法内部通过get_range_split_object第 70-74 行调用正是partitioners 向 Range 传递拆分比例这一机制代码注释原话Type enables transmission of splitting proportion from partitioners to range objects的落地实现。四、经典实现blocked_range 的拆分blocked_range是本仓库 TBB 中最典型的 Splittable 类型也是 mold 链接器实际使用的类型。它在 blocked_range.h 中实现了两个拆分构造函数//! Split range. blocked_range( blocked_range r, split ) : my_end(r.my_end), my_begin(do_split(r, split())), my_grainsize(r.my_grainsize) { } //! Split range. blocked_range( blocked_range r, proportional_split proportion ) : my_end(r.my_end), my_begin(do_split(r, proportion)), my_grainsize(r.my_grainsize) { }注意源码中的一条重要注释第 112 行my_end必须在my_begin之前声明否则拆分构造函数会出错——因为do_split会修改r.my_end而my_end的初始化表达式依赖r.my_end声明顺序决定了初始化求值顺序。4.1 基本拆分取中点基本拆分的核心逻辑在私有静态函数do_split(blocked_range, split)第 118-124 行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; return middle; }它的效果是设原范围[i, j)则新对象代表[i(j-i)/2, j)后半段原对象被更新为[i, i(j-i)/2)前半段。这正是规范文档在 Range 需求中提到的约定——新建对象构造原范围的第二部分原对象更新为第一部分从而保证parallel_for、parallel_reduce、parallel_scan在顺序执行时按递增方向遍历范围行为与普通顺序循环一致见 range.rst 的说明。4.2 比例拆分按系数划分比例拆分的实现第 126-139 行用浮点运算计算右半部分大小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);即右部分 ≈size * right / (left right)四舍五入到整数。源码注释第 130-135 行诚实指出了精度限制32 位浮点算术无法精确处理超过2^24次迭代的范围但对2^64量级的范围计算误差约为0.000001%对均匀分布影响很小若需要精确拆分算法可参考test_partitioner_whitebox测试。规范文档 blocked_range_cls.rst 给出了一个直观示例blocked_rangeint r(5, 14, 2); // [5, 14)grainsize2 blocked_rangeint s(r, proportional_split(2, 3));执行后r表示[5, 52*9/5)即[5, 8)s表示[8, 14)二者比例约为2:3且 grainsize 均保持为 2。4.3 可拆分性的判据grainsizeblocked_range的is_divisible()第 85 行定义了何时可以继续拆bool is_divisible() const { return my_grainsizesize(); }即只有范围大小size() grainsize时才允许继续拆分。grainsize是构造时指定的视为不可再分的最小工作单元blocked_range.h 要求必须为正调试版本会断言。理想情况下Range 应一直递归拆分到串行执行比继续拆分更高效的程度而具体阈值取决于上层上下文所以blocked_range把控制权通过 grainsize 暴露给用户range.rst 中明确提到这一点。五、如何编写一个满足 Splittable 的自定义 RangeTBB 规范文档在examples目录下给出了一个最小可编译示例 range_concept.h完整演示了一个自定义 Range 需要具备的全部要素#include oneapi/tbb/tbb_stddef.h // for split tags struct TrivialNaturalRange { // restore the default constructor TrivialNaturalRange() {} size_t lower; size_t upper; bool empty() const { return lower upper; } bool is_divisible() const { return upper lower 1; } // basic splitting constructor TrivialNaturalRange(TrivialNaturalRange r, oneapi::tbb::split) { size_t m r.lower (r.upper - r.lower) / 2; upper r.upper; r.upper lower m; } // optional proportional splitting constructor TrivialNaturalRange(TrivialNaturalRange r, oneapi::tbb::proportional_split p) { size_t m r.lower ((r.upper - r.lower) * p.left()) / (p.left() p.right()); if (m r.lower) m; else if (m r.upper) m--; upper r.upper; r.upper lower m; } // optional trait that enables proportional split static const bool is_splittable_in_proportion true; };对照这个示例可以提炼出编写自定义 Splittable Range 的完整清单恢复默认构造函数因为声明了拷贝构造函数和拆分构造函数编译器不再自动生成默认构造函数必须显式定义规范文档 range.rst 特别强调了这一点实现empty()与is_divisible()两个 const 查询函数实现基本拆分构造函数X(X r, split)——取中点拆分为前后两半新对象为后半原对象更新为前半可选实现比例拆分构造函数X(X r, proportional_split p)——按p.left() : p.right()的比例拆分并对中点做边界修正防止m lower或m upper导致空切片可选定义is_splittable_in_proportion true特征常量启用比例拆分路径。主函数 range_concept.cpp 演示了它的基本用法构造TrivialNaturalRange r设置upper1, lower0然后调用r.empty()。六、Splittable 在 mold 链接器中的实际应用Splittable 概念不是纸面规范——mold 的并行链接流程正是通过tbb::blocked_range与tbb::parallel_for/parallel_for_each/parallel_reduce的组合来驱动。搜索src/目录可以发现大量直接调用gc-sections.cc垃圾回收阶段用tbb::parallel_for_each(ctx.objs, ...)并行遍历所有对象文件扫描引用关系icf.ccICFIdentical Code Folding相同代码折叠阶段用tbb::parallel_for((i64)0, (i64)ctx.objs.size(), ...)并行处理对象文件与节哈希arch-arm32.ccARM32 架构的松弛relaxation与重定位阶段用tbb::parallel_for/parallel_for_each并行处理条目gdb-index.ccGDB 索引生成阶段使用tbb::blocked_rangei64构造 Range 并配合tbb::parallel_reducescan函数对象带一个累加状态PoolSize做并行归约扫描。其中 gdb-index.cc 的用法最能体现本文主题——它显式创建了tbb::blocked_rangei64(0, data.entries.size())这正是构造一个 Range → 并行算法递归拆分Splittable→ 分发给工作线程的完整链条auto scan - PoolSize { // 对 range 内的条目做归约扫描 }; tbb::parallel_reduce( tbb::blocked_rangei64(0, data.entries.size()), PoolSize{}, scan, /* join */);工作过程如下parallel_reduce拿到blocked_rangei64(0, N)后若N grainsize则调用拆分构造函数递归切分每次调用blocked_range(blocked_range, split)取中点直到子范围不可再分为止每个工作线程通过工作窃取work stealing拿到子范围后执行scan回调最后各线程的部分结果通过 join 归并。整个过程完全建立在 Splittable 需求之上——blocked_range正是因为满足X::X(X, split)这一条需求才能被 TBB 的并行算法所接受。七、与 Partitioners 的协作拆分过程由库的partitioner划分器驱动。规范文档 auto_partitioner.rst 描述了默认auto_partitioner的行为初始只把范围拆成约S个子范围S与global_control或task_arena指定的线程数成正比每个子范围只有在被空闲线程窃取时才进一步拆分因此auto_partitioner只做足以均衡负载的拆分而不一定拆分到Range::is_divisible()允许的最细粒度使用auto_partitioner时 body 收到的子范围可能大于 grainsize不能假设 grainsize 是上界需要上界保证时应改用simple_partitioner。这也解释了 Splittable 需求设计上的精妙之处Range 负责声明我能怎么拆拆分构造函数 is_divisiblePartitioner 负责决定实际怎么拆、拆多少二者通过split/proportional_split标签解耦。八、小结与自检清单回顾本篇文章的核心内容Splittable 的本质一个类型拥有X::X(X, split)形式的拆分构造函数即可把一个实例原地拆成前后两个部分splittable.rst两个标签类型split空类型区分拆分/拷贝构造与proportional_split携带left()/right()比例系数可显式转换回split实现降级定义见 _range_common.h典型实现blocked_range通过取中点实现基本拆分、通过浮点比例计算实现比例拆分并以grainsize控制可拆分性blocked_range.h自定义方法显式恢复默认构造函数、实现empty()/is_divisible()/拆分构造函数参考 range_concept.hmold 中的应用parallel_for/parallel_reduce配合tbb::blocked_rangei64在 gc-sections、icf、gdb-index、arch-arm32 等模块中并行处理见 gdb-index.cc。如果要在自己的代码里使用 TBB 并行算法并让它们正确高效地工作请对照这份清单检查你的 Range 类型是否显式恢复了默认构造函数empty()/is_divisible()是否语义正确is_divisible返回 true 时empty()必须为 false基本拆分构造函数是否满足新对象为后半、原对象为前半的约定以保持顺序遍历方向拆分后两个子范围是否恰好覆盖原范围、无重叠无遗漏是否需要比例拆分如果需要是否实现了X(X, proportional_split)并处理了边界取整问题【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考