基本布局

好吧,所以链表是什么东西呢?大致上说,它是一大片相互指向的数据,以顺序连接起来(嘘,Linux内核!)。链表是过程式程序员应该用一切代价避免的东西,而函数程序员则在所有情况下使用它。那么,看起来向函数式程序员询问链表的定义是很公平的。他们可能会给你类似这样的定义:

List a = Empty | Elem a (List a)

它可以大致读成“一个列表要么是空的,要么是一个元素接着一个列表”。这是用一个复合类型(sum type)表达的递归定义,而复合类型只是“一个可以拥有多种类型的值的类型”的酷炫叫法。Rust把复合类型称作enum!如果你是从一个C系语言过来的,那么这正是你所熟知并热爱的枚举类型,但是强大了许多。让我们把这个函数式的链表定义转录到Rust吧!

现在为了保持说明简单,我们会避开泛型。我们暂时只支持有符号的32位整数:

// 在 first.rs 中

// pub 表明我们想让这个模块外之外的人使用这个 List
pub enum List {
    Empty,
    Elem(i32, List),
}

呼,这一点也不麻烦嘛。我们继续下去编译它吧:

> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/lists)
src/first.rs:1:1: 4:2 error: illegal recursive enum type; wrap the inner value in a box to make it representable [E0072]
src/first.rs:1 pub enum List {
src/first.rs:2    Empty,
src/first.rs:3    Elem(T, List),
src/first.rs:4 }
error: aborting due to previous error
Could not compile `lists`.

不!!!!函数式程序员欺骗了我们!它让我们做了不合法的东西!这是圈套!

……

我冷静下来了。你冷静了么?如果我们真正去检查错误消息(而不是像我们中的某些人一样,准备逃出这个国家),我们就会发现rustc实际上在告诉我们如何解决这个问题:

illegal recursive enum type; wrap the inner value in a box to make it representable 不合法的递归枚举类型;把值包装在一个box里让它变得可表示 好吧,box。那是什么东西?让我们 google 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提供了当次内存分配的所有权,并在退出作用域时销毁存放的内容。

示例

创建一个box

let x = Box::new(5);

创建一个递归数据结构:

#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{:?}", list);
}

这会打印 Cons(1, Box(Cons(2, Box(Nil)))).

递归的结构必须使用box包装,因为如果Cons的定义如下这样:

Cons(T, List<T>),

是不会工作的。这是因为List的大小由其中的元素数量所决定,所以我们无法决定为一个Cons分配多少内存。通过引入一个具有固定大小的Box,我们才知道Cons需要占用多少内存。

哇哦。这或许是我见过的最相关最有帮助的文档了。在里面的第一个东西就是我们正在尝试写的东西,为什么它不能工作,以及如何修复它。好耶,文档。

OK,我们来完成它:

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}
> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/lists)

嘿,它成功编译了!

……但这实际上是一个非常蠢的List的定义,出于以下的一些原因。

考虑一个拥有两个元素的列表:

[] = 栈
() = 堆

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

这里有两个关键问题:

  • 我们创建了一个“实际上不是个节点”的节点
  • 其中的一个节点根本没分配在堆里

在表面上,这两个问题似乎相互抵消。我们分配了一个多余的节点,但有一个节点完全无需在堆里分配。然而,考虑我们链表的一个潜在的内存布局:

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

在这个布局里,我们在堆里分配所有的元素。和第一个布局相比,核心的区别是多余的垃圾的消失。这个垃圾到底是什么?为了理解它,我们需要看一看enum是如何在内存中布局的。

通常的,如果我们有像这样的一个enum:

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

一个Foo需要保存一个整数,来指出它实际表示的是哪一个变体D1, D2, .. Dn)。这是enum的标签(tag)。它也需要足够大的空间,来存储T1, T2, .. Tn中的最大元素(以及用来满足内存对齐要求的附加空间)。

一个很大的缺陷是,尽管Empty只存储了一位的信息,它却消耗了一个指针和一个元素的内存空间,因为它要随时准备成为一个Elem。因此第一种布局在堆里分配了一个充满垃圾的多余元素,比第二种布局消耗更多的空间。

让我们的一个元素不在堆中分配,或许也比所有元素都在堆中分配更糟。这是因为它给了我们一个不一致的节点内存布局。在推入和弹出节点时这并无问题,但在分割和合并列表时确实会有影响。

考虑在两种布局里分别分割一个列表:

布局 1:

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

在C点分割:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)
布局 2:

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

在C点分割:

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

布局2的分割仅仅涉及将B的指针拷贝到栈上,并把原值设置为null。布局1最终还是做了同一件事,但是还得把C从堆中拷贝到栈中。反过来执行上述操作,就是合并列表。

