C++17并行算法实战：STL中的执行策略与性能优化

如果有人搜“STL”出来一堆“STL转STP”“Revit导出STL”的内容那多半是3D打印那边的STL文件格式跟C开发者说的STL完全是两码事。这篇聊的是C标准模板库里的并行算法也就是C17开始正式进入标准的那套std::execution策略、并行版本的std::sort、std::transform、std::reduce这类东西。从C11引入线程库开始多线程写起来已经不算痛苦了但手写std::thread、std::async去拆任务、合并结果始终有一层“算法逻辑”和“并发实现”之间的胶水代码要去维护。C17的并行算法把这层胶水直接做进了标准库你不需要告诉程序怎么拆数据只需要在调用算法时多传一个执行策略参数剩下的事交给标准库。性能未必永远最优但代码可读性、可维护性一下子上了个台阶。这篇文章就围绕“并行算法在STL中的应用”把原理、实操、性能瓶颈和踩坑记录一次说透适合已经会写STL基础算法、想把手头代码改成并行版本的同学参考。1. 并行算法不是什么黑魔法先搞懂执行策略1.1 四种执行策略到底怎么选C17标准库加入了三个执行策略C20又补了一个一共四种。它们不是花架子每种都对应不同的底层执行约束用错了轻则性能倒退重则直接未定义行为。std::execution::seq串行执行。相当于传统STL算法的显式版本加了和没加一样但可以用来做基准对比。std::execution::par允许并行执行但禁止向量化产生数据竞争。标准库实现通常会开线程池来分摊任务。std::execution::par_unseq允许并行外加向量化SIMD要求每个元素的操作之间没有任何依赖也不允许调用会阻塞的库函数。约束最严格编译器发挥空间也最大。std::execution::unseqC20不并行但允许单线程内的向量化。适合那些不想开线程、只想用SIMD加速的场景。用生活化的方式理解seq就是一个人按顺序搬砖par是多叫了几个人一起搬每人负责一片区域par_unseq是搬砖的同时每个人还骑了个平衡车脚不沾地跑得更快但平衡车要求路面必须平整不能有障碍物unseq是一个人骑平衡车速度快但不会叫帮手。代码层面最简单的改动长这样#include algorithm #include execution #include vector std::vectorint v(1000000); // 传统写法 std::sort(v.begin(), v.end()); // 并行写法 std::sort(std::execution::par, v.begin(), v.end());就这么一个参数排序从单核变成了多核协作。但我必须提醒不是所有算法都值得加这个参数后面专门有一节讲开销问题。1.2 并行算法在标准库中的分布别以为所有算法都真并行了C17的时候标准库给69个算法加了执行策略的重载C20又补充了一些。但这里有个容易踩的误区很多算法的并行版本就是串行实现的标准只规定了“允许”并行没规定“必须”并行。所以你在MSVC上跑std::for_each可能真的开线程在GCC的某些版本上可能只是转发到了串行实现。大致可以把常用算法分三类第一类是真正实现并行且收益明显的包括std::sort、std::stable_sort、std::transform、std::for_each、std::reduce、std::exclusive_scan、std::inclusive_scan。这几个在三大编译器上都有比较成熟的并行实现拿来做性能验证最容易看到效果。第二类是并行实现存在但有额外开销的比如std::find、std::count、std::all_of/any_of/none_of。理论上它们可以提前退出短路但一旦并行怎么优雅地“叫停”其他线程就是个工程问题。GCC的实现会对小数据量回退串行大数据量才真正开线程。第三类是纯挂名的典型如std::copy、std::move、std::fill。这类内存操作的瓶颈通常在内存带宽上不在CPU核心数上并行反而可能因为线程调度开销更慢。标准委员会给它们加策略重载纯粹是为了接口统一不指望你真去用。所以当你准备把一个算法加上std::execution::par时多问自己一句这个算法是CPU密集型的计算还是内存搬运型操作前者并行有效后者大概率白折腾。2. 核心细节解析sort、transform、reduce 的并行机制与正确姿势2.1 并行sort的底层思路归并段与分治std::sort的串行实现通常是内省排序IntroSort数据量大时用快速排序递归深度过深切到堆排序。并行版本的基本思路是分治先把数组划分成若干个段每段交给一个线程去排序然后再做多路归并——听起来简单实现细节非常多不同标准库的切分策略也完全不同。GCClibstdc的并行sort走的是OpenMP加__gnu_parallel的旧路子后来C17的std::execution::par版本在有TBB的情况下会调用TBB的并行排序。MSVC的STL实现则自己维护了一个线程池按CPU核心数切成段排序后做k路归并。Clang的libc早期基本只支持par的串行回退近几个版本才逐步完善。实际使用中并行sort有个比较影响性能的因素稳定排序。std::sort不保证稳定std::stable_sort才保证。问题在于stable_sort的并行版本为了保持稳定性归并阶段需要额外的O(n)空间内存占用直接翻倍。如果你只是对int或double排序不关心相同元素的相对顺序用std::sort就够了别用stable_sort空间和时间都省。写一个简单的性能对比测试#include algorithm #include chrono #include execution #include iostream #include numeric #include random #include vector void test_sort(int n) { std::vectorint v1(n), v2(n); std::mt19937 rng(42); std::generate(v1.begin(), v1.end(), rng); v2 v1; auto t0 std::chrono::high_resolution_clock::now(); std::sort(v1.begin(), v1.end()); auto t1 std::chrono::high_resolution_clock::now(); std::sort(std::execution::par, v2.begin(), v2.end()); auto t2 std::chrono::high_resolution_clock::now(); auto ms1 std::chrono::duration_caststd::chrono::milliseconds(t1 - t0).count(); auto ms2 std::chrono::duration_caststd::chrono::milliseconds(t2 - t1).count(); std::cout n n serial ms1 ms parallel ms2 ms speedup (double)ms1 / ms2 \n; } int main() { test_sort(1000000); test_sort(10000000); test_sort(100000000); }我在一台8核心16线程的机器上跑出来的结果大致是100万数据并行反而慢一点1000万数据才看到约3倍加速1亿数据能到6倍多。原因很简单——线程池创建、任务切分、最后的归并都需要开销数据不够大时这些开销盖过了并行收益。建议排序列超过500万再考虑并行否则老老实实用串行。2.2 transform 与 for_each无依赖任务的典型并行场景std::transform是典型的“每个元素独立计算”算法每个输出元素只依赖对应的输入元素线程之间完全不需要通信。这种embarrassingly parallel尴尬并行场景是并行算法收益最大的地方。#include algorithm #include execution #include vector #include cmath std::vectordouble input(1000000); std::vectordouble output(input.size()); // 串行版本 std::transform(input.begin(), input.end(), output.begin(), [](double x) { return std::sin(x) * std::cos(x); }); // 并行版本 std::transform(std::execution::par_unseq, input.begin(), input.end(), output.begin(), [](double x) { return std::sin(x) * std::cos(x); });这里我特意用了par_unseq而不是par因为sin和cos这种纯函数运算完全满足向量化条件par_unseq能让编译器在安全前提下对循环做SIMD优化。实测下来par大概4-5倍加速par_unseq在某些编译器上能到7-8倍。但有一个重要的前提变换函数必须是“纯”的不能修改外部状态不能有数据竞争。最常见的问题是在lambda里捕获一个std::vector然后push_back这属于迭代器失效和数据竞争双重违规标准直接判定为未定义行为连报错都不会有。2.3 reduce 和 accumulate并行求和为什么结果不一样std::accumulate是串行版的左折叠数学上等价于(((ab)c)d)操作的执行顺序是确定的。std::reduce允许乱序底层会把数据切成多个块并行求和再把部分和合并。问题来了浮点数加法不满足结合律。double a 1e16, b 1.0, c -1e16; // 串行: (ab)c 0 // 若先算 bc -1e16, 再算 a(-1e16) 0 也恰好相同 // 但换个数字就可能完全不同你可能会问既然结果可能不同为什么还要用reduce因为大多数数值计算场景结果的微小浮点差异是可接受的而并行带来的性能提升是实打实的。如果你做的是金融计算、需要逐位确定的场合老老实实用accumulate。无符号整数和整数加法不需要担心这个问题整数加法满足结合律reduce的结果和accumulate保证一致。实际编码时如果只是想求个和直接这样写#include numeric #include execution #include vector std::vectorunsigned long long v(1000000, 1); auto sum std::reduce(std::execution::par, v.begin(), v.end(), 0ull);注意初始值类型要写0ull如果写0会推断成int累加过程中可能溢出这是并行reduce最常见的低级错误。2.4 其他值得知道的并行STL功能std::exclusive_scan和std::inclusive_scan是前缀和prefix sum的并行版本。C17同时提供了串行版本std::partial_sum和并行版本scan并行前缀和的实现通常是Blelloch算法或Hillis-Steele算法能把O(n)步长降到O(log n)步长但代价是更多的总操作数。在实际代码里如果你只是要做前缀和数据量低于10万时partial_sum更快超过这个量级并行scan才有优势。std::for_each和std::for_each_n的并行版本也值得提一下。for_each_n接受一个迭代器和元素个数跳过end()判断理论上少一次迭代器比较性能会有微弱的提升更重要的是它配合计数循环更自然。还有std::none_of/all_of/any_of的并行版本它们内部会在找到结果后尝试取消任务但标准没有要求必须提前终止所以“短路”效果完全看实现不能依赖。3. 实操过程从串行到并行的完整改造路线3.1 第一步编译器与工具链准备并行算法不是加个头文件就能跑的它对工具链有要求。MSVCVisual Studio 2019 16.7或2022开箱即用直接#include execution。GCClibstdc需要GCC 9以上且要安装TBBThreading Building Blocks或oneTBB。编译时加-ltbb链接。GCC 12以上对par_unseq的支持更完善。Clanglibc需要Clang 14以上且同样要链接TBB。Linux下的典型编译命令g -stdc20 -O2 -ltbb parallel_demo.cpp -o parallel_demo如果编译时报错找不到execution头文件先检查GCC版本如果报链接错误undefined reference to tbb::...说明没装TBB。Ubuntu/Debian下装libtbb-devCentOS/RHEL下装tbb-devel。macOS上Clang自带的libc对并行算法的支持一直不太完整很多版本编译不过或者直接回退串行。我的建议是macOS上做跨平台开发时并行算法相关代码老实加条件编译或者直接用第三方库兜底。实际上如果你在macOS上编译C17并行算法报错也不用慌这是工具链的已知情况不是代码的问题。3.2 第二步容器选择与迭代器要求并行算法对迭代器的要求比普通STL算法更严格std::execution::par要求迭代器是前向迭代器及以上par_unseq要求随机访问迭代器。这意味着链表std::list基本告别并行算法因为它的迭代器是双向迭代器不支持随机访问没法高效切分数据。std::forward_list连std::sort都用不了更别说并行版本。如果你面对的是链表结构又想做并行处理老老实实先拷贝到std::vector处理完再拷回去。这个拷贝开销通常比并行节省的时间少得多。std::vector是最理想的容器std::array和原生数组也都能用。std::deque虽然是随机访问迭代器但它的内存不是连续的并行性能会比vector差一些不推荐。还有一点容易忽略如果容器正在被其他地方访问比如另一个线程在遍历那就不应该在这个容器上跑并行算法。别以为并行算法只负责自己内部的线程安全它不会替你加锁。3.3 第三步lambda表达式的并发安全约束这是并行算法和传统STL算法最大的分水岭。串行算法里你可以在lambda里随便写但并行算法要求传入的Callable必须是“可并行调用”的不能有数据竞争data race。多个线程同时读写同一个变量就是未定义行为。不能用迭代器失效的方式修改容器比如lambda里对同一个vector push_back。调用者提供的函数最好是原子操作或只读外部状态。举个例子统计正数个数的时候很多人会下意识这么写// 错误示范count 存在数据竞争结果不确定 int count 0; std::for_each(std::execution::par, v.begin(), v.end(), [count](int x) { if (x 0) count; });这段代码跑起来不会崩但count的结果基本是错的。两个线程同时执行count时读改写三步会交错。正确姿势是让每个线程维护局部计数最后归并。最简单的做法// 正确示范用 transform 返回标记再 reduce 求和 auto positive std::transform_reduce( std::execution::par, v.begin(), v.end(), 0, std::plus(), [](int x) { return x 0 ? 1 : 0; } );std::transform_reduce是C17引入的专门用来做“先映射、后归约”的组合。它把std::transform和std::reduce合成一个调用内部避免中间容器的分配。这个函数在并行计算里出场率极高值得重点掌握。3.4 第四步数据规模与切分的经验阈值很多人的疑问是数据量多小才不该用并行这个没有标准答案但根据我自己的测试和社区的反馈有几个经验值可以参考。以std::sort为例1000万以上的随机数据并行收益明显500万到1000万之间可以测试对比再决定500万以下别用。std::transform这类无通信任务的阈值可以低一些一般来说10万以上就可以尝试并行。为什么阈值差别这么大排序需要归并归并阶段的开销是O(n)的额外空间加O(n)的合并操作这会摊薄并行收益而transform每个元素完全独立没有最后的合并步骤。另外线程池创建和调度也有固定开销通常是几十微秒到几百微秒的量级。如果你不确定某个数据规模是否适合并行最靠谱的办法是写个简单的benchmark用std::chrono测串行和并行各跑5次取中位数再决定用哪个策略。别猜实测最准。4. 常见问题与排查技巧实录4.1 并行sort崩了迭代器不可交换这是我遇到过的最隐蔽的一个坑。std::sort要求迭代器指向的值类型支持swap操作这本是STL的基本要求但并行版本的sort在归并阶段可能会调用更多的移动和交换操作。如果你排序的是自定义对象而这个对象没有正确实现移动构造函数和移动赋值运算符串行可能侥幸能跑并行版本就会在某个角落崩溃。排查方法先用std::is_move_constructible_vT和std::is_move_assignable_vT检查类型如果返回false基本就是这个问题。解决办法是给自定义类型加上移动语义struct MyData { std::string name; int score; // 移动构造函数 MyData(MyData) noexcept default; // 移动赋值 MyData operator(MyData) noexcept default; // 建议同时提供 swap friend void swap(MyData a, MyData b) noexcept { using std::swap; swap(a.name, b.name); swap(a.score, b.score); } };4.2iota_view配合并行transform性能诡异下降std::ranges::iota_view是C20的惰性整数序列视图配合并行算法时有个奇怪的现象某些版本的MSVC上iota_view迭代器的operator不是noexcept或者不够内联导致并行线程切分时反复移动迭代器性能比串行还差。你把iota_view换成std::vector预先填充数字性能立刻恢复。这不算标准库的bug属于实现层面的优化不到位。实际建议是涉及并行算法时尽量用真正的容器迭代器不要用视图迭代器。C23的std::views::iota配合std::ranges::views::transform确实方便但并行场景下还是先物化成vector再说。4.3 处理“异常不可靠”并行算法里的异常处理规则标准规定并行算法在调用用户提供的Callable时如果Callable抛出了异常这个异常会在调用算法的线程上重新抛出。听起来没问题但关键是“如果有多个异常同时发生”标准委员会直接摆烂程序会被std::terminate终止。也就是说并行算法内部一个任务挂了其他任务可能还在跑此时如果它们也抛异常不好意思直接崩溃。所以工程上比较稳妥的做法是lambda内部自己捕获所有异常把错误信息记录下来返回一个哨兵值。算法结束后统一检查错误标记。比如std::atomicbool has_error{false}; std::mutex err_mutex; std::string error_msg; std::for_each(std::execution::par, v.begin(), v.end(), [](int x) { try { x process(x); } catch (const std::exception e) { bool expected false; if (has_error.compare_exchange_strong(expected, true)) { std::lock_guardstd::mutex lock(err_mutex); error_msg e.what(); } } }); if (has_error) { // 统一处理错误避免并行异常导致 terminate }4.4par_unseq的未定义行为禁区par_unseq看起来比par更快但约束也更严格标准要求不能调用会阻塞的库函数不能调用会获取锁的函数不能调用std::mutex成员函数不能调用分配内存的non-vectorized版本其实就是禁止在par_unseq的lambda里直接new。如果你的lambda里用了std::lock_guard或者std::malloc理论上都是未定义行为编译器不会报错但可能在某些优化下产生诡异结果。还有一个容易忽略的细节par_unseq要求迭代器的所有操作不能抛异常。因为向量化后的代码通常不做异常处理一旦异常穿过SIMD指令整个程序状态就不可预测了。4.5 并行reduce结果不对但串行正确这个问题我见过太多次原因基本就两个第一个是浮点数非结合律。前面已经讲过了这种情况不是代码bug是算法语义不同。如果你一定要串行完全一致的结果用accumulate。第二个是归约的初始值和操作符类型不匹配。reduce的签名是reduce(exec, first, last, init, binary_op)要求init和累加结果的类型必须与binary_op兼容。最常见的错误是init传了0int但容器的元素是double累加时每次都会做int到double的转换精度可能丢失。我之前还遇到过一种情况自定义类型的operator没有写成对称的比如a b和b a结果不同不满足交换律。reduce要求二元操作符是结合律且可交换的如果你的操作符不交换并行结果就完全没法预测。排查方式很简单对同一个数据集跑10次看结果是否每次都一样。如果10次结果不同基本可以确定操作符不满足交换律或结合律。4.6 并行算法和手写线程池怎么选很多人在造轮子之前会纠结要不要自己用std::thread写个线程池再配合std::async手动切分数据我的经验是能用标准库并行算法解决的绝对不要手写线程池。自写线程池的优势是控制力强能针对特定场景调参但劣势也很明显——错误处理、任务窃取、缓存友好度这些细活儿要做到高标准极其费时间。标准库的并行算法版本在GCC和MSVC上已经迭代很多年底层用TBB或自家线程池工程成熟度远高于个人实现的轮子。但是如果你的任务不是“在容器上做算法”而是复杂的任务依赖图比如先算A再并发算B和C最后合并那并行算法就不够用了该上std::async或者专门的Taskflow库还是得上。并行算法的定位是“数据并行”任务并行不是它的主场。5. 编译器支持现状与跨平台实战心得5.1 三大编译器的并行算法支持横向对比写跨平台代码的时候并行算法这块真的是“一套代码各跑各的”。下面这张表是我在实际项目里对比总结出来的情况编译器/库版本要求后端依赖par支持度par_unseq支持度备注MSVC STLVS2019 16.7内置线程池完善完善开箱即用文档较好GCC libstdcGCC 9TBB/oneTBB完善部分依赖TBB需按-ltbb链接Clang libcClang 14通常依赖TBB一般较弱有些版本直接回退串行MSVC是最省心的标准库实现质量高而且微软的STL团队一直在优化容器和算法的性能。GCC的并行sort性能很好但依赖TBB这一点让很多不喜欢额外依赖的开发者望而却步。Clang的libc说实话是三者里最拉胯的据我了解很多版本就是直接调到串行实现加par纯属心理安慰。5.2 跨平台代码的降级策略由于并行算法在Clang上可能没有实际加速效果跨平台项目应该做好降级准备。我的做法是封装一个头文件// parallel_algo.h #if defined(_MSVC_LANG) _MSVC_LANG 201703L #define PAR_EXEC std::execution::par #elif defined(__GNUC__) (__GNUC__ 9) defined(__TBB__) #define PAR_EXEC std::execution::par #else #include algorithm // 降级直接调用串行版本通过空执行策略不可行干脆不用并行算法 #endif当然这只是个粗糙的宏方案更优雅的做法是用if constexpr配合特性检测。但中心思想只有一个平台能力不确定时默认降级到串行保证程序的正确性优先于性能。5.3 与C20 ranges的配合与限制C20的ranges库让代码写起来特别优雅namespace rv std::ranges::views; auto result numbers | rv::transform([](int x) { return x * 2; }) | rv::filter([](int x) { return x 10; });但ranges视图和并行算法的兼容性到目前为止仍然不理想。问题在于很多视图的迭代器类型不满足并行算法要求的迭代器类别尤其是par_unseq要求随机访问迭代器filter_view还要求迭代器支持跳过被过滤元素这本身就和随机访问矛盾。C23标准对std::ranges::*算法加上并行策略不太可能因为ranges的管道式组合和并行执行策略的“先切分再合并”本质上有冲突。实际工程中我通常这样处理小数据量用ranges写法图个简洁大数据量还是老老实实把结果拷贝进std::vector再跑并行算法代码难看一点性能稳一点。6. 总结一个最简单有效的算法选型清单写了这么多最后给大家一个可以直接抄作业的清单。拿到一个任务时按这个顺序去决策先判断数据规模。数据量小比如少于10万直接用传统STL算法别加执行策略。再判断操作类型。CPU密集型的纯计算用transform加par或par_unseq需要全局有序输出用sort加par需要数值归约用reduce或transform_reduce加par需要并行前缀和用inclusive_scan加par。然后判断依赖关系。每个元素完全独立用transform相邻元素之间有关联考虑scan或sort不要硬上并行操作符不满足交换律结合律用串行版本。最后还有一句实话并行算法不是银弹。标准库给我们提供了便捷的入口但真正的性能提升还要靠对数据规模、内存布局、编译器行为的深刻理解。我从C11的std::async一路用到现在的std::execution::par_unseq最大的感受是标准库把“并发”的门槛降下来了但把“判断什么时候该并发”的责任更多留给了开发者。我自己在实际项目里最常用的是transform_reduce其次是并行的sort和transform。这三个基本覆盖了95%的数据并行需求。如果哪天你在优化代码时发现并行版本比串行还慢别急着骂标准库先看一眼是不是数据太小、是不是有归并开销、是不是容器迭代器拖了后腿。把这些问题排查一遍大多数情况都能找到原因。