并行算法(Parallel Algorithms) ​

什么是并行算法 ​

C++17 为标准库中的大量算法(<algorithm>、<numeric>)添加了并行版本。使用方式非常简单:在原有算法调用的第一个参数位置传入一个"执行策略"(execution policy),算法就可以在多个线程上并行执行。

cpp
// 传统顺序排序
std::sort(vec.begin(), vec.end());

// C++17 并行排序——只多了一个参数
std::sort(std::execution::par, vec.begin(), vec.end());

这是 C++ 标准库首次在语言层面直接支持并行计算。在此之前,开发者要么手动管理线程,要么依赖 OpenMP、Intel TBB 等第三方库来并行化算法。C++17 的并行算法让多核利用变得和添加一个参数一样简单。

同时,C++17 还引入了几个全新的算法(std::reduce、std::transform_reduce、std::inclusive_scan、std::exclusive_scan 等),它们是专门为并行场景设计的,对操作的结合律和交换律有明确的要求。

头文件 ​

cpp
#include <algorithm>   // sort, for_each, find, count 等
#include <numeric>     // reduce, transform_reduce, inclusive_scan 等
#include <execution>   // 执行策略:seq, par, par_unseq

执行策略 ​

策略对象说明
顺序执行std::execution::seq和不带策略的版本行为相同,单线程顺序执行
并行执行std::execution::par可以在多个线程上执行,但每个线程内是顺序的
并行非顺序执行std::execution::par_unseq可以多线程 + SIMD 向量化,最大自由度
非顺序执行std::execution::unseq(C++20)单线程但允许 SIMD 向量化

关键限制:

  • par:元素访问函数不能引起数据竞争,但可以使用锁(mutex)
  • par_unseq:元素访问函数不能引起数据竞争,也不能使用锁(因为同一线程可能交错执行不同元素的操作,用锁会死锁)
  • 并行算法中如果元素访问函数抛出异常,会调用 std::terminate

基本示例 ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <execution>
#include <random>
#include <chrono>
#include <string>

// 计时辅助函数
template<typename Func>
auto measure(const std::string& name, Func f) {
    auto start = std::chrono::high_resolution_clock::now();
    auto result = f();
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << name << ": " << ms << " ms" << std::endl;
    return result;
}

// ============================
// 示例1:并行排序
// ============================

void parallel_sort_demo() {
    const int N = 10'000'000;
    std::vector<int> data(N);
    std::mt19937 gen{42};
    std::generate(data.begin(), data.end(), gen);

    // 拷贝一份用于并行排序
    auto data_par = data;

    // 顺序排序
    measure("顺序 sort", [&data]() {
        std::sort(std::execution::seq, data.begin(), data.end());
        return data.size();
    });

    // 并行排序
    measure("并行 sort", [&data_par]() {
        std::sort(std::execution::par, data_par.begin(), data_par.end());
        return data_par.size();
    });

    // 验证结果一致
    std::cout << "结果一致? " << std::boolalpha << (data == data_par) << std::endl;
}

// ============================
// 示例2:并行 for_each
// ============================

void parallel_for_each_demo() {
    const int N = 10'000'000;
    std::vector<double> data(N, 1.0);

    // 并行地对每个元素执行操作
    std::for_each(std::execution::par, data.begin(), data.end(),
        [](double& x) {
            // 模拟一些计算
            x = std::sin(x) * std::cos(x) + std::sqrt(x);
        });

    std::cout << "for_each 结果[0]: " << data[0] << std::endl;
}

// ============================
// 示例3:std::reduce(并行求和)
// ============================

void reduce_demo() {
    const int N = 10'000'000;
    std::vector<double> data(N, 0.5);

    // std::accumulate 是严格顺序的(从左到右),不能并行
    double sum_seq = std::accumulate(data.begin(), data.end(), 0.0);

    // std::reduce 允许乱序组合(要求操作满足结合律和交换律)
    double sum_par = std::reduce(std::execution::par, data.begin(), data.end(), 0.0);

    std::cout << "accumulate: " << sum_seq << std::endl;
    std::cout << "reduce:     " << sum_par << std::endl;
    // 两者结果可能略有不同(浮点数加法不严格满足结合律)
}

