栈-堆

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

内存管理

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

这是一个高层次的比较：

栈非常快速，并且是Rust默认分配内存的地方。不过这个分配位于函数调用的本地，并有大小限制。堆，相反，更慢，并且需要被你的程序显式分配。不过它无事实上的大小限制，并且是全局可访问的。

栈

让我们讨论下这个 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。这个数字来自 230，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\，而装箱在堆上分配内存。装箱的实际值是一个带有指向“堆”指针的结构。当我们开始执行这个函数，然后Box::new()被调用，它在堆上分配了一些内存，并把5放在这。现在内存看起来像这样：

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

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

在这个例子中，我们在堆上分配了4个东西，不过释放了它们中的两个。在 (230) - 1 和 (230) - 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：

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

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

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

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

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

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

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

操作系统会将物理内存映射成虚拟地址空间，程序在启动时看到的虚拟地址空间是一块完整连续的内存。

栈内存从高位地址向下增长，且栈内存分配是连续的，一般操作系统对栈内存大小是有限制的，Linux/Unix 类系统上面可以通过 ulimit 设置最大栈空间大小，所以C中无法创建任意长度的数组，函数调用时会创建一个临时栈空间，通常由操作系统完成的，函数调用结束后操作系统会自动销毁栈空间，其上内存也会自动释放，无需程序员手动干预，因而栈内存申请和释放是非常高效的。

相对地，堆上内存则是从低位地址向上增长，堆内存通常只受物理内存限制，而且通常是不连续的，一般由程序员手动申请和释放的，如果想申请一块连续内存，则操作系统需要在堆中查找一块未使用的满足大小的连续内存空间，故其效率比栈要低很多，尤其是堆上如果有大量不连续内存时。另外内存使用完也必须由程序员手动释放，不然就会出现内存泄漏，内存泄漏对需要长时间运行的程序(例如守护进程)影响非常大。

Rust 中的堆和栈

由于函数栈在函数执行完后会销毁，所以栈上存储的变量不能在函数之间传递，这也意味着函数没法返回栈上变量的引用，而这通常是 C/C++ 新手常犯的错误。而 Rust 中编译器则会检查出这种错误，错误提示一般为 xxx does not live long enough，看下面一个例子

fn main() {
    let b = foo("world");
    println!("{}", b);
}
fn foo(x: &str) -> &str {
    let a = "Hello, ".to_string() + x;
    &a
}

之所以这样写，很多人觉得可以直接拷贝字符串 a 的引用从而避免拷贝整个字符串，然而得到的结果却是 a does not live long enough 的编译错误。因为引用了一个函数栈中临时创建的变量，函数栈在函数调用结束后会销毁，这样返回的引用就变得毫无意义了，指向了一个并不存在的变量。相对于 C/C++ 而言，使用 Rust 就会幸运很多，因为 C/C++ 中写出上面那样的程序，编译器会默默地让你通过直到运行时才会给你报错。

其实由于 a 本身是 String 类型，是使用堆来存储的，所以可以直接返回，在函数返回时函数栈销毁后依然存在。同时 Rust 中下面的代码实际上也只是浅拷贝。

fn main() {
    let b = foo("world");
    println!("{}", b);
}
fn foo(x: &str) -> String {
    let a = "Hello, ".to_string() + x;
    a
}

Rust 默认使用栈来存储变量，而栈上内存分配是连续的，所以必须在编译之前了解变量占用的内存空间大小，编译器才能合理安排内存布局。

Box

C 里面是通过 malloc/free 手动管理堆上内存空间的，而 Rust 则有多种方式，其中最常用的一种就是 Box,通过 Box::new() 可以在堆上申请一块内存空间，不像 C 里面一样堆上空间需要手动调用 free 释放，Rust 中是在编译期编译器借助 lifetime 对堆内存生命期进行分析，在生命期结束时自动插入 free。当前 Rust 底层即 Box 背后是调用 jemalloc 来做内存管理的，所以堆上空间是不需要程序员手动去管理释放的。很多时候你被编译器虐得死去活来时，那些 borrow, move, lifetime 错误其实就是编译器在教你认识内存布局，教你用 lifetime 规则去控制内存。这套规则说难不难，说简单也不简单，以前用别的语言写程序时对内存不关心的，刚写起来可能真的会被虐得死去活来，但是一旦熟悉这套规则，对内存布局掌握清楚后，借助编译器的提示写起程序来就会如鱼得水。这套规则是理论界研究的成果在Rust编译器上的实践，

很多面向对象语言会自称”一切皆对象(Everything is an object)”，潜在的意思就是所有值都是 boxed value

boxed 值相对于 unboxed，内存占用空间会大些，同时访问值的时候也需要先进行 unbox，即对指针进行解引用再获取真正存储的值，所以内存访问开销也会大些。既然 boxed 值既费空间又费时间，为什么还要这么做呢？因为通过 box，所有对象看起来就像是以相同大小存储的，因为只需要存储一个指针就够了，应用程序可以同等看待各种值，而不用去管实际存储是多大的值，如何申请和释放相应资源。

Box 是堆上分配的内存，通过 Box::new() 会创建一个堆空间并返回一个指向堆空间的指针

nightly 版本中引入 box 关键词，可以用来取代 Box::new() 申请一个堆空间，也可以用在模式匹配上面

#![feature(box_syntax, box_patterns)]
fn main() {
   let boxed = Some(box 5);
   match boxed {
       Some(box unboxed) => println!("Some {}", unboxed),
       None => println!("None"),
   }
}

下面看一个例子，对比一下 Vec\ 和 Vec> 内存布局，这两个图来自 Stack Overflow，从这两张内存分布图可以清楚直观地看出 Box 是如何存储的

Vec<i32>
(stack)    (heap)
┌──────┐   ┌───┐
│ vec1 │──→│ 1 │
└──────┘   ├───┤
           │ 2 │
           ├───┤
           │ 3 │
           ├───┤
           │ 4 │
           └───┘
Vec<Box<i32>>
(stack)    (heap)   ┌───┐
┌──────┐   ┌───┐ ┌─→│ 1 │
│ vec2 │──→│   │─┘  └───┘
└──────┘   ├───┤    ┌───┐
           │   │───→│ 2 │
           ├───┤    └───┘
           │   │─┐  ┌───┐
           ├───┤ └─→│ 3 │
           │   │─┐  └───┘
           └───┘ │  ┌───┐
                 └─→│ 4 │
                    └───┘

一些语言里会有看起来既像数组又像列表的数据结构，例如 python 中的 List，其实就是与 Vec> 类似，只是把 i32 换成任意类型，就操作效率而言比单纯的 List 高效，同时又比数组使用更灵活。

一般而言大小在编译时不能确定的数据类型都需要使用堆上内存，因为编译器无法为其在栈上分配固定大小的内存空间，例如 String, Vec，另外需要从函数中返回一个浅拷贝的变量时也需要使用堆内存而不能直接返回一个指向函数内部定义变量的引用。