并行算法

从“执行策略只是许可”开始

前几章你学会了亲手招厨师、分活、排队取菜——那是把并行的每个零件都自己拧。可大多数时候你只想说一句：「把这一筐菜都处理一遍」。要是连「分给几个厨师、要不要同时上」都得自己排班，未免太累。

更省心的办法是：下这句指令时，顺手挑一个并行档位。你可以说「一个厨师顺着做就行」，也可以说「多叫几个厨师分批同时做」，还可以说「多叫几个厨师，而且每人允许一手同时颠两个锅」。同一句「处理这筐菜」，挑的档位不同，快慢就天差地别——而排班的脏活，交给后厨总管去办。

没有这套「挑档位」的本事会怎样？要么你为了让活儿快点，又得回去手搓那套招人、分活、合账的全套流程；要么图省事永远只用顺序版本。更重要的是，档位只是给实现许可：par 不承诺创建新线程，也不承诺更快，资源不足时可以顺序执行。

执行策略：算法的「并行档位」

把「挑档位」翻译成 C++17 的话，就是给算法传一个 执行策略。它是算法的第一个实参，描述实现可以采用哪类执行方式。C++17 提供三档；C++20 另加只允许无序向量化、不允许多线程并行的 std::execution::unseq，不要把它误写成 C++17 接口：

第一档 std::execution::seq（顺序）：元素访问函数都在调用线程执行，彼此不交错，也不得并行化。它不等于给所有算法额外承诺“按输入顺序回调”；顺序仍要看具体算法的规范。

第二档 std::execution::par（并行）：允许把工作分给多个线程，但并不保证这样做。代价是：函子必须能被并发调用，不能依赖调用线程身份或调用顺序，更不能产生数据竞争。

第三档 std::execution::par_unseq（并行 + 不排序）：在多线程许可之上，再允许同一线程内 向量化。互斥锁等阻塞同步可能让同一线程在尚未解锁时再次请求同一把锁，因此属于向量化不安全操作。不要把规则简化成“禁止所有原子或内存分配”：标准对内存分配/释放和无锁原子读改写有例外；工程上仍优先让函子保持纯计算，把合并交给归约算法。

三档不是「越强越好」，而是「越强对你的函子要求越严、且只在活够大够独立时才真划算」（§4 的判断清单专门讲这个）。

并行 STL：给算法传策略，授予执行许可

执行策略真正的妙处在于：调用形状几乎不用改。原来怎么调 std::sort、std::for_each、std::reduce，现在只是在参数最前面放一个执行策略。这些「能接受执行策略、从而允许并行执行」的算法重载，就叫 并行算法（并行 STL）。

从「自己 new 线程、自己分块、自己合并」到「加一个 par」，省下的代码量是巨大的——这正是本章 §6 要带你一行行体会的。for_each 并行处理每个元素、sort 并行排序、reduce 并行求和……都只是多打了几个字符。

reduce vs accumulate：能并行的求和，凭什么能并行

并行求和这件事，藏着一个微妙但关键的区别。老朋友 std::accumulate 你早就用过——它从左到右、一个一个累加：((((0+a)+b)+c)+d)，第 $i$ 步必须等第 $i-1$ 步算完。这是严格顺序的，天生无法并行，所以标准库没给它执行策略重载。

C++17 新增的 std::reduce 长得几乎一样，却能并行。秘密在于它用 树形归约：先把 (a+b) 和 (c+d) 同时算出来，再合并成 ((a+b)+(c+d))。这棵树的每一层内部互不依赖，可以并行。下面这张动画把「线性链 vs 树形」并排演给你看——先猜一猜：

猜一猜：reduce 既然能把 (a+b)、(c+d) 拆开并行算，那把它的加号换成减号、做 a-b-c-d，并行出来的结果还对吗？

盯住右半区：reduce 之所以敢把求和顺序重排成树形，前提是操作可结合、可交换——加法满足 (a+b)+c == a+(b+c)，怎么分组、谁先算结果都一样。可一旦操作不满足这个前提，重排就会算错。这就引出本章一个核心术语 可结合性：加法可结合，所以 reduce(+) 怎么并行都对；可减法 a-b-c-d 一旦重排成 (a-b)-(c-d)，结果就完全变了。所以 reduce 只对可结合 / 可交换的操作才能保证结果正确——这是它和 accumulate 最本质的分水岭（§6 有正反代码，§7 有踩坑）。

何时该并行：并行不是免费的

最后一个、也是最常被忽略的判断：这段代码到底该不该并行？ 很多人以为「能并行就并行、能选 par_unseq 就选最强」，结果加上 par 反而更慢。原因是并行有它自己的开销——把活分给多个线程、调度它们、最后合并结果，这些都要花时间；还可能撞上第九章讲过的 false sharing、锁争用。当每个元素的活又少又轻、数据量又小时，这笔开销会盖过并行省下的时间。

下面这张对比图给你一份「该不该 par」的判断清单：