// ============================
// 示例4:std::transform_reduce(Map-Reduce)
// ============================

void transform_reduce_demo() {
    const int N = 1'000'000;
    std::vector<int> data(N);
    std::iota(data.begin(), data.end(), 1);  // 1, 2, 3, ..., N

    // 计算所有元素平方和:先 transform(平方)再 reduce(求和)
    long long sum_of_squares = std::transform_reduce(
        std::execution::par,
        data.begin(), data.end(),
        0LL,                                    // 初始值
        std::plus<>{},                          // reduce 操作(加法)
        [](int x) -> long long { return static_cast<long long>(x) * x; }  // transform 操作(平方)
    );

    std::cout << "1~" << N << " 的平方和: " << sum_of_squares << std::endl;

    // 向量点积(两个范围的 transform_reduce)
    std::vector<double> a{1.0, 2.0, 3.0, 4.0};
    std::vector<double> b{5.0, 6.0, 7.0, 8.0};

    double dot_product = std::transform_reduce(
        std::execution::par,
        a.begin(), a.end(),
        b.begin(),
        0.0  // 初始值
        // 默认:reduce 用 +,transform 用 *
    );
    std::cout << "点积: " << dot_product << std::endl;  // 1*5 + 2*6 + 3*7 + 4*8 = 70
}

// ============================
// 示例5:并行 count_if / find_if
// ============================

void parallel_search_demo() {
    const int N = 10'000'000;
    std::vector<int> data(N);
    std::mt19937 gen{42};
    std::generate(data.begin(), data.end(), [&gen]() { return gen() % 1000; });

    // 并行计数
    auto count = std::count_if(std::execution::par, data.begin(), data.end(),
        [](int x) { return x > 500; });
    std::cout << "大于500的个数: " << count << std::endl;

    // 并行查找
    auto it = std::find_if(std::execution::par, data.begin(), data.end(),
        [](int x) { return x == 999; });
    if (it != data.end()) {
        std::cout << "找到999,位置: " << std::distance(data.begin(), it) << std::endl;
    }
}

// ============================
// 示例6:inclusive_scan / exclusive_scan(前缀和)
// ============================

void scan_demo() {
    std::vector<int> input{1, 2, 3, 4, 5};
    std::vector<int> inclusive_result(5);
    std::vector<int> exclusive_result(5);

    // inclusive_scan:第 i 个输出 = input[0] + input[1] + ... + input[i]
    std::inclusive_scan(std::execution::par,
        input.begin(), input.end(),
        inclusive_result.begin());
    // 结果: {1, 3, 6, 10, 15}

    // exclusive_scan:第 i 个输出 = init + input[0] + ... + input[i-1]
    std::exclusive_scan(std::execution::par,
        input.begin(), input.end(),
        exclusive_result.begin(),
        0);  // 初始值
    // 结果: {0, 1, 3, 6, 10}

    std::cout << "inclusive_scan: ";
    for (auto x : inclusive_result) std::cout << x << " ";
    std::cout << std::endl;

    std::cout << "exclusive_scan: ";
    for (auto x : exclusive_result) std::cout << x << " ";
    std::cout << std::endl;
}

int main() {
    std::cout << "=== 并行排序 ===" << std::endl;
    parallel_sort_demo();

    std::cout << "\n=== 并行 for_each ===" << std::endl;
    parallel_for_each_demo();

    std::cout << "\n=== reduce ===" << std::endl;
    reduce_demo();

    std::cout << "\n=== transform_reduce ===" << std::endl;
    transform_reduce_demo();

    std::cout << "\n=== 并行查找 ===" << std::endl;
    parallel_search_demo();

    std::cout << "\n=== scan ===" << std::endl;
    scan_demo();

    return 0;
}

