Rust RFC 1884 深度解读:sort_unstable 与 pdqsort——为 libcore 引入的非分配型不稳定排序
Rust RFC 1884 深度解读:sort_unstable 与 pdqsort——为 libcore 引入的非分配型不稳定排序
本篇以 Rust 官方 RFC 仓库中的 RFC 1884 原文(text/1884-unstable-sort.md) 为绝对主体,完整还原其设计动机、API 形态、算法选型与替代方案讨论,并结合仓库内相关的 RFC 与流程文档做纵深补充。读完本文,你将透彻理解"稳定性"与"堆分配"这两个排序 API 的关键设计维度,掌握 sort_unstable / sort_unstable_by / sort_unstable_by_key 的完整用法与语义,并了解 pattern-defeating quicksort(pdqsort)为何能成为 Rust 标准库不稳定排序的奠基算法。
RFC 背景:Rust 为何需要内置的不稳定排序
RFC 1884 的 Summary 目标非常简洁:在 libcore 中增加一个不稳定排序(unstable sort)。提出之时(2017 年 2 月),libstd 中唯一的排序函数是 slice::sort,它有三个特点:
- 稳定:不会打乱相等元素的相对顺序——这是一个"好但保守"的默认值;
- 分配额外内存:排序过程需要堆分配;
- 在
#![no_std]环境中不可用:原因正是上一条——它要分配内存。
RFC 指出,稳定性在实践中很少是必需性质;相比之下,更高的性能、更低的内存开销往往更值得追求。而当时的 Rust 只能通过第三方 crate(如 pdqsort)获得高性能的不稳定排序,对一个系统编程语言来说,这是一种不寻常的缺失。把"性能好、零分配"的不稳定排序放进 libcore,正好填补这一空白。
稳定性 FAQ:厘清核心概念
RFC 用一组问答澄清了稳定性相关的核心概念,这是理解整个设计的基础。
Q:什么是稳定性?
如果排序函数不会重排相等元素的相对顺序,那么它就是稳定的。
RFC 给出了如下对照示例:
let mut orig = vec![(0, 5), (0, 4)];
let mut v = orig.clone();
// 稳定排序保留相等元素的原始顺序
v.sort_by_key(|p| p.0);
assert!(orig == v); // OK!
// 不稳定排序"可能"保留、也可能不保留原始顺序
v.sort_unstable_by_key(|p| p.0);
assert!(orig == v); // MAY FAIL!
两个元素的 p.0 都是 0(相等键):sort_by_key 是稳定的,因此 (0, 5) 一定排在 (0, 4) 之前;而 sort_unstable_by_key 不提供这一保证,断言可能失败。这个示例同时演示了 sort_by_key 与 sort_unstable_by_key 在命名上的一一对应关系。
Q:稳定性什么时候有用?
不多见。典型例子是交互式 GUI 表格的列排序:希望行先按列 Y 排序、在键相等时再按列 X 打破平局,于是用户先点列 Y、再点列 X——这个过程要求排序是稳定的。
Q:能否用不稳定排序实现稳定排序?
可以。把 [T] 变换为 [(T, usize)]:为每个元素配上原始下标,执行不稳定排序,最后去掉下标,结果就等价于稳定排序。下面给出一个可运行的完整实现:
let items = vec![(2, "b"), (1, "x"), (1, "a")];
// 第一步:为每个元素附加其原始下标
let mut indexed: Vec<((i32, &str), usize)> =
items.iter().cloned().enumerate().collect();
// 第二步:以“(元素, 原始下标)”作为键做不稳定排序
indexed.sort_unstable_by_key(|&(item, idx)| (item, idx));
// 第三步:剥离下标,恢复为 [T]
let sorted: Vec<_> = indexed.into_iter().map(|(item, _)| item).collect();
assert_eq!(sorted, vec![(1, "x"), (1, "a"), (2, "b")]); // 相等键 (1, *) 保持原始顺序
因为键中携带下标,键相等的两个元素会按下标决出先后,最终顺序与稳定排序完全一致。
Q:为什么 slice::sort 是稳定的?
因为"稳定"是一个好的默认值。程序员调用排序函数时未必会先查文档确认是否稳定,而"稳定"是最符合直觉的假设;如果 slice::sort 默认做不稳定排序,容易造成令人不快的意外。RFC 引用了一个 Swift 排序问题的真实案例作为教训。
Q:为什么 slice::sort 会分配内存?
实现一个不分配内存的稳定排序是可能的,但会明显更慢。稳定排序(本质上是归并类算法)与"零分配"很难兼得。
Q:为什么 slice::sort 与 #![no_std] 不兼容?
因为它需要额外分配内存。
Q:不稳定排序能快多少?
用 pdqsort 对 1000 万个 64 位整数排序,比 slice::sort 快 45%(该基准数据来自 RFC 引用的 pdqsort crate 的 extensive benchmarks)。这正是把不稳定排序放进 libcore 的最大收益点。
Q:不稳定排序能否受益于分配内存?
通常不能。计算机科学中并不存在"必须分配才能更快"的定理,但实践中"零分配"与"不稳定"总是相辅相成——这也是 RFC 1884 把两者绑定在一起的现实依据。
详细设计:镜像 slice::sort 的三件套 API
RFC 1884 的 Detailed design 提出在 core::slice 中新增三个函数,与 libstd 现有的排序 API 一一对应:
| libstd(稳定排序) | libcore(新增,不稳定排序) |
|---|---|
slice::sort |
core::slice::sort_unstable |
slice::sort_by |
core::slice::sort_unstable_by |
slice::sort_by_key |
core::slice::sort_unstable_by_key |
有意思的是,C++ 的默认值恰好相反:std::sort 默认是不稳定排序,而 std::stable_sort 才是稳定排序。Rust 选择把"稳定"留给默认的 sort,把"不稳定"作为显式的 sort_unstable,遵循了"稳定性是安全默认"的设计哲学。
接口定义(RFC 原始提案)
RFC 给出的接口位于当时标准的 SliceExt trait 中(这是彼时给 slice 扩展方法所用的特性门控机制):
pub trait SliceExt {
type Item;
// ...
fn sort_unstable(&mut self)
where Self::Item: Ord;
fn sort_unstable_by<F>(&mut self, compare: F)
where F: FnMut(&Self::Item, &Self::Item) -> Ordering;
fn sort_unstable_by_key<B, F>(&mut self, mut f: F)
where F: FnMut(&Self::Item) -> B,
B: Ord;
}
三个方法的约束条件值得逐条说明:
sort_unstable要求元素类型实现Ord(全序),因此可以直接用默认比较;sort_unstable_by接受自定义比较器F: FnMut(&Item, &Item) -> Ordering,FnMut意味着比较器可以是带内部状态的可变闭包;sort_unstable_by_key接受键提取闭包F: FnMut(&Item) -> B,要求键类型B: Ord,适合"按结构体某个字段排序"这类高频场景。
补充:
SliceExt是 Rust 2018 之前 slice 扩展方法所处的过渡形态。RFC 被接受后,sort_unstable系列最终以<a href="https://link.gitcode.com/i/face0e0b17ffe38663f8b1ecbeeff478" target="_blank">T]上的固有方法(inherent method)形式落地,这一事实可从仓库内另一份相关 RFC [text/2351-is-sorted.md 中找到旁证——该 RFC 在讨论is_sorted的归属时明确提到"sort及其同类方法都是直接定义在 slice 上的",并主张is_sorted也应如此。
示例:三个 API 的完整运行语义
RFC 给出了一个覆盖全部三个函数的示例,下面逐行解读其语义:
let mut v = [-5i32, 4, 1, -3, 2];
v.sort_unstable();
assert!(v == [-5, -3, 1, 2, 4]); // 全序升序排列
v.sort_unstable_by(|a, b| b.cmp(a)); // 自定义比较器:反转比较方向
assert!(v == [4, 2, 1, -3, -5]); // 得到降序
v.sort_unstable_by_key(|k| k.abs()); // 按绝对值排序
assert!(v == [1, 2, -3, 4, -5]); // |-3| 与 |3| 位置上的元素顺序无保证
第一个断言验证默认升序;第二个断言通过 b.cmp(a) 反转比较方向得到降序;第三个断言按 abs() 键排序,此时 -3 与 3(abs 值相等)之间的相对顺序不受任何保证——这正是"不稳定"语义在示例中的体现。
在 no_std 中的实际用法
由于三个 sort_unstable* 函数位于 libcore、不依赖堆分配,它们是 #![no_std] 环境的天然选择:
#![no_std]
// 只依赖 core,不需要分配器
let mut arr = [3i32, 1, 2];
arr.sort_unstable();
assert_eq!(arr, [1, 2, 3]);
对比之下,slice::sort 因需要堆分配而在 no_std 环境中不可用(详见前文"为什么 slice::sort 与 no_std 不兼容")。
实战选型建议
综合 RFC 的动机论证,可以给出如下选型建议:
- 默认使用
sort(或sort_by/sort_by_key):行为保守、语义符合直觉,适合绝大多数业务代码; - 追求性能、数据量较大时改用
sort_unstable系列:零分配且更快,适合对延迟敏感的系统编程场景; no_std/ 嵌入式环境只能使用sort_unstable系列:这是其进入 libcore 的根本原因;- 需要自定义顺序时使用
_by变体,需要按键排序时使用_by_key变体,二者与_unstable前缀可自由组合。
算法选型:为什么是 pdqsort(pattern-defeating quicksort)
RFC 用相当篇幅论证了算法选择。首先盘点主流语言的不稳定排序实现:
| 语言 | 排序算法 |
|---|---|
| C | quicksort |
| C++ | introsort |
| D | introsort |
| Swift | introsort |
| Go | introsort |
| Crystal | introsort |
Java(Arrays.sort) |
dual-pivot quicksort |
introsort:quicksort 的深度保险
最流行的选择是 introsort——一种限制递归深度的 quicksort。当递归深度超过 2 * log(n) 时,算法切换到 heapsort,从而保证最坏情况复杂度为 O(n log n)。它结合了两者的优点:quicksort 优异的平均性能 + heapsort 可靠的最坏情况表现。
dual-pivot quicksort
Java 的 Arrays.sort(注意不是 Collections.sort)使用双轴快速排序:一次选取两个枢轴,划分粒度更细,实践中性能更好。
pdqsort:introsort 的现代改进
pdqsort(pattern-defeating quicksort)是 introsort 的最新改进,在常见场景下明显更快。它的关键技巧之一是论文 BlockQuicksort(ESA 2016)中提出的**块划分(block partitioning)**技术,通过批量化处理分区过程中的元素扫描与交换,减少分支预测失败的代价,从而显著提速。RFC 指出,这一算法当时尚未被任何编程语言的标准库内置,但已有 C++ 实现计划将其纳入;在所有候选中,pdqsort 是明确的最优解。
RFC 同时记录了 pdqsort 的性能对比结论:对 1000 万个 64 位整数排序,pdqsort 比 slice::sort 快约 45%(与 Motivation 部分的基准数据一致)。
什么时候反而该用 slice::sort?
RFC 坦诚地列出了稳定排序偶尔反超的场景:
- 切片由若干已排序子序列拼接而成时,
slice::sort很可能更快(归并类算法能识别这种结构并加以利用); - 比较函数代价高昂(例如排序字符串)时,
slice::sort非常善于压低比较次数,而 pdqsort 以略多的比较换取了更少的内存写入。
除此之外,slice::sort 总体慢于 pdqsort。这一结论也为后文 Drawbacks 中"用户可能惊讶地发现 slice::sort 更快"的讨论埋下伏笔。
为什么不用 radix sort?
RFC 明确排除了基数排序(radix sort),理由有三:
- 基数排序对数据中的"模式"不敏感——完全随机与部分有序的输入它一视同仁,难以结合数据模式优化;
- 它本质上是非比较排序,与基于比较的通用 API 不兼容,作为通用排序入口很别扭;
- 即便忽略以上两点,它并不比 pdqsort 快多少,性价比不足。
教学与文档:How We Teach This
"稳定性"是一个容易造成混淆的重载术语。RFC 特别担心:slice::sort_unstable 可能被误读为"API 本身不稳定"的函数。为此文档策略有两条硬性要求:
- 文档必须清楚说明"stable"与"unstable"的确切含义(不重排相等元素 / 可能重排相等元素);
slice::sort_unstable的文档必须明确声明其保证不分配内存。
同时,slice::sort 的文档中会提及 sort_unstable 作为"更快、不分配"的替代选项,形成互相引用的文档闭环。
权衡与替代方案
Drawbacks(代价)
- 排序相关代码量增大,标准库的 review 负担随之增加;
- 用户可能遇到"
slice::sort反而比sort_unstable快"的反直觉情况。RFC 的应对是:这些特例可以在文档中解释清楚。
Alternatives(备选设计)
RFC 讨论了三种替代方案,均被否决:
- 对基本整数做特化:排序基本整数时,稳定与不稳定不可区分。可以特化
slice::sort,在元素为基本整数时回退到sort_unstable以提升性能。但"按类型逐个打补丁、混用不同算法"会让性能表现变得不一致、难以预测,因此被否决。 - 改名为
sort_noalloc/sort_unstable_noalloc:命名上突出"零分配"承诺,语义更直白,但读起来别扭得多,被否决。 - 作为独立 crate 提供:把不稳定排序放在标准库之外。但 RFC 反问:其他系统编程语言的标准库都有快速的不稳定排序,Rust 为何不该有?此方案也被否决——这正是"放进 libcore"这一决策的核心论证。
Unresolved questions
RFC 1884 的未决问题清单为空(None),说明设计在提出时已足够收敛。
历史走向与本 RFC 的长期影响
RFC 1884 于 2017 年 2 月提出,对应 Rust Issue 40585(信息见 RFC 原文头部)。此后该设计被接受,sort_unstable、sort_unstable_by、sort_unstable_by_key 以 [T] 固有方法的形式进入标准库并稳定(sort_unstable 系列自 Rust 1.20 起可用)。值得留意的是,标准库的排序实现此后仍在持续演进(例如后续版本中又引入了 ipnsort、driftsort 等新算法),但本 RFC 确立的三件套 API 形态、零分配承诺、不稳定语义至今未变,一直是 Rust 排序生态的地基。
RFC 还确立了"raw / _by / _by_key 三件套"这一 API 惯例。仓库内后续的 text/2351-is-sorted.md(为 slice 与 Iterator 增加 is_sorted 系列)正是沿用了同一惯例——该文档明确提到标准库中"排序相关函数都以 raw、_by、_by_key 三种风味出现",并以此论证 is_sorted_by_key 也应当存在。可见 RFC 1884 的影响力不止于排序本身,还塑造了后续 API 的设计预期。
延伸阅读
- RFC 1884 原文:text/1884-unstable-sort.md:本文主体文档,含完整接口定义与示例代码;
- RFC 2351:text/2351-is-sorted.md:基于 slice 排序 API 三件套惯例的后续 RFC,可交叉印证本 RFC 的长期影响;
- README.md:Rust RFC 流程总览,说明"实质性变更需走 RFC 流程"的规则;
- RFC 流程规范:text/0002-rfc-process.md:RFC 生命周期与评审流程的说明文档。