多线程排序为什么更慢？小数据量并行开销揭秘

1. 问题从哪来：一次让我尴尬的排序实验

前两天一个用C#写业务的同事跑过来问我一个很有意思的问题：“我写了个数据聚合demo，大概2万条记录，想用多线程排序提高速度，结果加完线程反而慢了将近一倍，这合理吗？”我第一反应是“不可能，肯定你代码写歪了”。但跑到他机器上一复现，结果还真不是他的锅，多线程版本就是稳定地比单线程慢。

后来我把这个问题抛给过好几个朋友，大家的第一反应出奇一致：多核CPU，多线程，怎么可能比单线程慢？排序这种计算密集任务不是应该天然适合并行吗？答案显然是否定的。这件事背后藏着一个很基础、但又很容易被忽视的性能问题：并行是有固定成本的，当任务本身的规模小到一定程度，这些固定成本会把并行带来的收益吃干抹净。这篇文章就是想把这个账算明白。

1.1 事情的起因：随手加个线程池，排序反而更慢

同事的原始逻辑非常标准：把数组从中间切一刀，左边的开一个Task排序，右边的开一个Task排序，两边都排完再把结果合并起来。这就是教科书里经典的多线程归并排序思路，看起来没有任何毛病。他的测试数据是2万个整数，机器是8核16线程，跑出来的结果却很打脸：单线程版本大约3毫秒，多线程版本大约5到7毫秒，反复跑了几次都是多线程更慢。

我一开始怀疑是线程池没有预热，任务粒度分配不合理，或者合并逻辑写得太蠢。但把各种写法都调了一遍之后，结论依然没有变化：在这个数据量级，单机普通配置上多线程排序就是打不过单线程。后来我在Java环境里用数组排序重测，在C++环境里用std::sort配合多线程归并再测，得到的规律也差不多——小数据量时并行不仅没有帮助，还稳定拖后腿。

这个问题之所以值得写一篇文章，是因为它很容易误导人。很多从I/O密集型场景转过来的开发者，脑子里存着“多线程=快”的刻板印象，一遇到性能问题就下意识上并行，结果在纯计算任务上栽跟头。排序正是最典型的纯计算场景。

1.2 直觉的误区：核多不等于“免费快”

我们日常的直觉是：多核CPU就是四个工人在干活，单线程是一个工人在干活，工人多自然快。但“工人多”是有前提的——招工人要花成本，工人之间沟通要花成本，工人交接还要花成本。如果活儿一共只需要1秒，你却花5秒去招工人、再花2秒安排分工，那这个工程必然亏本。排序就是这样一种“活儿”。

数据量小的时候，整个排序耗时可能只有几毫秒，而多线程引入的开销从几百微秒到几毫秒不等，占比非常可观。这不是代码写错了，而是问题规模本身就不适合并行。把这句话牢牢记住，后面我们所有的计算都是围绕它展开的。理解了这一点，你就掌握了判断“这个任务该不该上多线程”的第一性原理。

2. 单线程排序其实非常快：先算算它干了多少活

为什么小数据量排序这么快？因为排序本身在做的事情，比很多人想象的要“轻”。要回答“多线程为什么慢”，首先得知道单线程到底有多快。

2.1 排序的复杂度只是起点

基于比较的排序算法，理论下界是 O(N log N)。这句话大家都很熟，但落到实际数字上，很多人没有感觉。以快速排序或归并排序为例，对10万条记录排序，大约需要做 10万 × log₂(10万) ≈ 166万 次比较；对100万条，约1993万次比较；对1000万条，约2.3亿次比较。每次比较还可能伴随一次交换或移动。

关键点在于：比较次数是 N log N，不是 N²。数据量从10万翻到100万，比较次数大约从166万变成1993万，只增加了约12倍。对比一下冒泡排序、插入排序这种 O(N²) 的算法，100万条数据要比较 5千亿 次，量级完全不是一个概念。所以现代排序库普遍采用快速排序、归并排序或者TimSort这类分治思想算法，目的就是用最少的比较次数完成大量数据的排序，这也是单线程排序能做到非常快的前提。

2.2 缓存命中时，CPU比你想的极限快得多

比较运算本身有多快？如果排序的是整数，比较指令在现代CPU上大约只需要0.2到1纳秒。当然，数据不可能都躲在寄存器里，大部分时间消耗在内存访问上。这里有一个关键事实：CPU访问L1缓存大约1纳秒，L2缓存大约3到5纳秒，L3缓存大约10到20纳秒，访问主内存则需要80到150纳秒。一次cache miss的代价，差不多够执行100次比较。

