Heap & Stack

簡介

堆和棧是計算機裡面最基本的概念，不過如果一直使用高級語言如 Python/Ruby/PHP/Java 等之類的語言的話，可能對堆和棧並不怎麼理解，當然這裡的棧(Stack)並不是數據結構裡面的概念，而是計算機對內存的一個抽象。相比而言，C/C++/Rust 這些語言就必須對堆和棧的概念非常瞭解才能寫出正確的程序，之所以有這樣的區別是因為它們的內存管理方式不同，Python 之類的語言程序運行時會同時會運行垃圾回收器，垃圾回收器與用戶程序或並行執行或交錯執行，垃圾回收器會自動釋放不再使用的內存空間，而 C/C++/Rust 則沒有垃圾回收器。

操作系統會將物理內存映射成虛擬地址空間，程序在啟動時看到的虛擬地址空間是一塊完整連續的內存。

棧內存從高位地址向下增長，且棧內存分配是連續的，一般操作系統對棧內存大小是有限制的，Linux/Unix 類系統上面可以通過 ulimit 設置最大棧空間大小，所以 C 語言中無法創建任意長度的數組。在Rust裡，函數調用時會創建一個臨時棧空間，調用結束後 Rust 會讓這個棧空間裡的對象自動進入 Drop 流程，最後棧頂指針自動移動到上一個調用棧頂，無需程序員手動干預，因而棧內存申請和釋放是非常高效的。

相對地，堆上內存則是從低位地址向上增長，堆內存通常只受物理內存限制，而且通常是不連續的，一般由程序員手動申請和釋放的，如果想申請一塊連續內存，則操作系統需要在堆中查找一塊未使用的滿足大小的連續內存空間，故其效率比棧要低很多，尤其是堆上如果有大量不連續內存時。另外內存使用完也必須由程序員手動釋放，不然就會出現內存洩漏，內存洩漏對需要長時間運行的程序(例如守護進程)影響非常大。

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編譯器上的實踐。

大多數帶 GC 的面嚮對象語言裡面的對象都是藉助 box 來實現的，比如常見的動態語言 Python/Ruby/JavaScript 等，其宣稱的"一切皆對象(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<i32> 和 Vec<Box<i32>> 內存佈局，這兩個圖來自 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<Box<i32>> 類似，只是把 i32 換成任意類型，就操作效率而言比單純的 List 高效，同時又比數組使用更靈活。

一般而言，在編譯期間不能確定大小的數據類型都需要使用堆上內存，因為編譯器無法在棧上分配 編譯期未知大小 的內存，所以諸如 String, Vec 這些類型的內存其實是被分配在堆上的。換句話說，我們可以很輕鬆的將一個 Vec move 出作用域而不必擔心消耗，因為數據實際上不會被複制。

另外,需要從函數中返回一個淺拷貝的變量時也需要使用堆內存而不能直接返回一個指向函數內部定義變量的引用。