栈和堆

the-stack-and-the-heap.md
commit 23a7a7bdb6a6a43cd7efdd9176b1d3f75d9d0e70

作为一个系统语言，Rust 在底层运作。如果你有一个高级语言的背景，这可能有一些你不太熟悉的系统编程方面的内容。最重要的一个是内存如何工作，通过栈和堆。如果你熟悉类 C 语言是如何使用栈分配的，这个章节将是一个复习。如果你不太了解，你将会学到这个更通用的概念，不过是专注于 Rust 的。

对于大部分内容，当学习他们的时候，我们会使用一个简化的模型来开始。这使得你可以掌握基础，而不会现在就因为不相关的细节而停滞不前。这里我们使用的例子不一定百分之百准确，不过它代表了目前我们的尝试学习的计数等级。一旦你掌握了基础，学习了更多分配器是如何实现的，虚拟内存和其他高级主题之后，将会揭示出这个特定抽象的漏洞。

内存管理

这两个术语是关于内存管理的。栈和堆是帮助你决定何时分配和释放内存的抽象（概念）。

这是一个高层次的比较：

栈非常快速，并且是 Rust 默认分配内存的地方。不过这个分配位于函数调用的本地，并有大小限制。堆，相反，更慢，并且需要被你的程序显式分配。不过它无事实上的大小限制，并且是全局可访问的。注意这里堆的意义，它意味着已任意顺序分配任意大小的内存块，这与堆数据结构有很大不同（黑我大 Java？）。

栈

让我们讨论下这个 Rust 程序：

fn main() {
    let x = 42;
}

这个程序有一个变量绑定，x。这个内存需要在什么地方被分配？Rust 默认“栈分配”，也就意味着基本（类型）值“出现在栈上”。这意味着什么呢？

好吧，当函数被调用时，一些内存被分配给所有它的本地变量和一些其它信息。这叫做一个“栈帧（stack frame）”，而为了这个教程的目的，我们将忽略这些额外信息并仅仅考虑我们分配的局部变量。所以在这个例子中，当main()运行时，我们将为我们的栈帧分配一个单独的32位整型。如你所见，这会自动为你处理，我们并不必须写任何特殊的 Rust 代码或什么的。

当这个函数结束时，它的栈帧被释放。这也是自动发生的，在这里我们也不必要做任何特殊的事情。

这就是关于这个简单程序的一切。在这里你需要理解的关键是栈的分配非常快。因为我们知道所有的局部变量是预先分配的，我们可以一次获取所有的内存。并且因为我们也会同时把它们都扔了，我们可以快速的释放它们。

缺点是如果我们需要它们活过一个单独的函数调用，我们并不能保留它们的值。我们也还没有聊聊这个名字，“栈”意味着什么。为此，我们需要一个稍微更复杂一点的例子：

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。这个数字来自 2³⁰，1GB 的字节数。[^gigabyte]

这个内存有点像一个巨型数组：地址从0开始一直增大到最终的数字。所以这是一个我们第一个栈帧的图表：

我们有位于地址0的x，它的值是42。

当foo()被调用，一个新的栈帧被分配：

因为0被第一个帧占有，1和2被用于foo()的栈帧。随着我们调用更多函数，它往上增长。

这有一些我们不得不注意的重要的内容。数字0，1和2都仅仅用于说明目的，并且与编译器会实际使用的具体数字没有关系。特别的，现实中这一系列的地址将会被一定数量的用于分隔地址的字节分隔开，并且这些分隔的字节可能甚至会超过被存储的值的大小。

在foo()结束后，它的帧被释放：

接着，在main()之后，就连最后一个值也木有了。简单明了！

它被叫做“栈”因为它就像一叠餐盘一样工作：最先放进去的盘子是最后一个你能取出来的。为此栈有时被叫做“后进先出队列”，因为你放入栈的最后值是第一个你能取出来的值。

让我们试试第三个更深入的例子：

fn italic() {
    let i = 6;
}
fn bold() {
    let a = 5;
    let b = 100;
    let c = 1;
    italic();
}
fn main() {
    let x = 42;
    bold();
}

好的，第一步，我们调用main()：

接下来，main()调用bold()：

接着bold()调用italic()：

噢！我们的栈变得很高了。

在italic()结束后，它的帧被释放，只留下bold()和main()：

然后接着bold()结束，只剩下main()的了：

接下来我们完事了。找到了窍门了吗？这就像堆盘子：你在顶部增加，从顶部取走。

堆

目前为止，它能出色的工作，不过并非所有事情都能这么运作。有时，你需要在不同函数间传递一些内存，或者让它活过一次函数执行。为此，我们可以使用堆。

在 Rust 中，你可以使用Box<T>类型在堆上分配内存。这是一个例子：

fn main() {
    let x = Box::new(5);
    let y = 42;
}

这是当main()被调用时内存中发生了什么：

我们在栈上分配了两个变量的空间。y是42，一如既往，不过x怎么样呢？好吧，x是一个Box<i32>，而装箱在堆上分配内存。装箱的实际值是一个带有指向“堆”指针的结构。当我们开始执行这个函数，然后Box::new()被调用，它在堆上分配了一些内存，并把5放在这。现在内存看起来像这样：

在我们假设的带有 1GB 内存（RAM）的电脑上我们有 (2³⁰) - 1 个地址。并且因为我们的栈从0开始增长，分配内存的最简单的位置是内存的另一头。所以我们第一个值位于内存的最顶端。而在x的结构的值有一个裸指针指向我们在堆上分配的位置，所以x的值是 (2³⁰) - 1，我们请求的内存位置。

