Modern C++中 STL 算法的执行策略
1. 引言
C++的<algorithm>提供了一系列通用的算法，这些算法可以与各种容器（如vector、list、array等）以及其他可迭代的数据结构一起使用。这些算法涵盖了从基本操作（如复制、查找、替换）到更复杂的操作（如排序、合并、堆操作）等多个方面。这些算法都接受迭代器作为参数，这使得它们可以与各种容器和可迭代对象一起使用。同时，从C++17开始，引入了执行策略（std::execution），该策略决定了它们的执行方式以及与底层硬件的交互方式，允许开发者指定算法的执行方式。
大多数算法拥有接受执行策略的重载。标准库中提供了相应的执行策略类型和对象。用户可以通过以对应类型的执行策略对象为参数调用并行算法，静态地选择执行策略。C++ 17 标准引入了三个新的执行策略，并在 C++20 中引入了一个策略。C++ 中的这些执行策略允许根据任务的要求和可用的硬件以不同的方式执行算法。它们如下：
sequenced_policy：串行执行策略（C++17）parallel_policy：并行执行策略（C++17）parallel_unsequenced_policy：并行无序执行策略（C++17）unsequenced_policy：无序执行策略（C++20）
其对应的策略实例分别为：
std::execution::seqstd::execution::parstd::execution::par_unseqstd::execution::unseq
这些实例用于指定并行算法的执行策略——即允许采用何种并行运算。
C++的执行策略是一种编程模式，它允许开发者指定如何执行特定的操作或算法，而不必关心底层的实现细节。这种策略模式为算法提供了灵活性，使得算法可以与不同的执行策略结合使用，从而实现并行、串行、延迟执行等不同的行为。
2. 执行策略
2.1 串行策略sequenced_policy
std::execution::sequenced_policy用来指定算法应按顺序执行，即不进行并行化。如果未指定执行策略，则算法将按顺序执行。
用法
通常将sequenced_policy类的实例std::execution::seq 作为算法的第一个参数传递，以指示算法应以顺序方式执行。其形式如下
STLFunction (std::execution::seq, ...other_arguments...);
这种策略适用于那些需要操作之间保持严格顺序的算法，或者当并行执行可能引入竞争条件或未定义行为时。
示例：
#include <algorithm>
#include <iostream>
#include <vector>
#include <execution>
int main()
{
std::vector<int> v = {5, 2, 3, 1, 4};
std::sort(std::execution::seq, v.begin(), v.end());
for (auto i : v)
std::cout << i << " ";
return 0;
}
输出：
1 2 3 4 5
优劣
优势 | 劣势 |
|---|---|
简单且可预测。避免数据争用。适用于小型任务，不存在并行开销。 | 对于大型任务效率不高。 |
应用场景
串行策略的应用场景通常包括：
- 顺序依赖的算法：当算法的操作之间存在顺序依赖关系时，即后续操作依赖于前一个操作的结果时，必须使用顺序执行策略。
- 调试和测试：在开发和调试阶段，使用顺序执行策略可以确保算法的正确性，因为它避免了并行执行可能引入的竞争条件或未定义行为。
- 单线程环境：在单线程环境中，算法只能顺序执行。使用
std::execution::sequenced_policy可以明确指示这一点，并且允许算法在将来更容易地迁移到支持并行执行的环境。 - 简单性和一致性：对于不需要并行化加速的简单算法，或者当并行执行不会带来性能提升时，使用顺序执行策略可以保持代码的简单性和一致性。
需要注意的是，虽然
std::execution::sequenced_policy指定了顺序执行，但它仍然允许算法实现使用任何同步机制来优化性能，只要这些优化不会改变操作的顺序。因此，即使指定了顺序执行策略，算法的实际执行仍然可能受到底层实现优化的影响。
2.2 并行策略parallel_policy
std::execution::parallel_policy用来指定算法应并行执行，即使用多个线程。但该标准没有指定应该使用的线程数。使用其作为算法的执行策略，通常是为了利用多核处理器或其他并行硬件来加速算法的执行。这种策略特别适用于那些可以并行化且没有严格顺序依赖关系的算法。
用法
将parallel_policy类的实例std::execution::par作为参数传递给 STL 算法函数。其形式如下
STLFunction (std::execution::par, ...other_arguments...);
示例：
#include <algorithm>
#include <execution>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v1 = { 1, 2, 3, 4, 5 };
std::vector<int> v2(5);
std::transform(std::execution::par, v1.begin(),
v1.end(), v2.begin(),
[](int x) { return x * x; });
for (int i : v2) {
std::cout << i << " ";
}
return 0;
}
输出：
1 4 9 16 25
优劣
优势 | 劣势 |
|---|---|
更快地执行大型任务，在多核系统下的效率最佳。 | 可能会引入开销。由于这种开销，可能并不总是比顺序执行快，也可能引入竞争。 |
应用场景
并行策略的应用场景通常包括：
- 计算密集型任务：对于计算量大且可以并行化的任务，使用并行执行策略可以显著提高程序的执行速度。
- 多核处理器优化：在现代多核处理器上，通过并行执行策略可以充分利用所有可用的核心，从而提高程序的性能。
- 数据并行处理：当需要对大量数据进行相同或类似的操作时，使用并行执行策略可以加快数据处理的速度。
- 算法优化：对于某些算法，如排序、搜索或图形处理算法，通过并行化可以显著提高算法的效率。 需要注意的是，使用并行执行策略时，必须确保算法的操作是线程安全的，并且没有数据竞争或其他并发问题。此外，并行执行可能会导致操作的顺序与顺序执行时不同，这可能会影响算法的正确性。因此，在使用并行执行策略时，需要仔细考虑算法的语义和并行化对程序的影响。
2.3 并行无序策略parallel_unsequenced_policy
使用 std::execution::parallel_unsequenced_policy 通常是为了最大化并行性能，特别是在处理可以并行化且不需要保持特定顺序的任务时。这种策略允许算法实现选择任何合适的并行执行模型，包括使用SIMD（单指令多数据）指令集进行向量化执行。
用法
通常将parallel_unsequenced_policy类的实例std::execution::par_unseq 作为算法的第一个参数传递，其形式如下
STLFunction (std::execution::par_unseq, ...other_arguments...);
示例：
#include <algorithm>
#include <iostream>
#include <vector>
#include <execution>
int main()
{
std::vector<int> v = { 1, 2, 3, 4, 5 };
std::for_each(std::execution::par_unseq, v.begin(),
v.end(),
[](int x) { std::cout << x << " "; });
return 0;
}
输出：
1 2 3 4 5
优劣
优势 | 劣势 |
|---|---|
加快重复性操作的执行速度。 可以在带有矢量指令的硬件上使用。 | 不适合所有任务，并非所有硬件都支持。 |
应用场景
并行无序策略的应用场景通常包括：
- 高度并行化任务：当算法的操作可以完全并行执行，并且不需要保持任何特定的顺序时，使用这种策略可以最大化并行性能。
- SIMD优化：对于可以利用SIMD指令集进行向量化执行的任务，使用
std::execution::parallel_unsequenced_policy可以允许算法实现选择使用这些指令来提高性能。 - 数据并行处理：在处理大型数据集时，尤其是当数据集可以被划分为独立的部分并并行处理时，这种策略非常有用。
- 性能优化：对于需要高性能的场景，如科学计算、图像处理或机器学习，使用
std::execution::parallel_unsequenced_policy可以帮助实现更高效的算法。 需要注意的是，由于执行顺序是不确定的，因此算法必须是线程安全的，并且不能依赖于操作的顺序。此外，由于并行执行可能引入并发问题，因此在使用这种策略时需要格外小心。
2.4 无序策略unsequenced_policy
std::execution::unsequenced_policy 是 C++20 标准中引入的执行策略，它表示算法的操作可以以非序的方式执行，但不一定并行。使用其作为算法的执行策略，通常是为了允许算法实现选择最优的执行方式，而不必担心操作的顺序。这种策略特别适用于那些不需要保持特定顺序，并且可以从任何执行顺序中受益的算法。此策略指定算法的执行可以向量化，即使用对多个数据项进行操作的指令在单个线程上执行。
用法
通常将unsequenced_policy类的实例std::execution::unseq 作为算法的第一个参数传递，其形式如下
STLFunction (std::execution::unseq, ...other_arguments...);
示例：
#include <algorithm>
#include <iostream>
#include <vector>
#include <execution>
int main()
{
std::vector<int> v = { 1, 2, 3, 4, 5 };
std::for_each(std::execution::unseq, v.begin(),
v.end(),
[](int x) { std::cout << x << " "; });
return 0;
}
输出：
1 2 3 4 5
优劣
优势 | 劣势 |
|---|---|
在单个线程上快速执行，避免竞争条件。 | 某些硬件可能不支持矢量化，非确定性执行序列。 |
应用场景
无序策略的应用场景通常包括：
- 算法优化：当算法的实现可以选择最优的执行方式时，使用
std::execution::unsequenced_policy可以允许编译器或运行时系统根据当前环境和资源情况进行选择。 - 非确定性算法：对于某些非确定性算法，即算法的结果不依赖于操作的顺序，使用这种策略可以允许算法实现选择最合适的执行方式。
- 向量化执行：在某些情况下，算法可以通过使用 SIMD 指令集进行向量化执行来提高性能。使用
std::execution::unsequenced_policy可以允许算法实现选择这种执行方式，即使它不是并行的。 - 任务并行化：当算法可以划分为多个独立的任务，并且这些任务可以以任何顺序完成时，使用这种策略可以允许并行执行这些任务，从而提高性能。 需要注意的是，由于执行顺序是不确定的，因此算法必须是线程安全的，并且不能依赖于操作的顺序。此外，由于执行方式可能是非传统的，因此在使用这种策略时需要格外小心，以确保算法的正确性。
3. 执行策略之间的性能比较
#include <algorithm>
#include <execution>
#include <iostream>
#include <vector>
#include <chrono>
// 比较函数，用于排序
bool compare(int a, int b) {
return a < b;
}
int main() {
std::vector<int> data = {4, 2, 5, 1, 3}; // 示例数据
// 使用不同的执行策略进行排序
auto seq_sort = [&]() {
std::sort(std::execution::seq, data.begin(), data.end(), compare);
};
auto par_sort = [&]() {
std::sort(std::execution::par, data.begin(), data.end(), compare);
};
auto par_unseq_sort = [&]() {
std::sort(std::execution::par_unseq, data.begin(), data.end(), compare);
};
auto unseq_sort = [&]() {
std::sort(std::execution::unseq, data.begin(), data.end(), compare);
};
// 测量排序性能
auto measure_sort = [&](auto&& sort_func) {
auto start = std::chrono::high_resolution_clock::now();
sort_func();
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> elapsed = end - start;
std::cout << "Elapsed time: " << elapsed.count() << " ms\n";
};
// 执行排序并测量性能
measure_sort(seq_sort);
measure_sort(par_sort);
measure_sort(par_unseq_sort);
measure_sort(unseq_sort);
return 0;
}
输出：
Elapsed time: 0.001195 ms
Elapsed time: 0.000514 ms
Elapsed time: 0.000421 ms
Elapsed time: 0.000337 ms
注：以上仅仅是对
sort使用不同执行策略在https://www.onlinegdb.com/上的表现，针对不同的算法函数，以及不同的硬件平台、编译器等得到的效率也是不同的。选取策略还是根据具体的情况而定。
在这个例子中，我们定义了四个lambda函数，每个函数都调用std::sort，但使用不同的执行策略。然后，我们使用std::chrono库来测量每个排序操作的执行时间。
在不同的平台，上述例子性能对比可能如下：
std::execution::seq: 在单核处理器上表现最佳，但在多核处理器上可能不是最快的，因为它不会利用多核的优势。std::execution::par: 在多核处理器上通常比seq快，因为它尝试并行处理元素。但是，如果数据量很小，性能提升可能不明显。std::execution::par_unseq: 结合了并行和向量化，可能在支持SIMD的硬件上提供最佳性能。但是，如果排序算法本身不适合向量化，这种策略可能不会带来额外的性能优势。std::execution::unseq: 这种策略允许算法以不确定的顺序执行，可能在某些情况下提高性能，特别是当排序操作不需要保持元素的原始顺序时。
请注意，这个例子仅用于演示目的，实际的性能测试应该在更广泛的数据集和不同的硬件配置上进行。
4. 总结
在C++中，选择std::execution的四种策略（seq、par、par_unseq和unseq）取决于你的应用场景、数据特性以及你希望算法执行的方式。以下是一些选择策略时的考虑因素：
- std::execution::seq (串行执行):
- 当你的算法需要元素顺序处理，或者你的数据集很小，以至于并行化不会带来性能提升时，使用顺序执行策略。
- 在单核处理器上，顺序执行通常是最佳选择，因为它避免了线程创建和管理的开销。
- std::execution::par (并行执行):
- 当你的算法可以并行执行，且数据集足够大，可以在多个核心上同时处理时，使用并行执行策略。
- 在多核处理器上，如果你的算法可以有效地分割工作负载，那么并行执行通常能提供性能提升。
- std::execution::par_unseq (并行无序执行):
- 如果你的算法可以并行执行，并且结果不依赖于元素处理的顺序，使用并行无序执行策略。
- 这种策略允许算法在并行的同时进行向量化操作，可能在支持SIMD的硬件上提供最佳性能。
- std::execution::unseq (无序执行):
- 当你的算法不需要保持元素处理的顺序，并且可以从向量化操作中受益时，使用无序执行策略。
- 这种策略适用于数值计算密集型的操作，如向量化的数学运算。
在选择策略时，还应该考虑以下因素：
- 数据依赖性: 如果算法中的元素处理有依赖关系，那么并行化可能会变得复杂。在这种情况下，顺序执行可能是唯一的选择。
- 数据竞争: 在并行执行时，需要确保没有数据竞争。如果算法需要访问共享资源，可能需要使用同步机制，如互斥锁或原子操作。
- 硬件特性: 考虑你的硬件配置，如CPU核心数、缓存大小和SIMD支持。这些因素都会影响并行执行策略的性能。
- 编译器支持: 不同的编译器对C++并行STL的支持程度不同。确保你的编译器支持你想要使用的策略。
- 性能测试: 在实际部署之前，进行性能测试来比较不同策略的性能。这可以帮助你找到最适合你特定应用的策略。
最后，由于并行执行可能会引入额外的复杂性，建议在确保算法可以正确并行化的情况下才使用并行策略。如果不确定，可以先从顺序执行开始，然后逐步尝试其他策略。同时，并非所有算法都支持所有执行策略，并且某些算法可能具有不同的性能特征，具体取决于所使用的执行策略。选择最适合任务要求和可用硬件的执行策略，并测试不同的策略以确定给定任务的最佳策略非常重要。