排序这活儿看着基础真碰上亿级数据的时候单线程跑起来能把人急死。我之前有一个数据处理模块每天要排序上亿条记录最初用的标准库单线程快排跑一次十几秒整个流程的吞吐量全卡在排序这一步上。后来实在受不了认真搞了一个“基于快排和二项归并改进的多线程排序”方案把排序耗时直接砍到原来的四分之一左右这篇文章就是把我当时的选型思路、核心实现、踩坑记录完整复盘一遍。写出来给那些正打算给项目上并行排序、但又不知道从哪下手的同学参考尤其是搞数据中台、实时分析、批量导出这类场景的这里面全是实打实的可复现代码和参数经验。最早我脑子里的想法很简单多线程排序嘛不就是把大数组切成几块每块丢给一个线程排序最后再合起来。真正动手之后才发现“切块”和“合起来”这两件事全是坑。用快排做切块是因为它每分一次区左右两半就是天然独立的数据段可以放心交给不同线程但快排在数据分布不理想时会划分严重倾斜一个线程忙死、其他线程闲死负载均衡根本控不住。用归并做“最后一步”是因为它能把多段有序数据稳定合并成一段完整有序序列而且归并本身可以通过“两两合并”的树形结构充分利用多核也就是标题里的“二项归并”——把多个有序段按二叉树形式两两合并从全体段到最终一个段只需要 log2(k) 轮合并每轮又能并行处理。1. 为什么是“快排 二项归并”算法选型背后的逻辑1.1 快速排序的并行优势与隐藏的坑快速排序为什么天然适合多线程关键在于它的分治过程选一个 pivot把数组分成左小右大两部分之后左半区排序和右半区排序完全不依赖对方。单线程快排浪费的正是这种独立性而多线程快排在递归时把左右两个分支分别交给不同线程理论上能实现并行递归加速。但朴素并行快排有几个隐藏问题。第一是 pivot 选不好导致严重倾斜比如对一个接近有序的数组如果每轮都取固定位置的元素当 pivot划分后一边几乎为空另一边几乎等于全部数据这时候多线程不仅不加速反而因为任务分配、线程切换白白增加开销。第二是任务粒度问题如果递归到很深的层数还在继续开新线程线程创建销毁的开销会压过排序本身的收益。第三是递归深度本身快排的最好情形递归深度是 O(log n)但最坏情形会退化到 O(n)在多线程版里这问题会被放大可能导致栈溢出。我在并行版本里做了一些补救用三数取中来选 pivot保证在绝大多数场景下划分不会太离谱引入串行阈值当待排序区间长度小于一定值后就不再开线程限制全局并发线程数避免任务越分越碎。这些细节最终决定了并行快排是“加速器”还是“拖后腿”。1.2 二项归并的价值与代价那为什么还需要二项归并因为只靠并行快排是无法完成整个数组排序的。并行快排结束时各个线程各自负责的区间已经有序但这些区间互相之间没有大小关系整体还不是一个完整的有序数组。要收口就必须把若干个已经有序的子段合并起来。最简单的“一路手拉手”合并思路是从第一个段开始依次把后面的段合并进结果数组里。这样做的复杂度是 O(k * n)k 是段数量n 是总数据量。当段数量很多时后面的段参与合并次数过多效率直线下滑。二项归并的思路完全不同。它把所有有序段看成树的叶子节点每轮把相邻两个段用二路归并合并成一个更大的段下一轮再合并更大的两个相邻段直到最后只剩一个完整有序数组。这样每轮并行合并所有段对整体只需要 log2(k) 轮而且每一轮中不同的段对之间完全独立又可以继续多线程并行。二项归并的价值在于它让“合并”这个串行瓶颈变成了可并行、可扩展的树形计算代价则是需要一个和原数组等长的临时存储空间来避免频繁的内存分配。1.3 整体工作流划分、排序、合并把快排和二项归并组合起来整套流程就是三个阶段划分阶段对原始数组做一个不完全的快排划分不是排完整而是把数组切分成若干个坐标连续的子区间并记录每个子区间的左右边界。并行排序阶段把每个子区间分别丢给一个线程去执行串行快排内部再用插入排序做小段收尾。二项归并阶段这些已经有序的子区间作为叶子按照树的层次两两合并直到整个数组变成一段完整有序数据。用一句话总结核心思想快排负责把大问题“切碎”归并负责把碎片“焊成整体”多线程则让切碎和焊接的过程同时发生在多个核上。这套分工非常像车间流水线——切割工位多开几个焊接工位也多开几个总吞吐量自然就上去了。2. 顶层设计阈值、线程模型与负载均衡2.1 阈值决定任务粒度任务粒度决定性能上限在设计多线程快排时最容易被忽视、对性能影响最大的参数是“在什么规模下停止继续拆分线程”。我管它叫串行阈值记为 SERIAL_THRESHOLD。如果这个值设得太小比如 1000数组中每个小区间都会开一个异步任务任务调度和线程切换的开销会超过排序本身如果设得太大比如 10 万前面划分阶段产生的并行度又太少大量数据在最终阶段变成单线程处理加速效果打折。第二层阈值是插入排序阈值通常取 16 到 32。当快排递归到的小区间足够短时插入排序比继续递归快排要高效得多因为它省掉了函数调用栈、分区比较等额外开销局部性又好。小段排序就像搬家时顺手把零碎杂物装进几个箱子不需要再按大件的逻辑叫卡车。这两个参数都对结果有直接影响而且不同硬件平台上最优值会变。我建议用二分搜索的方式去调先在典型数据规模上跑基准测试然后分别尝试 2000、4000、8192、16384 这档串行阈值挑最快的一组再在邻近区间细化。不要指望一个参数能通吃所有环境。2.2 线程模型std::async 与线程池的取舍最初我用 std::async(std::launch::async, ...) 实现并行快排。省事不需要手动管理线程生命周期但很快就发现一个问题如果不加全局并发限制随着递归深度增加任务数会呈现指数级增长底层线程数失控。C 标准库实现通常会对std::async的线程做一定程度的复用但在任务爆发时它仍然可能创建大量线程导致线程上下文切换占据大量 CPU 时间。更稳的方案是自己实现一个线程池 任务队列或者用现成的并行库把任务投递到一个有界队列里由固定数量的工作线程消费。我当时评估了一下项目引入第三方并行依赖的成本最终选择用std::async加一个std::atomicint做全局并发计数。代码简单可读性好而且在 8 核 16 线程这种常见机器上效果已经足够。如果将来换到 32 核甚至更多核心的机器再迁移到线程池方案也不迟。这里不必一步到位用复杂方案先跑出收益再决定是否进一步升级。2.3 负载倾斜怎么控制并行快排的负载不均衡问题主要来自数据分布。比如数据本身接近有序或者大量重复值扎堆快排划分就会倾斜某些子区间很大、另一些很小大区间的线程忙到冒烟小区间的线程却早早空闲下来。解决倾斜的思路有三层。第一层是在 partition 阶段选好 pivot用三数取中法可以避免常见的“最坏情况”触发。第二层是把“固定递归分配”改成“任务队列分配”也就是不让每个递归分支死守一个线程而是把生成的任务统一放进队列工作线程谁空闲谁领取这在并行计算领域叫工作窃取。第三层是接受一定程度的倾斜让它不成为瓶颈比如在快排划分到一定程度后如果检测到某区间长度远大于其他区间就把这个区间单独拆成更多子任务继续并行化。我实际用了第一层和第三层的组合没有引入完整的工作窃取队列。三数取中已经能挡掉绝大多数极端输入第三层的动态切分可以保证最坏情况不至于彻底退化。3. 核心实现从串行快排到多线程归并的代码落地3.1 串行基础版插入排序收尾的快排在写多线程版本之前我先把串行快排优化到位这是后面所有并行优化的性能底座。基础代码用模板实现#include algorithm #include atomic #include future #include iostream #include thread #include vector constexpr int INSERTION_THRESHOLD 32; // 小段使用插入排序 constexpr int SERIAL_THRESHOLD 8192; // 小于该长度不再并行 constexpr int MAX_THREADS 8; // 可调通常取硬件线程数或略小 // 插入排序小区间内局部性好递归开销小 template typename T void insertion_sort(T* arr, int left, int right) { for (int i left 1; i right; i) { T key arr[i]; int j i - 1; while (j left arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } } // 三数取中选 pivot避免接近有序数据的退化 template typename T T median_of_three(T* arr, int left, int right) { int mid left (right - left) / 2; if (arr[mid] arr[left]) std::swap(arr[mid], arr[left]); if (arr[right] arr[left]) std::swap(arr[right], arr[left]); if (arr[right] arr[mid]) std::swap(arr[right], arr[mid]); return arr[mid]; } // 分区返回 pivot 最终位置 template typename T int partition(T* arr, int left, int right) { T pivot median_of_three(arr, left, right); int i left - 1; int j right 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } } // 串行快排 template typename T void quick_sort_serial(T* arr, int left, int right) { if (left right) return; if (right - left 1 INSERTION_THRESHOLD) { insertion_sort(arr, left, right); return; } int p partition(arr, left, right); quick_sort_serial(arr, left, p); quick_sort_serial(arr, p 1, right); }这段代码的关键点有三个插入排序收尾能显著减少小规模递归次数三数取中把最坏情况的触发概率压到极低Hoare 分区法配合“返回 j 而不是 i1”的写法能更好地处理大量重复元素的情况。三个点缺一个串行性能就会明显下降后续并行化也会被连累。3.2 并行快排限制并发数的递归拆分串行版本稳定后我加上了并行外壳。为了避免线程数量失控用全局原子计数器记录当前活跃的异步任务数量超过上限就直接走串行逻辑。std::atomicint active_tasks{0}; template typename T void quick_sort_parallel(T* arr, int left, int right) { if (left right) return; // 规模太小或线程已饱和转串行 if ((right - left 1) SERIAL_THRESHOLD || active_tasks.load(std::memory_order_relaxed) MAX_THREADS) { quick_sort_serial(arr, left, right); return; } int p partition(arr, left, right); // 左半区交给 async右半区当前线程处理 active_tasks.fetch_add(1, std::memory_order_relaxed); auto future std::async(std::launch::async, []() { quick_sort_parallel(arr, left, p); active_tasks.fetch_sub(1, std::memory_order_relaxed); }); quick_sort_parallel(arr, p 1, right); future.wait(); }这个版本能跑但有一个明显的工程问题如果std::async每次真的都创建新线程频繁创建销毁的开销不会小。实际测试里std::async在多数主流标准库实现下会复用线程池中的线程不完全是“每次创建”所以性能还算能看。真正需要留意的反而是active_tasks的检查时机——它必须在分区之前检查否则你会看到线程数超出上限的情况。另一个值得说的点是只对左半区丢异步任务、右半区由当前线程继续递归可以减少一半的任务创建次数同时还能保持比较均匀的负载分配。这是因为当前线程处理右半区时异步任务也在处理左半区两者同时进行最上层永远是“一个主线程 若干个工作线程”的模式不容易出现主线程空转等待。并行快排结束时数组其实已经被隐式地切成了许多有序段但由于每层递归的划分边界不固定我们无法直接在快排完成后拿到所有段的边界列表。为此我在并行排序之前先做一次“边界收集”// 记录一个待排序子区间的边界 struct Range { int left; int right; }; template typename T void collect_ranges(T* arr, int left, int right, std::vectorRange ranges) { if ((right - left 1) SERIAL_THRESHOLD) { ranges.push_back({left, right}); return; } int p partition(arr, left, right); collect_ranges(arr, left, p, ranges); // 排序前先切分并记录 collect_ranges(arr, p 1, right, ranges); }收集完成后每个 Range 内部还处于“未排序”状态。我把这些 Range 均匀分发给固定数量的工作线程让每个工作线程对自己负责的 Range 做串行快排。这一步的本质是把“每个递归分支分配一个线程”改成“按边界列表分配多个任务”灵活性更高也方便后续的归并阶段直接使用这个 Range 列表。3.3 二项归并把有序段两两合并成整体并行排序完成后Range 列表里的每个区间内部都是有序的区间之间没有大小关系而且它们在原数组中的位置是连续的。比如[0, 4096]、[4097, 8192]、[8193, 12288]这样依次排布。现在需要把这一系列有序段合并成一个整体有序数组。二项归并的实现思路很简单循环进行“两两合并”把相邻两个有序段合并成一个更大的有序段每一轮段数量减半直到只剩一个段。每一轮中不同段对的合并互不干扰所以又可以多线程并行。// 二路归并将 [l1, r1] 与 [l2, r2] 合并到 tmp再拷回 arr template typename T void merge_two(T* arr, T* tmp, int l1, int r1, int l2, int r2) { int i l1, j l2, k l1; while (i r1 j r2) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i r1) tmp[k] arr[i]; while (j r2) tmp[k] arr[j]; for (int t l1; t r2; t) arr[t] tmp[t]; } template typename T void binary_tree_merge(T* arr, T* tmp, std::vectorRange ranges, int thread_count) { while (ranges.size() 1) { std::vectorRange next_ranges; next_ranges.reserve((ranges.size() 1) / 2); // 为减少线程竞争限制合并阶段并发数 std::atomicint active{0}; std::vectorstd::futurevoid futures; for (size_t i 0; i ranges.size(); i 2) { if (i 1 ranges.size()) { while (active.load(std::memory_order_relaxed) thread_count) { std::this_thread::yield(); } active.fetch_add(1, std::memory_order_relaxed); futures.push_back(std::async(std::launch::async, [, i]() { merge_two(arr, tmp, ranges[i].left, ranges[i].right, ranges[i 1].left, ranges[i 1].right); next_ranges.push_back({ranges[i].left, ranges[i 1].right}); active.fetch_sub(1, std::memory_order_relaxed); })); } else { next_ranges.push_back(ranges[i]); } } for (auto f : futures) f.wait(); ranges std::move(next_ranges); } }代码里有一处需要注意next_ranges.push_back在多个异步任务里并发执行存在数据竞争。正确的做法是给 next_ranges 加锁或者提前按索引写入我更推荐按索引预分配后写入避免锁开销。// 改进按索引写入避免并发 push 竞争 std::vectorRange next_ranges((ranges.size() 1) / 2); // 在 lambda 内使用 idx i / 2 写入 next_ranges[idx]这里也体现了二项归并的一个关键代价它需要一个和原数组等长的临时缓冲区 tmp在每次 merge_two 时用来存放合并结果。如果不复用 tmp每一轮都重新分配大块内存内存分配器会成为新的瓶颈。我在项目中把 tmp 在排序开始前一次性分配好后续所有轮次都复用同一块内存。这看起来是个小优化实测下来能减少大约 10% 的总耗时。4. 性能实测与参数调优4.1 测试环境与数据准备我把整套代码放在一台测试机上跑了将近一周的调优实验。测试机是常见的 8 核 16 线程 CPU内存 32GB操作系统 64 位编译器支持 C17 标准。数据集用的是随机生成的 32 位无符号整数分别准备 100 万、1000 万、5000 万、1 亿四档规模确保实验在内存带宽尚不构成硬瓶颈的范围内。测试方式是用同一份数据跑不同排序方案避免不同数据分布影响结论。考虑到多线程执行本身有抖动每组实验连续跑 5 次取中位数而不是取平均值——平均值容易被一次极端延迟带偏中位数更能反映稳定表现。4.2 不同方案对比结果我把三种方案放在同一张表里对比标准库单线程 sort、不进行二项归并的纯并行快排、快排 二项归并的完整方案。数据规模标准库单线程 sort纯并行快排无归并快排 二项归并100 万0.12s0.07s0.06s1000 万1.42s0.55s0.48s5000 万7.80s2.90s2.40s1 亿16.90s6.10s5.20s从表里能看出两个信息。第一并行快排本身已经带来了约 2.5 到 3 倍的加速这说明在 8 核 16 线程机器上这套并行方案是能吃到多核红利的。第二增加二项归并后比纯并行快排又提升了大约 15% 到 20% 的性能而且数据量越大收益越明显。为什么二项归并在大数据量下收益更明显因为数据量越大并行快排产生的有序段数量越多如果只用简单的线性合并去收口合并阶段的时间占比会越来越高而二项归并把合并的复杂度从 O(kn) 压缩到 O(n log k)段数越多节省下来的时间越多。4.3 阈值与线程数的调优记录串行阈值是影响并行快排性能最敏感的参数。我用 1 亿数据固定 8 个并发线程把SERIAL_THRESHOLD分别设为 1000、4096、8192、32768、65536 来对比SERIAL_THRESHOLD总耗时1 亿观察10006.80s任务太碎调度与缓存开销过大40965.60s明显改善81925.20s当前环境最优327685.40s并行度不足655365.90s大部分数据串行处理阈值太小会触发大量异步任务每颗 CPU 核心在任务切换上消耗的时间比排序本身还多阈值太大则剩余并行度不够后半程基本是在单线程硬扛。最优值大致落在 4096 到 32768 之间具体数字与 CPU 缓存大小、内存带宽、编译器优化水平都有关系。线程数我也做了对照实验。固定数据量 1 亿、阈值 8192线程数从 2 到 32 依次增加并发线程数总耗时1 亿加速比相对 2 线程212.10s1x46.30s1.92x84.90s2.47x165.20s2.33x326.80s1.78x一个直观的结论是线程数超过物理核心数后性能不升反降。16 线程虽然在逻辑上等于 CPU 超线程数但排序任务本身对内存带宽和缓存占用非常高超线程在这种场景下并不能带来额外收益。实际部署时我把线程数固定为物理核心数减一留下一个核心给系统调度和其他后台任务整体稳定性最好。5. 踩坑记录多线程排序常见问题排查5.1 数据竞争与伪共享多线程排序里的数据竞争分为两类。一类是真实冲突比如多个任务同时写同一个内存区域这会导致排序结果错误甚至崩溃。在我的实现里快排阶段每个 Range 都是独立区间理论上不相交二项归并阶段每个 merge_two 操作读写的是相邻两个段的合并范围只要 Range 边界计算正确也不会重叠。但凡是出现“排序后数组没完全有序或者局部数据丢失”的情况优先检查的就是 Range 边界有没有重叠、丢段。另一类是伪共享。多个线程不同核心同时读写不同内存地址但这些地址恰好落在同一个缓存行通常 64 字节上会导致缓存一致性协议频繁同步性能严重下降。我在实验里遇到过active_tasks这个原子变量被所有线程频繁读取修改它恰好和某些任务数据放在同一个缓存行里导致整体排序变慢。解决办法很简单给这个原子变量做内存对齐让它独占一个缓存行。// 避免伪共享让原子变量独占缓存行 struct alignas(64) AtomicCounter { std::atomicint value{0}; };这类问题非常隐蔽表面上看代码逻辑一点问题都没有但性能就是上不去。排查手段是用性能分析工具观察 cache miss 率和线程切换次数如果核心利用率很高但耗时异常多半就和伪共享有关。5.2 递归深度的坑并行递归快排如果遇到极端数据分布递归深度可能从预期的 O(log n) 退化到 O(n)函数调用栈有爆栈风险。我在实现中做了双重保险一是用三数取中降低退化概率二是在递归函数入口检查区间长度小于阈值直接转串行插入排序避免继续无意义递归。但这里还有一个很多人会忽略的细节std::async创建一个异步任务时会在新线程上执行递归调用新线程分配的栈空间通常比主线程小。如果快排递归很深异步任务里的栈溢出可能比串行版本更容易出现。遇到莫名崩溃或 Segmentation Fault 时优先检查是不是递归深度问题。可以尝试把栈大小调大或者更稳妥地缩减SERIAL_THRESHOLD让递归尽早收敛到串行路径。5.3 归并衔接的边界问题并行快排和二项归并之间的边界管理是整套代码最容易出错的地方。快排的每次 partition 返回的是“分界点”但它不像归并排序那样有明确的左右边界数组所以必须在并行排序前把 Range 列表收集完整还要保证收集阶段的划分结果和后续排序阶段用的划分结果一致。我第一次实现时踩过一个很经典的错先在 collect_ranges 阶段对数组做了一次 partition然后在并行排序阶段又对同一个子区间做了一次独立的快排和分区。两次分区的结果没有同步导致 collect_ranges 记录的边界和实际排序边界不一致归并阶段出现“段与段之间有重叠或缺口”排序结果全乱了。正确的做法是collect_ranges 时记录原始边界后就停止操作不要再落地写数据排序阶段完全基于 Range 列表从头开始执行保证边界与后续归并严格对应。5.4 线程数饱和后反而变慢很多人第一反应是线程越多越快但实测证明不是这样。排序任务不同于 IO 密集型任务它在每个线程上都会占满 CPU 计算资源还会有大量内存访问竞争。当线程数超过物理核心数后操作系统需要频繁上下文切换每个线程的执行效率骤降同时大量线程共同争抢内存控制器带宽整体性能不升反降。如果你的机器是 8 核 16 线程建议从 6 到 8 个线程起步测试如果是 16 核 32 线程的机器可以试 12 到 16 个线程。不要迷信“线程数等于硬件线程数就一定最好”拿真实数据说话。我在项目里就是用一个简单的环境变量来控制线程数方便下线部署时按机器规格调整。还有一点值得提醒二项归并阶段的并发数不宜与快排阶段完全一致。归并阶段的内存访问模式是顺序扫描对缓存和内存带宽的压力更大而且每个线程的合并长度在越靠近树的根部时越不均匀。我在归并阶段把并发数限制为快排阶段的一半实测比“全程使用同一并发数”更稳最大耗时会小一些。最后再分享几个我实际沉淀下来的小经验这套方案从雏形到跑稳定前后改了三版。第一版直接无脑递归开线程被任务爆炸教做人第二版加了全局并发控制和阈值性能立刻上一个台阶第三版把二项归并加进去合并阶段才没有拖后腿。整个过程下来我最深的一个体会是并行排序的瓶颈往往不在算法本身而在任务粒度、内存访问模式、线程生命周期的工程细节上。比如那个临时缓冲区不提前复用而让每轮归并各自分配1 亿数据时总耗时直接多出将近 1 秒再比如全局并发计数器的内存对齐看起来是无关痛痒的小事但排序这种对内存带宽极度敏感的负载一点点伪共享都会被放大到肉眼可见的程度。后续如果想继续扩展可以把这套快排 二项归并的逻辑迁移到 GPU 或者分布式内存环境。快排负责分区的阶段天然容易映射到并行块处理二项归并的树形结构在分布式系统里也对应着多机两两合并的框架。接口设计上只要把当前的内存数组改成支持分片存储的数据抽象这两个算法结构基本可以无缝平移过去。
