# 棧和堆 > [the-stack-and-the-heap.md](https://github.com/rust-lang/rust/blob/master/src/doc/book/the-stack-and-the-heap.md) commit 049b9e4e8067b998e4581d026b0bc6d1113ab9f5 作為一個系統語言，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 | 我們有位于地址`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 italic() { let i = 6; } fn bold() { let a = 5; let b = 100; let c = 1; italic(); } fn main() { let x = 42; bold(); } ~~~ 好的，第一步，我們調用`main()`： | 地址 | 名稱 | 值 | |-----|-----|-----| | 0 | x | 42 | 接下來，`main()`調用`bold()`： | 地址 | 名稱 | 值 | |-----|-----|-----| | **3** | **c** | **1** | | **2** | **b** | **100** | | **1** | **a** | **5** | | 0 | x | 42 | 接著`bold()`調用`italic()`： | 地址 | 名稱 | 值 | |-----|-----|-----| | *4* | *i* | *6* | | **3** | **c** | **1** | | **2** | **b** | **100** | | **1** | **a** | **5** | | 0 | x | 42 | 噢！我們的棧變得很高了。 在`italic()`結束后，它的幀被釋放，只留下`bold()`和`main()`： | 地址 | 名稱 | 值 | |-----|-----|-----| | **3** | **c** | **1** | | **2** | **b** | **100** | | **1** | **a** | **5** | | 0 | x | 42 | 然后接著`bold()`結束，只剩下`main()`的了： | 地址 | 名稱 | 值 | |-----|-----|-----| | 0 | x | 42 | 接下來我們完事了。找到了竅門了嗎？這就像堆盤子：你在頂部增加，從頂部取走。 ### 堆 目前為止，它能出色的工作，不過并非所有事情都能這么運作。有時，你需要在不同函數間傳遞一些內存，或者讓它活過一次函數執行。為此，我們可以使用堆。 在Rust中，你可以使用[`Box<T>`類型](http://doc.rust-lang.org/std/boxed/index.html)在堆上分配內存。這是一個例子： ~~~ fn main() { let x = Box::new(5); let y = 42; } ~~~ 這是當`main()`被調用時內存中發生了什么： | 地址 | 名稱 | 值 | |-----|-----|-----| | 1 | y | 42 | | 0 | x | ?????? | 我們在棧上分配了兩個變量的空間。`y`是`42`，一如既往，不過`x`怎么樣呢？好吧，`x`是一個`Box<i32>`，而裝箱在堆上分配內存。裝箱的實際值是一個帶有指向“堆”指針的結構。當我們開始執行這個函數，然后`Box::new()`被調用，它在堆上分配了一些內存，并把`5`放在這。現在內存看起來像這樣： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 5 | | ... | ... | ... | | 1 | y | 42 | | 0 | x | → (230) - 1 | 在我們假設的帶有 1GB 內存（RAM）的電腦上我們有 (230) - 1 個地址。并且因為我們的棧從`0`開始增長，分配內存的最簡單的位置是內存的另一頭。所以我們第一個值位于內存的最頂端。而在`x`的結構的值有一個[裸指針](#)指向我們在堆上分配的位置，所以`x`的值是 (230) - 1，我們請求的內存位置。 我們還沒有過多的討論在這個上下文中分配和釋放內存具體意味著什么。深入非常底層的細節超出了這個教程的范圍，不過需重要指出的是這里的堆不僅僅就是一個相反方向增長的棧。在本書的后面我們會有一個例子，不過因為堆可以以任意順序分配和釋放，它最終會產生“洞”。這是一個已經運行了一段時間的程序的內存圖表： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 5 | | (230) - 2 | | | | (230) - 3 | | | | (230) - 4 | | 42 | | ... | ... | ... | | 3 | y | → (230) - 4 | | 2 | y | 42 | | 1 | y | 42 | | 0 | x | → (230) - 1 | 在這個例子中，我們在堆上分配了4個東西，不過釋放了它們中的兩個。在 (230) - 1 和 (230) - 4 之間有一個目前并沒有被使用的斷片（gap）。如何和為什么這會發生的具體細節依賴你用來管理堆的何種策略。不同的程序可以使用不同的“內存分配器”，它們是為你管理（內存）的庫。Rust 程序為此選擇了使用了[jemalloc](http://www.canonware.com/jemalloc/)。 不管怎么說，回到我們的例子。因為這些內存在堆上，它可以比分配裝箱的函數活的更久。然而在這個例子中，它并不如此。[移動](#)當函數結束，我們需要為`main()`釋放棧幀。然而`Box<T>`有一些玄機：[Drop](#)。`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) - 1 | | 20 | | ... | ... | ... | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 我們為`j`，`i`和`h`分配內存。`i`在堆上，所以這里我們有一個指向它的值。 下一步，在`main()`的末尾，`foo()`被調用： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | ... | ... | ... | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 為`x`，`y`和`z`分配了空間。參數`x`和`j`有相同的值，因為這是我們傳遞給它的。它是一個指向`0`地址的指針，因為`j`指向`h`。 接著，`foo()`調用`baz()`，傳遞`z`： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | ... | ... | ... | | 7 | g | 100 | | 6 | f | → 4 | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 我們為`f`和`g`分配了內存。`baz()`非常短，所以當它結束時，我們移除了它的棧幀： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | ... | ... | ... | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 接下來，`foo()`調用`bar()`并傳遞`x`和`z`： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | (230) - 2 | | 5 | | ... | ... | ... | | 10 | e | → 9 | | 9 | d | → (230) - 2 | | 8 | c | 5 | | 7 | b | → 4 | | 6 | a | → 0 | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 我們最終在堆上分配了另一個值，所以我們必須從 (230) - 1 減一。它比直接寫`1,073,741,822`更簡單。在任何情況下，我們通常用這個值。 在`bar()`的末尾，它調用了`baz()`： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | (230) - 2 | | 5 | | ... | ... | ... | | 12 | g | 100 | | 11 | f | → (230) - 2 | | 10 | e | → 9 | | 9 | d | → (230) - 2 | | 8 | c | 5 | | 7 | b | → 4 | | 6 | a | → 0 | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 這樣，我們就到達最深的位置！噢！恭喜你一路跟了過來。 在`baz()`結束后，我們移除了`f`和`g`： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | (230) - 2 | | 5 | | ... | ... | ... | | 10 | e | → 9 | | 9 | d | → (230) - 2 | | 8 | c | 5 | | 7 | b | → 4 | | 6 | a | → 0 | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 接下來，我們從`bar()`返回。在這里`d`是一個`Box<T>`，所以它也釋放了它指向的內存空間：(230) - 2。 | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | ... | ... | ... | | 5 | z | → 4 | | 4 | y | 10 | | 3 | x | → 0 | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 0 | h | 3 | 而在這之后，`foo()`返回： | 地址 | 名稱 | 值 | |-----|-----|-----| | (230) - 1 | | 20 | | ... | ... | ... | | 2 | j | → 0 | | 1 | i | → (230) - 1 | | 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<T>`和`Arc<T>`中用到了引用計數）。 當考慮到極端情況，堆分配的增加的表現力帶來了要么是顯著的運行時支持（例如，以垃圾回收器的形式）要么是顯著的程序猿努力（以必需進行 Rust 編譯器并未提供的驗證的顯式的內存管理調用的形式）的開銷。 gigabyte > . `Gigabyte` > 可以表示兩個意思：10 9 > 或 2 30 > 。SI（國際單位制）標準解釋為“gigabyte”是 10 9 > ， 而“gibibyte”是 2 30 > 。然而，很少有人用這個術語，而依賴語境上下文來區別。這里我們遵循傳統。 [ ?](# "Jump back to footnote [gigabyte] in the text.") 移動 > . 我們可以通過轉移所有權來讓內存活的更久，這有時叫做“移出箱子”。我們將在后面涉及更復雜的例子。 [ ?](# "Jump back to footnote [移動] in the text.")