标准库并行算法与执行策略

发表于 2026-05-08 分类于学习，高性能C++并行编程阅读次数：

标准库并行算法与执行策略

时间：2026/05/08

关键词：std::execution、par、par_unseq、reduce、transform_reduce、scan、无副作用、确定性
核心目标：理解 C++ 标准库并行算法能做什么、不能做什么，以及什么时候用它、什么时候换 TBB。

1. 为什么需要标准库并行算法

手写线程经常会遇到这些问题：

如何分块
如何处理尾部
如何归约
如何控制任务粒度
如何避免共享写
如何处理异常和生命周期

标准库并行算法的思路是：

把“我要对一段数据做什么”交给算法，把“怎么并行”交给实现。

例如：

#include <algorithm>
#include <execution>
#include <vector>

std::vector<float> a, b, c;

std::transform(std::execution::par,
               a.begin(), a.end(),
               b.begin(),
               c.begin(),
               [](float x, float y) {
                   return x + y;
               });

它比手写线程更短，也更容易表达意图。

2. 执行策略有哪些

常见执行策略：

策略	含义
`std::execution::seq`	顺序执行
`std::execution::par`	允许多线程并行
`std::execution::unseq`	允许单线程内无序/向量化执行
`std::execution::par_unseq`	允许并行 + 向量化 + 无序执行

直觉：

seq       最保守
par       多线程
unseq     SIMD/无序
par_unseq 多线程 + SIMD，限制也最多

注意：

标准允许并行，不等于实现一定并行
标准库实现和编译器支持会影响实际效果
性能结论必须 benchmark

3. 第一个并行 `for_each`

#include <algorithm>
#include <execution>
#include <vector>

void scale(std::vector<float>& a, float k) {
    std::for_each(std::execution::par,
                  a.begin(), a.end(),
                  [=](float& x) {
                      x *= k;
                  });
}

这个例子是安全的，因为每次迭代只修改当前元素。

危险写法：

float sum = 0.0f;

std::for_each(std::execution::par,
              a.begin(), a.end(),
              [&](float x) {
                  sum += x; // 数据竞争
              });

并行算法里最重要的一条规则：

每个迭代最好只操作自己拥有的数据，不要随手写共享状态。

4. 用 `reduce` 替代共享累加

不要在 for_each(par) 里写共享 sum。
用 std::reduce：

#include <execution>
#include <functional>
#include <numeric>
#include <vector>

float sum(const std::vector<float>& a) {
    return std::reduce(std::execution::par,
                       a.begin(), a.end(),
                       0.0f);
}

reduce 和 accumulate 的关键区别：

accumulate 严格按顺序从左到右
reduce 允许重排和分块合并

所以 reduce 更适合并行，但结果可能不逐位等同于顺序浮点求和。

5. `transform_reduce`：map + reduce 合在一起

点积：

#include <execution>
#include <numeric>
#include <vector>

float dot(const std::vector<float>& a,
          const std::vector<float>& b) {
    return std::transform_reduce(std::execution::par,
                                 a.begin(), a.end(),
                                 b.begin(),
                                 0.0f,
                                 std::plus<>{},
                                 std::multiplies<>{});
}

等价于：

1	sum += a[i] * b[i]

但实现可以：

分块
局部求和
最后合并
可能向量化

这是数值代码里非常常用的模式。

6. `transform`：并行生成输出

逐元素计算：

std::transform(std::execution::par,
               x.begin(), x.end(),
               y.begin(),
               out.begin(),
               [](float a, float b) {
                   return a * a + b;
               });

安全前提：

输出范围足够大
输入输出重叠关系符合算法要求
lambda 不修改共享状态
每个输出元素只由一个迭代写入

在高性能 C++ 中，这类“输入数组到输出数组”的形式非常适合：

SIMD
GPU
TBB
标准并行算法

因为数据流清楚，副作用少。

7. `sort` 也有并行版本

#include <algorithm>
#include <execution>
#include <vector>

void sort_data(std::vector<int>& a) {
    std::sort(std::execution::par, a.begin(), a.end());
}

注意：

并行 sort 可能消耗更多临时内存
小数组不一定更快
比较函数必须是严格弱序
比较函数不要有共享副作用

危险比较函数：

int count = 0;

