掌握C++17的并行算法：std::execution 与并行 STL

作者

在 C++17 标准中，STL 并行算法的引入为我们带来了更简单、更高效的并行编程方式。通过在标准算法中传入执行策略（execution policy）即可让算法在多核 CPU 上并行执行，而无需手写线程或使用 OpenMP。下面我们从执行策略、支持的算法、实现细节以及性能调优等几个方面系统梳理 C++17 并行算法的核心概念，并给出实战示例。

一、执行策略（execution policy）

执行策略决定了算法的执行模式。C++17 定义了三种策略：

策略 说明
std::execution::seq 顺序执行，等价于传统 STL
std::execution::par 并行执行，利用多核 CPU
std::execution::par_unseq 并行 + 向量化（数据级并行），适合数值计算

在调用算法时，只需在算法的前面加上策略即可：

std::sort(std::execution::par, vec.begin(), vec.end());

如果没有显式指定策略，默认采用顺序执行。

二、支持的标准算法

C++17 并行化的算法涵盖了 STL 的大部分常用算法。按功能可分为三类：

1. 需要单调性或可分割的算法

  • std::sort, std::stable_sort, std::nth_element, std::partial_sort, std::partial_sort_copy

2. 需要随机访问迭代器的算法

  • std::unique, std::is_sorted, std::count, std::find, std::find_if, std::for_each, std::transform, std::accumulate, std::inner_product, std::adjacent_difference

3. 需要顺序或非顺序的算法

  • std::includes, std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference, std::merge, std::inplace_merge

需要注意的是，并非所有算法都支持所有策略。例如，std::merge 在 par_unseq 下不保证结果的确定性。

三、实现细节

1. 分割与合并

大多数并行算法通过 divide‑and‑conquer 方式将工作分成若干块，分别在不同线程中执行，最后合并结果。C++ 标准库实现通常使用 std::thread 或内部线程池来调度任务。若算法不易分割（如排序），实现会采用 work‑stealing 或 chunking 的技术。

2. 线程安全

并行算法要求 迭代器 必须是 随机访问（如 vector::iterator），并且数据结构在并行操作期间保持不可变。否则会出现竞争条件。若需在并行算法内部修改数据，建议使用原子操作或对数据加锁。

3. 向量化（par_unseq）

在 par_unseq 模式下，编译器会尝试对循环进行向量化，将多个迭代合并成 SIMD 指令。适用于数值密集型代码，例如矩阵乘法、FFT 等。

四、实战示例：并行排序与统计

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>
#include <random>
#include <chrono>

int main() {
    const size_t N = 1'000'000;
    std::vector <int> data(N);

    // 随机填充
    std::mt19937 rng(42);
    std::uniform_int_distribution <int> dist(1, 1'000'000);
    std::generate(data.begin(), data.end(), [&](){ return dist(rng); });

    // 并行排序
    auto t1 = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, data.begin(), data.end());
    auto t2 = std::chrono::high_resolution_clock::now();

    std::cout << "并行排序耗时: " << std::chrono::duration<double>(t2 - t1).count() << " 秒\n";

    // 并行统计相同元素出现次数
    t1 = std::chrono::high_resolution_clock::now();
    int target = 500'000;
    int count = std::count_if(std::execution::par,
                              data.begin(), data.end(),
                              [&](int v){ return v == target; });
    t2 = std::chrono::high_resolution_clock::now();

    std::cout << "值 " << target << " 出现次数: " << count << "\n" << "计数耗时: " << std::chrono::duration<double>(t2 - t1).count() << " 秒\n";
    return 0;
}

小结：此代码展示了如何使用 std::execution::par 对大规模数据进行并行排序和计数。性能收益取决于 CPU 核数、数据规模以及编译器对 par 的支持。

五、性能调优技巧

  1. 避免过度并行：线程数不宜过多，否则线程创建与上下文切换成本会抵消收益。一般以 CPU 核数的 1~2 倍为宜。
  2. 使用 execution::par_unseq：如果算法允许无序执行且不需要顺序性，开启向量化可进一步提升速度。
  3. 编译器优化：开启 -O3、-march=native 等优化标志，提升 SIMD 使用率。
  4. 线程池：C++17 标准库并没有公开线程池接口，若想进一步控制线程数量，可自行实现线程池并包装算法。

六、常见陷阱与注意事项

  • 迭代器失效：并行算法在内部会多次访问迭代器，若在算法期间对容器进行插入/删除操作，迭代器会失效，导致未定义行为。
  • 顺序要求：某些算法在并行执行时不保证顺序（如 for_each 的执行顺序），如果算法内部依赖顺序，需要改写或使用 seq。
  • 异常传播：若并行算法内部抛出异常，所有线程会被终止，异常会在主线程中抛出。务必在并行代码块中使用异常安全的操作。

七、未来展望

C++20 进一步扩展了并行算法的功能，提供了更细粒度的执行策略（如 std::execution::par_unseq 的更安全实现），并改进了内部调度算法。与此同时，Boost 等第三方库也在提供更成熟的并行 STL 替代方案。对 C++ 开发者而言，掌握并行 STL 是提升代码性能的高效路径。

通过本文的学习，你已经掌握了 C++17 并行 STL 的核心概念、使用方法以及性能调优技巧。希望在今后的项目中，你能借助这些工具，让代码在多核时代发挥更大的威力。

发表评论