概述

C++17引入了STL算法的并行化，作为一个Cpper，还是要小小的把玩一下，看看到底该怎么使用这个新特性，并且了解一下背后的实现原理。整体的测试代码可以在这里找到。

如何使用

让我们以std::sort来作为一个小例子来介绍怎么将其并行化。

通常来讲如果要对一个序列进行排序的话，我们大概率会写出以下benchmark程序。

1
2
3
4
5
6
7
8
for (int i = 0; i < iterationCount; ++i) {
  // testSize = 1'000'000;
  vector<double> sorted(doubles);
  const auto startTime = high_resolution_clock::now();
  sort(sorted.begin(), sorted.end());
  const auto endTime = high_resolution_clock::now();
  print_results("Serial", sorted, startTime, endTime);
}

这里的sorted是利用随机数生成的一个浮点数序列，序列长度为100000，在我的机子上把优化全打开，进行5次测试，测试数据如下。

1
2
3
4
5
6
Testing with 1000000 doubles...
Serial: Lowest: 1052 Highest: 4.29496e+09 Time: 76.077300ms
Serial: Lowest: 1052 Highest: 4.29496e+09 Time: 76.480900ms
Serial: Lowest: 1052 Highest: 4.29496e+09 Time: 77.995400ms
Serial: Lowest: 1052 Highest: 4.29496e+09 Time: 76.134400ms
Serial: Lowest: 1052 Highest: 4.29496e+09 Time: 75.936800ms

整体时间大体是在75ms左右，看起来虽然还可以，但是当我们把它并行化之后，你会发现速度提升还是非常明显的。并行化的benchmark程序样例如下：

1
2
3
4
5
6
7
8
for (int i = 0; i < iterationCount; ++i) {
    vector<double> sorted(doubles);
    const auto startTime = high_resolution_clock::now();
    // std::execution 并行化调用
    sort(std::execution::par_unseq, sorted.begin(), sorted.end());
    const auto endTime = high_resolution_clock::now();
    print_results("Parallel", sorted, startTime, endTime);
  }

可以看到唯一的区别在于std::sort多传入了一个参数std::execution::par_unseq，而这里的std::execution便是并行化的关键。该库文件下面主要是有4中并行化执行策略，分别为sequenced_policy,parallel_policy,parallel_unsequenced_policy,unsequenced_policy,其中前3个是C++17开始支持，第四个则是C++20开始支持。而我们这里所使用的par_unseq则是parallel_unsequenced_policy，其描述如下：

以该执行策略类型为一种独有类型，对并行算法重载消歧义，并指示并行算法的执行可以并行化、向量化，或在线程间迁移（例如用亲窃取的调度器）。容许以此策略调用的并行算法中的元素访问函数调用在未指定线程中以无序方式执行，并相对于每个线程中的另一调用无顺序。

这四种策略的不同可以在cppreference中查到。在并行化之后，我们以同样的测试标准进行测试，得到结果如下：

1
2
3
4
5
6
Testing with 1000000 doubles...
Parallel: Lowest: 1850 Highest: 4.29497e+09 Time: 16.916000ms
Parallel: Lowest: 1850 Highest: 4.29497e+09 Time: 16.415900ms
Parallel: Lowest: 1850 Highest: 4.29497e+09 Time: 17.215400ms
Parallel: Lowest: 1850 Highest: 4.29497e+09 Time: 18.038900ms
Parallel: Lowest: 1850 Highest: 4.29497e+09 Time: 17.581000ms

可以看到时间会下降到16ms左右，这个效率还是值得称赞的。不过这里面并没有做什么并发控制，也就是很容易出现一些问题，只有在做一些简单的数学运算，或者是彼此不会出现的竟态的操作之中，我们才可以使用这个并行化算法（感觉我在说废话）。

总结

总体来看还是不错的，如果能确保数据访问在并行化时不会出问题的话，这些新算法的效率还是相当优秀的。

引用