基本数据布局( Layout )

发现一件尴尬的事情,之前介绍了这么多,但是竟然没有介绍链表是什么...亡羊补牢未为晚也,链表就是一系列存储在堆上的连续数据,大家是不是发现这个定义跟动态数据 Vector 非常相似,那么区别在于什么呢?

区别就在于链表中的每一个元素都指向下一个元素,最终形成 - 顾名思义的链表: A1 -> A2 -> A3 -> Null。 而数组中的元素只是连续排列,并不存在前一个元素指向后一个元素的情况,而是每个元素通过下标索引来访问。

既然函数式语言的程序员最常使用链表,那么我们来看看他们给出的定义长什么样:

#![allow(unused)]
fn main() {
List a = Empty | Elem a (List a)
}

mu...看上去非常像一个数学定义,我们可以这样阅读它, 列表 a 要么是空,要么是一个元素后面再跟着一个列表。非常递归也不咋好懂的定义,果然,这很函数式语言。

下面我们再来使用 Rust 的方式对链表进行下定义,为了简单性,这先不使用泛型:

#![allow(unused)]
fn main() {
// in first.rs

pub enum List {
    Empty,
    Elem(i32, List),
}
}

喔,看上去人模狗样,来,运行下看看:

$ cargo run
error[E0072]: recursive type `List` has infinite size
 --> src/first.rs:1:1
  |
1 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
2 |     Empty,
3 |     Elem(i32, List),
  |               ---- recursive without indirection
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable
  |
3 |     Elem(i32, Box<List>),

帅不过 3 秒的玩意儿~~ 好在这个问题,我们在之前的章节中就讲过了,简而言之,当前的类型是不定长的,对于 Rust 编译器而言,所有栈上的类型都必须在编译期有固定的长度,一个简单的解决方案就是使用 Box 将值封装到堆上,然后使用栈上的定长指针来指向堆上不定长的值。

实际上,如果大家有仔细看编译错误的话,它还给出了我们提示: Elem(i32, Box<List>),和我们之前的结论一致,下面来试试:

#![allow(unused)]
fn main() {
pub enum List {
    Empty,
    Elem(i32, Box<List>),
}
}
$ cargo build

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

万能的编译器再一次拯救了我们,这次的代码成功完成了编译。但是这依然是不咋滴的 List 定义,有几个原因。

首先,考虑一个拥有两个元素的 List:

[] = Stack
() = Heap

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

这里有两个问题:

  • 最后一个节点分配在了堆上,但是它看上去根本不像一个 Node
  • 第一个 Node 是存储在栈上的,结果一家子不能整整齐齐的待在堆上了

这两点看上去好像有点矛盾:你希望所有节点在堆上,但是又觉得最后一个节点不应该在堆上。那再来考虑另一种布局( Layout )方式:

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

在这种布局下,我们无条件的在堆上创建所有节点,最大的区别就是这里不再有 junk。那么什么是 junk?为了理解这个概念,先来看看枚举类型的内存布局( Layout )长什么样:

#![allow(unused)]
fn main() {
enum Foo {
   D1(u8),
   D2(u16),
   D3(u32),
   D4(u64)
}
}

大家觉得 Foo::D1(99) 占用多少内存空间?是 u8 对应的 1 个字节吗?答案是 8 个字节( 为了好理解,这里不考虑 enum tag 所占用的额外空间 ),因为枚举有一个特点,枚举成员占用的内存空间大小跟最大的成员对齐,在这个例子中,所有的成员都会跟 u64 进行对齐。

在理解了这点后,再回到我们的 List 定义。这里最大的问题就是尽管 List::Empty 是空的节点,但是它依然得消耗和其它节点一样的内存空间。

与其让一个节点不进行内存分配,不如让它一直进行内存分配,无论是否有内容,因为后者会保证节点内存布局的一致性。这种一致性对于 pushpop 节点来说可能没有什么影响,但是对于链表的分割和合并而言,就有意义了。

下面,我们对之前两种不同布局的 List 进行下分割:

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*)
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*)

可以看出,在布局 1 中,需要将 C 节点从堆上拷贝到栈中,而布局 2 则无需此过程。而且从分割后的布局清晰度而言,2 也要优于 1。

现在,我们应该都相信布局 1 更糟糕了,而且不幸的是,我们之前的实现就是布局 1, 那么该如何实现新的布局呢 ?也许,我们可以实现类似如下的 List :

#![allow(unused)]
fn main() {
pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}
}

但是,你们有没有觉得更糟糕了...有些不忍直视的感觉。这让我们的代码复杂度大幅提升,例如你现在得实现一个完全不合法的状态: ElemThenNotEmpty(0, Box(Empty)),而且这种实现依然有之前的不一致性的问题。

之前我们提到过枚举成员的内存空间占用和 enum tag 问题,实际上我们可以创建一个特例:

#![allow(unused)]
fn main() {
enum Foo {
    A,
    B(ContainsANonNullPtr),
}
}

在这里 null 指针的优化就开始介入了,它会消除枚举成员 A 占用的额外空间,原因在于编译器可以直接将 A 优化成 0,而 B 则不行,因为它包含了非 null 指针。这样一来,编译器就无需给 A 打 tag 进行识别了,而是直接通过 0 就能识别出这是 A 成员,非 0 的自然就是 B 成员。

事实上,编译器还会对枚举做一些其他优化,但是 null 指针优化是其中最重要的一条。

所以我们应该怎么避免多余的 junk,保持内存分配的一致性,还能保持 null 指针优化呢?枚举可以让我们声明一个类型用于表达多个不同的值,而结构体可以声明一个类型同时包含多个值,只要将这两个类型结合在一起,就能实现之前的目标: 枚举类型用于表示 List,结构体类型用于表示 Node.

#![allow(unused)]
fn main() {
struct Node {
    elem: i32,
    next: List,
}

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

让我们看看新的定义是否符合之前的目标:

  • List 的尾部不会再分配多余的 junk 值,通过!
  • List 枚举的形式可以享受 null 指针优化,完美!
  • 所有的元素都拥有统一的内存分配,Good!

很好,我们准确构建了之前想要的内存布局,并且证明了最初的内存布局问题多多,编译下试试:

error[E0446]: private type `Node` in public interface
 --> src/first.rs:8:10
  |
1 | struct Node {
  | ----------- `Node` declared as private
...
8 |     More(Box<Node>),
  |          ^^^^^^^^^ can't leak private type

在英文书中,这里是一个 warning ,但是在笔者使用的最新版中(Rust 1.59),该 warning 已经变成一个错误。主要原因在于 pub enum 会要求它的所有成员必须是 pub,但是由于 Node 没有声明为 pub,因此产生了冲突。

这里最简单的解决方法就是将 Node 结构体和它的所有字段都标记为 pub :

#![allow(unused)]
fn main() {
pub struct Node {
    pub elem: i32,
    pub next: List,
}
}

但是从编程的角度而言,我们还是希望让实现细节只保留在内部,而不是对外公开,因此以下代码相对会更加适合:

#![allow(unused)]
fn main() {
pub struct List {
    head: Link,
}

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

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

从代码层面看,貌似多了一层封装,但是实际上 List 只有一个字段,因此结构体的大小跟字段大小是相等的,没错,传说中的零开销抽象!

至此,一个令人满意的数据布局就已经设计完成,下面一起来看看该如何使用这些数据。