我们还没有过多的讨论在这个上下文中分配和释放内存具体意味着什么。深入非常底层的细节超出了这个教程的范围，不过需重要指出的是这里的堆不仅仅就是一个相反方向增长的栈。在本书的后面我们会有一个例子，不过因为堆可以以任意顺序分配和释放，它最终会产生“洞”。这是一个已经运行了一段时间的程序的内存图表：

在这个例子中，我们在堆上分配了4个东西，不过释放了它们中的两个。在 (2³⁰) - 1 和 (2³⁰) - 4 之间有一个目前并没有被使用的断片（gap）。如何和为什么这会发生的具体细节依赖你用来管理堆的何种策略。不同的程序可以使用不同的“内存分配器”，它们是为你管理（内存）的库。Rust 程序为此选择了 使用了jemalloc。

不管怎么说，回到我们的例子。因为这些内存在堆上，它可以比分配装箱的函数活的更久。然而在这个例子中，它并不如此。^移动当函数结束，我们需要为main()释放栈帧。然而Box<T>有一些玄机：Drop。Box的Drop实现释放了当它创建时分配的内存。很好！所以当x消失时，它首先释放了分配在堆上的内存：

接着栈帧消失，释放所有的内存。

参数和借用

我们有了一些关于栈和堆运行的基础例子，不过函数参数和借用又怎么样呢？这是一个小的 Rust 程序：

fn foo(i: &i32) {
    let z = 42;
}
fn main() {
    let x = 5;
    let y = &x;
    foo(y);
}

当我们进入main()，内存看起来像这样：

x是一个普通的5，而y是一个指向x的引用。所以它的值是x的所在内存位置，它在这是0。

那么当我们调用foo()，传递y作为一个参数会怎么样呢？

栈帧不再仅仅是本地绑定了，它也有参数。所以在这里，我们需要有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()：

我们为j，i和h分配内存。i在堆上，所以这里我们有一个指向它的值。

下一步，在main()的末尾，foo()被调用：

为x，y和z分配了空间。参数x和j有相同的值，因为这是我们传递给它的。它是一个指向0地址的指针，因为j指向h。

接着，foo()调用baz()，传递z：

我们为f和g分配了内存。baz()非常短，所以当它结束时，我们移除了它的栈帧：

接下来，foo()调用bar()并传递x和z：

我们最终在堆上分配了另一个值，所以我们必须从 (2³⁰) - 1 减一。它比直接写1,073,741,822更简单。在任何情况下，我们通常用这个值。

在bar()的末尾，它调用了baz()：

这样，我们就到达最深的位置！噢！恭喜你一路跟了过来。

在baz()结束后，我们移除了f和g：

接下来，我们从bar()返回。在这里d是一个Box<T>，所以它也释放了它指向的内存空间：(2³⁰) - 2。

而在这之后，foo()返回：

接着，最后，main()，它清理了剩下的东西。当i被Drop时，它也会清理最后的堆空间。

其它语言怎么做？

大部分语言有一个默认堆分配的垃圾回收器。这意味着每个值都是装箱的。有很多原因为什么要这么做，不过这超出了这个教程的范畴。这也有一些优化会使得这些规则不是 100% 的时间都成立。垃圾回收器用处理堆来代替依赖栈和Drop来清理内存的方式。

该用啥？（Which to use?）

那么如果栈是更快并更易于管理的，那么我们为啥还需要堆呢？一个大的原因是只有栈分配的话意味着你只有后进先出语义的获取存储的方法。堆分配，严格的说，更通用，允许以任意顺序从池中取出和返回存储，不过有复杂度开销。

一般来说，你应该倾向于栈分配，因此，Rust 默认栈分配。栈的后进先出模型在基本原理层面上更简单。这有两个重大的影响：运行时效率和语义影响。

运行时效率

管理栈的内存是平凡的（trivial：来自C++的概念）：机器只是增加和减少一个单独的值，所谓的“栈指针”。管理堆的内存是不平凡的（non-trivial）：堆分配的内存在任意时刻被释放，而且每个堆分配内存的块可以是任意大小，内存管理器通常需要更多工作来识别出需要重用的内存。

如果你想深入这个主题的更多细节，这篇论文是一个很好的介绍。

语义影响（Semantic impact）

栈分配影响 Rust 语言自身，因此还有开发者的心智模型（mental model：想起苍蓝的握爪）。后进先出语义驱动了 Rust 语言如何处理自动内存管理。甚至是一个单独所有权堆分配的装箱的释放也可以被基于栈的后进先出语义驱动，就像本章中的讨论一样。非后进先出语义的灵活性（也就是说：表现力）意味着大体上讲编译器不能在编译时自动推断出哪些内存应该被释放；它不得不依赖动态协议，可能来自于语言之外，来驱动释放（例如，Rc<T>和Arc<T>中用到了引用计数）。

当考虑到极端情况，堆分配的增加的表现力带来了要么是显著的运行时支持（例如，以垃圾回收器的形式）要么是显著的程序猿努力（以必需进行 Rust 编译器并未提供的验证的显式的内存管理调用的形式）的开销。

[^gigabyte]: Gigabyte可以表示两个意思：10⁹ 或 2³⁰。SI（国际单位制）标准解释为“gigabyte”是 10⁹， 而“gibibyte”是 2³⁰。然而，很少有人用这个术语，而依赖语境上下文来区别。这里我们遵循传统。