C++20 并行算法如何工作？

作者

C++20 标准库在 <algorithm> 头文件中引入了并行算法，允许程序员在不需要显式线程管理的情况下，让标准算法在多个线程上并发执行。这一特性利用了现代 CPU 的多核特性，显著提升了在大数据集上的性能。下面我们详细拆解并行算法的工作原理、使用方式以及常见陷阱。

1. 并行执行策略

在 C++20 中，算法可以接收一个 execution policy 参数，用来告诉算法采用何种执行方式。标准提供了三种策略：

策略 关键字 含义
Sequential std::execution::seq 传统顺序执行，类似 C++17 之前的实现。
Parallel std::execution::par 允许在多个线程中并行执行。
Parallel Unsequenced std::execution::par_unseq 允许多线程 和 SIMD 并行执行。

如果未显式指定策略，算法默认使用 seq。要使用并行，需要在调用时传入 std::execution::par 或 par_unseq。

#include <execution>
#include <algorithm>
#include <vector>

std::vector <int> v = /* ... */;
std::sort(std::execution::par, v.begin(), v.end()); // 并行排序

2. 底层实现细节

2.1 线程池与线程调度

标准并未要求实现必须使用线程池，但大多数实现（如 libstdc++、libc++、MSVC）会在内部维护一个线程池，复用现有线程以降低创建/销毁成本。线程数通常与硬件线程数（std::thread::hardware_concurrency()）相关。

2.2 分块与分治

大多数算法采用 分块 或 分治 方式来实现并行。例如：

  • std::for_each：将容器划分为若干块，每块交给一个线程执行。块的大小通常是 container.size() / num_threads。
  • std::sort：通常使用 introsort（快速排序 + 堆排序）或 Timsort。并行版本会先把数组划分为若干子序列，分别在不同线程上进行排序，然后使用并行归并（如 k-way merge）合并。

2.3 随机访问与迭代器特性

并行算法要求迭代器满足 随机访问 或 双向访问 的属性，以便能够高效地分块。std::vector、std::deque、std::array 都满足；std::list 则不支持。

3. 线程安全与副作用

并行算法对副作用有严格要求：

  • 函数对象（Functors）：在多线程环境下使用时，必须是 线程安全 的。即对共享状态的写操作必须使用互斥锁或原子操作。通常建议使用无状态的 lambda 或函数指针。
  • 异常安全：若在并行执行过程中抛出异常，所有线程都会被取消。算法会把异常向上抛出，调用者需要捕获。

4. 性能评估与调优

4.1 什么时候并行值得？

  • 大数据集：元素数量至少在 10⁶ 以上，或者需要大量 CPU 时间的运算。
  • 无副作用：算法不涉及全局状态修改，或者你已保证线程安全。
  • CPU 多核：目标机器至少有 4 个以上逻辑核心。

4.2 常见瓶颈

  • 内存带宽：并行访问共享数组可能导致缓存线争用。使用 分块 时，尽量让每块的数据位于不同的缓存行。
  • 负载不均：例如 std::sort 的分区不均匀，导致部分线程过载。可以通过 work stealing（工作窃取）动态分配任务。
  • 同步开销：如 par_unseq 中的 SIMD 与多线程同步成本。仅在数据量大、每次操作耗时高时才值得。

5. 示例：并行计数奇偶数

下面演示如何使用并行算法统计一个整数序列中奇数和偶数的个数。示例使用 std::for_each 并行执行，并通过原子计数器保证线程安全。

#include <execution>
#include <algorithm>
#include <vector>
#include <atomic>
#include <iostream>

int main() {
    std::vector <int> data(10'000'000);
    std::iota(data.begin(), data.end(), 0); // 0..9999999

    std::atomic <int> even{0}, odd{0};

    std::for_each(
        std::execution::par,
        data.begin(),
        data.end(),
        [&](int x) {
            if (x % 2 == 0) ++even;
            else ++odd;
        });

    std::cout << "Even: " << even.load() << ", Odd: " << odd.load() << '\n';
}

注意：`std::atomic

` 的自增操作在大规模并行下仍可能成为瓶颈。若需要更高吞吐量，可以采用 **分块局部计数** 后再聚合，减少原子操作次数。

6. 未来展望

  • 更细粒度的执行策略：C++23 将引入 std::execution::single、std::execution::unseq 等更多细粒度策略，方便用户选择。
  • 协程与并行算法的结合：通过协程可以在需要 I/O 等阻塞操作时更优雅地切换。
  • GPU 与 OpenCL：C++23 的 Parallelism TS（Technical Specification）进一步推动 GPU 加速。

7. 小结

  • 并行算法通过 execution policy 接口简化并发编程。
  • 需要满足 随机访问 迭代器、线程安全的函数对象。
  • 并行优势体现在 大数据集、无副作用 的场景。
  • 性能调优重点在 负载均衡 与 内存带宽。

熟练掌握并行算法能够让你的 C++ 程序在多核 CPU 上获得显著性能提升。下一步，你可以尝试在实际项目中用 std::execution::par 替代原有的循环，观察速度变化，并根据需要进行微调。祝你编码愉快！

发表评论