2.7、并行版本算法（std::sort等）

C++17并行版本算法

传统STL算法如std::sort、std::for_each等，默认都是顺序执行，单线程跑完所有数据。C++17引入了“执行策略”（execution policy）的概念，允许你告诉算法“用什么方式执行”：顺序执行、并行执行，甚至并行加向量化执行。

执行策略主要有三种：

• • std::execution::seq：顺序执行，和传统算法一样。
• • std::execution::par：并行执行，算法内部会将任务拆分给多个线程并行处理，但每个线程内操作是顺序的。
• • std::execution::par_unseq：并行加向量化执行，允许线程内部操作不按顺序执行，利用SIMD指令集做数据级并行。

设计哲学上，这种策略模式让算法调用接口保持不变，仅增加一个策略参数，极大降低了代码改动成本。底层实现会根据策略和硬件环境智能调度线程和指令集，开发者无需手动写多线程代码，降低了并行编程的门槛。

并行版本算法的底层原理简析

并行算法的底层实现大致分为以下几个步骤：

1. 1. 任务拆分
   算法会根据数据规模和硬件线程数，将输入区间划分成多个子区间，分配给不同线程处理。
2. 2. 线程调度与执行
   通过线程池（如Intel TBB）管理线程，避免线程频繁创建销毁带来的开销。每个线程独立执行子任务。
3. 3. 同步与合并
   并行任务完成后，算法会合并结果（比如排序时合并各个子区间的有序序列），保证最终结果正确。
4. 4. 向量化优化（par_unseq）
   允许编译器使用SIMD指令对数据做批量操作，进一步提升单线程内的执行效率。

这种设计既保证了并行的高效利用，也兼顾了算法的正确性和线程安全。

典型案例：并行排序 std::sort

代码示例

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

int main() {
    std::vector<int> data(100000);
    for (int i = 0; i < 100000; ++i) data[i] = 100000 - i;

    auto start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::seq, data.begin(), data.end()); // 顺序排序
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Sequential sort took "
              << std::chrono::duration<double>(end - start).count() << " seconds.\n";

    for (int i = 0; i < 100000; ++i) data[i] = 100000 - i; // 重置数据

    start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, data.begin(), data.end()); // 并行排序
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Parallel sort took "
              << std::chrono::duration<double>(end - start).count() << " seconds.\n";

    return 0;
}

解析

• • 顺序版本：单线程按传统方式执行，时间较长。
• • 并行版本：底层自动将数据分块，多个线程同时排序各自块，再合并结果。多核CPU能显著缩短排序时间。

底层细节

• • 并行排序通常采用并行归并排序或并行快速排序。
• • 任务拆分时，算法会动态决定分块大小，避免线程过多导致上下文切换开销。
• • 线程池（如Intel TBB）负责线程复用和负载均衡。
• • 合并阶段是关键，必须保证最终序列有序且无数据竞争。

高级用法示例

结合自定义比较器和字符串视图：

std::vector<std::string> coll = {"id10", "ID2", "id3", "ID20"};
std::sort(std::execution::par, coll.begin(), coll.end(),
          [](const auto& a, const auto& b) {
              return std::string_view{a}.substr(2) < std::string_view{b}.substr(2);
          });

这里用std::string_view避免了substr()产生临时字符串的开销，结合并行排序，性能提升明显。

常见错误及面试关注点

常见错误

1. 1. 线程安全问题
   使用std::execution::par_unseq时，操作必须无副作用且不依赖执行顺序。否则可能出现竞态条件或死锁。例如在并行for_each里使用带锁的操作极易死锁。
2. 2. 数据量过小
   并行算法有启动线程和合并的开销，数据量太小反而比顺序慢。一般建议数据量达到几千以上才考虑并行。
3. 3. 不支持的算法
   并非所有STL算法都支持并行执行，如std::accumulate不支持，需用std::reduce替代。

面试可能考点

1. 1. 执行策略的区别和使用场景
   能解释seq、par、par_unseq的区别及适用场景。
2. 2. 并行算法的底层实现原理
   任务拆分、线程调度、结果合并的流程。
3. 3. 线程安全和竞态条件
   如何保证并行算法中操作的线程安全。
4. 4. 性能权衡
   何时使用并行算法，何时顺序执行更优。

总结

C++17的并行版本算法是一项革命性的改进，它将复杂的多线程并行处理封装进标准库算法，极大简化了并行编程。通过执行策略参数，开发者可以灵活控制算法执行方式，兼顾性能和安全。掌握它不仅能提升程序性能，更是现代C++高阶技能的体现。
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）