一句话总则：数据量大 + 每元素处理够重 + 元素间无依赖无争用，三条都占，par 才划算；反之小数据、极轻处理、有共享写 / 有副作用，老老实实 seq，甚至并行还不如顺序快。这正好呼应第九章的 Amdahl 定律（串行部分卡住上限）和 false sharing（共享写拖垮并行）——并行算法只是把那些道理换了个更省力的接口，底层的账还是同一本。

上手玩一玩这三张图

本章三张图各管一件事，配合 §6 代码一起玩比读十遍管用：

• 执行策略三档 <ExecutionPolicyDiagram />（主 Demo）：单步看同一个 for_each 在 seq / par / par_unseq 三档下的处理节奏——seq 8 拍逐个、par 2 拍分块、par_unseq 1 拍叠加向量化。先想「是不是无脑选最强的就好」，再看正文 §4 的反例。盯住「档位越强、用时越短，但对函子要求越严」这一点。
• reduce 树形归约 <ReduceTreeDiagram />：左边 accumulate 一个一个顺着加（4 步串行），右边 reduce 两两并行求和再合并（2 层）。重点体会末尾那条警示：reduce 重排的前提是操作可结合 / 可交换，减法一重排就错。
• 该不该并行 <WhenToParallelizeDiagram />：两栏对照「值得并行」与「并行反而亏」的三条判据。做 §8 分析题前，先把这份清单记牢——并行不是免费的。

代码：给算法加一个执行策略

for_each 加 std::execution::par 一键并行

最直接的并行化：原来怎么 for_each，现在只在最前面塞一个 std::execution::par，算法就自动把元素分给多个线程处理。比如把一张图片的所有像素并行调亮：

#include <algorithm>
#include <execution>
#include <vector>
 
// 给所有元素并行地乘 2：第一个实参传执行策略 std::execution::par
void brighten(std::vector<int>& pixels) {
    std::for_each(std::execution::par, pixels.begin(), pixels.end(),
                  [](int& x) { x *= 2; });
}

和老写法的唯一差别，就是多了 std::execution::par, 这一个实参。算法内部会把 pixels 切成若干块、分给多个线程各跑各的——而每个像素只是独立地乘 2，互不依赖，正是并行的理想场景。

std::sort 并行排序

排序适合展示策略重载。给 std::sort 传 par 后，实现可以采用并行分治，也可以因数据规模、资源或后端限制退回顺序执行：

#include <algorithm>
#include <execution>
#include <vector>
 
// 并行排序：把 std::execution::par 作为第一个实参传给 std::sort
void parallel_sort(std::vector<double>& data) {
    std::sort(std::execution::par, data.begin(), data.end());
}

比较器必须满足严格弱序，而且要能被并发调用。捕获一个可变计数器并在比较时裸写，会产生数据竞争；比较结果依赖调用次数或外部可变状态，还会破坏排序契约。实际收益取决于元素类型、比较成本、数据分布、规模与实现后端，必须和同一数据上的无策略 sort 做基准对照。

reduce vs accumulate：并排看「能并行的求和」

并行求和是本章的灵魂对照。accumulate 严格顺序、没有执行策略重载；reduce 能传 par 并行——但要求二元操作可结合 / 可交换：

#include <execution>
#include <numeric>
#include <vector>
 
// accumulate：从左到右严格顺序累加，无执行策略重载——天生串行
long sum_accumulate(const std::vector<long>& v) {
    return std::accumulate(v.begin(), v.end(), 0L);
}
 
// reduce：可传执行策略并行；默认用加法，可结合可交换 → 重排安全
long sum_reduce(const std::vector<long>& v) {
    return std::reduce(std::execution::par, v.begin(), v.end(), 0L);
}

假设 long 求和不溢出，两个函数都表达「所有元素之和」。区别在于：accumulate 按顺序折叠，而 reduce 可以改变分组与求值次序——这就是 §5 那张树形归约图。对浮点数，即使用加法，舍入也会让不同分组得到不同末位；需要可复现实验结果时，要固定归约树或使用更稳定的求和方案。

transform_reduce：先映射、再并行归约

很多「先逐元素算一下、再把结果汇总」的活，可以用 std::transform_reduce 一步并行搞定。典型如点积：先把两个向量逐对相乘，再把乘积求和：

#include <execution>
#include <numeric>
#include <vector>
 
// 并行算两个等长向量的点积：先逐对相乘（transform），再并行求和（reduce）
double dot_parallel(const std::vector<double>& a, const std::vector<double>& b) {
    return std::transform_reduce(
        std::execution::par,
        a.begin(), a.end(), b.begin(),
        0.0,                  // 归约初值
        std::plus<>(),        // 归约：求和（可结合 / 可交换）
        std::multiplies<>()); // 映射：逐对相乘
}

transform_reduce 把「映射 + 归约」融成一个算法：映射（multiplies）逐对独立，归约（plus）允许改变分组。它通常能避免显式中间数组，但这里是 double 点积，结果可能随归约分组改变末位；不能把数学上的结合律直接当成 IEEE 浮点的逐位确定性。

scan：保留每个前缀结果

