Dtsort 这个项目最值得关注的不是它又做了一个排序算法而是它把 decision-tree 的思路用在稳定排序上并且直接对标 C 标准库的 std::stable_sort。一个基于决策树的稳定排序要跑赢 std::stable_sort并没有想象中那么容易稳定排序天然要处理相等元素的相对次序移动和拷贝的开销也比普通排序更高标准库实现经过多年优化随便一个实验性排序想在所有数据分布上全面超越概率不大。所以这篇内容不会急着宣布谁胜谁负而是先把 Dtsort 要解决的问题讲清楚再给出一套可以复现的对比测试方法最后聊聊这类排序算法能不能安全替换标准库入口。我先把结论写在前面认真评测 Dtsort 这类项目重点不是看某个数据点上快了多少而是看它快在哪种分布、慢在哪种分布、比较次数是否真的下降、内存使用有没有失控、稳定排序的约束有没有被打破。下面按落地测评的顺序拆开讲。1. 稳定排序和 decision-tree 到底在同一个赛道上比什么1.1 稳定排序为什么比普通排序更贵稳定排序要求排序前后相等 key 的相对顺序不变。工程实现里最常用的路径是归并排序先把序列拆成小块让小块内部有序再一点点合并出完整有序序列。合并时必须保证“先左边后右边”否则相等元素的原始顺序会被打乱。这个约束意味着稳定排序通常要做更多拷贝也需要更多临时空间。C 标准里的 std::stable_sort复杂度要求并不是简单的 O(N log N)。在临时内存充足的情况下很多标准库实现会走接近 O(N log N) 的归并路径临时内存不足时可能会退化成 O(N log² N) 的原地稳定归并。也就是说std::stable_sort 的真实性能受内存分配、元素类型和标准库实现影响很大。这恰恰是 Dtsort 这类项目可以找机会的地方。我这里不会把“std::stable_sort 很慢”当前提。准确的说法是std::stable_sort 是一个面向通用输入的契约型算法它必须先保证稳定、保证任何合法比较器都能工作、保证异常安全等附加条件。而 Dtsort 如果只针对常见数据模式和比较代价做优化自然有机会在特定输入上做得更快。1.2 decision-tree 想省下的可能是“无谓比较”不具体看 Dtsort 源码时可以从名称推断的只有一点它把排序决策组织成了树形结构。比较排序在理论上都可以展开成一棵决策树每次比较都是一个分支节点。普通归并排序的比较路径是动态决定也等于一棵树但树的形态由归并过程硬编码。Dtsort 的定位如果是“decision-tree based stable sort”更可能的思路是让算法根据输入特征走不同分支比如提前识别数据是否接近有序、重复 key 是否很多、比较代价是否偏高然后选择不同的内部策略。这么做的好处是减少“无谓比较”已经有序的区间就不用反复折腾大量重复 key 也不需要在递归和归并里浪费太多判断。但代价也很明显判断“走哪条分支”本身就要消耗 CPU 时间分支树越复杂单次比较开销越高。所以评测 Dtsort 不能只看平均时间长不长。要拆开看比较次数、分支预测命中、缓存局部性和拷贝次数。如果比较次数降了但整体时间没降说明决策树本身引入了额外开销如果比较次数差不多但时间变快那可能是缓存或移动路径更友好这种收益不一定能稳定复现。1.3 先确认“beats”是在哪个前提下成立项目标题说 Beats std::stable_sort但任何严肃评测都需要回答三个问题在哪种标准库实现上 beats在哪种元素类型和数据分布上 beats在多大并发、多少数据量、多少可用内存下 beats如果只是在一个编译器、一个平台、一组随机整数上跑赢了那这个结论的适用范围非常窄。标准库实现不是只有一种libstdc、libc、MSVC STL 的 std::stable_sort 内部策略都有差异差 20% 很正常。可复现评测的第一步就是先把这些条件全部固定而不是让项目名里的“beats”替你下结论。2. 复现前先固定环境、数据分布和正确性检查2.1 编译器和优化选项会影响结论排序这类微基准最怕两件事一是优化级别没统一二是不同标准库实现混在一起比。我建议先确定一组基准环境编译器版本例如 GCC 12、Clang 16或 MSVC 对应版本标准库实现libstdc、libc、MSVC STL 中明确一个编译选项使用-O2 -DNDEBUG作为第一轮基准是否开启架构原生优化-marchnative可作为第二轮对比但不要作为唯一结论使用-O0测排序没有任何意义因为标准库的 debug 迭代器和内存检查可能被启用排序慢更多是环境造成的不是算法差距。-O3也可以跑但要记录有时-O3的激进内联只对某个实现有利。如果需要跨编译器比较把 GCC 和 Clang 的结果分开记录不要合并成一条曲线。2.2 元素类型要能区分“比较贵”和“移动贵”Dtsort 如果主打减少比较次数那么元素里 key 的比较代价越高越能体现优势。如果只是对 int 排序决策树从额外分支里省下来的比较很可能被分支预测误差抵消。相比标准库int 排序已经快到极限优化空间不大。建议至少准备三种元素类型int比较和移动都很便宜适合看算法框架本身std::string作为 key 的元素比较昂贵适合观察比较次数下降是否有效带大 payload 的结构体移动昂贵适合观察稳定排序的拷贝行为有一点在写测试时很容易漏如果元素只包含 key排序的稳定性无法验证。要验证稳定就必须在元素里保留一个原始序号。测试元素可以设计成struct Item { int key; // 实际排序时只比较这个字段 std::uint64_t seq; // 原始顺序标记 };生成数据时给每个 Item 的seq赋值为0, 1, 2, ...排序完成后所有 key 相等的位置上seq 必须仍然递增。2.3 数据分布至少覆盖五类场景想验证“是否真的 beats std::stable_sort”数据分布不能只生成一个随机数组。决策树类方法往往对某些结构比较敏感比如有序前缀、重复 key 区间、局部乱序。如果测试数据太单一结论很容易被带偏。推荐覆盖以下五类数据模式生成思路主要观察点完全随机key 在较大范围内均匀分布通用性能基线已经有序key 从小到大排列对有序输入的优化是否有效完全逆序key 从大到小排列归并/分治路径是否退化大量重复 keykey 取值范围很小相等区间稳定性、比较压缩局部有序长有序片段里混入少量乱序接近真实增量数据的场景生成时使用固定随机种子保证两个算法每次拿到的是同一组数组。Dtsort 和 std::stable_sort 必须基于完全相同的输入进行对比不然任何耗时差别都不成立。2.4 稳定性检查不能交给肉眼排序结果是否有序不能用“感觉没问题”判断。普通有序性检查可以交给std::is_sorted但稳定性必须单独写一个检查函数。稳定性麻烦的地方在于不能为了让结果“看起来稳定”就在比较器里把 seq 当第二关键字。那样会破坏 key 相等的语义std::stable_sort 本来就能保证输出稳定因为整个比较对象已经变成唯一值了这完全测不出稳定性的意义。正确做法是bool check_stability(const std::vectorItem v) { for (size_t i 0; i v.size();) { size_t j i; while (j v.size() v[j].key v[i].key) { j; } for (size_t k i 1; k j; k) { if (v[k - 1].seq v[k].seq) { return false; } } i j; } return true; }这个函数检查的是在 key 相等的区间里seq 是否严格递增。如果相等 key 区间的原始相对顺序被打乱稳定性就失败了。Dtsort 如果宣称 stable却没有通过这个检查那后续性能数据再漂亮也没有意义。3. 最小对比测试怎么写才不会被误导3.1 每次从相同输入拷贝排序后立刻验证排序会修改输入数组。最容易犯的错误是先用同一个 vector 跑 std::stable_sort跑完后再用已经有序的数组跑 Dtsort。第二次排序开始时数据已经有序两个算法面临的输入完全不同结果自然不可信。正确结构是维护一个只读的“原始输入源”每次排序前都从头深拷贝一份。拷贝过程不计入排序耗时因为它不是评测目标。下面是一个最小评测骨架#include algorithm #include chrono #include cstdint #include cstdlib #include iostream #include vector struct Item { int key; std::uint64_t seq; }; bool sorted_by_key(const std::vectorItem v) { for (size_t i 1; i v.size(); i) { if (v[i].key v[i - 1].key) return false; } return true; } bool stable_order(const std::vectorItem v) { for (size_t i 0; i v.size();) { size_t j i; while (j v.size() v[j].key v[i].key) j; for (size_t k i 1; k j; k) { if (v[k - 1].seq v[k].seq) return false; } i j; } return true; } using SortFn void (*)(std::vectorItem); double time_once(const std::vectorItem src, SortFn fn) { std::vectorItem v src; // 每次从相同输入拷贝 auto t0 std::chrono::steady_clock::now(); fn(v); auto t1 std::chrono::steady_clock::now(); if (!sorted_by_key(v) || !stable_order(v)) { std::cerr invalid sort result\n; std::exit(1); } return std::chrono::durationdouble, std::milli(t1 - t0).count(); } void sort_std(std::vectorItem v) { std::stable_sort(v.begin(), v.end(), [](const Item a, const Item b) { return a.key b.key; }); } void sort_dtsort(std::vectorItem v) { // 这里换成 Dtsort 项目实际导出的入口函数 // 例如 dtsort::stable_sort(v.begin(), v.end(), comparator) // 本次示例不写死具体 API防止误导 }实际接入时把sort_dtsort内容替换成 Dtsort 头文件提供的真实函数。如果不清楚函数命名先看项目头文件不要靠猜。3.2 多轮采样取中位数不要只报最好成绩排序耗时受 CPU 频率、缓存状态、后台进程影响很大。只跑一次不够最好先跑一轮预热让页缓存和分支预测器进入较稳定状态再正式记录。对每个数据分布建议至少跑 5 到 10 轮最后取中位数。不建议只取最小值因为最小值本质上是“机器最安静时候的表现”不能代表日常生产环境中位数更能反映稳定可用的情况。如果想看上限可以额外记录最小值但报告结论时优先用中位数。如果数组长度很小比如只有几千个元素单次排序可能只有几十微秒直接取中位数仍会被计时精度干扰。可以把一轮改成连续排序多次计算总耗时再除以次数也可以直接加大数组规模到排序耗时稳定在几十毫秒以上。一般我建议从小规模开始验证正确性然后从 10 万元素开始记录性能。3.3 消耗排序结果防止编译器把无用代码优化掉微基准里还有一个隐藏问题如果排序后的数据不再被使用编译器在非常激进的内联和优化下有可能把部分无副作用代码裁掉。排序算法通常不会被整段移除但为了保险还是要在排序之后立即做有序性检查、稳定性检查或者至少算一个校验值。前面的time_once在计时结束后调用了sorted_by_key和stable_order这本质上消耗了排序结果。如果结果无效就直接退出不会继续进行无意义的耗时对比。这种做法既保护了计时有效性也避免把错误排序当成有效基准。3.4 计时的边界要控制好我习惯把拷贝放在计时外面把排序本身放在计时里面验证逻辑放在计时之后。这样计时区间只反映排序算法调用本身不包含深拷贝、数据生成和验证检查。如果目标是想评测“后端接口整体替换 std::stable_sort 之后用户感受到的差别”那可以把拷贝、分配和排序都放进计时但这套结果不能拿去和其他论文里的 sort 时间对比。先明确你到底在测哪个层次别混着谈。4. 真正要看的数据耗时、比较次数、内存峰值和方差4.1 耗时才只是表层的成绩单耗时是最直观的数据但它解释不了“为什么快”。同一个数据集上 Dtsort 如果比 std::stable_sort 快首先要看比较次数有没有下降。如果比较次数减少很多耗时却没什么变化说明 Dtsort 的比较逻辑比标准库重收益被抵消了。给比较器加计数不复杂struct CountingLess { std::uint64_t* count; bool operator()(const Item a, const Item b) const { (*count); return a.key b.key; } };在每次调用前把count归零传入 sort 入口排序完成后读取计数。但要注意排序算法内部可能复制比较器所以计数不要挂在比较器内部的对象字段上应该使用外部指针或引用。上面的写法通过指针指向外部 counter能正确累计。移动次数更难统计因为标准库可能直接使用已有对象的拷贝构造、移动构造和赋值。一种可行方案是写一个包装类在包装类的移动/拷贝函数里计数再把比较器委托给内部 key。这样能观察排序过程到底创建和搬动多少对象。这个方案对std::stable_sort和 Dtsort 都生效结果才可比。4.2 比较次数少不一定代表耗时少决策树排序和普通归并排序一个根本区别在于归并排序的比较通常简单且集中决策树排序每走一步可能需要判断当前数据属于哪个分支额外分支会让 CPU 分支预测变得更难。所以我一般会做两层判断第一层比较次数是否下降第二层单次比较/分支的平均成本是否上升如果 Dtsort 每比较一次都要付出大约 2 到 3 倍于标准库比较器的指令代价那么比较次数只降 30%耗时可能并不占优势。反过来如果比较次数下降 50% 以上耗时也下降那基本可以说明优化方向是对的。4.3 观察临时缓冲区和内存峰值std::stable_sort 在被临时内存允许时会使用额外缓冲区来提升合并效率内存分配失败时可能退回较慢的原地归并。Dtsort 如果用了不同策略内存足迹很可能完全不同。比较内存时不是只看排序前申请了多少。建议用系统工具查看进程峰值内存在 Linux 下可以在命令前加/usr/bin/time -v ./sort_benchmark然后查看Maximum resident set size。如果 Dtsort 用了一个较大的辅助数组内存峰值会比 std::stable_sort 高很多。对于小数组这无所谓但在大数据量、高并发服务里内存翻倍可能是致命问题。排序时间也要和高内存占用分开评价。一个排序器在多占用 100 MB 内存时跑得比标准库快 20%并不总是能直接上线。4.4 记录表最好区分“平均提升”和“局部提升”报告对比结果时不要只写一个“快了多少”。建议按数据分布扩成一张表数据模式std 中位数耗时Dtsort 中位数耗时std 比较次数Dtsort 比较次数稳定性完全随机msms次数次数通过已经有序msms次数次数通过完全逆序msms次数次数通过大量重复 keymsms次数次数通过局部有序msms次数次数通过在表格之外再记录一轮内存峰值和方差。拿到表之后可以先问自己如果 Dtsort 只在“大量重复 key”上赢在完全随机上输了 30%那么它更适合哪个业务显然答案是更适配重复 key 多的榜单更新、分组统计、批量去重场景而不是所有排序都换。5. 常见误差来源和排查顺序5.1 排序结果错乱时先查比较器和数据模型如果 Dtsort 输出没有通过有序性检查问题不一定只在算法内部。先确认比较器是不是严格弱序。比如比较器只写了a.key b.key或者相等时返回 true都会彻底破坏排序前提。再看稳定性检查方式。我见过很多人把一个带 seq 的 Item 直接按seq排一次然后说“std 稳Dtsort 不稳”。这属于对稳定排序理解偏了稳定性考察的是 key 相等时是否保持 seq 原顺序而不是让你把 seq 当第二比较条件。如果比较器同时比较 key 和 seq那么不存在“相等 key”的对象稳定性恒成立这个测试就失去意义。如果要在测试里快速寻找稳定性问题关键子必须是 key 本身seq 只是验证线索。5.2 耗时方差很大时先看环境而不是改代码排序基准很容易被机器噪声干扰。如果同一组测试两次运行相差超过 20%先不要比 Dtsort 和 std先做几轮预热确认后台没有编译任务、系统更新、云主机 CPU 抢占。必要时可以使用 CPU 绑核跑一轮或者在安静机器上复测。在云主机上跑微基准尤其要谨慎。虚拟化环境下 CPU 频率、缓存大小、邻居负载都不可控一次测试的波动可能比算法差距还大。5.3 输入分布太单一结论会失真如果只在完全随机数据上测相当于只验证了决策树排序的一个侧面。决策树如果真的有训练或拟合成分它会在和“训练数据分布”接近的输入上表现更好在分布外数据上可能退化。建议至少加两组“不太好”的数据一组是高度重复 key一组是已经有序一组是逆序。这三个分布往往能暴露排序算法的最坏情况也能帮我们判断它到底是通用算法还是特化排序。5.4 原数组被复用导致第二次排序输入不同这是基准测试里最隐蔽也最常犯的错误。第一个算法对数组排序完成后如果不恢复数组原状第二个算法拿到的是已经排好序的数据。已经有序的数据对任何排序算法都不公平