std::accumulate vs std::reduce ​

特性std::accumulatestd::reduce
头文件<numeric><numeric>
执行顺序严格从左到右任意顺序
支持并行不支持支持(接受执行策略)
对操作的要求无(任意二元操作)结合律 + 交换律
浮点求和结果确定性(同一输入同一结果)可能有细微差异

C++17 新增的并行算法 ​

算法说明
std::reduce乱序归约(并行版 accumulate)
std::transform_reduce先变换再归约(Map-Reduce 模式)
std::inclusive_scan包含当前元素的前缀和
std::exclusive_scan不包含当前元素的前缀和
std::transform_inclusive_scan先变换再做包含前缀和
std::transform_exclusive_scan先变换再做排除前缀和
std::for_each_n对前 n 个元素执行操作

适用场景 ​

  • 大数据量的排序(百万级以上元素并行排序提速明显)
  • 大规模数值计算(向量运算、矩阵操作的求和/变换)
  • 数据过滤和统计(count_if、find_if 在大数据集上并行)
  • 图像处理(对每个像素并行执行变换)
  • 科学计算中的 Map-Reduce 模式

常见问题 ​

并行算法一定比顺序快吗?

不一定。并行有线程创建和同步的开销。对于小数据集(几千个元素以下),并行版本通常比顺序版本更慢。经验法则是数据量超过几万、且每个元素的操作有一定计算量时,并行才有收益。排序这种 O(n log n) 的算法在大数据量下并行收益比较大。

std::reduce 和 std::accumulate 结果为什么可能不同?

因为浮点数加法不严格满足结合律。accumulate 严格从左到右累加,reduce 可能把元素分成多组分别求和再合并。不同的分组方式导致浮点舍入误差的累积方式不同,最终结果可能有微小差异。对于整数运算,两者结果完全相同。

par_unseq 和 par 有什么区别?

par 允许多线程但每个线程内顺序执行;par_unseq 还允许 SIMD 向量化(同一线程内交错执行不同元素的操作)。par_unseq 更严格:你的操作不能使用互斥锁(可能死锁),不能有信号处理相关的操作。如果不确定,先用 par。

哪些标准库算法支持并行?

大部分 <algorithm> 和 <numeric> 中的算法都有并行版本,包括 sort、stable_sort、for_each、transform、find、count、reduce、all_of、any_of、none_of、equal、mismatch、remove、remove_if、search 等。完整列表请查看编译器文档。

注意事项 ​

  • 并行算法中的元素访问函数不能引起数据竞争(不要修改共享状态)
  • 使用 par_unseq 时不能在元素访问函数中加锁
  • 并行算法中抛出的异常会导致 std::terminate,不会被 catch
  • std::reduce 要求操作满足结合律和交换律,否则结果不确定
  • 小数据集不要用并行——线程开销可能大于并行收益
  • 不同编译器的并行实现差异很大:MSVC 使用 Windows 线程池,GCC 依赖 Intel TBB
  • GCC 使用并行算法需要链接 TBB 库(-ltbb)

编译器支持与依赖 ​

编译器最低支持版本额外依赖
GCC9.0需要安装并链接 Intel TBB(-ltbb)
Clang17.0(部分)依赖 libc++ 或 libstdc++ 的支持
MSVC19.14 (VS 2017 15.7)无额外依赖,使用 Windows 线程池

总结 ​

C++17 的并行算法是标准库中最具影响力的新增功能之一。通过在算法调用中添加一个执行策略参数(std::execution::par),现有的排序、查找、变换、归约等算法就能利用多核并行执行。同时新增的 std::reduce、std::transform_reduce、std::inclusive_scan 等算法专为并行设计,提供了 Map-Reduce 和前缀和等常见并行计算模式。使用时需要注意:小数据集不值得并行,元素访问函数不能有数据竞争,浮点运算的并行归约可能有微小精度差异。目前 MSVC 的支持最完善,GCC 需要依赖 TBB 库。