4.1.栈和堆
最后更新于：2022-04-01 00:43:02
作为一个系统语言，Rust在底层运作。如果你来自一个高层次语言（背景），这可能有一些你不太熟悉的系统编程方面的内容。最重要的一个是内存如何工作，通过栈和堆。如果你熟悉类C语言如何使用栈分配，这个章节将是一个复习。如果你不太了解，你将会学到这个更通用的概念，不过是专注于Rust的。
## 内存管理
这里有两个术语是关于内存管理的。栈和堆是帮助你决定何时分配和释放内存的抽象（概念）。
这是一个高层次的比较：
栈非常快速，并且是Rust默认分配内存的地方。不过这个分配位于函数调用的本地，并有大小限制。堆，在另一方面，更慢，并且需要被你的程序显式分配。不过它无事实上的大小限制，并且是全局可访问的。
## 栈
让我们讨论下这个Rust程序：
~~~
fn main() {
let x = 42;
}
~~~
这个程序有一个变量绑定，`x`。这个内存需要在什么地方被分配。Rust默认“栈分配”，也就意味着基本（类型）值“出现在栈上”。这意味着什么呢？
好吧，当函数被调用时，一些内存被分配用于所有它的本地变量和一些其它信息。这叫做一个“栈帧（stack frame）”，而为了这个教程的目的，我们将忽略这些额外信息并仅仅考虑我们分配的局部变量。所以在这个例子中，当`main()`运行时，我们将为我们的栈帧分配一个单独的32位整型。如你所见，这会自动为你处理，我们并不必须写任何特殊的Rust1代码或什么的。
当这个函数结束时，它的栈帧被释放。这也是自动发生的，在这里我们也不必要做任何特殊的事情。
这就是关于这个简单程序的一切。在这里你需要理解的关键是栈分配灰常灰常快。因为我们知道所有的局部变量是预先分配的，我们可以一次获取所有的内存。并且因为我们也会同时把它们都扔了，我们可以快速的释放它们。
缺点是如果我们需要它们活过一个单独的函数调用，我们并不能保留它们的值。我们也还没有聊聊这个名字，“栈”意味着什么。为此，我们需要一个稍微更复杂一点的例子：
~~~
fn foo() {
let y = 5;
let z = 100;
}
fn main() {
let x = 42;
foo();
}
~~~
这个程序总共有3个变量：`foo()`中两个，`main()`中一个。就像之前一样，当`main()`被调用时，在它的栈帧中被分配了一个单独的整型。不过在我们展示当`foo()`被调用后发生了什么之前，我们需要可视化一下内存中发生了什么。你的操作系统为你的程序提供了一个非常简单内存视图：一个巨大的地址列表。从`0`到一个很大的数字，代表你的电脑有多少内存。例如，如果你有1GB的内存，你的地址从`0`到`1,073,741,824`。这个数字来自230，1GB的字节数。
这个内存有点像一个巨型数组：地址从`0`开始一直增大到最终的数字。所以这是一个我们第一个栈帧的图表：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 0 | x | 42 |
我们有位于地址`0`的`x`，它的值是`42`。
当`foo()`被调用，一个新的栈帧被分配：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 2 | z | 100 |
| 1 | y | 5 |
| 0 | x | 42 |
因为`0`被第一个帧占有，`1`和`2`被用于`foo()`的栈帧。它向上增长，随着我们调用更多函数。
这有一些我们不得不注意的重要的内容。数字`0`，`1`和`2`都仅仅用于说明目的，并且与编译器会实际使用的具体数字没有关系。特别的，现实中这一系列的地址将会被一定数量的用于分隔地址的字节分隔开，并且这些分隔的字节可能甚至会超过被存储的值的大小。
在`foo()`结束后，它的帧被释放：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 0 | x | 42 |
接着，在`main()`之后，就连最后一个值也木有了。简单明了！
它被叫做“栈”因为它就像一叠餐盘一样工作：最先放进去的盘子是最后一个你能取出来的。为此栈有时被叫做“后进，先出队列”，因为你放入栈的最后值是第一个你能取出来的值。
让我们试试第三个更深入的例子：
~~~
fn bar() {
let i = 6;
}
fn foo() {
let a = 5;
let b = 100;
let c = 1;
bar();
}
fn main() {
let x = 42;
foo();
}
~~~
好的，第一步，我们调用`main()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 0 | x | 42 |
接下来，`main()`调用`foo()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 3 | c | 1 |
| 2 | b | 100 |
| 1 | a | 5 |
| 0 | x | 42 |
接着`foo()`调用`bar()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 4 | i | 6 |
| 3 | c | 1 |
| 2 | b | 100 |
| 1 | a | 5 |
| 0 | x | 42 |
噢！我们的栈变得很高了。
在`bar()`结束后，它的帧被释放，只留下`foo()`和`main()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 3 | c | 1 |
| 2 | b | 100 |
| 1 | a | 5 |
| 0 | x | 42 |
然后接着`foo()`结束，只剩下`main()`的了：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 0 | x | 42 |
接下来我们完事了。找到了窍门了吗？这就像堆盘子：你在顶部增加，从顶部取走。
## 堆
目前为止，它能出色的工作，不过并非所有事情都能这么运作。有时，你需要在不同函数间传递一些内存，或者让它活过一次函数执行。为此，我们可以使用堆。
在Rust中，你可以使用[`Box`类型](http://doc.rust-lang.org/std/boxed/)在堆上分配内存。这是一个例子：
~~~
fn main() {
let x = Box::new(5);
let y = 42;
}
~~~
这是当`main()`被调用时内存中发生了什么：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 1 | y | 42 |
| 0 | x | ?????? |
我们在栈上分配了两个变量的空间。`y`是`42`，一如既往，不过`x`怎么样呢？好吧，`x`是一个`Box`，而装箱在堆上分配内存。装箱的实际值是一个带有指向“堆”指针的结构。当我们开始执行这个函数，然后`Box::new()`被调用，它在堆上分配了一些内存，并把`5`放在这。现在内存看起来像这样：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 5 |
| ... | ... | ... |
| 1 | y | 42 |
| 0 | x | 230 |
在我们假设的带有1GB内存（RAM）的电脑上我们有230个地址。并且因为我们的栈从`0`开始增长，分配内存的最简单的位置是内存的另一头。所以我们第一个值位于内存的最顶端。而在`x`的结构的值有一个[裸指针](http://kaisery.gitbooks.io/rust-book-chinese/content/content/from%20the%20other%20end)指向我们在堆上分配的位置，所以`x`的值是230，我们请求的内存位置。
我们还没有过多的讨论在这个上下文中分配和释放内存具体意味着什么。深入非常底层的细节超出了这个教程的范围，不过重要的是指出的是这里的堆不仅仅就是一个相反方向增长的栈。在本书的后面我们会有一个例子，不过因为堆可以以任意顺序分配和释放，它最终会产生“洞”。这是一个已经运行了一段时间的程序的内存图表：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 5 |
| (230) - 1 |
| (230) - 2 |
| (230) - 3 | 42 |
| ... | ... | ... |
| 3 | y | (230) - 3 |
| 2 | y | 42 |
| 1 | y | 42 |
| 0 | x | 230 |
在这个例子中，我们在堆上分配了4个东西，不过释放了它们中的两个。在230和(230) - 3之间有一个目前并没有被使用的沟。如何和为什么这会发生的具体细节依赖你用来管理堆的何种策略。不同的程序可以使用不同的“内存分配器”，它们是为你管理（内存）的库。Rust程序为此选择了 使用了[jemalloc](http://www.canonware.com/jemalloc/)
不管怎么说，回到我们的例子。因为这些内存在堆上，它可以比分配装箱的函数活的更久。然而在这个例子中，它并不如此。[移动]当函数结束，我们需要为`main()`释放栈帧。然而`Box`有一些玄机：[Drop](http://kaisery.gitbooks.io/rust-book-chinese/content/content/trick%20up%20its%20sleve)。`Box`的`Drop`实现释放了当它创建时分配的内存。很好！所以当`x`消失时，它首先释放了分配在堆上的内存：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 1 | y | 42 |
| 0 | x | ?????? |
[移动]：我们可以通过转移所有权来让内存活的更久，这有时叫做“走出盒子”。我们将在后面涉及更复杂的例子。
接着栈帧消失，释放所有的内存。
## 参数和借用
我们有了一些关于栈和堆运行的基础例子，不过函数参数和借用又怎么样呢？这是一个小的Rust程序：
~~~
fn foo(i: &i32) {
let z = 42;
}
fn main() {
let x = 5;
let y = &x;
foo(y);
}
~~~
当我们进入`main()`，内存看起来像这样：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 1 | y | 0 |
| 0 | x | 5 |
`x`是一个普通的`5`，而`y`是一个指向`x`的引用。所以它的值是`x`的所在内存位置，它在这是`0`。
那么当我们调用`foo()`，传递`y`作为一个参数会怎么样呢？
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 3 | z | 42 |
| 2 | i | 0 |
| 1 | y | 0 |
| 0 | x | 5 |
栈帧不再仅仅是本地绑定了，它也有参数。所以在这里，我们需要有`i`，参数，和`z`，我们本地的变量绑定。`i`是参数`y`的一个拷贝。因为`y`的值是`0`，`i`也是。
为什么要借用一个变量的一个原因是不需要分配任何内存：一个引用的值仅仅是一个内存位置的指针。如果我们溢出任何底层内存，事情就不能这么顺利工作了。
## 一个复杂的例子
好的，让我们一步一步过一遍这个复杂程序：
~~~
fn foo(x: &i32) {
let y = 10;
let z = &y;
baz(z);
bar(x, z);
}
fn bar(a: &i32, b: &i32) {
let c = 5;
let d = Box::new(5);
let e = &d;
baz(e);
}
fn baz(f: &i32) {
let g = 100;
}
fn main() {
let h = 3;
let i = Box::new(20);
let j = &h;
foo(j);
}
~~~
首先，我们调用`main()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
我们为`j`，`i`和`h`分配内存。`i`在堆上，所以这里我们有一个指向它的值。
下一步，在`main()`的末尾，`foo()`被调用：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
为`x`，`y`和`z`分配了空间。参数`x`和`j`有相同的值，因为这是我们传递给它的。它是一个指向`0`地址的指针，因为`j`指向`h`。
接着，`foo()`调用`baz()`，传递`z`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 7 | g | 100 |
| 6 | f | 4 |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
我们为`f`和`g`分配了内存。`baz()`非常短，所以当它结束时，我们移除了它的栈帧：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
接下来，`foo()`调用`bar()`并传递`x`和`z`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| (230) - 1 | 5 |
| ... | ... | ... |
| 10 | e | 4 |
| 9 | d | (230) - 1 |
| 8 | c | 5 |
| 7 | b | 4 |
| 6 | a | 0 |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
我们最终在堆上分配了另一个值，所以我们必须从230减一。它比直接写`1,073,741,823`更简单。在任何情况下，我们通常用这个值。
在`bar()`的末尾，它调用了`baz()`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| (230) - 1 | 5 |
| ... | ... | ... |
| 12 | g | 100 |
| 11 | f | 4 |
| 10 | e | 4 |
| 9 | d | (230) - 1 |
| 8 | c | 5 |
| 7 | b | 4 |
| 6 | a | 0 |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
这样，我们就到达最深的位置！噢！恭喜你一路跟了过来。
在`baz()`结束后，我们移除了`f`和`g`：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| (230) - 1 | 5 |
| ... | ... | ... |
| 10 | e | 4 |
| 9 | d | (230) - 1 |
| 8 | c | 5 |
| 7 | b | 4 |
| 6 | a | 0 |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
接下来，我们从`bar()`返回。在这里`d`是一个`Box`，所以它也释放了它指向的内存空间：(230) - 1。
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 5 | z | 4 |
| 4 | y | 10 |
| 3 | x | 0 |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
而在这之后，`foo()`返回：
| 地址 | 名称 | 值 |
| --- | --- | --- |
| 230 | 20 |
| ... | ... | ... |
| 2 | j | 0 |
| 1 | i | 230 |
| 0 | h | 3 |
接着，最后，`main()`,它清理了剩下的东西。当`i`被`Drop`时，它也会清理最后的堆空间。
## 其它语言怎么做？
大部分语言有一个默认堆分配的垃圾回收器。这意味着每个值都是装箱的。有很多原因为什么要这么做，不过这超出了这个教程的范畴。这也有一些优化会使得这些规则不是100%的时间为真。与其依赖栈和`Drop`来清理内存，垃圾回收器用处理堆来代替。
## 该用啥？（Which to use?）
那么如果栈是更快并更易于管理的，那么我们为啥还需要堆呢？一个大的原因是只有栈分配的话意味着你只有先进后出语义的获取存储的方法。堆分配严格的说更通用，允许以任意顺序从池中取出和返回存储，不过有复杂度开销。
一般来说，你应该倾向于栈分配，因此，Rust默认栈分配。栈的先进后出模型在基础层面上更简单。这有两个重大的影响：运行时效率和语义影响。
### 运行时效率
管理栈的内存是平凡的（trivial：来自C++的概念）：机器只是增加和减少一个单独的值，所谓的“栈指针”。管理堆的内存是不平凡的（non-trivial）：堆分配的内存在任意时刻被释放，而且每个堆分配内存的块可以是任意大小，内存管理器通常需要更多工作来识别出需要重用的内存。
如果你想深入这个主题的更多细节，[这篇文章](http://www.cs.northwestern.edu/~pdinda/icsclass/doc/dsa.pdf)是一个很好的介绍。
### 语义影响（Semantic impact）
栈分配影响Rust语言自身，因此还有开发者的心智模型（mental model：想起苍蓝的握爪）。先进后出语义驱动了Rust语言如何处理自动内存管理。甚至是一个单独所有权堆分配的装箱的释放也可以被基于栈的先进后出语义驱动，就像本章中的讨论一样。非先进后出语义的灵活性（也就是说：表现力）意味着大体上讲编译器不能在编译时自动推断出哪些内存应该被释放；它不得不依赖动态协议，可能来自于语言之外，来驱动释放（引用计数，就像是用`Rc`和`Arc`，是这个的一个例子）。
当考虑到极端情况，堆分配的增加的表现力带来了要么是显著的运行时支持（例如，以垃圾回收器的形式）要么是显著的程序猿努力（以要求进行Rust编译器并未提供的验证的显式的内存管理调用的形式）的开销。