所以排序性能的天花板，往往不是“比较次数”，而是“内存访问模式”。数据量小的时候，整个数组能塞进L2甚至L1缓存，CPU的实际处理速度会超出你的直觉。数据量一旦大到只能放在主内存里，排序耗时会明显抬升，但依然比大多数人预估的快。这也是为什么很多性能怪人特别在意“局部性”——把数据弄进缓存里，比优化算法本身还管用。

2.3 用10万条数据算一笔时间账

我们来做一次估算。假设排序10万个整数，约166万次比较。如果数据能基本命中L2缓存，每次比较加移动的摊还成本按2纳秒算，那么纯排序时间大约是 166万 × 2ns ≈ 3.3毫秒。再加上递归调用、函数指针间接调用、偶发的cache miss，实际用C++的std::sort或者Java的Arrays.sort跑下来，10万条整数通常也就在3到8毫秒之间。

这个数字意味着什么？如果多线程方案想让这3毫秒的活儿变快，它必须先付出一个启动成本——线程创建、任务分发、数据准备、结果合并。这些成本哪怕再低，也算几百微秒。你让多线程来抢的利润空间，从头到尾一共也就几毫秒，固定开销就已经吃掉其中相当一部分。这就是小数据量多线程反而慢的根本原因：单线程本身太快了，没有足够的并行空间让多线程施展拳脚。

3. 多线程的“固定开销”清单

要验证上面的判断，需要把多线程的固定开销一项项列出来。这些开销在写代码的时候很容易被低估，因为它们不直接体现在业务逻辑里，但每一项都在消耗真实时间。我按常见顺序拆解一下，给每个环节标一个大致量级。

3.1 线程创建与销毁：微秒级别的“起步价”

线程创建不是免费的。在Linux下用pthread_create创建一条线程，普遍要花50到100微秒；Windows下CreateThread的量级类似；Java底层走系统线程，创建一条线程同样是几十到几百微秒；C#的Task虽然比裸线程轻，但底层依然要复用线程池线程，第一次提交任务时仍然有初始化成本。如果为了排序2万条数据临时创建4条线程，光是创建开销就是0.2到0.4毫秒，而单线程排序可能总共只需要不到1毫秒。这一项已经快赶上收益了。

所以生产代码里很少出现“临时创建线程来排序”的写法，更多是预先准备好线程池。但线程池只能省掉线程创建，省不掉任务提交、队列调度、结果回传这些环节，只是把“一次性的固定成本”转化成了“每次任务的边际成本”。这一点在后面的基准测试章节还会提到。

3.2 上下文切换：时间片不够分的时候更明显

如果线程数量超过核心数，操作系统就要在时间片之间来回切换线程。每次切换需要保存和恢复寄存器、页表、栈指针等现场，一次上下文切换大约1到10微秒。可别小看这几微秒，如果系统里还有别的进程在跑，切换会更频繁，排序任务被切走之后恢复，原本在缓存里的数据可能已经失效，后续访问全部要回主内存，这个损失比切换本身大得多。

在我的实际经验里，一个常见误区是“开线程越多越快”。实际上，在4核机器上开8个排序线程，多出来的4条线程并不会同时运行，只会带来无谓的上下文切换。排序这种纯CPU密集任务，线程数最好和可用的物理核心数接近，而不是越多越好。如果你发现并行排序比单线程慢，先数数自己是不是开了太多的线程。

3.3 同步锁、原子操作与内存屏障

多线程之间只要共享数据，就需要同步。在分治排序的思路里，左右两半虽说是不同线程在排，但结果要合并，合并双方要把各自排序完成的状态通知给主线程，这就要用到Future、CountDownLatch、join之类的机制。这些操作背后是原子变量和锁。一个无竞争的原子操作大约20纳秒，看起来不贵，但锁竞争一旦发生，代价立刻跳到微秒级。更隐蔽的是内存屏障——为了保证一个线程对数据的修改能被另一个线程看见，CPU必须刷新缓存一致性协议的状态，跨核通信的延迟通常在上百纳秒甚至更高。

同步开销对排序的影响在于：它必须发生在所有并行线程都排完之后的收尾阶段。也就是说，并行排序的合并点是天然的串行点，所有线程必须在合并这里汇合。数据量越小的任务，等待汇合的开销相对越大。你可以想象一群工人分别砌完几堵墙，最后必须等所有人都完工才能验收，而这些等待时间里，其他工人无事可做。

3.4 数据切分、回传与合并：最容易漏算的一项