链表的优点之一就是可以在节点中构建元素,然后在列表中随意调换它的位置而不需移动它的内存。你只需要调整指针,元素就被“移动了”。第一个布局毁掉了这个特点。

好吧,我现在很确信布局1是糟糕的。我们要怎么重写List呢?可以这么做:

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

或许你觉得这看起来更糟了。一个问题是,这让逻辑变得更复杂了。具体地说,现在出现了一个完全无效的状态:ElemThenNotEmpty(0, Box(Empty))。它也被内存分配模式不一致的问题所困扰。

不过它确实有一个有趣的特性:它完全避免了在堆里分配Empty,让堆内存分配的数量减少了1。不幸的是,这么做反而浪费了更多空间!因为之前的布局利用了空指针优化

我们之前了解到每个enum需要存储一个标签,来指明它代表哪一个enum的变体。然而,如果我们有如下特殊类型的enum:

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

空指针优化就会发挥作用,消除标签所占用的内存空间。如果变体是A,那整个enum就被设置为0。否则,变体是B。这可以工作,因为B存放了一个非空指针,永远不可能为0。真聪明!

你还能想到能进行这种优化的enum和类型么?实际上有很多!这就是为什么Rust没有详细描述enum的内存布局。悲伤的是,现在实现的优化只有空指针优化——尽管它很重要!这意味着&, &mut, Box, Rc, Arc, Vec,以及其他一些Rust中的重要类型,在放到一个 Option 中时没有多余开销!(上面这些概念的大部分,我们在适当的时候都会接触到)

所以我们要如何避免多余垃圾,统一的分配内存,并且从空指针优化中获益呢?我们需要更好的将存储元素和分配列表这两个想法分开。要做到它,我们该像C语言看齐:struct!

enum让我们定义了一种可以存放多个变体中的一个的类型,而struct则让我们定义可以同时存放多种元素的类型。让我们把List分成两个类型吧:一个List,和一个Node。

和之前一样,一个List要么是Empty,要么是一个元素跟着一个List。不过,要通过另外一种类型来表示“一个元素跟着一个List”,我们可以将Box提升到一个更理想的位置:

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

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

让我们检查各个条目:

  • 列表末尾不分配多余垃圾:通过!
  • enum 享受美妙的空指针优化:通过!
  • 所有元素的内存分配一致:通过!

好的!我们创建的正是用来指明第一种内存布局(官方Rust文档中所建议的那种)有问题的第二种内存布局。

> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/lists)
src/first.rs:8:11: 8:18 error: private type in exported type signature
src/first.rs:8    More(Box<Node>),
                           ^~~~~~~
error: aborting due to previous error
Could not compile `lists`.

:(

Rust又对我们发飙了。我们将List标记为public(因为我们想让其他人使用它),却没有公开Node。问题在于,enum的内部是完全公开的,所以在其中包含内部类型是不允许的。我们可以让整个Node都成为公开的,但是通常在Rust中,我们倾向于让实现细节私有化。让我们把List改造成一个struct,这样我们就可以隐藏实现细节:

pub struct List {
    head: Link,
}

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

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

因为List是一个单值的struct,它的大小和该值完全相同。零代价抽象超赞!

> cargo build
   Compiling lists v0.1.0 (file:///Users/ABeingessner/dev/lists)
src/first.rs:2:2: 2:15 warning: struct field is never used: `head`, #[warn(dead_code)] on by default
src/first.rs:2    head: Link,
                  ^~~~~~~~~~~~~
src/first.rs:6:2: 6:7 warning: variant is never used: `Empty`, #[warn(dead_code)] on by default
src/first.rs:6    Empty,
                  ^~~~~
src/first.rs:7:2: 7:20 warning: variant is never used: `More`, #[warn(dead_code)] on by default
src/first.rs:7    More(Box<Node>),
                  ^~~~~~~~~~~~~~~~~~
src/first.rs:11:2: 11:9 warning: struct field is never used: `elem`, #[warn(dead_code)] on by default
src/first.rs:11   elem: i32,
                  ^~~~~~~
src/first.rs:12:2: 12:15 warning: struct field is never used: `next`, #[warn(dead_code)] on by default
src/first.rs:12   next: Link,
                  ^~~~~~~~~~~~~

好吧,终于编译了!Rust非常生气,因为我们现在写的东西完全无用:我们从不使用head,并且因为它是私有的;使用我们库的人也无法使用它。进而Link和Node也毫无用处。让我们来解决它吧!为我们的List实现一些代码!

results matching ""

    No results matching ""