企业官网建设流程全解析

mold 链接器的 TBB 并行基石：BlockedRangeValue 命名要求深度解析

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold

本指南聚焦 oneTBB（Threading Building Blocks）中支撑blocked_range等可递归切分区间类模板的BlockedRangeValue命名要求（named requirement）。mold 链接器在 GDB 索引构建等阶段直接使用tbb::blocked_range进行并行扫描（见 src/gdb-index.cc），理解这一定义于 blocked_range_val.rst 的契约，是读懂 mold 并行代码、乃至自行设计自定义区间类型的前提。读完本文，你将掌握：一个值类型要成为合法的区间元素需要满足哪五个操作、它们的精确语义与类型约束、以及这些约束如何与Range概念和blocked_range类模板的实现一一对应。

什么是 BlockedRangeValue：区间元素的最小契约

oneTBB 的并行算法（parallel_for、parallel_reduce、parallel_scan）把工作负载描述为可递归切分的区间。区间里的每个元素是什么？答案非常宽泛：它可以是一个整数下标、一个指针，甚至是一个 STL 随机访问迭代器。为了让区间类模板（如blocked_range<Value>）对所有这些类型都成立，规范（specification）在[req.blocked_range_value]中定义了一组名为BlockedRangeValue的命名要求。

命名要求（named requirement）是 C++ 标准库风格的抽象契约：它不要求类型继承某个基类，只要求类型提供若干具备特定语义的操作。任何满足这些操作的类型，都可以直接作为blocked_range的模板参数，无需任何适配器。

该契约定义的原始文档位于 blocked_range_val.rst，它是blocked_range类模板（blocked_range_cls.rst）对模板参数Value的全部约束。

五个必备操作：伪签名与精确语义

BlockedRangeValue要求类型Value提供如下操作：

逐一拆解：

拷贝构造与析构：区间在递归切分与跨线程分发的过程中会被反复拷贝（parallel_for会为每个子区间拷贝一份 body 与 range），因此拷贝构造和析构是硬性要求，且语义必须与内置类型一致。

赋值operator=：伪签名中返回值写为void是一种标注——规范明确指出，operator=并不要求返回值；真实代码中即使返回了值（例如返回引用），blocked_range也会忽略它。也就是说，赋值只要求具有"把状态复制过去"的副作用。

小于比较operator<：这是整个契约中语义最关键的一环。区间是一个半开区间[i, j)，"i在j之前"（i precedes j）必须由operator<定义。注意blocked_range的实现只依赖operator<（以及由它推导出的相等关系），见 blocked_range.h 中的断言注释：only comparison 'less than' is required from values of blocked_range objects。换言之，你的值类型不需要提供==、!=、<=、>等全套比较运算符。

减法operator-：j - i的返回值记为D，其含义是半开区间[i, j)内的元素个数。它决定了blocked_range::size()的数值，是整个切分算法计算区间大小的基础。

加法operator+：i + k返回i之后的第 k 个值，它配合减法和operator<，构成了区间二分切分（[i, i+(j-i)/2)与[i+(j-i)/2, j)）的全部数学工具。

关于类型 D 的重要约束

规范特别强调：D是表达式j - i的类型，可以是任何可转换为size_t的整数类型。这个约束不是随意为之——blocked_range的size_type恒为std::size_t（见 blocked_range_cls.rst 对size_type的说明），size()返回end() - begin()，其实现即为size_type(my_end - my_begin)（blocked_range.h）。因此若operator-的返回类型无法隐式转换为size_t，代码将无法编译。

模型类型：整数、指针与随机访问迭代器

文档明确指出，以下三类类型天然满足BlockedRangeValue：

1. 整数类型（integral types）：如int、i64。j - i返回整数，i + k直接算术前进，是绝大多数并行循环（mold 即如此）的使用方式。
2. 指针（pointers）：指针差p - q是ptrdiff_t（可转换为size_t），p + k是指针算术。
3. STL 随机访问迭代器（random-access iterators）：要求其difference_type可隐式转换为size_t。此时blocked_range的行为与只读 STL 容器一致——这正是blocked_range把类型别名命名为const_iterator的原因："so that if it is a const_iterator, the blocked_range behaves like a read-only STL container"（blocked_range_cls.rst）。

需要警惕的一个反例：前向迭代器（forward iterator）或双向迭代器不满足此要求，因为它们没有operator-和operator+（operator+只能用于随机访问迭代器），无法计算区间大小，也就无法切分。

为何要求如此克制：与 Range 概念的职责分工

要理解BlockedRangeValue为什么只要求这五个操作，需要把它放进 oneTBB 的两层契约体系中：

• 值层（BlockedRangeValue）：只回答"单个值如何表达、如何前进、如何求差"，见 blocked_range_val.rst；
• 区间层（Range）：回答"一段连续的值如何判断空、如何判断可切分、如何切分"，见 range.rst。

Range概念要求类型R提供：拷贝构造、析构、empty()、is_divisible()、基本切分构造R::R(R& r, split)，以及可选的比例切分构造R::R(R& r, proportional_split p)。其中split是库定义的空标签类型（split_cls.rst），用于与拷贝构造区分——两者形参数量相同，靠哑元参数类型来重载区分。