std::sort(std::execution::par,
          a.begin(), a.end(),
          [&](int x, int y) {
              ++count;        // 数据竞争
              return x < y;
          });

比较函数应该像纯函数一样使用。

8. scan：前缀和

前缀和是并行算法里的经典基础操作。

输入：

1 2 3 4

inclusive scan：

1 3 6 10

exclusive scan：

0 1 3 6

C++ 写法：

#include <execution>
#include <numeric>
#include <vector>

std::vector<int> in{1, 2, 3, 4};
std::vector<int> out(in.size());

std::inclusive_scan(std::execution::par,
                    in.begin(), in.end(),
                    out.begin());

scan 常用于：

压缩数组
stream compaction
构建偏移表
稀疏数据结构
GPU 并行算法

9. `par_unseq` 的限制更严格

par_unseq 允许并行和向量化，意味着不同迭代之间：

可能并行
可能交错
可能无序
可能在同一线程内以 SIMD lane 执行

所以 lambda 里不要做这些事：

加锁
等待条件变量
访问线程局部但有顺序依赖的状态
修改共享非原子变量
依赖执行顺序
调用不适合向量化的复杂副作用函数

适合 par_unseq 的形状：

std::transform(std::execution::par_unseq,
               a.begin(), a.end(),
               b.begin(),
               c.begin(),
               [](float x, float y) {
                   return x + y;
               });

不适合：

std::for_each(std::execution::par_unseq,
              a.begin(), a.end(),
              [&](float x) {
                  std::lock_guard<std::mutex> lk(m);
                  log.push_back(x);
              });

如果 lambda 里需要锁，通常就不该用 par_unseq。

10. 异常处理要特别注意

使用标准执行策略时，如果并行算法中的函数对象抛出异常，程序可能调用 std::terminate。
这和普通顺序算法的异常传播直觉不同。

所以并行算法里的 callable 最好满足：

不抛异常
不做复杂资源操作
不把错误藏在共享状态里

如果确实需要错误处理，常见做法：

在函数对象内部捕获异常
写入线程安全错误标志
算法结束后统一检查

但这会增加复杂度，也可能影响性能。
热路径里更常见的是让输入先被验证好。

11. 迭代器和数据结构选择

并行算法最喜欢：

std::vector
std::array
连续内存
随机访问迭代器
每个元素处理成本相近

不太适合：

链表
大量指针追逐
迭代器解引用很贵的结构
每个元素工作量差异巨大
需要频繁共享写的数据结构

虽然有些算法只要求 ForwardIterator，但从性能角度看，连续数组仍然是第一选择。

12. 并行算法和数据竞争

标准并行算法不会自动保护你的共享数据。

安全：

std::transform(std::execution::par,
               in.begin(), in.end(),
               out.begin(),
               [](int x) {
                   return x * 2;
               });

危险：

std::vector<int> out;

std::for_each(std::execution::par,
              in.begin(), in.end(),
              [&](int x) {
                  out.push_back(x * 2); // 数据竞争
              });

更好的做法：

std::vector<int> out(in.size());

std::transform(std::execution::par,
               in.begin(), in.end(),
               out.begin(),
               [](int x) {
                   return x * 2;
               });

核心原则：

并行算法优先写“已分配好的输出位置”，不要在热路径里共享 push_back。

13. 确定性和浮点误差

并行算法可能改变操作顺序。
整数加法在不溢出的理想数学意义下问题不大，但 C++ 有类型边界和溢出规则。
浮点更明显：

1 2	auto s1 = std::accumulate(a.begin(), a.end(), 0.0); auto s2 = std::reduce(std::execution::par, a.begin(), a.end(), 0.0);

s1 和 s2 可能不逐位相同。

如果你需要：

完全可复现
严格顺序结果
数值误差受控

就要慎用并行归约，或者使用确定性归约策略。

14. 什么时候标准并行算法很合适

适合：

对连续数组做逐元素变换
简单归约
点积、范数、统计量
排序
scan
没有复杂副作用的批处理

典型场景：

std::transform(std::execution::par_unseq, ...);
std::reduce(std::execution::par, ...);
std::transform_reduce(std::execution::par, ...);
std::sort(std::execution::par, ...);

这种代码表达清楚，可读性高，也方便先写顺序版再切策略。

15. 什么时候更适合 TBB 或手写调度

更适合 TBB：

