棧和堆

棧和堆

作為一種系統(tǒng)語(yǔ)言，Rust 運(yùn)行在較低的層次。如果你只學(xué)習(xí)過(guò)高級(jí)語(yǔ)言，有一些系統(tǒng)編程方面的問(wèn)題，你可能不熟悉。最重要的一個(gè)問(wèn)題是存儲(chǔ)器如何工作，例如如何使用堆和棧。如果你對(duì) c 語(yǔ)言如何使用堆棧分配熟悉的話，本章將會(huì)是一個(gè)復(fù)習(xí)。如果你不熟悉的話，你將會(huì)學(xué)習(xí)到Rust-y 關(guān)注的一些相關(guān)基本概念。

內(nèi)存管理

關(guān)于內(nèi)存管理有兩個(gè)常用術(shù)語(yǔ)。棧和堆是一種抽象概念，幫助您確定何時(shí)分配和釋放內(nèi)存。

這里有一個(gè)更高層次的比較：

棧是非?？斓?，也是 Rust 默認(rèn)的內(nèi)存分配方式。但是分配存在于本地函數(shù)調(diào)用，且在大小方面是有限的。另一方面，堆的速度相對(duì)比較慢，但是你的程序可以明確地分配堆內(nèi)存。且它實(shí)際上是無(wú)限制的，可以在全局范圍內(nèi)訪問(wèn)。

棧

讓我們談?wù)勥@個(gè) Rust 程序:

    fn main() {
        let x = 42;
    }

這個(gè)程序有一個(gè)變量綁定 x。這需要分配內(nèi)存。默認(rèn)情況下，Rust 進(jìn)行棧分配，這意味著基值存儲(chǔ)到棧內(nèi)。這是什么意思呢?

當(dāng)一個(gè)函數(shù)被調(diào)用時(shí)，一些內(nèi)存被分配給它的所有局部變量和其他一些信息。這就是所謂的“棧幀”，本教程的目的，我們將忽略額外的信息，只考慮局部變量的分配。所以在這種情況下，當(dāng) main() 運(yùn)行時(shí)，將為我們的棧幀分配一個(gè) 32 位整數(shù)。如你所見(jiàn)，這是自動(dòng)處理的，我們不必為此編寫(xiě)任何特殊 Rust 代碼或其他任何東西。

函數(shù)結(jié)束后，它的棧幀被收回。這也是自動(dòng)實(shí)現(xiàn)的，我們不需要做什么特別的事情。

這就是一個(gè)簡(jiǎn)單的程序全部的內(nèi)容。關(guān)鍵的是要理解棧分配是非常，非常快的。在我們了解所有的局部變量之前，我們有時(shí)間可以一次性抓取內(nèi)存。并且因?yàn)槲覀兛梢栽谕粫r(shí)間丟棄他們，我們也可以迅速擺脫它。

不利的一面是，當(dāng)我們不只是在一個(gè)單一的函數(shù)內(nèi)需要它們時(shí)，卻不能長(zhǎng)存這些值。我們還沒(méi)有談到這個(gè)名字：“?！钡囊馑?。為此,我們需要一個(gè)稍微復(fù)雜一點(diǎn)的例子：

    fn foo() {
        let y = 5;
        let z = 100;
    }

    fn main() {
        let x = 42;

        foo();
    }

這個(gè)程序總共有三個(gè)變量：兩個(gè)在 foo() 中,一個(gè)在 main() 中。和之前一樣，當(dāng) main() 被調(diào)用時(shí)，單個(gè)整數(shù)分配它的棧幀。但是在此之前可以顯示調(diào)用 foo() 時(shí)會(huì)發(fā)生什么，我們需要想象內(nèi)存中是如何操作的。操作系統(tǒng)提供了一個(gè)程序的內(nèi)存視圖，它非常簡(jiǎn)單：一個(gè)巨大的地址列表，從 0 到很大的值，代表你的計(jì)算機(jī)有多少內(nèi)存。例如，如果你有一個(gè) G 的內(nèi)存，你的地址從 0 到 1,073,741,824。這一數(shù)字來(lái)自于 2 的 30 次方，是一個(gè)十億字節(jié)的數(shù)字級(jí)別。

