How Programs Remember: Stack and Heap

程式如何記憶：Stack 與 Heap

@ 技術討論

前言

學習高階程式語言通常都會接受一個觀念是：「沒用到的變數會自動被垃圾回收掉」。不過越接近底層或開始探討效能問題，發現自己對於程式語言核心的記憶體概念 Heap 與 Stack 並沒有那麼清楚。程式語言究竟是如何分配與管理記憶體的？所謂的垃圾回收（Garbage Collection, GC）具體來說又做了哪些事情？

為什麼需要 Stack 與 Heap？

程式運行時需要將變數存放於記憶體當中，而作業系統作為程式與硬體之間協調的媒介，Stack 與 Heap 正是作業系統與語言執行環境用來管理記憶體的架構：

  • 效率：現代 CPU 為了效能會使用快取來暫存常用的記憶體片段，當記憶體內容變動時則必須同步更新快取，而這個過程本身是有成本的，從效能角度來看，資料在記憶體中越連續緊湊，CPU 快取命中率就越高，效能也越好。透過利用 Stack 可預期的記憶體分配方式，來換取極高的存取效率。
  • 靈活性：基於需要動態改變內容的資料與大量存放的需求，透過 Heap 靈活存放的特性互補 Stack 的弱項。

Stack

Stack 是一種「後進先出」的資料結構用於存放函式運行中的資訊，想像一層層鬆餅堆疊後從最上面開始吃，最後放上去的最先被吃掉，且只能 push（推入）與 pop （彈出）來改變內容，運行原理如下：

  1. 系統會在 Stack 上建立一個新的 Stack Frame
  2. 把該函式的參數、區域變數、返回地址、暫存器狀態⋯⋯等資料放進去
  3. 函式執行完畢後，整個 frame 會一次被 pop（彈出）
  • 優點：
    • 快速頻繁的操作：結構上不需要找位置或判斷資料還有沒有在使用，可預期的結果造就高操作效率。
    • 存放緊湊：運用記憶體緊湊方便快取。
  • 缺點：
    • 無法應對對於浮動尺寸的資料：結構上很難優雅的應對浮動尺寸的資料。
    • 空間有限：結構上 Stack 需要指派固定尺寸，通常是數個 MB，可能在大量資料或遞迴場合下 Stack Overflow。

Heap

Process
 ├─ Thread A → Stack A
 ├─ Thread B → Stack B
 └─ Heap (shared)

Heap 是一塊用來存放「動態分配資料」的記憶體區域，不具備嚴格的進出順序限制，可以採用不同的寫入策略（First Fit、Best Fit、Worst Fit）。

基於 Stack 較小的固定尺寸且寫入時只能緊湊的推入資料，Stack 通常僅保存指向 Heap 的指標，實際資料分配於 Heap，以避免 Stack 容量小且生命週期受限的問題。

  • 優點：
    • 靈活寫入與釋放：可動態的向 OS 申請更多空間。
    • 可存放跨多個函式存活的資料：由於 Stack 容量固定且資料生命週期受限，當資料需要跨函式存活或大小在編譯期無法確定時，通常會分配於 Heap，而 Stack 僅保存指向 Heap 的指標。
  • 缺點：
    • 分配速度較慢：需要尋找合適的記憶體區塊來存放資料。
    • 需要額外的管理機制：在高階語言中，這通常由垃圾回收器（GC）負責，在 C 語言中則透過：
      • malloc / calloc / realloc：向 Heap 分配記憶體。
      • free：釋放已分配的記憶體。
    • 可能產生記憶體碎片：長時間分配與釋放不同大小的區塊，會造成可用空間不連續。

Go 觀察逃逸到 Heap 的變數

Go 編譯器可以透過逃逸分析（Escape Analysis）來決定變數應該分配在 Stack 還是 Heap，當編譯器無法證明變數在函數返回後不會被使用時，變數就會「逃逸」到 Heap 上：

Terminal window
go build -gcflags="-m" main.go


./heap-test.go:5:5: moved to heap: x
./heap-test.go:11:5: moved to heap: count
./heap-test.go:20:9: moved to heap: arr
./heap-test.go:27:12: 100 escapes to heap
package main


import "fmt"


// 範例 1: 返回局部變數的指針
func createPointer() *int {
    x := 42  // x 原本在 stack 上
    return &x  // 返回指針導致 x 逃逸到 heap
}


// 範例 2: 變數被閉包捕獲
func createClosure() func() int {
    count := 0  // count 逃逸到 heap
    return func() int {
        count++
        return count
    }
}


// 範例 3: 變數太大
func largeArray() *[10000]int {
    var arr [10000]int  // 太大，逃逸到 heap
    return &arr
}


// 範例 4: interface 類型
func useInterface() interface{} {
    x := 100  // 賦值給 interface 導致逃逸
    return x
}


func main() {
    // 範例 1
    ptr := createPointer()
    fmt.Println("指針值:", *ptr)


    // 範例 2
    counter := createClosure()
    fmt.Println("計數:", counter()) // 1
    fmt.Println("計數:", counter()) // 2


    // 範例 3
    arr := largeArray()
    fmt.Println("陣列第一個元素:", arr[0])


    // 範例 4
    val := useInterface()
    fmt.Println("interface 值:", val)
}

延伸閱讀