3.1 数据布局
原文链接: https://rust-unofficial.github.io/too-many-lists/third-layout.html
好，重新考虑布局。
持久化链表最重要的是，你可以几乎免费地操纵链表尾部：
例如，持久化链表上常见的工作负载是这样的：
1
2
3
| list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D
|
但最后我们希望内存看起来像这样：
1
2
3
4
5
6
7
| list1 -> A ---+
|
v
list2 ------> B -> C -> D
^
|
list3 -> X ---+
|
用 Box 根本做不到，因为 B 的所有权是共享的。该由谁释放？如果我 drop list2，会释放 B 吗？用 Box 我们当然会这么期望！
函数式语言——事实上几乎所有其他语言——靠垃圾回收蒙混过关。有了 GC 的魔法，只有没人再看 B 时才会释放。好耶！
Rust 没有这些语言那种垃圾回收器。它们有追踪式 GC，会在运行时翻遍所有内存自动找出垃圾。Rust 目前只有引用计数。引用计数可以看作非常简单的 GC。对很多工作负载，吞吐量明显低于追踪式收集器，而且一旦形成环就会彻底崩溃。但嘿，我们只有这个！好在我们的用例永远不会遇到环（欢迎自己证明——我肯定不会）。
那怎么做引用计数垃圾回收？Rc！Rc 就像 Box，但可以复制，而且只有从它派生的所有 Rc 都 drop 后内存才会释放。可惜这种灵活性代价很高：我们只能对其内部取共享引用。这意味着我们没法真正从链表里取出数据，也没法修改它们。
那布局长什么样？之前是：
1
2
3
4
5
6
7
8
9
10
| pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
|
能把 Box 改成 Rc 吗？
1
2
3
4
5
6
7
8
9
10
11
12
| // 在 third.rs 中
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
|
1
2
3
4
5
6
7
8
9
10
11
| cargo build
error[E0412]: cannot find type `Rc` in this scope
--> src/third.rs:5:23
|
5 | type Link<T> = Option<Rc<Node<T>>>;
| ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
|
1 | use std::rc::Rc;
|
|
哦糟，真损。不像可变链表用的那些东西，Rc 逊到连每个 Rust 程序默认导入都做不到。真逊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| cargo build
warning: field is never used: `head`
--> src/third.rs:4:5
|
4 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
|
看起来靠谱。Rust 写起来依然完全轻松。我打赌全局查找替换 Box 为 Rc 就完事了！
……
不行。真不行。