這個(gè)內(nèi)存就像是一個(gè)巨大的數(shù)組：地址從 0 開(kāi)始，到最后的數(shù)。這是第一個(gè)棧幀的圖表：

我們可以知道地址為 0 的地方存儲(chǔ)了一個(gè)名稱為 x，值為 42 的東西。

調(diào)用 foo()，一個(gè)新的棧幀被分配：

因?yàn)?0 被第一幀占用，1 和 2 用于 foo() 的棧幀。我們調(diào)用的函數(shù)越多，內(nèi)存向上增長(zhǎng)的越多。

這里，我們必須注意一些重要的事情。數(shù)字 0、1 和 2 都僅僅是為了便于說(shuō)明，和計(jì)算機(jī)實(shí)際使用的情況沒(méi)有絲毫關(guān)系。特別是，是現(xiàn)實(shí)中，一系列地址是會(huì)被一些單獨(dú)的自己隔開(kāi)成單獨(dú)的每個(gè)地址的，這些分割甚至可能會(huì)超過(guò)存儲(chǔ)的值的大小。

foo() 結(jié)束后，其幀被收回：

然后，main() 結(jié)束后，甚至最后的值都會(huì)消除。簡(jiǎn)單吧!

這就是所謂的“?！?，因?yàn)樗褚粋€(gè)餐盤(pán)的棧：你放下去的第一塊盤(pán)子將是你最后拿回來(lái)的盤(pán)子。棧有時(shí)被稱為“后進(jìn)先出隊(duì)列”的原因，就是你最后放入棧內(nèi)的值就是第一個(gè)你需要檢索的值。

讓我們嘗試一個(gè)三層的例子：

    fn bar() {
        let i = 6;
    }

    fn foo() {
        let a = 5;
        let b = 100;
        let c = 1;

        bar();
    }

    fn main() {
        let x = 42;

        foo();
    }

好吧，首先，我們調(diào)用 main()：

接下來(lái)，main() 調(diào)用 foo()：

然后 foo() 調(diào)用 bar()：

現(xiàn)在，我們的棧越來(lái)越高了。

bar() 結(jié)束后，其棧幀被回收，留下 foo() 和 main()：

然后 foo() 結(jié)束后，只留下 main()：

然后我們就大功告成了。明白了嗎？就像堆餐具：一直添加到頂部，然后從頂部開(kāi)始取走。

堆

這種方法可以很好地工作，但并不是一切事物都可以像這樣工作。有時(shí)，不同功能之間需要共享內(nèi)存，或者不只是在單個(gè)函數(shù)的執(zhí)行期間保持活動(dòng)狀態(tài)。為此，我們可以使用堆。

在 Rust 中，你可以使用 Box 類型在堆上分配內(nèi)存。這里有一個(gè)例子：

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

當(dāng) main() 被調(diào)用時(shí)，內(nèi)存發(fā)生如下變化：

我們?cè)跅Ｉ蠟閮蓚€(gè)變量分配空間。像以往一樣，y 值為 42，但 x 呢？恩，x 是一個(gè) Box 類型的值，Boxes 在堆上分配內(nèi)存。boxes 的實(shí)際值是一種數(shù)據(jù)結(jié)構(gòu)，實(shí)際上是指向“堆”的一個(gè)指針。當(dāng)我們開(kāi)始執(zhí)行函數(shù)，調(diào)用 Box::new()，它為堆分配一些內(nèi)存，將 5 放在內(nèi)存內(nèi)。內(nèi)存現(xiàn)在看起來(lái)像這樣：

在一個(gè)假想的電腦里，我們有 1GB 的 RAM。因?yàn)槲覀兊臈牧阍鲩L(zhǎng)，從最簡(jiǎn)單的地方開(kāi)始分配內(nèi)存。所以我們的第一個(gè)值是在內(nèi)存中最高的地方。x 這個(gè)結(jié)構(gòu)的值有一個(gè)原始指針，指向在堆上分配的位置，所以 x 的值是 2 的 30 次方，即我們請(qǐng)求的內(nèi)存位置。

