1.1 数据布局

  6 分钟阅读  

原文链接: https://rust-unofficial.github.io/too-many-lists/first-layout.html

好，链表是什么？基本上就是堆上（内核党先别吵！）一串按顺序互相指向的数据。链表是过程式程序员不该用十英尺杆子碰的东西，却是函数式程序员什么都用的结构。公平起见，我们向函数式程序员要链表的定义。他们大概会给你类似下面的定义：

1

List a = Empty | Elem a (List a)

大致读作：「List 要么是 Empty，要么是 Element 后面跟着一个 List」。这是用和类型（sum type）表达的递归定义，fancy 名字指的是「可以有不同取值、且取值类型可能不同的类型」。Rust 把和类型叫 enum！若你来自类 C 语言，这就是你熟悉并喜爱的 enum，只是开到了满功率。把函数式定义抄进 Rust 吧！

暂时不用泛型，保持简单。只支持存有符号 32 位整数：

1
2
3
4
5
6
7

// 在 first.rs 中

// pub 表示我们希望模块外的人也能使用 List
pub enum List {
    Empty,
    Elem(i32, List),
}

呼，累死了。先编译一下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

> cargo build

error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:4:1
  |
4 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
5 |     Empty,
6 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

好吧。不知你怎样，我确实觉得被函数式编程社区背叛了。

若我们真去看错误信息（熬过背叛感之后），会发现 rustc 其实在告诉我们怎么解决：

insert indirection (e.g., a Box, Rc, or &) at some point to make first::List representable

好，box。那是啥？谷歌 rust box……

std::boxed::Box - Rust

看看……

pub struct Box<T>(_);

A pointer type for heap allocation. See the module-level documentation for more.

点链接

Box<T>，口语里叫「box」，提供 Rust 里最简单的堆分配形式。Box 拥有这块分配，离开作用域时 drop 其内容。

Examples

Creating a box:

let x = Box::new(5);

Creating a recursive data structure:

1
2
3
4
5

#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

1
2
3
4

fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{:?}", list);
}

This will print Cons(1, Box(Cons(2, Box(Nil)))).

Recursive structures must be boxed, because if the definition of Cons looked like this:

Cons(T, List<T>),

It wouldn’t work. This is because the size of a List depends on how many elements are in the list, and so we don’t know how much memory to allocate for a Cons. By introducing a Box, which has a defined size, we know how big Cons needs to be.

哇。这也许是我见过最贴切、最有用的文档。字面意义上文档第一件事就是我们正想写的、为何不行、怎么修。

文档真棒。

好，照做：

1
2
3
4

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

1
2
3

> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

嘿，编过了！

……但这其实是 List 的非常愚蠢的定义，原因有好几个。

考虑有两个元素的链表：

1
2
3
4

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

有两个关键问题：

  • 我们分配了一个节点，它只说「我其实不是 Node」
  • 其中一个节点根本不是堆分配的。

表面上看，这两点似乎互相抵消。我们多堆分配了一个节点，但有一个节点不必堆分配。然而考虑下面这种可能的布局：

1

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)

这种布局里我们无条件堆分配所有节点。关键区别是第一种布局里没有垃圾。这垃圾是什么？要理解它，得看 enum 在内存里怎么布局。

一般来说，若有这样的 enum：

1
2
3
4
5
6

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

Foo 需要存一个整数，表示它代表 enum 的哪个变体（D1、D2、…… Dn）。这就是 enum 的标签。还需要足够空间存 T1、T2、…… Tn 中最大的那个（再加一些空间满足对齐）。

这里的大结论是：尽管 Empty 只有一比特信息，它必然占用指针加一个元素的空间，因为它随时可能变成 Elem。因此第一种布局会堆分配一个充满垃圾的额外元素，比第二种布局多占一点空间。

有一个节点完全不分配，也许令人惊讶，也比总是分配更糟。因为这给我们不统一的节点布局。对压入弹出影响不大，但对拆分合并链表有影响。

考虑两种布局下拆分链表：

1
2
3
4
5
6
7
8

layout 1:

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

split off C:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)

1
2
3
4
5
6
7
8

layout 2:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

split off C:

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)

布局 2 的拆分只需把 B 的指针拷到栈上并把旧值置空。布局 1 最终也做同样的事，但还要把 C 从堆拷到栈。合并是反向过程。

链表少数好处之一是可以在节点里构造元素，然后在链表间自由挪动而不移动元素本身。你只摆弄指针，东西就「动了」。布局 1 毁掉了这个性质。

好，我相当确信布局 1 很糟。怎么重写 List？可以：

1
2
3
4
5

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

希望你觉得这更糟。最突出的是这让逻辑复杂很多，因为出现了完全无效的状态：ElemThenNotEmpty(0, Box(Empty))。它仍然有元素分配不统一的问题。

但它有一个有趣性质：完全避免为 Empty 分配，堆分配总数减 1。不幸的是，这样反而浪费更多空间！因为之前的布局利用了空指针优化。

我们之前看到每个 enum 都要存标签，说明其比特代表哪个变体。但若有一种特殊 enum：

1
2
3
4

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

空指针优化就会生效，省掉标签所需的空间。若变体是 A，整个 enum 全设为 0。否则是 B。这可行是因为 B 不可能全是 0，因为它包含非零指针。巧妙！

能想到其他能做这种优化的 enum 和类型吗？其实很多！所以 Rust 不规定 enum 布局。Rust 还会为我们做几种更复杂的 enum 布局优化，空指针优化肯定最重要！ 这意味着 &、&mut、Box、Rc、Arc、Vec 以及 Rust 里其他几种重要类型放在 Option 里时没有额外开销！ （这些我们后面会陆续讲到。）

那怎么避免额外垃圾、统一分配，又得到甜蜜的空指针优化？需要更好地区分「有元素」和「再分配一条链表」。为此得稍微 C 一点：结构体！

enum 让我们声明能包含若干取值之一的类型，struct 让我们声明同时包含多个*值的类型。把 List 拆成两种类型：List 和 Node。

和之前一样，List 要么是 Empty，要么是一个元素后面跟着另一条 List。 把「有元素后面跟着另一条 List」用完全独立的类型表示，就能把 Box 放到更优的位置：

1
2
3
4
5
6
7
8
9

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

检查优先级：

  • 链表尾部从不分配额外垃圾：✓
  • enum 是美味的空指针优化形式：✓
  • 所有元素统一分配：✓

好！我们其实正好构造了用来证明第一种布局（官方 Rust 文档建议的那种）有问题的布局。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

:(

Rust 又对我们发火了。我们把 List 标成 public（因为希望别人能用），但没把 Node 标 public。问题是 enum 的内部完全 public，我们不能公开谈论私有类型。可以把整个 Node 都 public，但 Rust 里通常倾向把实现细节藏起来。把 List 改成 struct，就能隐藏实现细节：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

因为 List 是只有一个字段的 struct，它的大小和该字段相同。零成本抽象，耶！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

> cargo build

warning: field is never used: `head`
 --> src/first.rs:2:5
  |
2 |     head: Link,
  |     ^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/first.rs:11:5
   |
11 |     elem: i32,
   |     ^^^^^^^^^

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

好，编过了！Rust 挺生气，因为在它看来我们写的东西完全没用：从没用过 head，用我们库的人也不能，因为它是私有的。传递下去，Link 和 Node 也没用。解决它！给 List 实现点代码！

最后修改 August 23, 2026: 更新 (499855b16)