Rust RFC 1884 深度解读:sort_unstable 与 pdqsort——为 libcore 引入的非分配型不稳定排序

原创2026-10-14 22:35:191,967 阅读
文章标签:文档

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,它有三个特点:

  1. 稳定:不会打乱相等元素的相对顺序——这是一个"好但保守"的默认值;
  2. 分配额外内存:排序过程需要堆分配;
  3. 在 #![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),理由有三:

  1. 基数排序对数据中的"模式"不敏感——完全随机与部分有序的输入它一视同仁,难以结合数据模式优化;
  2. 它本质上是非比较排序,与基于比较的通用 API 不兼容,作为通用排序入口很别扭;
  3. 即便忽略以上两点,它并不比 pdqsort 快多少,性价比不足。

教学与文档:How We Teach This

"稳定性"是一个容易造成混淆的重载术语。RFC 特别担心:slice::sort_unstable 可能被误读为"API 本身不稳定"的函数。为此文档策略有两条硬性要求:

  1. 文档必须清楚说明"stable"与"unstable"的确切含义(不重排相等元素 / 可能重排相等元素);
  2. slice::sort_unstable 的文档必须明确声明其保证不分配内存。

同时,slice::sort 的文档中会提及 sort_unstable 作为"更快、不分配"的替代选项,形成互相引用的文档闭环。

权衡与替代方案

Drawbacks(代价)

  • 排序相关代码量增大,标准库的 review 负担随之增加;
  • 用户可能遇到"slice::sort 反而比 sort_unstable 快"的反直觉情况。RFC 的应对是:这些特例可以在文档中解释清楚。

Alternatives(备选设计)

RFC 讨论了三种替代方案,均被否决:

  1. 对基本整数做特化:排序基本整数时,稳定与不稳定不可区分。可以特化 slice::sort,在元素为基本整数时回退到 sort_unstable 以提升性能。但"按类型逐个打补丁、混用不同算法"会让性能表现变得不一致、难以预测,因此被否决。
  2. 改名为 sort_noalloc / sort_unstable_noalloc:命名上突出"零分配"承诺,语义更直白,但读起来别扭得多,被否决。
  3. 作为独立 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 的设计预期。

延伸阅读

登录后查看全文
rfcs