并行算法(Parallel Algorithms)
什么是并行算法
C++17 为标准库中的大量算法(<algorithm>、<numeric>)添加了并行版本。使用方式非常简单:在原有算法调用的第一个参数位置传入一个"执行策略"(execution policy),算法就可以在多个线程上并行执行。
// 传统顺序排序
std::sort(vec.begin(), vec.end());
// C++17 并行排序——只多了一个参数
std::sort(std::execution::par, vec.begin(), vec.end());这是 C++ 标准库首次在语言层面直接支持并行计算。在此之前,开发者要么手动管理线程,要么依赖 OpenMP、Intel TBB 等第三方库来并行化算法。C++17 的并行算法让多核利用变得和添加一个参数一样简单。
同时,C++17 还引入了几个全新的算法(std::reduce、std::transform_reduce、std::inclusive_scan、std::exclusive_scan 等),它们是专门为并行场景设计的,对操作的结合律和交换律有明确的要求。
头文件
#include <algorithm> // sort, for_each, find, count 等
#include <numeric> // reduce, transform_reduce, inclusive_scan 等
#include <execution> // 执行策略:seq, par, par_unseq执行策略
| 策略 | 对象 | 说明 |
|---|---|---|
| 顺序执行 | std::execution::seq | 和不带策略的版本行为相同,单线程顺序执行 |
| 并行执行 | std::execution::par | 可以在多个线程上执行,但每个线程内是顺序的 |
| 并行非顺序执行 | std::execution::par_unseq | 可以多线程 + SIMD 向量化,最大自由度 |
| 非顺序执行 | std::execution::unseq(C++20) | 单线程但允许 SIMD 向量化 |
关键限制:
par:元素访问函数不能引起数据竞争,但可以使用锁(mutex)par_unseq:元素访问函数不能引起数据竞争,也不能使用锁(因为同一线程可能交错执行不同元素的操作,用锁会死锁)- 并行算法中如果元素访问函数抛出异常,会调用
std::terminate
基本示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <execution>
#include <random>
#include <chrono>
#include <string>
// 计时辅助函数
template<typename Func>
auto measure(const std::string& name, Func f) {
auto start = std::chrono::high_resolution_clock::now();
auto result = f();
auto end = std::chrono::high_resolution_clock::now();
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << name << ": " << ms << " ms" << std::endl;
return result;
}
// ============================
// 示例1:并行排序
// ============================
void parallel_sort_demo() {
const int N = 10'000'000;
std::vector<int> data(N);
std::mt19937 gen{42};
std::generate(data.begin(), data.end(), gen);
// 拷贝一份用于并行排序
auto data_par = data;
// 顺序排序
measure("顺序 sort", [&data]() {
std::sort(std::execution::seq, data.begin(), data.end());
return data.size();
});
// 并行排序
measure("并行 sort", [&data_par]() {
std::sort(std::execution::par, data_par.begin(), data_par.end());
return data_par.size();
});
// 验证结果一致
std::cout << "结果一致? " << std::boolalpha << (data == data_par) << std::endl;
}
// ============================
// 示例2:并行 for_each
// ============================
void parallel_for_each_demo() {
const int N = 10'000'000;
std::vector<double> data(N, 1.0);
// 并行地对每个元素执行操作
std::for_each(std::execution::par, data.begin(), data.end(),
[](double& x) {
// 模拟一些计算
x = std::sin(x) * std::cos(x) + std::sqrt(x);
});
std::cout << "for_each 结果[0]: " << data[0] << std::endl;
}
// ============================
// 示例3:std::reduce(并行求和)
// ============================
void reduce_demo() {
const int N = 10'000'000;
std::vector<double> data(N, 0.5);
// std::accumulate 是严格顺序的(从左到右),不能并行
double sum_seq = std::accumulate(data.begin(), data.end(), 0.0);
// std::reduce 允许乱序组合(要求操作满足结合律和交换律)
double sum_par = std::reduce(std::execution::par, data.begin(), data.end(), 0.0);
std::cout << "accumulate: " << sum_seq << std::endl;
std::cout << "reduce: " << sum_par << std::endl;
// 两者结果可能略有不同(浮点数加法不严格满足结合律)
}
// ============================
// 示例4:std::transform_reduce(Map-Reduce)
// ============================
void transform_reduce_demo() {
const int N = 1'000'000;
std::vector<int> data(N);
std::iota(data.begin(), data.end(), 1); // 1, 2, 3, ..., N
// 计算所有元素平方和:先 transform(平方)再 reduce(求和)
long long sum_of_squares = std::transform_reduce(
std::execution::par,
data.begin(), data.end(),
0LL, // 初始值
std::plus<>{}, // reduce 操作(加法)
[](int x) -> long long { return static_cast<long long>(x) * x; } // transform 操作(平方)
);
std::cout << "1~" << N << " 的平方和: " << sum_of_squares << std::endl;
// 向量点积(两个范围的 transform_reduce)
std::vector<double> a{1.0, 2.0, 3.0, 4.0};
std::vector<double> b{5.0, 6.0, 7.0, 8.0};
double dot_product = std::transform_reduce(
std::execution::par,
a.begin(), a.end(),
b.begin(),
0.0 // 初始值
// 默认:reduce 用 +,transform 用 *
);
std::cout << "点积: " << dot_product << std::endl; // 1*5 + 2*6 + 3*7 + 4*8 = 70
}
// ============================
// 示例5:并行 count_if / find_if
// ============================
void parallel_search_demo() {
const int N = 10'000'000;
std::vector<int> data(N);
std::mt19937 gen{42};
std::generate(data.begin(), data.end(), [&gen]() { return gen() % 1000; });
// 并行计数
auto count = std::count_if(std::execution::par, data.begin(), data.end(),
[](int x) { return x > 500; });
std::cout << "大于500的个数: " << count << std::endl;
// 并行查找
auto it = std::find_if(std::execution::par, data.begin(), data.end(),
[](int x) { return x == 999; });
if (it != data.end()) {
std::cout << "找到999,位置: " << std::distance(data.begin(), it) << std::endl;
}
}
// ============================
// 示例6:inclusive_scan / exclusive_scan(前缀和)
// ============================
void scan_demo() {
std::vector<int> input{1, 2, 3, 4, 5};
std::vector<int> inclusive_result(5);
std::vector<int> exclusive_result(5);
// inclusive_scan:第 i 个输出 = input[0] + input[1] + ... + input[i]
std::inclusive_scan(std::execution::par,
input.begin(), input.end(),
inclusive_result.begin());
// 结果: {1, 3, 6, 10, 15}
// exclusive_scan:第 i 个输出 = init + input[0] + ... + input[i-1]
std::exclusive_scan(std::execution::par,
input.begin(), input.end(),
exclusive_result.begin(),
0); // 初始值
// 结果: {0, 1, 3, 6, 10}
std::cout << "inclusive_scan: ";
for (auto x : inclusive_result) std::cout << x << " ";
std::cout << std::endl;
std::cout << "exclusive_scan: ";
for (auto x : exclusive_result) std::cout << x << " ";
std::cout << std::endl;
}
int main() {
std::cout << "=== 并行排序 ===" << std::endl;
parallel_sort_demo();
std::cout << "\n=== 并行 for_each ===" << std::endl;
parallel_for_each_demo();
std::cout << "\n=== reduce ===" << std::endl;
reduce_demo();
std::cout << "\n=== transform_reduce ===" << std::endl;
transform_reduce_demo();
std::cout << "\n=== 并行查找 ===" << std::endl;
parallel_search_demo();
std::cout << "\n=== scan ===" << std::endl;
scan_demo();
return 0;
}std::accumulate vs std::reduce
| 特性 | std::accumulate | std::reduce |
|---|---|---|
| 头文件 | <numeric> | <numeric> |
| 执行顺序 | 严格从左到右 | 任意顺序 |
| 支持并行 | 不支持 | 支持(接受执行策略) |
| 对操作的要求 | 无(任意二元操作) | 结合律 + 交换律 |
| 浮点求和结果 | 确定性(同一输入同一结果) | 可能有细微差异 |
C++17 新增的并行算法
| 算法 | 说明 |
|---|---|
std::reduce | 乱序归约(并行版 accumulate) |
std::transform_reduce | 先变换再归约(Map-Reduce 模式) |
std::inclusive_scan | 包含当前元素的前缀和 |
std::exclusive_scan | 不包含当前元素的前缀和 |
std::transform_inclusive_scan | 先变换再做包含前缀和 |
std::transform_exclusive_scan | 先变换再做排除前缀和 |
std::for_each_n | 对前 n 个元素执行操作 |
适用场景
- 大数据量的排序(百万级以上元素并行排序提速明显)
- 大规模数值计算(向量运算、矩阵操作的求和/变换)
- 数据过滤和统计(count_if、find_if 在大数据集上并行)
- 图像处理(对每个像素并行执行变换)
- 科学计算中的 Map-Reduce 模式
常见问题
并行算法一定比顺序快吗?
不一定。并行有线程创建和同步的开销。对于小数据集(几千个元素以下),并行版本通常比顺序版本更慢。经验法则是数据量超过几万、且每个元素的操作有一定计算量时,并行才有收益。排序这种 O(n log n) 的算法在大数据量下并行收益比较大。
std::reduce 和 std::accumulate 结果为什么可能不同?
因为浮点数加法不严格满足结合律。accumulate 严格从左到右累加,reduce 可能把元素分成多组分别求和再合并。不同的分组方式导致浮点舍入误差的累积方式不同,最终结果可能有微小差异。对于整数运算,两者结果完全相同。
par_unseq 和 par 有什么区别?
par 允许多线程但每个线程内顺序执行;par_unseq 还允许 SIMD 向量化(同一线程内交错执行不同元素的操作)。par_unseq 更严格:你的操作不能使用互斥锁(可能死锁),不能有信号处理相关的操作。如果不确定,先用 par。
哪些标准库算法支持并行?
大部分 <algorithm> 和 <numeric> 中的算法都有并行版本,包括 sort、stable_sort、for_each、transform、find、count、reduce、all_of、any_of、none_of、equal、mismatch、remove、remove_if、search 等。完整列表请查看编译器文档。
注意事项
- 并行算法中的元素访问函数不能引起数据竞争(不要修改共享状态)
- 使用
par_unseq时不能在元素访问函数中加锁 - 并行算法中抛出的异常会导致
std::terminate,不会被 catch std::reduce要求操作满足结合律和交换律,否则结果不确定- 小数据集不要用并行——线程开销可能大于并行收益
- 不同编译器的并行实现差异很大:MSVC 使用 Windows 线程池,GCC 依赖 Intel TBB
- GCC 使用并行算法需要链接 TBB 库(
-ltbb)
编译器支持与依赖
| 编译器 | 最低支持版本 | 额外依赖 |
|---|---|---|
| GCC | 9.0 | 需要安装并链接 Intel TBB(-ltbb) |
| Clang | 17.0(部分) | 依赖 libc++ 或 libstdc++ 的支持 |
| MSVC | 19.14 (VS 2017 15.7) | 无额外依赖,使用 Windows 线程池 |
总结
C++17 的并行算法是标准库中最具影响力的新增功能之一。通过在算法调用中添加一个执行策略参数(std::execution::par),现有的排序、查找、变换、归约等算法就能利用多核并行执行。同时新增的 std::reduce、std::transform_reduce、std::inclusive_scan 等算法专为并行设计,提供了 Map-Reduce 和前缀和等常见并行计算模式。使用时需要注意:小数据集不值得并行,元素访问函数不能有数据竞争,浮点运算的并行归约可能有微小精度差异。目前 MSVC 的支持最完善,GCC 需要依赖 TBB 库。