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::seq
std::execution::par
std::execution::par_unseq
std::execution::unseq
这些实例用于指定并行算法的执行策略——即允许采用何种并行运算。
C++的执行策略是一种编程模式,它允许开发者指定如何执行特定的操作或算法,而不必关心底层的实现细节。这种策略模式为算法提供了灵活性,使得算法可以与不同的执行策略结合使用,从而实现并行、串行、延迟执行等不同的行为。
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
指定了顺序执行,但它仍然允许算法实现使用任何同步机制来优化性能,只要这些优化不会改变操作的顺序。因此,即使指定了顺序执行策略,算法的实际执行仍然可能受到底层实现优化的影响。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
优劣
优势 | 劣势 |
---|---|
更快地执行大型任务,在多核系统下的效率最佳。 | 可能会引入开销。由于这种开销,可能并不总是比顺序执行快,也可能引入竞争。 |
应用场景
并行策略的应用场景通常包括:
使用 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
优劣
优势 | 劣势 |
---|---|
加快重复性操作的执行速度。 可以在带有矢量指令的硬件上使用。 | 不适合所有任务,并非所有硬件都支持。 |
应用场景
并行无序策略的应用场景通常包括:
std::execution::parallel_unsequenced_policy
可以允许算法实现选择使用这些指令来提高性能。std::execution::parallel_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
可以允许编译器或运行时系统根据当前环境和资源情况进行选择。std::execution::unsequenced_policy
可以允许算法实现选择这种执行方式,即使它不是并行的。#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
: 这种策略允许算法以不确定的顺序执行,可能在某些情况下提高性能,特别是当排序操作不需要保持元素的原始顺序时。请注意,这个例子仅用于演示目的,实际的性能测试应该在更广泛的数据集和不同的硬件配置上进行。
在C++中,选择std::execution
的四种策略(seq
、par
、par_unseq
和unseq
)取决于你的应用场景、数据特性以及你希望算法执行的方式。以下是一些选择策略时的考虑因素:
在选择策略时,还应该考虑以下因素:
最后,由于并行执行可能会引入额外的复杂性,建议在确保算法可以正确并行化的情况下才使用并行策略。如果不确定,可以先从顺序执行开始,然后逐步尝试其他策略。同时,并非所有算法都支持所有执行策略,并且某些算法可能具有不同的性能特征,具体取决于所使用的执行策略。选择最适合任务要求和可用硬件的执行策略,并测试不同的策略以确定给定任务的最佳策略非常重要。