關(guān)于在這些環(huán)境中實(shí)際上如何進(jìn)行分配和釋放內(nèi)存，我們還沒(méi)有談?wù)撎唷１窘坛讨?，我們?huì)討論更深的細(xì)節(jié)，但這里必須指出的是，堆不像棧是從一端開(kāi)始生長(zhǎng)。在本書(shū)后邊的部分，我們會(huì)討論到這樣的一個(gè)例子，但是由于堆可以以任何順序分配和釋放內(nèi)存，最終以很多“洞”的存在結(jié)束。這是一個(gè)現(xiàn)在已經(jīng)運(yùn)行了一段時(shí)間的程序的內(nèi)存布局圖:

在現(xiàn)在的情況下，我們?cè)诙焉戏峙淞怂膫€(gè)事物，但釋放了兩個(gè)。目前，在 2 的 30 次方和 2 的 30 次方 -3 之間還有一些空白還沒(méi)有被使用。這種情況如何以及為什么發(fā)生的具體細(xì)節(jié)取決于你用什么樣的策略來(lái)管理堆。不同的程序可以使用不同的內(nèi)存分配器，有函數(shù)庫(kù)來(lái)管理。Rust 程序使用 jemalloc 達(dá)到這個(gè)目的。

無(wú)論如何，現(xiàn)在回到我們的例子。因?yàn)檫@是堆上的內(nèi)存，它的生存周期可以超過(guò)函數(shù)分配 box 的范圍。然而，在這種情況下，在函數(shù)結(jié)束后，它不能 [moving]。我們需要通過(guò) main().Box 釋放棧幀，不過(guò)，有一個(gè)更巧妙的技巧：Drop。Drop 即釋放創(chuàng)建 box 時(shí)分配的內(nèi)存。太棒了!因此，當(dāng)刪除 x 時(shí)，它首先釋放分配在堆上的內(nèi)存：

[moving]：我們可以使內(nèi)存有更長(zhǎng)的生存周期，通過(guò)轉(zhuǎn)移所有權(quán)，有時(shí)被稱為 “moving out of the box”。稍后介紹更復(fù)雜的例子。

然后棧幀消失，釋放我們所有的內(nèi)存。

參數(shù)和引用

我們已經(jīng)了解了一些棧和堆的基本例子，但是關(guān)于函數(shù)參數(shù)和引用呢?這里有一個(gè)小的 Rust 程序：

    fn foo(i: &i32) {
        let z = 42;
    }

    fn main() {
        let x = 5;
        let y = &x;

        foo(y);
    }

當(dāng)我們進(jìn)入 main()，內(nèi)存看起來(lái)像這樣：

x 值為 5，y 是 x 的一個(gè)引用。所以它的值是 x 的內(nèi)存地址，本例中為0。

調(diào)用 foo()，將 y 作為參數(shù)傳遞：

棧幀不只是本地綁定，它們還可以用作參數(shù)。在這種情況下，我們需要有 i 作為參數(shù)，z 作為局部變量綁定。i 是參數(shù) y 的一個(gè)副本。由于 y 的值為 0，所以 i 的值也是 0。

這就是為什么引用一個(gè)變量不占用任何內(nèi)存：一個(gè)引用的值只是一個(gè)指向內(nèi)存位置的指針。但是如果我們不使用潛在的內(nèi)存，事情就不能很好的工作了。

一個(gè)復(fù)雜的例子

好吧,讓我們一步一步地看下這個(gè)復(fù)雜的程序：

    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);
    }

首先,我們調(diào)用 main()：

為 j，i，h 分配內(nèi)存。i 在堆內(nèi)，所以它有一個(gè)指向那兒的值。

接下來(lái)，在 main() 結(jié)束時(shí)調(diào)用 foo()：

給 x，y 和 z 分配空間。參數(shù) x 和 j 有相同的值，因?yàn)檫@就是我們?cè)谄渲袀鬟f的。它是一個(gè)指向地址 0 的指針，因?yàn)?j 指向 h。

接下來(lái)，foo() 調(diào)用 baz()，傳遞 z：

給 f 和 g.baz() 分配內(nèi)存，這個(gè)內(nèi)存占用空間不大，所以當(dāng)它結(jié)束時(shí)，我們可以釋放其棧幀：