reduce 只返回一个总结果；扫描算法则写出每个前缀的结果。exclusive_scan 在位置 i 写入“初值与输入区间 [first, i) 的归约”，所以输入 {1, 2, 3, 4}、初值 0 会得到 {0, 1, 3, 6}：

#include <execution>
#include <numeric>
#include <vector>
 
std::vector<int> prefix_offsets(const std::vector<int>& sizes) {
    std::vector<int> offsets(sizes.size());
    std::exclusive_scan(std::execution::par, sizes.begin(), sizes.end(),
                        offsets.begin(), 0);
    return offsets;
}

同族还有 inclusive_scan、transform_inclusive_scan 与 transform_exclusive_scan。它们适合前缀和、压缩布局偏移等任务，但同样可能改变运算分组；输出区间必须满足该算法的重叠规则，不能想当然地原地覆盖。

迭代器要求由具体重载决定，不能笼统说“并行算法都要求随机访问迭代器”。例如 C++17 的多个策略重载以 ForwardIterator 表达最低要求，而 sort 本身仍要求随机访问。写泛型封装时应查目标算法的签名与前置条件，而不是从 par 推断迭代器类别。

注意事项：异常与数据竞争

并行算法还有两条必须记牢的硬约束。第一条：使用 seq、par、par_unseq 这些标准执行策略时，元素访问函数的异常若越过算法边界，程序会调用 std::terminate；这条规则连 seq 策略也覆盖。正解是使用不抛函子，或在函子内部把失败转换为明确的结果状态：

#include <algorithm>
#include <execution>
#include <stdexcept>
#include <vector>
 
void process(std::vector<int>& v) {
    // 标准执行策略下，元素访问函数的异常逸出会触发 terminate。
    std::for_each(std::execution::par, v.begin(), v.end(), [](int& x) {
        try {
            if (x < 0) throw std::runtime_error("bad");
            x *= 2;
        } catch (const std::exception&) {
            x = 0; // 就地兜住，异常不逸出并行算法
        }
    });
}

第二条：par 要求函子无数据竞争。多个线程会并发调用它，若函子里多个线程同写一个普通变量，就是 UB。要跨元素汇总，得用 std::atomic（或干脆用 reduce 让标准库替你安全合并）：

#include <algorithm>
#include <atomic>
#include <execution>
#include <vector>
 
// par 要求函子无数据竞争：用 atomic 计数，避免多线程同写普通变量
std::size_t count_positive(const std::vector<int>& v) {
    std::atomic<std::size_t> n{0};
    std::for_each(std::execution::par, v.begin(), v.end(), [&n](int x) {
        if (x > 0) n.fetch_add(1, std::memory_order_relaxed);
    });
    return n.load();
}

并行调用还可能在失败发生前完成一部分元素修改；terminate 不会替你回滚。需要事务式“全成或全不成”时，先写入独立临时结果，验证全部成功后再提交，或改用能显式传播错误与取消的任务模型。

容易踩的坑

小结

• 执行策略授予许可：seq 禁止并行，par 允许并行，par_unseq 还允许同一线程内不排序执行；后二者都可退回顺序执行，不保证新线程、SIMD 或提速
• 算法契约仍有效：比较器必须满足严格弱序且可并发调用，元素操作不能产生数据竞争，也不能依赖调用顺序或线程身份
• 归约与扫描会改变分组：减法不能直接交给 reduce；浮点加法也可能出现末位差异，需要确定性时应固定归约方案
• 标准策略有失败边界：元素访问函数的异常逸出会 std::terminate，且此前副作用不会自动回滚；需要传播、取消与提交协议时改用显式任务
• 性能必须实测：确认目标标准库和后端，以无策略版本为基线测不同规模；标准策略不提供线程池、线程数或粒度控制旋钮

#include <algorithm>
#include <execution>
#include <vector>
 
std::size_t count_positive_buggy(const std::vector<int>& v) {
    std::size_t count = 0;
    std::for_each(std::execution::par, v.begin(), v.end(),
                  [&count](int x) {
                      if (x > 0) ++count; // ← 多线程同写 count：数据竞争 UB
                  });
    return count;
}

#include <algorithm>
#include <atomic>
#include <execution>
#include <vector>
 
std::size_t count_positive_atomic(const std::vector<int>& v) {
    std::atomic<std::size_t> count{0};
    std::for_each(std::execution::par, v.begin(), v.end(), [&count](int x) {
        if (x > 0) count.fetch_add(1, std::memory_order_relaxed);
    });
    return count.load();
}

#include <execution>
#include <functional>
#include <numeric>
#include <vector>
 
std::size_t count_positive_reduce(const std::vector<int>& v) {
    return std::transform_reduce(
        std::execution::par, v.begin(), v.end(),
        std::size_t{0}, std::plus<>(),
        [](int x) -> std::size_t { return x > 0 ? 1 : 0; });
}

#include <functional>
#include <numeric>
#include <vector>
 
double subtract_chain(const std::vector<double>& v, double init) {
    // accumulate 严格从左到右：init - v[0] - v[1] - ... 顺序确定
    return std::accumulate(v.begin(), v.end(), init, std::minus<>());
}