C++17 详解 24 —并行 STL 算法

本文为 《C++17 in detail》 一书的中文渣中渣译文，不足之处还望指正。

翻译太特么累人了……剩余部分还是只做摘要翻译吧。

13. 并行 STL 算法

13.1 介绍

不止线程

除使用多线程外，还可以通过 CPU 或 GPU 的向量指令集进行加速。

CPU 中此类方法统称 SIMD — Single Instruction Multiple Data，即单指令多数据。常见的实现有 AVX256、AVX512、NEON。

GPU 中并行计算更碎片化，大多是跟硬件绑定，比如 NVIDIA 的 CUDA，Intel 的 TBB。也存在一些硬件无关的并行库，比如 OPENCL、OPENGL、OPENMP。

C++17 在这个方向上迈出了一小步：它解锁了标准库中算法的自动向量化/自动并行化。

译注：关于并发和并行，我见过的最通俗易懂的解读是这样的：

你吃饭吃到一半，电话来了，你一直到吃完了以后才去接，这就说明你不支持并发也不支持并行。

你吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，这说明你支持并发。

你吃饭吃到一半，电话来了，你一边打电话一边吃饭，这说明你支持并行。

我个人总结：
并行其实是跟串行区分比较的，所以 SIMD 这种可以同时处理多个数据的就是并行；如果多线程运行在同一个 CPU core 上，就是并发；如果多线程运行在不同的 CPU core 上，就是并行。

13.2 概览

新特性在使用角度看起来超简单：只是在大多数算法函数中新加了一个参数，这个参数叫做执行策略（execution policy）。

std::algorithm_name(policy, /* normal args... */);

示例：

std::vector<int> v = genLargeVector();
// 以并行策略对 vector 排序
std::sort(std::execution::par, v.begin(), v.end());

std::execution::par 表示使用并行策略。由 STL 实现来决定选择最好的并行方案，通常都是利用线程池。

13.3 执行策略

三类执行策略：

• sequenced_policy：同 C++17 之前，顺序执行。
• parallel_policy：并行执行算法，如果采用多线程方式的话，每一个线程内的执行是顺序的、但是顺序不确定（即上次函数调用结束再进行下一次调用）。
• parallel_unsequenced_policy：多线程 + 向量指令集，线程内、线程间均是无序的。

标准库预定义了三类策略的全局对象：

• std::execution::seq
• std::execution::par
• std::execution::par_unseq

限制和风险

1. std::execution::par 不是线程安全的，如果有用到共享数据需要自己做同步保护。

std::vector<int> vec(1000);
std::iota(vec.begin(), vec.end(), 0);
std::vector<int> output;
std::mutex m;
std::for_each(std::execution::par, vec.begin(), vec.end(),
[&output, &m, &x](int& elem) {
    if (elem % 2 == 0) {
        std::lock_guard guard(m);
        output.push_back(elem);
}
});

2. std::execution::par_unseq 同样不是线程安全的，而且同一线程内的执行是交错的（interleaved），如果像上面一样加锁的话，会造成死锁。

如我之前所吐槽，各编译器厂商中并行 STL 的实现进度缓慢，现在好像还不是深入研究并实战应用并行算法的时候。所以本章到此结束，原书中后续的 benchmark、新加算法介绍等内容暂时不理会了。