C++并行算法执行策略-execution深度解析
C++17 标准引入了一个重要特性：执行策略 (Execution Policies)。这允许开发者指定标准库算法（主要在 <algorithm> 和 <numeric> 中）应该如何执行，特别是能否并行或向量化执行。这为利用现代多核处理器和SIMD指令集提供了标准化的方式，从而可能显著提高代码性能。
<execution> 头文件定义了相关的执行策略类型。
简介
在C++17之前，标准库算法通常是顺序执行的。如果需要并行化，开发者不得不依赖特定平台的库（如OpenMP, TBB）或手动管理线程。执行策略的引入，使得并行化成为C++标准的一部分，增强了代码的可移植性和易用性。
执行策略作为算法的第一个参数传递，告知编译器和库实现者可以采用的执行方式。
执行策略类型
<execution> 头文件定义了以下执行策略对象（它们是具有特定类型的全局常量对象）：
std::execution::sequenced_policy(std::execution::seq)
这是默认策略，表示算法应按顺序执行，与C++17之前的行为一致。不允许并行或向量化。
#include <execution>
// ...
std::sort(std::execution::seq, my_vector.begin(), my_vector.end());std::execution::parallel_policy(std::execution::par)
表示算法的执行可以并行化。实现可以将工作划分到多个线程上执行。元素的处理顺序是不确定的。如果一个操作抛出异常，程序将调用 std::terminate。
#include <execution>
// ...
std::sort(std::execution::par, my_vector.begin(), my_vector.end());std::execution::parallel_unsequenced_policy(std::execution::par_unseq)
表示算法的执行不仅可以并行化，还可以在每个线程内进行向量化（例如使用SIMD指令）。这是约束最少的策略，给予实现最大的自由度来优化性能。与 par 类似，未捕获的异常会导致 std::terminate。此策略要求操作不能有线程间的同步（如互斥锁）。
#include <execution>
// ...
std::for_each(std::execution::par_unseq, data.begin(), data.end(), some_operation);std::execution::unsequenced_policy(std::execution::unseq) (C++20)
表示算法的执行可以向量化，但不能在多个线程上并行执行。这意味着操作将在调用线程上执行，但可以乱序或交错执行，以利用SIMD。与 par_unseq 类似，要求操作不能有线程间的同步。
#include <execution>
// ...
// Assuming an algorithm supports unseq (many do from C++20 onwards)
// std::transform(std::execution::unseq, ...);如何使用执行策略
将执行策略对象作为支持它的算法的第一个参数传递即可。
#include <vector>
#include <algorithm>
#include <numeric> // For std::reduce
#include <execution>
#include <iostream>
int main() {
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
// 顺序排序
// std::sort(v.begin(), v.end()); // Old way
std::vector<int> v_seq = v;
std::sort(std::execution::seq, v_seq.begin(), v_seq.end());
std::cout << "Sequentially sorted: ";
for (int x : v_seq) std::cout << x << " ";
std::cout << std::endl;
// 并行排序
std::vector<int> v_par = v;
std::sort(std::execution::par, v_par.begin(), v_par.end());
std::cout << "Parallel sorted: ";
for (int x : v_par) std::cout << x << " ";
std::cout << std::endl;
// 并行求和 (std::reduce is the parallel-friendly version of std::accumulate)
long long sum = std::reduce(std::execution::par, v.begin(), v.end(), 0LL);
std::cout << "Parallel sum: " << sum << std::endl;
return 0;
}支持执行策略的算法
C++17 标准中，许多 <algorithm> 和 <numeric> 中的算法被重载以接受执行策略。并非所有算法都支持所有策略。常见的支持算法包括（但不限于）：
- adjacent_difference, adjacent_find
- all_of, any_of, none_of
- count, count_if
- copy, copy_if, copy_n
- equal
- fill, fill_n
- find, find_if, find_if_not, find_end, find_first_of
- for_each, for_each_n
- generate, generate_n
- includes
- inner_product
- inplace_merge
- is_heap, is_heap_until, is_partitioned, is_sorted, is_sorted_until
- lexicographical_compare
- max_element, min_element, minmax_element
- merge
- mismatch
- move
- nth_element
- partial_sort, partial_sort_copy
- partition, stable_partition, partition_copy
- reduce (C++17, 替代 accumulate 的并行版本)
- remove, remove_if, remove_copy, remove_copy_if
- replace, replace_if, replace_copy, replace_copy_if
- reverse, reverse_copy
- rotate, rotate_copy
- search, search_n
- set_difference, set_intersection, set_symmetric_difference, set_union
- sort, stable_sort
- transform
- transform_reduce (C++17)
- unique, unique_copy
通常，如果一个算法的并行版本有意义且可以安全实现，标准库会提供相应的重载。具体哪些算法支持哪些策略，应查阅最新的C++标准文档或编译器/库文档。
使用自定义函数对象的要求
当使用并行策略 (par, par_unseq, unseq) 时，传递给算法的函数对象（如谓词、比较器、操作函数）必须满足更严格的要求，以避免未定义行为：
数据竞争
- 无数据竞争: 函数对象的调用（包括其内部操作）不能引入数据竞争。这意味着：
- 如果函数对象修改共享状态，必须通过原子操作或适当的同步机制（尽管 par_unseq 和 unseq 通常禁止大多数同步原语）。
- 访问序列中的元素通常是安全的，因为算法会确保对不同元素的并发访问是安全的（例如，std::sort 的并行版本会正确处理元素交换）。但是，如果函数对象通过捕获的引用访问外部共享数据，则需要用户自己保证线程安全。
异常处理
- std::terminate: 如果在使用 par 或 par_unseq 策略时，用户提供的函数对象抛出未被捕获的异常，程序的行为是调用 std::terminate。这意味着你不能依赖常规的 try-catch 块来处理从并行算法内部抛出的异常并期望程序继续正常执行。如果需要复杂的错误处理，可能需要将错误状态通过其他方式传出（例如，写入线程局部存储或原子标志）。
- seq 策略下的异常行为与传统算法相同（异常可以被捕获和处理）。
- unseq 策略下，如果异常抛出，行为也是 std::terminate。
元素访问顺序和依赖
- 独立性: 对于 par, par_unseq, unseq 策略，函数对象对一个元素的操作不应该依赖于对其他元素的操作顺序或副作用。算法可以以任意顺序处理元素。
- 例如，在 std::transform 中，计算目标元素 output[i] 的操作不应依赖于 output[j] (其中 i != j) 的计算结果或状态。
向前进度保证
- 无死锁: 用户提供的函数对象不应导致死锁。特别是对于 par_unseq 和 unseq，它们通常不允许函数对象内部使用可能导致阻塞的同步原语（如互斥锁）。
简而言之，用于并行执行的函数对象应该是“纯粹的”或至少是线程安全的，并且不依赖于特定的执行顺序。
示例
并行排序 (std::sort)
#include <vector>
#include <algorithm>
#include <execution>
#include <random> // For generating random data
#include <iostream>
int main() {
std::vector<int> data(1000000);
std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<> distrib(1, 100000);
std::generate(std::execution::par, data.begin(), data.end(), [&](){ return distrib(gen); });
auto start_time = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par, data.begin(), data.end());
auto end_time = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
std::cout << "Parallel sort took: " << duration.count() << " ms\n";
// Verify (optional)
// if (!std::is_sorted(data.begin(), data.end())) {
// std::cerr << "Sort failed!\n";
// }
return 0;
}并行转换 (std::transform)
#include <vector>
#include <algorithm>
#include <execution>
#include <iostream>
int main() {
std::vector<double> input = {1.0, 2.0, 3.0, 4.0, 5.0, /* ... many more ... */};
input.resize(1000000, 1.0); // Example large vector
std::vector<double> output(input.size());
// Apply a potentially expensive operation in parallel
std::transform(std::execution::par_unseq, input.begin(), input.end(), output.begin(),
[](double val) {
// Simulate some work
double res = val;
for (int i = 0; i < 10; ++i) res = std::sin(res) + std::cos(res);
return res;
});
std::cout << "Transform completed. Output[0] = " << output[0] << std::endl;
return 0;
}并行求和 (std::reduce)
std::reduce (C++17) 是 std::accumulate 的并行版本。std::accumulate 本身不保证并行安全，因为它通常按顺序处理元素。
#include <vector>
#include <numeric> // For std::reduce, std::iota
#include <execution>
#include <iostream>
int main() {
std::vector<long long> nums(10000000);
std::iota(nums.begin(), nums.end(), 1); // Fill with 1, 2, 3, ...
long long sum = std::reduce(std::execution::par, nums.begin(), nums.end(), 0LL, std::plus<long long>());
// The initial value is 0LL (long long zero)
// The binary operation is std::plus<long long>()
std::cout << "Sum: " << sum << std::endl;
return 0;
}注意事项和最佳实践
- 性能并非总是提升: 对于小数据集或非常轻量级的操作，并行化的开销（线程创建、同步、任务划分）可能超过其带来的收益，甚至导致性能下降。应进行基准测试以确定并行化是否有利。
- 开销问题: std::execution::par_unseq 给予实现最大的自由度，但也可能引入最高的调度开销。std::execution::unseq (C++20) 旨在提供向量化而不引入多线程开销，适用于某些场景。
- 调试难度: 调试并行代码通常比调试顺序代码更复杂。数据竞争和死锁等问题可能难以复现和定位。
- 编译器和库支持: 确保你的编译器和标准库实现完全支持C++17/C++20的执行策略。支持程度可能因平台和版本而异。
- 选择合适的策略:
- seq: 用于保证顺序执行或当并行化不适用/不安全时。
- par: 当操作是线程安全的，并且可以从多线程中受益，但不需要或不能进行向量化时。
- par_unseq: 当操作既线程安全又可向量化，并且没有线程间同步时。这是最具潜力的性能选项，但也要求最严格。
- unseq: 当操作可向量化，但希望避免多线程开销或需要在单个线程内执行时。
- Lambda 捕获: 小心 Lambda 表达式的捕获。按引用捕获可能导致数据竞争，除非被引用的对象是线程本地的或其访问是同步的（但同步在 par_unseq/unseq 中受限）。按值捕获通常更安全。
- 资源限制: 过度并行化可能耗尽系统资源（如线程池）。标准库实现通常会管理一个全局或默认的线程池，但其行为可能不可配置或不透明。
总结
C++执行策略为标准库算法的并行化和向量化提供了一个强大且可移植的机制。通过明智地选择执行策略并确保用户提供的代码满足相关要求（尤其是无数据竞争和异常处理），开发者可以更容易地利用现代硬件的并行能力来提升应用程序性能。然而，性能提升并非必然，务必通过分析和基准测试来验证并行化的效果。
