oneTBB parallel_scan 算法详解并行前缀和原理、API 规范与 mold 链接器实战应用【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 oneTBB 官方规范文档 parallel_scan_func.rst 为核心骨架系统讲解oneapi::tbb::parallel_scan的函数模板签名、并行前缀parallel prefix的数学原理、命令式与函数式两种用法、pre_scan_tag/final_scan_tag两阶段机制及simple_partitioner的粒度控制并结合本仓库mold 现代链接器在.gdb_index名称池偏移计算与重定位节偏移计算中的真实调用展示该算法如何被用于将看似必然串行的依赖计算改造成可并行执行。读完本文你将掌握parallel_scan的完整 API 契约、Body/Scan/Combine 三个命名需求的实现要点以及前缀和在链接器性能敏感路径中的落地姿势。一、parallel_scan是什么parallel_scan是一个函数模板用于计算并行前缀parallel prefix又称并行扫描parallel scan。在并行计算领域前缀和是一类看起来存在固有串行依赖的问题序列中第i个输出依赖于第i-1个输出直觉上必须从左到右逐个计算。parallel_scan通过重新结合reassociate运算顺序、分两趟扫描把这类问题改造成可以跨多个硬件线程并行执行的形式。官方规范对它的定义如下头文件oneapi/tbb/parallel_scan.htemplatetypename Range, typename Body void parallel_scan( const Range range, Body body ); templatetypename Range, typename Body void parallel_scan( const Range range, Body body, /* see-below */ partitioner ); templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine ); templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine, /* see-below */ partitioner );前两个重载是命令式形式imperative form要求用户提供一个满足ParallelScanBody需求的Body对象后两个是函数式形式functional form面向仿函数functor和 lambda 表达式设计由算法内部隐藏命令式形式的复杂度。partitioner参数只能是以下两种类型之一const auto_partitioner默认自动分块const simple_partitioner简单分块要求用户在 Range 中显式给出 grain size文档出处parallel_scan_func.rst二、并行前缀的数学定义设 × 是一个结合associative的二元运算且存在左单位元 id×即对任意 x 有 id× × x x。× 作用于序列 z0, z1, …, zn-1 的并行前缀定义为序列 y0, y1, …, yn-1y0 id× × z0yi yi-1 × zii ≥ 1例如当 × 为加法时并行前缀就是前缀和running sum。对应的串行实现为T temp id; for( int i1; in; i ) { temp temp z[i]; y[i] temp; }parallel_scan之所以能并行关键在于结合律它可以把 (…((idz0)z1)z2)… 重新结合成互不依赖的多个局部子段subrange先分别求前缀再通过两趟扫描合并。代价是它可能最多调用 ×两倍于串行算法的次数——即使做的工作更多只要 grain size 选择得当把工作分发到多个硬件线程后并行算法仍可能显著快于串行版本。两点重要约束后文还会结合源码印证× 必须严格满足结合律且Body的方法必须忠实刻画 ×浮点加法这类近似结合的运算可以使用但结果舍入可能因并行扫描时的结合顺序不同而变化即使在同一次运行的不同线程分配下也可能不同不过在串行执行时parallel_scan的结合方式与本节开头的串行形式完全一致结果可复现。文档出处parallel_scan_func.rst三、类型需求Range / Body / Value / Scan / Combineparallel_scan的模板参数受到如下约束详见 parallel_scan_func.rst模板参数必须满足的需求说明RangeRange 需求描述可拆分、可并行的索引空间如blocked_rangeBodyParallelScanBody 需求命令式形式的核心定义 pre_scan 与 final_scan 两阶段行为ValueISO C 标准的CopyConstructible与CopyAssignable扫描累加量的类型需要能被复制构造和复制赋值ScanParallelScanFunc 需求函数式形式的扫描仿函数CombineParallelScanCombine 需求函数式形式的摘要合并仿函数C17 起的两处放宽Scan还可以是指向Range中某个 const 成员函数的指针该成员函数接收const Value与bool两个参数并返回ValueCombine还可以是指向Value中某个 const 成员函数的指针接收const Value参数并返回Value。3.1 ParallelScanBody命令式形式Body类型需满足 par_scan_body.rst 中的伪签名void Body::operator()( const Range r, pre_scan_tag ) // 累加 r 的摘要summary不写结果 void Body::operator()( const Range r, final_scan_tag ) // 计算 r 的扫描结果与摘要 Body::Body( Body b, split ) // 拆分this 与 b 各自独立累加摘要 void Body::reverse_join( Body b ) // 反向合并把 b 的摘要并入 this void Body::assign( Body b ) // 用 b 的摘要覆盖 this这里摘要summary指足以推导后续子段结果的信息比如求数组前缀和时子段 r 的摘要就是 r 内元素之和。摘要必须满足两条性质对任意相邻子段 r 与 s若 r 之前没有其它子段则仅凭 s 与 r 的摘要即可算出 s 的扫描结果r 与 s 连接后的摘要可由 r 与 s 各自的摘要合并得到。3.2 ParallelScanFunc 与 ParallelScanCombine函数式形式par_scan_func.rst 要求Scan提供Value Scan::operator()(const Range r, const Value sum, bool is_final) const即以sum为起点计算 r 的摘要当is_final true时同时计算 r 的扫描结果并返回计算得到的摘要。Value必须与parallel_scan模板参数一致。par_scan_combine.rst 要求Combine提供Value Combine::operator()(const Value left, const Value right) const即合并两个摘要left与right并返回结果。函数式形式全程使用同一个scan仿函数用布尔参数区分两趟摘要合并交给combine仿函数最终返回整个range上的摘要。identity参数是Scan::operator()的左单位元。四、两趟扫描pre_scan 与 final_scanparallel_scan的核心机制是两趟two-pass处理。它先把 range 拆分成若干子段然后pre_scan预扫描从左到右为各子段计算前瞻部分摘要look-ahead partial reductions用于把右面子段的起始累加值提前算好。预扫描只累计摘要、不写最终结果。final_scan最终扫描拿到正确的起始累加值后从左到右计算各子段的扫描结果并写出同时也要算出本子段的摘要——因为如果还没有其它线程预扫描过下一个子段这个摘要就用来继续推进。区分两阶段的标签类型定义在 pre_scan_tag_and_final_scan_tag_clses.rstnamespace oneapi { namespace tbb { struct pre_scan_tag { static bool is_final_scan(); // 返回 false operator bool(); // 返回 false }; struct final_scan_tag { static bool is_final_scan(); // 返回 true operator bool(); // 返回 true }; }}is_final_scan()与operator bool()的语义一致final_scan_tag为truepre_scan_tag为false。这解释了后文示例里if( Tag::is_final_scan() )的写法。parallel_scan会尽可能避免预扫描当串行执行时它直接按从左到右的顺序对每个子段只做 final_scan因此 final scan 必须同时产出结果和摘要——摘要可能用于处理下一个子段。只有当确实存在并行机会其它线程需要预扫描结果时才引入 pre_scan 趟。文档出处parallel_scan_func.rst五、命令式形式完整示例官方规范给出了计算前缀和的Body实现parallel_scan_func.rstclass Body { T sum; // 摘要当前已累计的和 T* const y; // 输出数组 const T* const z; // 输入数组 public: Body( T y_[], const T z_[] ) : sum(id), z(z_), y(y_) {} T get_sum() const { return sum; } templatetypename Tag void operator()( const oneapi::tbb::blocked_rangeint r, Tag ) { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( Tag::is_final_scan() ) y[i] temp; // 只有 final_scan 才写结果 } sum temp; // 两趟都要更新摘要 } Body( Body b, oneapi::tbb::split ) : z(b.z), y(b.y), sum(id) {} void reverse_join( Body a ) { sum a.sum sum; } void assign( Body b ) { sum b.sum; } }; T DoParallelScan( T y[], const T z[], int n ) { Body body(y,z); oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), body ); return body.get_sum(); }这段代码蕴含了命令式形式的三个典型模式单个模板同时覆盖两趟operator()用templatetypename Tag定义一次通过Tag::is_final_scan()区分版本。规范允许写两个重载但两个版本通常高度相似合写更省代码。pre_scan 只算摘要计算 × 归约但不更新y供算法生成前瞻部分摘要final_scan 既算摘要又更新y。reverse_join与parallel_reduce的join类似但参数顺序相反this是 × 的右操作数即sum a.sum sum注意a在左、this在右。parallel_scan决定何时何地生成并行工作因此 × 的结合性以及 Body 方法对其的忠实刻画是正确性根基。5.1 使用 simple_partitioner 时务必提供 grain size默认的auto_partitioner会自动选择分块。若改用simple_partitioner必须显式给出 grain size例如粒度 1000parallel_scan( blocked_rangeint(0,n,1000), total, simple_partitioner() );grain size 是分块的粗粒度阈值它决定了并行收益与拆分开销之间的平衡点过小会引入过多调度与合并开销过大则并行度不足。六、函数式形式lambda 写法官方规范给出了与前例等价的 lambda 函数式形式parallel_scan_func.rstT DoParallelScan( T y[], const T z[], int n ) { return oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), id, // 左单位元 [](const oneapi::tbb::blocked_rangeint r, T sum, bool is_final_scan)-T { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( is_final_scan ) y[i] temp; } return temp; // 返回子段摘要 }, []( T left, T right ) { return left right; // 合并两个摘要 } ); }对比命令式版本可见函数式形式的收益不必手写split构造、reverse_join、assign这些机械样板算法用同一个scanlambda靠bool is_final_scan参数区分两趟配合combinelambda 即可完成等价的并行前缀计算并直接返回整个 range 的摘要。这正是规范所说的隐藏了命令式形式的某些复杂性。七、在 mold 链接器中的实战两处真实调用parallel_scan并非纸上谈兵——mold 在构建调试信息与重定位节时用它处理两类典型的前缀偏移计算。本文档对应的 oneTBB 即来自本仓库内嵌的 third-party/tbb 依赖。7.1 为 .gdb_index 名称池计算偏移函数式形式在 gdb-index.cc 中mold 需要把数百万个 GDB 名称记录按编译单元顺序排布进类型池与字符串池每个条目的type_vector_offset与name_offset取决于前面所有条目的累计字节数——典型的前缀和依赖链// The map may contain millions of names. Assign their type and string // ranges with a parallel prefix sum. auto scan { for (i64 i range.begin(); i range.end(); i) { GdbNameMap::Entry *ent data.entries[i]; if (is_final) { ent-value.type_vector_offset size.type_bytes; ent-value.name_offset size.name_bytes; } size.type_bytes ent-value.count * 4 4; size.name_bytes ent-keylen 1; } return size; }; data.pool_size tbb::parallel_scan( tbb::blocked_rangei64(0, data.entries.size()), PoolSize{}, scan, [](PoolSize a, PoolSize b) - PoolSize { return {a.type_bytes b.type_bytes, a.name_bytes b.name_bytes}; });对照规范可以逐项印证Value PoolSize含type_bytes、name_bytes两个成员满足 CopyConstructible/CopyAssignableScan scanlambda签名(const Range, Value, bool) - Value与ParallelScanFunc的伪签名完全一致is_final为真时才把累计偏移写回条目否则只累计摘要Combine 合并 lambda把两个子段的字节数分别相加正是ParallelScanCombine语义identity PoolSize{}即 0 字节是加法意义上的左单位元。这正是文档所述函数式形式隐藏命令式形式复杂性的工程范例mold 无需维护带split/reverse_join/assign的 Body 类直接用两个 lambda 便完成了数千万条目的并行偏移分配。7.2 为重定位节计算各输入节的偏移命令式形式在 output-chunks.cc 的RelocSection构造中需要为每个输入节计算其在输出重定位节中的起始偏移偏移 前面所有输入节重定位条目数之和// Compute an offset for each input section offsets.resize(osec.members.size()); auto scan { for (i64 i r.begin(); i r.end(); i) { InputSectionE isec *osec.members[i]; if (is_final) offsets[i] sum; sum isec.get_rels(ctx).size(); } return sum; }; i64 num_entries tbb::parallel_scan( tbb::blocked_rangei64(0, osec.members.size()), 0, scan, std::plus());这里同样采用函数式形式Value为i64identity为0Combine直接复用标准库std::plus()。计算出的num_entries随后用于设置节头sh_sizenum_entries * sizeof(ElfRelE)一个parallel_scan调用同时完成了偏移分配与总条目数统计两件事。值得说明的是mold 源码中这两处都选择了函数式形式与规范面向仿函数与 lambda 设计的定位吻合命令式形式及其split/reverse_join/assign方法则更多用于需要长期维护内部状态如持有输入输出数组指针的 Body 类的复杂场景。八、关联组件与延伸阅读Range 概念blocked_range类见 blocked_range_cls.rst它提供begin()/end()并支持按 grain size 拆分姊妹算法parallel_reduce 是归约不要求子段间顺序parallel_scan是前缀子段间存在顺序依赖两者共享split/join的拆分-合并思想但reverse_join的方向性差异正是扫描语义的关键命名需求全文ParallelScanBody、ParallelScanFunc、ParallelScanCombine标签类型pre_scan_tag 与 final_scan_tagmold 实战源码gdb-index.cc、output-chunks.cc。总结parallel_scan是 oneTBB 中少数能并行化固有串行依赖计算的算法。掌握它的关键在于理解四件事结合律是并行化的数学前提因此也带来浮点结果可能随结合顺序变化、但串行时结果稳定的特性两趟机制pre_scan 制造前瞻摘要、final_scan 写出结果并续传摘要是并行正确性的实现骨架命令式与函数式两种形式分别对应需要显式状态管理与lambda 轻量使用两类场景partitioner 选择决定并行粒度simple_partitioner必须给出 grain size。mold 在.gdb_index名称池与重定位节偏移计算中的两处调用则为前缀偏移这一经典工程问题提供了可直接参考的范式。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 oneTBB parallel_scan 算法详解：并行前缀和原理、API 规范与 mold 链接器实战应用
oneTBB parallel_scan 算法详解并行前缀和原理、API 规范与 mold 链接器实战应用【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold本文以 oneTBB 官方规范文档 parallel_scan_func.rst 为核心骨架系统讲解oneapi::tbb::parallel_scan的函数模板签名、并行前缀parallel prefix的数学原理、命令式与函数式两种用法、pre_scan_tag/final_scan_tag两阶段机制及simple_partitioner的粒度控制并结合本仓库mold 现代链接器在.gdb_index名称池偏移计算与重定位节偏移计算中的真实调用展示该算法如何被用于将看似必然串行的依赖计算改造成可并行执行。读完本文你将掌握parallel_scan的完整 API 契约、Body/Scan/Combine 三个命名需求的实现要点以及前缀和在链接器性能敏感路径中的落地姿势。一、parallel_scan是什么parallel_scan是一个函数模板用于计算并行前缀parallel prefix又称并行扫描parallel scan。在并行计算领域前缀和是一类看起来存在固有串行依赖的问题序列中第i个输出依赖于第i-1个输出直觉上必须从左到右逐个计算。parallel_scan通过重新结合reassociate运算顺序、分两趟扫描把这类问题改造成可以跨多个硬件线程并行执行的形式。官方规范对它的定义如下头文件oneapi/tbb/parallel_scan.htemplatetypename Range, typename Body void parallel_scan( const Range range, Body body ); templatetypename Range, typename Body void parallel_scan( const Range range, Body body, /* see-below */ partitioner ); templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine ); templatetypename Range, typename Value, typename Scan, typename Combine Value parallel_scan( const Range range, const Value identity, const Scan scan, const Combine combine, /* see-below */ partitioner );前两个重载是命令式形式imperative form要求用户提供一个满足ParallelScanBody需求的Body对象后两个是函数式形式functional form面向仿函数functor和 lambda 表达式设计由算法内部隐藏命令式形式的复杂度。partitioner参数只能是以下两种类型之一const auto_partitioner默认自动分块const simple_partitioner简单分块要求用户在 Range 中显式给出 grain size文档出处parallel_scan_func.rst二、并行前缀的数学定义设 × 是一个结合associative的二元运算且存在左单位元 id×即对任意 x 有 id× × x x。× 作用于序列 z0, z1, …, zn-1 的并行前缀定义为序列 y0, y1, …, yn-1y0 id× × z0yi yi-1 × zii ≥ 1例如当 × 为加法时并行前缀就是前缀和running sum。对应的串行实现为T temp id; for( int i1; in; i ) { temp temp z[i]; y[i] temp; }parallel_scan之所以能并行关键在于结合律它可以把 (…((idz0)z1)z2)… 重新结合成互不依赖的多个局部子段subrange先分别求前缀再通过两趟扫描合并。代价是它可能最多调用 ×两倍于串行算法的次数——即使做的工作更多只要 grain size 选择得当把工作分发到多个硬件线程后并行算法仍可能显著快于串行版本。两点重要约束后文还会结合源码印证× 必须严格满足结合律且Body的方法必须忠实刻画 ×浮点加法这类近似结合的运算可以使用但结果舍入可能因并行扫描时的结合顺序不同而变化即使在同一次运行的不同线程分配下也可能不同不过在串行执行时parallel_scan的结合方式与本节开头的串行形式完全一致结果可复现。文档出处parallel_scan_func.rst三、类型需求Range / Body / Value / Scan / Combineparallel_scan的模板参数受到如下约束详见 parallel_scan_func.rst模板参数必须满足的需求说明RangeRange 需求描述可拆分、可并行的索引空间如blocked_rangeBodyParallelScanBody 需求命令式形式的核心定义 pre_scan 与 final_scan 两阶段行为ValueISO C 标准的CopyConstructible与CopyAssignable扫描累加量的类型需要能被复制构造和复制赋值ScanParallelScanFunc 需求函数式形式的扫描仿函数CombineParallelScanCombine 需求函数式形式的摘要合并仿函数C17 起的两处放宽Scan还可以是指向Range中某个 const 成员函数的指针该成员函数接收const Value与bool两个参数并返回ValueCombine还可以是指向Value中某个 const 成员函数的指针接收const Value参数并返回Value。3.1 ParallelScanBody命令式形式Body类型需满足 par_scan_body.rst 中的伪签名void Body::operator()( const Range r, pre_scan_tag ) // 累加 r 的摘要summary不写结果 void Body::operator()( const Range r, final_scan_tag ) // 计算 r 的扫描结果与摘要 Body::Body( Body b, split ) // 拆分this 与 b 各自独立累加摘要 void Body::reverse_join( Body b ) // 反向合并把 b 的摘要并入 this void Body::assign( Body b ) // 用 b 的摘要覆盖 this这里摘要summary指足以推导后续子段结果的信息比如求数组前缀和时子段 r 的摘要就是 r 内元素之和。摘要必须满足两条性质对任意相邻子段 r 与 s若 r 之前没有其它子段则仅凭 s 与 r 的摘要即可算出 s 的扫描结果r 与 s 连接后的摘要可由 r 与 s 各自的摘要合并得到。3.2 ParallelScanFunc 与 ParallelScanCombine函数式形式par_scan_func.rst 要求Scan提供Value Scan::operator()(const Range r, const Value sum, bool is_final) const即以sum为起点计算 r 的摘要当is_final true时同时计算 r 的扫描结果并返回计算得到的摘要。Value必须与parallel_scan模板参数一致。par_scan_combine.rst 要求Combine提供Value Combine::operator()(const Value left, const Value right) const即合并两个摘要left与right并返回结果。函数式形式全程使用同一个scan仿函数用布尔参数区分两趟摘要合并交给combine仿函数最终返回整个range上的摘要。identity参数是Scan::operator()的左单位元。四、两趟扫描pre_scan 与 final_scanparallel_scan的核心机制是两趟two-pass处理。它先把 range 拆分成若干子段然后pre_scan预扫描从左到右为各子段计算前瞻部分摘要look-ahead partial reductions用于把右面子段的起始累加值提前算好。预扫描只累计摘要、不写最终结果。final_scan最终扫描拿到正确的起始累加值后从左到右计算各子段的扫描结果并写出同时也要算出本子段的摘要——因为如果还没有其它线程预扫描过下一个子段这个摘要就用来继续推进。区分两阶段的标签类型定义在 pre_scan_tag_and_final_scan_tag_clses.rstnamespace oneapi { namespace tbb { struct pre_scan_tag { static bool is_final_scan(); // 返回 false operator bool(); // 返回 false }; struct final_scan_tag { static bool is_final_scan(); // 返回 true operator bool(); // 返回 true }; }}is_final_scan()与operator bool()的语义一致final_scan_tag为truepre_scan_tag为false。这解释了后文示例里if( Tag::is_final_scan() )的写法。parallel_scan会尽可能避免预扫描当串行执行时它直接按从左到右的顺序对每个子段只做 final_scan因此 final scan 必须同时产出结果和摘要——摘要可能用于处理下一个子段。只有当确实存在并行机会其它线程需要预扫描结果时才引入 pre_scan 趟。文档出处parallel_scan_func.rst五、命令式形式完整示例官方规范给出了计算前缀和的Body实现parallel_scan_func.rstclass Body { T sum; // 摘要当前已累计的和 T* const y; // 输出数组 const T* const z; // 输入数组 public: Body( T y_[], const T z_[] ) : sum(id), z(z_), y(y_) {} T get_sum() const { return sum; } templatetypename Tag void operator()( const oneapi::tbb::blocked_rangeint r, Tag ) { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( Tag::is_final_scan() ) y[i] temp; // 只有 final_scan 才写结果 } sum temp; // 两趟都要更新摘要 } Body( Body b, oneapi::tbb::split ) : z(b.z), y(b.y), sum(id) {} void reverse_join( Body a ) { sum a.sum sum; } void assign( Body b ) { sum b.sum; } }; T DoParallelScan( T y[], const T z[], int n ) { Body body(y,z); oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), body ); return body.get_sum(); }这段代码蕴含了命令式形式的三个典型模式单个模板同时覆盖两趟operator()用templatetypename Tag定义一次通过Tag::is_final_scan()区分版本。规范允许写两个重载但两个版本通常高度相似合写更省代码。pre_scan 只算摘要计算 × 归约但不更新y供算法生成前瞻部分摘要final_scan 既算摘要又更新y。reverse_join与parallel_reduce的join类似但参数顺序相反this是 × 的右操作数即sum a.sum sum注意a在左、this在右。parallel_scan决定何时何地生成并行工作因此 × 的结合性以及 Body 方法对其的忠实刻画是正确性根基。5.1 使用 simple_partitioner 时务必提供 grain size默认的auto_partitioner会自动选择分块。若改用simple_partitioner必须显式给出 grain size例如粒度 1000parallel_scan( blocked_rangeint(0,n,1000), total, simple_partitioner() );grain size 是分块的粗粒度阈值它决定了并行收益与拆分开销之间的平衡点过小会引入过多调度与合并开销过大则并行度不足。六、函数式形式lambda 写法官方规范给出了与前例等价的 lambda 函数式形式parallel_scan_func.rstT DoParallelScan( T y[], const T z[], int n ) { return oneapi::tbb::parallel_scan( oneapi::tbb::blocked_rangeint(0,n), id, // 左单位元 [](const oneapi::tbb::blocked_rangeint r, T sum, bool is_final_scan)-T { T temp sum; for( int ir.begin(); ir.end(); i ) { temp temp z[i]; if( is_final_scan ) y[i] temp; } return temp; // 返回子段摘要 }, []( T left, T right ) { return left right; // 合并两个摘要 } ); }对比命令式版本可见函数式形式的收益不必手写split构造、reverse_join、assign这些机械样板算法用同一个scanlambda靠bool is_final_scan参数区分两趟配合combinelambda 即可完成等价的并行前缀计算并直接返回整个 range 的摘要。这正是规范所说的隐藏了命令式形式的某些复杂性。七、在 mold 链接器中的实战两处真实调用parallel_scan并非纸上谈兵——mold 在构建调试信息与重定位节时用它处理两类典型的前缀偏移计算。本文档对应的 oneTBB 即来自本仓库内嵌的 third-party/tbb 依赖。7.1 为 .gdb_index 名称池计算偏移函数式形式在 gdb-index.cc 中mold 需要把数百万个 GDB 名称记录按编译单元顺序排布进类型池与字符串池每个条目的type_vector_offset与name_offset取决于前面所有条目的累计字节数——典型的前缀和依赖链// The map may contain millions of names. Assign their type and string // ranges with a parallel prefix sum. auto scan { for (i64 i range.begin(); i range.end(); i) { GdbNameMap::Entry *ent data.entries[i]; if (is_final) { ent-value.type_vector_offset size.type_bytes; ent-value.name_offset size.name_bytes; } size.type_bytes ent-value.count * 4 4; size.name_bytes ent-keylen 1; } return size; }; data.pool_size tbb::parallel_scan( tbb::blocked_rangei64(0, data.entries.size()), PoolSize{}, scan, [](PoolSize a, PoolSize b) - PoolSize { return {a.type_bytes b.type_bytes, a.name_bytes b.name_bytes}; });对照规范可以逐项印证Value PoolSize含type_bytes、name_bytes两个成员满足 CopyConstructible/CopyAssignableScan scanlambda签名(const Range, Value, bool) - Value与ParallelScanFunc的伪签名完全一致is_final为真时才把累计偏移写回条目否则只累计摘要Combine 合并 lambda把两个子段的字节数分别相加正是ParallelScanCombine语义identity PoolSize{}即 0 字节是加法意义上的左单位元。这正是文档所述函数式形式隐藏命令式形式复杂性的工程范例mold 无需维护带split/reverse_join/assign的 Body 类直接用两个 lambda 便完成了数千万条目的并行偏移分配。7.2 为重定位节计算各输入节的偏移命令式形式在 output-chunks.cc 的RelocSection构造中需要为每个输入节计算其在输出重定位节中的起始偏移偏移 前面所有输入节重定位条目数之和// Compute an offset for each input section offsets.resize(osec.members.size()); auto scan { for (i64 i r.begin(); i r.end(); i) { InputSectionE isec *osec.members[i]; if (is_final) offsets[i] sum; sum isec.get_rels(ctx).size(); } return sum; }; i64 num_entries tbb::parallel_scan( tbb::blocked_rangei64(0, osec.members.size()), 0, scan, std::plus());这里同样采用函数式形式Value为i64identity为0Combine直接复用标准库std::plus()。计算出的num_entries随后用于设置节头sh_sizenum_entries * sizeof(ElfRelE)一个parallel_scan调用同时完成了偏移分配与总条目数统计两件事。值得说明的是mold 源码中这两处都选择了函数式形式与规范面向仿函数与 lambda 设计的定位吻合命令式形式及其split/reverse_join/assign方法则更多用于需要长期维护内部状态如持有输入输出数组指针的 Body 类的复杂场景。八、关联组件与延伸阅读Range 概念blocked_range类见 blocked_range_cls.rst它提供begin()/end()并支持按 grain size 拆分姊妹算法parallel_reduce 是归约不要求子段间顺序parallel_scan是前缀子段间存在顺序依赖两者共享split/join的拆分-合并思想但reverse_join的方向性差异正是扫描语义的关键命名需求全文ParallelScanBody、ParallelScanFunc、ParallelScanCombine标签类型pre_scan_tag 与 final_scan_tagmold 实战源码gdb-index.cc、output-chunks.cc。总结parallel_scan是 oneTBB 中少数能并行化固有串行依赖计算的算法。掌握它的关键在于理解四件事结合律是并行化的数学前提因此也带来浮点结果可能随结合顺序变化、但串行时结果稳定的特性两趟机制pre_scan 制造前瞻摘要、final_scan 写出结果并续传摘要是并行正确性的实现骨架命令式与函数式两种形式分别对应需要显式状态管理与lambda 轻量使用两类场景partitioner 选择决定并行粒度simple_partitioner必须给出 grain size。mold 在.gdb_index名称池与重定位节偏移计算中的两处调用则为前缀偏移这一经典工程问题提供了可直接参考的范式。【免费下载链接】moldmold: A Modern Linker 项目地址: https://gitcode.com/GitHub_Trending/mo/mold创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考