blocked_range<Value>正是把"值层的代数运算"与"区间层的切分策略"组合起来的桥梁：切分时它调用Value的减法和加法计算中点，用grainsize控制切分粒度。关于grainsize有一个需要注意的实现细节：Range概念要求显式提供拷贝构造，因此编译器不会自动生成默认构造（range.rst），而blocked_range的三参构造blocked_range(Value begin, Value end, size_type grainsize=1)正是那个"额外的构造器"，它要求grainsize为正，调试版库会以断言失败拦截违规（blocked_range_cls.rst、blocked_range.h）。

落地实现：blocked_range 类模板源码对照

文档中的契约在 blocked_range.h 中得到了精确落实。该文件第 30-43 行直接以注释形式重述了Range概念的四项要求，并用 C++20 约束__TBB_requires(blocked_range_value<Value>)把BlockedRangeValue固化进模板签名——不满足契约的类型在编译期即被拒绝，而非等到运行时才报错。

关键成员与文档的对应关系：

• size()：要求end()<begin()为假，返回size_type(my_end - my_begin)——直接使用operator-（第 68-71 行）；
• empty()：返回!(my_begin < my_end)——只用operator<，不依赖==（第 81 行）；
• is_divisible()：返回my_grainsize < size()，即"区间大小超过粒度才可切分"（第 85 行）；
• 基本切分构造（第 90-97 行）：调用私有辅助函数do_split(r, split())计算新区间的起点，新对象持有右半部分、原对象更新为左半部分，grainsize保持不变；
• 比例切分构造（第 102-109 行）：同样经由do_split，但按proportional_split给定的比例分配左右两部分；
• 成员声明顺序my_end必须在my_begin之前（第 112 行注释），否则切分构造会因初始化顺序出错——这是实现层面的一个隐蔽约束，也解释了为什么两个切分构造都要显式写出成员初始化列表。

进阶：proportional_split 比例切分

BlockedRangeValue契约本身只定义了算术操作，但blocked_range还支持一种可选的比例切分，其比例由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; // 可退化为基本 split }; }}

其构造与访问语义为：proportional_split(left, right)构造一个左右比例，left()返回左部系数、right()返回右部系数，两者默认均为 1。文档给出了精确的切分公式示例：若r表示半开区间[i, j)、粒度为g，执行blocked_range<int> s(r, proportional_split(2, 3))后，r变为[i, i+2*(j-i)/(2+3))，s变为[i+2*(j-i)/(2+3), j)，两者粒度仍为g（blocked_range_cls.rst）。

此外，explicit operator split()使得proportional_split可以显式转换为split，从而在不支持比例切分的自定义 Range 类型上也能复用同一套代码路径——这是规范层面为"可选特性降级"预留的兼容通道。

parallel_for文档（parallel_for_func.rst）进一步说明：算法会把区间递归切分到每个子区间的is_divisible()为假为止，并为每个子区间拷贝一份 body 执行；未显式指定时采用auto_partitioner策略。

在 mold 中的真实应用：GDB 索引的并行扫描

mold 之所以捆绑 vendor 了 oneTBB（third-party/tbb），正是因为链接器的大量热路径依赖并行区间算法。一个典型实例在 GDB 索引（.gdb_index）的字符串池扫描阶段，src/gdb-index.cc 中构造了tbb::blocked_range<i64>并对之调用parallel_reduce：

auto scan = & { ... }; ... tbb::parallel_reduce( tbb::blocked_range<i64>(0, data.entries.size()), PoolSize{}, scan, ...);

这里的Value = i64是long long整数，天然满足BlockedRangeValue：operator-得到差值、operator+算术前进、operator<排序，三者均由语言内建提供，无需任何包装。这正是规范选择"克制的五个操作"带来的工程回报——内置类型零成本接入并行框架，而parallel_reduce内部对区间的递归切分、body 的拷贝与合并，全部建立在本文所述的两层契约之上。

编写自定义 Value 类型的实战清单

若你的业务需要把自定义类型直接塞进blocked_range（例如用迭代器遍历容器、用指针扫描内存映射文件），对照本文契约做如下检查：

1. 五个操作齐备：拷贝构造、析构、赋值（返回值可忽略）、operator<、operator-、operator+；
2. 减法可转 size_t：D = j - i必须能隐式转换为std::size_t，否则size()无法编译；
3. 只用<定义序：empty()与切分断言都基于operator<，请确保序关系严格全序（严格弱序即可），且i < i恒为假；
4. 加法语义：i + k必须返回"第 k 个后继"，且与减法互逆（(i + k) - i == k）；
5. 可选优化：若希望支持比例切分（负载不均衡的场景），无需改动值类型——比例切分完全由blocked_range的构造器处理，值类型只提供加减运算即可。

完整契约文本见 blocked_range_val.rst，区间层的切分要求见 range.rst，二者配套阅读即可完整理解 oneTBB 并行区间的设计哲学：把"什么是值"压缩到最小公倍数，把"如何并行"留给库。

【免费下载链接】moldmold: A Modern Linker 🦠项目地址: https://gitcode.com/GitHub_Trending/mo/mold