oneTBB split 类深度解析Range 分裂构造函数的标记机制与实现原理【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldsplit是 oneAPI Threading Building BlocksoneTBB中用于区分 Range 分裂构造函数与拷贝构造函数的标记类型是parallel_for、parallel_reduce、parallel_scan等并行算法能够递归划分工作区间的基础。本文基于 mold 仓库中内置的 oneTBB 第三方源码third-party/tbb与官方规范文档split_cls.rst、proportional_split_cls.rst、range.rst从规范、源码实现、构造函数重载三个维度完整讲解split的语义、使用方式与底层原理并附带自定义 Range 的实战示例帮助读者彻底理解 TBB 任务划分机制的第一块基石。split是什么一个用于区分构造函数的标记类型在 oneTBB 中Range是一个可以递归细分为两个部分的概念concept。细分通过调用 Range 的分裂构造函数splitting constructor完成而split类型正是这个构造函数的参数标记类型为split的参数用于将分裂构造函数与拷贝构造函数区分开。为什么需要这样一个标记原因在于分裂构造函数与拷贝构造函数在语法上有着天然冲突分裂构造函数的形式是R::R( R r, split )其第一个参数是非 const 左值引用R且会修改传入的r将其收缩为前半部分而拷贝构造函数是R::R( const R )。如果不引入一个独立的标记类型编译器无法可靠地区分拷贝一个 range与把一个 range 劈成两半这两种语义。split就是一个空类empty class它不携带任何数据纯粹作为重载决议的标签存在。在规范文档split_cls.rst中split的定义极为精简其完整的规范描述如下// Defined in header oneapi/tbb/blocked_range.h // Defined in header oneapi/tbb/blocked_range2d.h // Defined in header oneapi/tbb/blocked_range3d.h // Defined in header oneapi/tbb/blocked_nd_range.h // Defined in header oneapi/tbb/partitioner.h // Defined in header oneapi/tbb/parallel_for.h // Defined in header oneapi/tbb/parallel_reduce.h // Defined in header oneapi/tbb/parallel_scan.h class split;需要注意的是规范文档给出的头文件列表覆盖了所有常用的 Range 类型一维到 N 维的blocked_range系列与并行算法parallel_for、parallel_reduce、parallel_scan以及partitioner.h。在实际代码中split的真实定义位于 _range_common.h并经由 blocked_range.h 等公开头文件注入到tbb命名空间// third-party/tbb/include/oneapi/tbb/detail/_range_common.h namespace tbb { namespace detail { inline namespace d0 { //! Dummy type that distinguishes splitting constructor from copy constructor. class split {}; } // namespace d0 } // namespace detail } // namespace tbb源码注释直白地称其为Dummy type哑类型它的全部作用就是让编译器在重载决议时能明确分辨分裂与拷贝两种意图。在 blocked_range.h 的末尾通过using detail::split;与using detail::proportional_split;将这两个类型提升到公开命名空间用户代码因此可以直接写tbb::split()或oneapi::tbb::split()。两种分裂构造函数基本分裂与比例分裂要理解split的用途必须先理解 oneTBB 的 Range 需求Range requirements。根据 range.rst一个满足Range概念的类型R需要提供两类分裂构造函数构造函数形式说明基本分裂构造函数必需R::R( R r, split )将r分成两个子区间规范推荐尽量均分但并非强制要求均分通常能带来最佳并行度比例分裂构造函数可选R::R( R r, proportional_split proportion )按给定的比例拆分r最优实践是遵循比例并在必要时四舍五入到最近整数一个完整满足Range概念的类型还需要提供拷贝构造函数R::R( const R )、析构函数R::~R()、bool R::empty() const区间为空返回 true以及bool R::is_divisible() const区间可继续拆分返回 true。规范特别强调理想情况下Range 应被递归拆分到串行执行比继续拆分更高效的程度blocked_range通过grainsize参数控制最小不可拆分的区间大小。如果值集合有方向感按约定分裂构造函数应构造后半部分同时将其参数更新为前半部分。这保证了parallel_for、parallel_reduce、parallel_scan在顺序执行模式下从左到右处理区间与普通顺序循环的行为一致。由于 Range 同时声明了分裂构造函数与拷贝构造函数其默认构造函数不会被自动生成——程序中若要直接创建 Range 实例必须显式定义默认构造函数或其他构造函数。从源码结构看blocked_range正是这一约定的典型实现。在 blocked_range.h 中基本分裂构造函数与新生成的区间之间的关系清晰可见// 新 Range *this 持有后半部分原 range r 被更新为前半部分 blocked_range( blocked_range r, split ) : my_end(r.my_end), my_begin(do_split(r, split())), my_grainsize(r.my_grainsize) { __TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly ); } // 辅助函数精确均分 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; }这里do_split使用begin (end - begin) / 2计算中点将原区间的my_end收缩到中点作为前半部分新对象则以中点为起点、原终点为终点从而得到后半部分。构造函数体内的__TBB_ASSERT是 oneTBB 内置的调试期断言用于校验分裂结果的正确性。实战用法在自定义 Range 中实现分裂构造函数理解了split的语义后最直接的实战场景是编写满足Range概念的自定义类型。oneTBB 自带的测试代码提供了可复用的范本。例如 test_partitioner.h 中的自定义区间通过split标记将分裂构造函数委托给基类class custom_range { public: // 基本分裂构造函数以 split 标记与拷贝构造函数区分 custom_range(custom_range r, tbb::split) : base_type(r, tbb::split()) {} // 同时支持比例分裂 custom_range_with_psplit(custom_range_with_psplit r, tbb::split) : base_type(r, tbb::split()) {} };而在正式的符合性测试中split的直接使用方式如下conformance_blocked_range.cpponeapi::tbb::blocked_rangeAbstractValueType r2(r, oneapi::tbb::split());其效果等价于把r劈成两半r留下前半部分r2拿走后半部分。同样的用法也出现在blocked_range2d、blocked_range3d、blocked_nd_range的符合性测试中conformance_blocked_range2d.cpp、conformance_blocked_range3d.cpp、conformance_blocked_nd_range.cpp说明split在所有维度的 Range 类型上具有一致的语义。如果你要编写自己的 Range 类型需要遵守以下要点必须提供R::R( R r, split )形式的分裂构造函数这是 Range 概念的必需项分裂构造函数应把参数r更新为前半部分*this作为后半部分实现内部应先断言r.is_divisible()避免对不可分区间进行分裂由于存在分裂构造函数默认构造函数不会自动生成需要显式声明。proportional_split按比例分裂的扩展标记与split配套的还有proportional_split类型规范见 proportional_split_cls.rst它允许 Range 按指定比例而非均分方式拆分。该类型在 _range_common.h 中的实现如下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; } // 当 range 不支持比例分裂时转换为 split 类型使用 explicit operator split() const { return split(); } private: size_t my_left, my_right; };其公开接口包括成员函数语义proportional_split(std::size_t _left 1, std::size_t _right 1)以_left、_right两个系数构造一个比例默认 1:1std::size_t left() const返回比例的左侧系数std::size_t right() const返回比例的右侧系数explicit operator split() const将proportional_split显式转换为split供不支持比例分裂的 Range 使用proportional_split与split的分工体现在blocked_range的重载实现中blocked_range.hblocked_range( blocked_range r, proportional_split proportion ) : my_end(r.my_end), my_begin(do_split(r, proportion)), my_grainsize(r.my_grainsize) { __TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly ); } static Value do_split( blocked_range r, proportional_split proportion ) { __TBB_ASSERT( r.is_divisible(), cannot split blocked_range that is not divisible ); // 使用 32 位浮点运算计算右半部分大小并按四舍五入取整 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); }从源码结构看这里的比例计算使用浮点运算并加 0.5 取整。源码注释也明确指出对超过 2^24 次迭代的区间32 位浮点运算的误差约为 0.000001%对均匀分布的影响极小如需精确分裂可以参考test_partitioner_whitebox测试中的精确算法实现。底层机制partitioner 如何把 split 传给 Rangesplit与proportional_split除了在用户自定义 Range 时直接使用外还是 partitioner分区器向 Range 传递分裂意图的内部通道。在 _range_common.h 中可以看到这套机制template 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; } }; template typename Range, typename PartitionerSplitType auto get_range_split_object( PartitionerSplitType split_obj ) - decltype(range_split_object_providerRange::get(split_obj)) { return range_split_object_providerRange::get(split_obj); }这是一个基于 SFINAE 的特征分派tag dispatch当Range支持比例分裂即可用Range和proportional_split构造时get直接返回 partitioner 传入的分裂对象原样当Range不支持比例分裂时get退化为返回一个普通的split()对象从而让这类 Range 自动降级为基本均分分裂。借助proportional_split的explicit operator split()转换运算符两种分裂方式可以在 partitioner 的统一调度下无缝衔接而split本身始终保持其零开销标记的角色——它不携带任何运行时状态只在编译期决定重载决议的结果。C20 约束splittable 与 tbb_range 概念在支持 C20 concepts 的构建环境下oneTBB 还在 _range_common.h 中定义了与split直接相关的概念约束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; };其中splittable概念的判定标准正是能否以T与tbb::detail::split为参数构造该类型这与 split_cls.rst 中split用于区分分裂构造函数与拷贝构造函数的规范描述完全一致。也就是说一个类型是否是合法的 Range在编译期即可通过splittable与tbb_range两个概念得到静态验证split这个空类由此成为了 TBB 并行框架类型约束体系中最基础的一块基石。总结split的设计要点与使用清单围绕split类可以从规范与源码中提炼出以下关键事实split是一个空类dummy type定义于 _range_common.h通过blocked_range.h等公开头文件暴露给用户跨多个维度的 Range 类型与并行算法头文件可见。它的唯一职责是重载标记让R::R( R r, split )这种分裂构造函数在重载决议中与拷贝构造函数、默认构造函数明确区分从而在语法层面杜绝拷贝与分裂的歧义。它是 Range 概念的必需接口任何一个满足tbb_range/Range需求的类型都必须提供以split为第二参数的分裂构造函数且按约定将参数更新为前半部分、自身成为后半部分。它与proportional_split协作proportional_split提供left()、right()比例系数与到split的显式转换不支持比例分裂的 Range 会在get_range_split_object的分派下自动退回基本分裂。编写自定义 Range 时记得显式提供默认构造函数、empty()、is_divisible()并在分裂构造函数内先断言is_divisible()再按均分或给定比例切分。mold 链接器将其作为第三方组件随仓库携带位于 third-party/tbb因此阅读本文时可以直接在仓库内查阅 blocked_range.h 与 _range_common.h 的完整实现以及 conformance_blocked_range.cpp 等测试用例结合实际代码加深对 TBB 递归任务划分机制的理解。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 oneTBB split 类深度解析：Range 分裂构造函数的标记机制与实现原理
oneTBB split 类深度解析Range 分裂构造函数的标记机制与实现原理【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/moldsplit是 oneAPI Threading Building BlocksoneTBB中用于区分 Range 分裂构造函数与拷贝构造函数的标记类型是parallel_for、parallel_reduce、parallel_scan等并行算法能够递归划分工作区间的基础。本文基于 mold 仓库中内置的 oneTBB 第三方源码third-party/tbb与官方规范文档split_cls.rst、proportional_split_cls.rst、range.rst从规范、源码实现、构造函数重载三个维度完整讲解split的语义、使用方式与底层原理并附带自定义 Range 的实战示例帮助读者彻底理解 TBB 任务划分机制的第一块基石。split是什么一个用于区分构造函数的标记类型在 oneTBB 中Range是一个可以递归细分为两个部分的概念concept。细分通过调用 Range 的分裂构造函数splitting constructor完成而split类型正是这个构造函数的参数标记类型为split的参数用于将分裂构造函数与拷贝构造函数区分开。为什么需要这样一个标记原因在于分裂构造函数与拷贝构造函数在语法上有着天然冲突分裂构造函数的形式是R::R( R r, split )其第一个参数是非 const 左值引用R且会修改传入的r将其收缩为前半部分而拷贝构造函数是R::R( const R )。如果不引入一个独立的标记类型编译器无法可靠地区分拷贝一个 range与把一个 range 劈成两半这两种语义。split就是一个空类empty class它不携带任何数据纯粹作为重载决议的标签存在。在规范文档split_cls.rst中split的定义极为精简其完整的规范描述如下// Defined in header oneapi/tbb/blocked_range.h // Defined in header oneapi/tbb/blocked_range2d.h // Defined in header oneapi/tbb/blocked_range3d.h // Defined in header oneapi/tbb/blocked_nd_range.h // Defined in header oneapi/tbb/partitioner.h // Defined in header oneapi/tbb/parallel_for.h // Defined in header oneapi/tbb/parallel_reduce.h // Defined in header oneapi/tbb/parallel_scan.h class split;需要注意的是规范文档给出的头文件列表覆盖了所有常用的 Range 类型一维到 N 维的blocked_range系列与并行算法parallel_for、parallel_reduce、parallel_scan以及partitioner.h。在实际代码中split的真实定义位于 _range_common.h并经由 blocked_range.h 等公开头文件注入到tbb命名空间// third-party/tbb/include/oneapi/tbb/detail/_range_common.h namespace tbb { namespace detail { inline namespace d0 { //! Dummy type that distinguishes splitting constructor from copy constructor. class split {}; } // namespace d0 } // namespace detail } // namespace tbb源码注释直白地称其为Dummy type哑类型它的全部作用就是让编译器在重载决议时能明确分辨分裂与拷贝两种意图。在 blocked_range.h 的末尾通过using detail::split;与using detail::proportional_split;将这两个类型提升到公开命名空间用户代码因此可以直接写tbb::split()或oneapi::tbb::split()。两种分裂构造函数基本分裂与比例分裂要理解split的用途必须先理解 oneTBB 的 Range 需求Range requirements。根据 range.rst一个满足Range概念的类型R需要提供两类分裂构造函数构造函数形式说明基本分裂构造函数必需R::R( R r, split )将r分成两个子区间规范推荐尽量均分但并非强制要求均分通常能带来最佳并行度比例分裂构造函数可选R::R( R r, proportional_split proportion )按给定的比例拆分r最优实践是遵循比例并在必要时四舍五入到最近整数一个完整满足Range概念的类型还需要提供拷贝构造函数R::R( const R )、析构函数R::~R()、bool R::empty() const区间为空返回 true以及bool R::is_divisible() const区间可继续拆分返回 true。规范特别强调理想情况下Range 应被递归拆分到串行执行比继续拆分更高效的程度blocked_range通过grainsize参数控制最小不可拆分的区间大小。如果值集合有方向感按约定分裂构造函数应构造后半部分同时将其参数更新为前半部分。这保证了parallel_for、parallel_reduce、parallel_scan在顺序执行模式下从左到右处理区间与普通顺序循环的行为一致。由于 Range 同时声明了分裂构造函数与拷贝构造函数其默认构造函数不会被自动生成——程序中若要直接创建 Range 实例必须显式定义默认构造函数或其他构造函数。从源码结构看blocked_range正是这一约定的典型实现。在 blocked_range.h 中基本分裂构造函数与新生成的区间之间的关系清晰可见// 新 Range *this 持有后半部分原 range r 被更新为前半部分 blocked_range( blocked_range r, split ) : my_end(r.my_end), my_begin(do_split(r, split())), my_grainsize(r.my_grainsize) { __TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly ); } // 辅助函数精确均分 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; }这里do_split使用begin (end - begin) / 2计算中点将原区间的my_end收缩到中点作为前半部分新对象则以中点为起点、原终点为终点从而得到后半部分。构造函数体内的__TBB_ASSERT是 oneTBB 内置的调试期断言用于校验分裂结果的正确性。实战用法在自定义 Range 中实现分裂构造函数理解了split的语义后最直接的实战场景是编写满足Range概念的自定义类型。oneTBB 自带的测试代码提供了可复用的范本。例如 test_partitioner.h 中的自定义区间通过split标记将分裂构造函数委托给基类class custom_range { public: // 基本分裂构造函数以 split 标记与拷贝构造函数区分 custom_range(custom_range r, tbb::split) : base_type(r, tbb::split()) {} // 同时支持比例分裂 custom_range_with_psplit(custom_range_with_psplit r, tbb::split) : base_type(r, tbb::split()) {} };而在正式的符合性测试中split的直接使用方式如下conformance_blocked_range.cpponeapi::tbb::blocked_rangeAbstractValueType r2(r, oneapi::tbb::split());其效果等价于把r劈成两半r留下前半部分r2拿走后半部分。同样的用法也出现在blocked_range2d、blocked_range3d、blocked_nd_range的符合性测试中conformance_blocked_range2d.cpp、conformance_blocked_range3d.cpp、conformance_blocked_nd_range.cpp说明split在所有维度的 Range 类型上具有一致的语义。如果你要编写自己的 Range 类型需要遵守以下要点必须提供R::R( R r, split )形式的分裂构造函数这是 Range 概念的必需项分裂构造函数应把参数r更新为前半部分*this作为后半部分实现内部应先断言r.is_divisible()避免对不可分区间进行分裂由于存在分裂构造函数默认构造函数不会自动生成需要显式声明。proportional_split按比例分裂的扩展标记与split配套的还有proportional_split类型规范见 proportional_split_cls.rst它允许 Range 按指定比例而非均分方式拆分。该类型在 _range_common.h 中的实现如下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; } // 当 range 不支持比例分裂时转换为 split 类型使用 explicit operator split() const { return split(); } private: size_t my_left, my_right; };其公开接口包括成员函数语义proportional_split(std::size_t _left 1, std::size_t _right 1)以_left、_right两个系数构造一个比例默认 1:1std::size_t left() const返回比例的左侧系数std::size_t right() const返回比例的右侧系数explicit operator split() const将proportional_split显式转换为split供不支持比例分裂的 Range 使用proportional_split与split的分工体现在blocked_range的重载实现中blocked_range.hblocked_range( blocked_range r, proportional_split proportion ) : my_end(r.my_end), my_begin(do_split(r, proportion)), my_grainsize(r.my_grainsize) { __TBB_ASSERT( !(my_begin r.my_end) !(r.my_end my_begin), blocked_range has been split incorrectly ); } static Value do_split( blocked_range r, proportional_split proportion ) { __TBB_ASSERT( r.is_divisible(), cannot split blocked_range that is not divisible ); // 使用 32 位浮点运算计算右半部分大小并按四舍五入取整 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); }从源码结构看这里的比例计算使用浮点运算并加 0.5 取整。源码注释也明确指出对超过 2^24 次迭代的区间32 位浮点运算的误差约为 0.000001%对均匀分布的影响极小如需精确分裂可以参考test_partitioner_whitebox测试中的精确算法实现。底层机制partitioner 如何把 split 传给 Rangesplit与proportional_split除了在用户自定义 Range 时直接使用外还是 partitioner分区器向 Range 传递分裂意图的内部通道。在 _range_common.h 中可以看到这套机制template 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; } }; template typename Range, typename PartitionerSplitType auto get_range_split_object( PartitionerSplitType split_obj ) - decltype(range_split_object_providerRange::get(split_obj)) { return range_split_object_providerRange::get(split_obj); }这是一个基于 SFINAE 的特征分派tag dispatch当Range支持比例分裂即可用Range和proportional_split构造时get直接返回 partitioner 传入的分裂对象原样当Range不支持比例分裂时get退化为返回一个普通的split()对象从而让这类 Range 自动降级为基本均分分裂。借助proportional_split的explicit operator split()转换运算符两种分裂方式可以在 partitioner 的统一调度下无缝衔接而split本身始终保持其零开销标记的角色——它不携带任何运行时状态只在编译期决定重载决议的结果。C20 约束splittable 与 tbb_range 概念在支持 C20 concepts 的构建环境下oneTBB 还在 _range_common.h 中定义了与split直接相关的概念约束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; };其中splittable概念的判定标准正是能否以T与tbb::detail::split为参数构造该类型这与 split_cls.rst 中split用于区分分裂构造函数与拷贝构造函数的规范描述完全一致。也就是说一个类型是否是合法的 Range在编译期即可通过splittable与tbb_range两个概念得到静态验证split这个空类由此成为了 TBB 并行框架类型约束体系中最基础的一块基石。总结split的设计要点与使用清单围绕split类可以从规范与源码中提炼出以下关键事实split是一个空类dummy type定义于 _range_common.h通过blocked_range.h等公开头文件暴露给用户跨多个维度的 Range 类型与并行算法头文件可见。它的唯一职责是重载标记让R::R( R r, split )这种分裂构造函数在重载决议中与拷贝构造函数、默认构造函数明确区分从而在语法层面杜绝拷贝与分裂的歧义。它是 Range 概念的必需接口任何一个满足tbb_range/Range需求的类型都必须提供以split为第二参数的分裂构造函数且按约定将参数更新为前半部分、自身成为后半部分。它与proportional_split协作proportional_split提供left()、right()比例系数与到split的显式转换不支持比例分裂的 Range 会在get_range_split_object的分派下自动退回基本分裂。编写自定义 Range 时记得显式提供默认构造函数、empty()、is_divisible()并在分裂构造函数内先断言is_divisible()再按均分或给定比例切分。mold 链接器将其作为第三方组件随仓库携带位于 third-party/tbb因此阅读本文时可以直接在仓库内查阅 blocked_range.h 与 _range_common.h 的完整实现以及 conformance_blocked_range.cpp 等测试用例结合实际代码加深对 TBB 递归任务划分机制的理解。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考