这部分是我实际排查时最常看到被忽略的。把数组从中间切一刀，看起来只是算个下标，但如果你的实现是复制两个子数组交给线程处理，然后再把排序结果合并回新数组，那数据移动的成本就全部算进固定开销里了。在.NET和Java里，数组复制是内存拷贝，10万条整数大约几十微秒，感觉不多；但到了千万级数据，复制和合并的耗时可能已经是百毫秒级，并行排序换来的加速会被这项成本悄悄吃掉一大块。

更值得留意的是内存分配。如果每次排序都new两个子数组，再new一个合并结果数组，GC的压力会肉眼可见地上升。排序这种高频操作，最好通过原地排序配合索引切片来避免复制，这也是生产级并行排序库实现复杂的真正原因。很多人写并行排序demo跑得慢，不是因为并行本身不行，而是因为数据切分和合并的复制操作写得太重。

4. 收益和成本的对赌：什么时候才值得并行

列完成本，再来看收益。我们需要一个可以自己动手算的模型，而不是停留在“感觉”。这部分的计算并不复杂，但能帮你把“多线程排序什么时候划算”这个问题彻底搞清楚。

4.1 理论收益：Amdahl定律能给多好的预期

并行排序的理想收益，可以用Amdahl定律描述：加速比 = 1 / (S + P/N)。其中S是串行部分占比，P是并行部分占比，N是处理器数量。对于归并排序的并行版本，串行部分包括任务拆分、线程调度、结果合并；并行部分是两个子数组的排序。假设S占5%，P占95%，4核情况下理想加速比是 1/(0.05 + 0.95/4) ≈ 3.48倍。这个数字看起来很美丽，但它是建立在“并行部分完全线性加速、没有额外开销”的前提下的。

现实世界不存在这种前提。并行部分会因缓存竞争、数据共享、调度不均而打折；串行部分耗时不会因为核多而减少。更重要的一点是，Amdahl定律算的是相对加速比，它不关心任务本身有多小。一个5毫秒的任务，哪怕理论加速比是3倍，省下的时间也就是3毫秒左右；如果固定开销是1毫秒，净收益只剩2毫秒。一顿操作猛如虎，实际收益却很小。

4.2 把固定开销放回公式里：计算实际拐点

这里给一个更实用的判断方式。设T_single为单线程排序耗时，C为并行方案的固定开销，T_par为并行排序耗时。判断并行是否值得，本质是看T_single是否明显大于 C + T_par。简化一下：只有当T_single比固定开销高出一个数量级以上时，并行才有动力。假设固定开销大约0.5毫秒，那么单线程排序时间至少要5到10毫秒，并行才可能见到正收益；如果单线程要50毫秒以上，那并行的价值就很确定了。

用具体数字套：排序10万条整数，单线程通常在几毫秒量级，和固定开销处于同一水平，并行基本属于白忙；排序100万条整数，单线程大约需要几十到一百多毫秒，固定开销已经只占很小比例，并行收益开始显现；到了1000万条，单线程排序轻松超过1秒，并行可以稳定获得2到4倍加速，这才是值得动手的场景。下表的实测部分会给你一个更直观的参考。

4.3 语言和硬件如何改变拐点位置

拐点并不是固定的数字。在Python里跑排序，因为解释器本身慢，同样10万条整数可能要几百毫秒，这个时候开多线程看起来会有差距——但Python的GIL会锁住同一进程内的CPU密集任务，用threading跑纯计算并不能真正并行，必须使用multiprocessing或者改用numpy这类扩展。这又引入了另一个层面的复杂度。

硬件也直接改变拐点。高端桌面CPU的单核性能更强，单线程排序本来就更快，拐点会往更大数据量方向移动；服务器多路CPU有更大的缓存和内存带宽，并行收益会来得更早。因此，别人告诉你的“某个数据量应该/不应该并行”只能当参考，你必须在自己目标机器上跑一次基准测试，才能确定真正的阈值。这也是下一章的核心内容。

5. 实测数字与基准测试避坑

光说不练不行。我自己在常规配置（8核16线程，3.5GHz，DDR4主机）上做过一组对比，分享出来，给大家一个数量级上的参考。注意，这是经验值，不是普适结论，语言和平台不同会差很远。

5.1 一组常规硬件的实测经验值

这组数据来自整数数组排序。单线程用语言标准库的快速排序；并行用“拆两半、各自排序、再归并”的经典实现。可以看到拐点大约出现在百万级数据附近，这也解释了为什么很多排序库内部会有“数组长度不够大就不并行”的判断逻辑。另外要注意，我刚才说的“并行明显亏”在1万到10万这个区间是最严重的，你实际工程里如果排序的数据量在这个范围，基本可以直接放弃多线程方案。

5.2 我踩过的三个测量坑