需要控制 grain size
需要任务嵌套
需要 pipeline
需要 task arena 限制并行度
需要 thread local / combinable
需要更清楚的负载均衡策略
需要和已有 TBB 系统融合

更适合手写同步：

少量长期 worker
特定资源生命周期
特定低延迟通信协议
自定义 lock-free 结构

经验：

标准并行算法适合“形状规则”的数据并行；TBB 适合“调度复杂”的任务并行。

16. 性能检查清单

使用标准并行算法后，至少检查：

是否真的比 seq 快
小数据规模是否被调度开销拖慢
callable 是否无共享副作用
输入输出是否连续
是否有 false sharing
浮点结果是否允许重排误差
标准库实现是否真的启用了并行后端
线程数是否和其他线程池冲突

一个常用对照实验：

1
2
3

auto r1 = std::reduce(std::execution::seq, a.begin(), a.end(), 0.0);
auto r2 = std::reduce(std::execution::par, a.begin(), a.end(), 0.0);
auto r3 = std::reduce(std::execution::par_unseq, a.begin(), a.end(), 0.0);

同时比较：

耗时
结果误差
CPU 使用率
profiler 热点

17. 常见误区

17.1 “加上 `par` 就一定多线程”

不一定。
标准允许并行，但实现可以根据情况选择策略。

17.2 “并行算法会自动避免数据竞争”

不会。
lambda 里的共享写仍然是你的责任。

17.3 “`reduce` 和 `accumulate` 完全一样”

不一样。
reduce 允许重排，适合并行；accumulate 是顺序左折叠。

17.4 “`par_unseq` 是最快的默认选择”

不是。
它限制最多，而且对 callable 要求更严格。

17.5 “标准算法能替代所有并行框架”

不能。
复杂调度、pipeline、NUMA-aware 设计仍然需要更强的框架或工程代码。

18. 一页总结

标准库并行算法的核心理解链：

用执行策略表达顺序、并行、向量化意图
用 transform/reduce/scan/sort 表达规则数据并行
callable 尽量无副作用
输出位置提前分配，避免共享 push_back
浮点归约要接受重排误差
是否真的并行和更快，要靠 benchmark 验证

一句话：

标准并行算法最适合把规则数组计算写得清楚；一旦调度和局部性成为主角，就该考虑 TBB 或更专门的方案。

19. 建议继续补充的相关主题

和本篇衔接最紧密的内容：

reduce / transform_reduce 的数值稳定性
par_unseq 与 SIMD 自动向量化
标准库并行后端差异
TBB 与标准算法的替换边界
ranges 与并行算法的组合限制

20. 参考资料

cppreference: execution policy
https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag
cppreference: std::reduce
https://en.cppreference.com/w/cpp/algorithm/reduce
cppreference: std::transform_reduce
https://en.cppreference.com/w/cpp/algorithm/transform_reduce
cppreference: numeric operations
https://en.cppreference.com/w/cpp/algorithm#Numeric_operations

标准库并行算法与执行策略

1. 为什么需要标准库并行算法

2. 执行策略有哪些

3. 第一个并行 for_each

4. 用 reduce 替代共享累加

5. transform_reduce：map + reduce 合在一起

6. transform：并行生成输出

7. sort 也有并行版本

8. scan：前缀和

9. par_unseq 的限制更严格

10. 异常处理要特别注意

11. 迭代器和数据结构选择

12. 并行算法和数据竞争

13. 确定性和浮点误差

14. 什么时候标准并行算法很合适

15. 什么时候更适合 TBB 或手写调度

16. 性能检查清单

17. 常见误区

17.1 “加上 par 就一定多线程”

17.2 “并行算法会自动避免数据竞争”

17.3 “reduce 和 accumulate 完全一样”

17.4 “par_unseq 是最快的默认选择”

17.5 “标准算法能替代所有并行框架”

18. 一页总结

19. 建议继续补充的相关主题

20. 参考资料

3. 第一个并行 `for_each`

4. 用 `reduce` 替代共享累加

5. `transform_reduce`：map + reduce 合在一起

6. `transform`：并行生成输出

7. `sort` 也有并行版本

9. `par_unseq` 的限制更严格

17.1 “加上 `par` 就一定多线程”

17.3 “`reduce` 和 `accumulate` 完全一样”

17.4 “`par_unseq` 是最快的默认选择”