接下來(lái)。foo() 調(diào)用 bar()，參數(shù)為 x 和 z：

最后，我們堆上分配另一個(gè)值，因此我們必須從 2 的 30 次方減去 1。即 1,073,741,823。在任何情況下，我們像往常一樣設(shè)置變量。

bar() 結(jié)束時(shí),它調(diào)用 baz()：

到這里，我們已經(jīng)到達(dá)了最深點(diǎn)! 看看接下來(lái)會(huì)怎樣？

bar() 結(jié)束后，f 和 g 就可以除去了：

接下來(lái)，我們從 bar() 返回。在本例中 d 是 Box 類型的，那么它也釋放了它所指向的：2 的 30 次方 -1 位置的內(nèi)存。

之后，foo() 返回：

最后是 main()，它清除了其余的內(nèi)存。當(dāng) i 被 Drop 時(shí)，它也會(huì)清理最后的堆。

其他語(yǔ)言怎么做?

大多數(shù)語(yǔ)言默認(rèn)情況下都有一個(gè)垃圾收集器 heap-allocate。這意味著，每個(gè)值都是會(huì)被封裝。這樣做有許多原因，但是它們不在本教程的范圍內(nèi)，我們?cè)谶@里就不詳細(xì)說(shuō)明了。這有一些可能的優(yōu)化，但也做不到 100% 時(shí)間的優(yōu)化。，垃圾收集器能夠更好地處理堆內(nèi)存的問(wèn)題。

使用哪一個(gè)?

棧更快，也更容易管理，那么為什么我們還需要堆呢？一個(gè)很大原因是，棧分配意味著你只能根據(jù)后進(jìn)先出的語(yǔ)義回收存儲(chǔ)。而堆分配嚴(yán)格說(shuō)來(lái)更一般化，允許以任意順序從池中取出或返回存儲(chǔ)器，但是其更復(fù)雜，成本更高。

一般來(lái)說(shuō)，更傾向于使用棧分配，因此，Rust 默認(rèn)情況下是棧分配。棧后進(jìn)先出模型比較簡(jiǎn)單，也更基礎(chǔ)。一般存在兩大影響因素：運(yùn)行時(shí)效率和語(yǔ)義影響。

運(yùn)行時(shí)的效率。

棧的內(nèi)存管理是微不足道的：機(jī)器只是增加或減少一個(gè)單一的值，即所謂的“棧指針”。堆的內(nèi)存管理就有點(diǎn)不一般了：堆可以在任意點(diǎn)上分配或釋放內(nèi)存，并且堆上分配的內(nèi)存塊可以是任意大小的，內(nèi)存管理器的日常工作必然更難，從而能夠識(shí)別內(nèi)存以便重用。

如果你想更詳細(xì)地深入這個(gè)主題,本文可以給出一個(gè)極好的介紹。

語(yǔ)義的影響

棧分配影響 Rust 語(yǔ)言本身，以及開(kāi)發(fā)人員的思維模型。后進(jìn)先出語(yǔ)義指示 Rust 語(yǔ)言如何自動(dòng)處理內(nèi)存管理。如在本章所討論的那樣，甚至一個(gè)獨(dú)特的基于堆的回收箱也可以通過(guò)基于棧的后進(jìn)先出語(yǔ)義驅(qū)動(dòng)。非后進(jìn)先出語(yǔ)義的靈活性（即表現(xiàn)力）意味著：一般情況下，編譯器在編譯時(shí)無(wú)法自動(dòng)推斷應(yīng)該釋放那些內(nèi)存；它必須依賴于動(dòng)態(tài)協(xié)議（可能來(lái)自語(yǔ)言本身之外）驅(qū)動(dòng)回收，引用計(jì)數(shù)器（Rc 和 Arc 所使用的）就是其中的一個(gè)例子。

在往更深層次說(shuō)呢，逐漸增長(zhǎng)的堆分配表達(dá)力主要來(lái)自有效的運(yùn)行時(shí)支持(如垃圾收集器的形式)和有效的程序員工作(顯式的內(nèi)存管理形式,不需要 Rust 編譯器提供驗(yàn)證)。