第一坑：只跑一次就下结论。现代CPU有频率boost，第一次跑可能特别快或特别慢，尤其是Java和C#有JIT预热问题。我最初测并行比单线程慢，其实是因为JIT还没暖起来，后面测着测着结果就变了。排序这种微小时间差别的对比，没有预热和多次取样，结论基本不可信。

第二坑：把线程创建放在计时区间里。如果代码写成“先开线程，再计时，然后等所有线程结束”，那线程创建开销就全算进排序时间了。正确做法是先把线程池准备好，或者至少多次计时后看稳定值，不要把一次性成本算成排序的一部分。这一点在做方案对比时尤其重要，否则你比较的不是排序算法，而是线程创建机制。

第三坑：打印日志。很多人喜欢在排序前后用println或Console.WriteLine输出结果，以为无伤大雅。实际上控制台输出可能比排序本身还慢，而且会把所有操作串行化，把并行优势全部抵消。测试环境里尽量去掉一切输出，实在要看结果，测完再输出一次即可。

5.3 靠谱的测法：预热、多轮、取中位数

标准的测法是：先跑几轮热身，让JIT、CPU、内存页都热起来；然后连续跑10到20轮，取中位数而不是平均值，因为平均值容易被某一次系统抖动拉高，中位数更能代表稳定表现。计时用高精度接口，Java用System.nanoTime，C#用Stopwatch，C++用std::chrono::steady_clock，不要用DateTime.Now这种低精度工具。

还有一个容易被忽略的细节：多线程版本的测法和单线程版本要完全对称，两个版本都要有相同的数据拷贝过程，避免某个版本因为数据已经呆在缓存里而占便宜。排序是破坏性操作，每次要么重新生成数据，要么从同一份原始数据拷贝，才能保证两边的缓存热度是公平的。没有这个对称条件，你测出的差异里混进了数据拷贝和内存分配的噪声。

6. 什么时候真正该用多线程排序，以及更简单的方案

到这里，问题已经不是能不能并行，而是该不该并行。我自己的判断方法很简单，也很粗暴，但大多数时候都好用。

6.1 判断标准：看“可并行时间”能不能盖住开销

先写单线程版本，量出T_single；再估一个C，经验值取0.5到1毫秒；如果T_single超过C的10倍以上，才考虑并行方案。然后，把并行版本同样测出来，跟单线程对比，胜出再上线，别凭感觉替换。这里有个额外的提醒：如果你的排序任务在真实业务里只跑一次，那并行收益还要再打折，因为很多固定开销（比如线程池预热）是一次性的，任务越少收益越不明显。

要注意，这个判断只适用于排序这种纯计算型任务。如果任务是I/O密集型的，比如从网络或磁盘读数据、发HTTP请求，那么多线程的价值完全不是一回事。I/O等待时间里CPU基本闲着，另开线程充分利用等待窗口，哪怕任务量小，并行也常常值得。这也是很多人从I/O场景带着“多线程=快”的印象来到排序场景时被坑的真正原因。

6.2 标准库里的现成方案，别手写线程池

实际项目里，我建议不要自己实现并行归并排序，标准库早就把这层逻辑封装好了，而且内部阈值都替你调过。Java的Arrays.parallelSort会在数组长度不够大时自动退化为普通排序；C++17有std::execution::par可以配合std::sort使用；.NET里有PLINQ，可以直接用AsParallel().OrderBy()。如果数据规模已经大到单机放不下，那就进入MapReduce或者Spark这类分布式框架的射程了，那是另一个量级的故事。

选用现成方案的关键理由是：它们把数据切分、任务调度、合并策略以及“到底要不要并行”的判断全部内置了。你只需要相信它们，不要自己做无谓的造轮子。我记得JDK的parallelSort内部对数组拆分有阈值控制，小数组根本不走并行分支，这正是整篇文章讨论的那个拐点的工程化体现。连JDK的工程师都在小数据量上拒绝并行，普通人就更没必要逆着规律硬上了。

6.3 一个建议：先测再优化，别为并行而并行

总结这些年踩坑的经验，优化第一步永远是测量。不测量就谈多线程，跟不看路就踩油门差不多。小数据量排序，单线程就是最优解；大数据量排序，优先用标准库的并行版本；实在要自己写并行，就把固定开销想清楚，再复现一遍前面的计算。

最后分享一个我常用的验证技巧：先把排序任务本身放大，用50倍的数据量跑一次单线程，如果100毫秒内能跑完，那说明你的任务还太小，不值得并行；如果跑出几百毫秒甚至几秒，再去捣鼓多线程。这个判断非常粗糙，却帮我挡住了好几次无意义的性能优化。排序如此，其他CPU密集型小任务同理——并行不是无限的免费午餐，它的每一分收益，都要先拿固定开销去买单。