為什麼 GC#
C 用 malloc/free、Rust 用 ownership、C++ 用 RAII ── 都把記憶體管理留給程式設計師。動態語言（Python、Ruby、JS、Java）選擇 GC：runtime 自己判斷哪些物件還在用、哪些可以回收。
代價：runtime 變大、有 pause、有時不可預測。 收益：程式設計師專注業務、避免一整類 bug（use-after-free、double-free、leak）。
設計 GC 時要平衡幾件事：
- 吞吐：總 GC 時間佔比
- 延遲：單次 pause 多長
- 記憶體開銷：保留多餘空間
- 實作複雜度：寫 GC 是出名的容易出錯
沒有「最好的 GC」── 只有「對這個 workload 最適合的 GC」。
引用計數（Reference Counting）#
最簡單：每個物件記著「有幾個 reference 指我」。reference 增加時 ++、減少時 –，歸零時釋放。
struct Object {
int rc;
...
};
void inc_ref(Object *o) { o->rc++; }
void dec_ref(Object *o) {
if (--o->rc == 0) {
scan_and_dec_children(o);
free(o);
}
}優點：
- 確定性釋放（物件 unreachable 立刻被回收）
- 沒有 pause（攤分到每次 ref 變動）
- 容易實作
缺點：
- 每個 ref 變動都付代價（即使物件還活著）
- 無法處理循環引用：兩物件互相 ref ➡️ rc 永不到 0
- thread 安全的 RC 要 atomic op，更慢
代表：CPython（基本機制）、Swift、Objective-C ARC、Perl 5、PHP。
CPython 配合一個 cycle collector 解循環引用：定期掃可疑 candidate，找出 RC > 0 但其實是循環的物件。
Mark-Sweep（標記-清掃）#
最古老的 tracing GC，1960 LISP 就有。
1. Mark phase
從 root（global、stack、register）開始，
遞迴標記所有可達物件
2. Sweep phase
遍歷所有 heap 物件，沒被 mark 的釋放，
被 mark 的清掉 mark bitvoid collect(void) {
// 1. Mark
for_each_root(r) {
mark(r);
}
// 2. Sweep
Object *prev = NULL, *o = heap.all;
while (o) {
Object *next = o->next;
if (o->is_marked) {
o->is_marked = false; // 清標記
prev = o;
} else {
if (prev) prev->next = next;
else heap.all = next;
free(o);
}
o = next;
}
}
void mark(Object *o) {
if (o == NULL || o->is_marked) return;
o->is_marked = true;
for_each_child(o, c) {
mark(c);
}
}優點：
- 處理循環
- 簡單
缺點：
- 整個程式 stop-the-world 直到 mark + sweep 完
- 碎片化（free 後留下不連續空洞）
- 遞迴 mark 可能爆 stack（深物件圖）
代表：Crafting Interpreters、許多教學 VM、CPython 的 cycle collector、Boehm GC。
Tri-color marking#
mark 過程的概念抽象：
| 顏色 | 含義 |
|---|---|
| 白 | 還沒看過（最初狀態，回收候選） |
| 灰 | 看過了但子節點還沒看 |
| 黑 | 自己跟子節點都看過了 |
init: 所有物件白
從 root 把 root 變灰
loop: 挑一個灰物件
把它變黑
把它的子物件中所有白變灰
直到沒有灰的
最後白的全可回收這個抽象是後續所有 incremental / concurrent GC 的理論基礎 ── 因為 marking 可以暫停與恢復（保持顏色狀態）。
Copying / Semi-space（複製式）#
把 heap 切兩半（from-space、to-space）。配置只在 from-space。GC 時：
1. 把所有從 root 可達的物件複製到 to-space
2. 把指標更新到新位置
3. from-space 整個丟掉
4. 兩邊角色互換優點：
- 配置就是 bump pointer，極快（一條 add）
- 沒碎片（複製後緊湊）
- 死物件不需要訪問
缺點：
- 記憶體只能用一半
- 物件需要可移動（pointer 更新）
代表：Lisp 系傳統、JVM 的 young generation。
Object *bump = to_space;
Object *limit = to_space + SIZE;
Object *alloc(size_t n) {
if (bump + n > limit) collect();
Object *p = bump;
bump += n;
return p;
}bump pointer 配置是 最快的 alloc 形式 ── 比 free list 還快。這也是 G1、ZGC 等現代 GC 仍用 copying 的原因。
Mark-Compact（標記-壓實）#
mark-sweep 的問題是碎片，copying 的問題是浪費一半空間。mark-compact 結合兩者優點：
1. Mark（同 mark-sweep）
2. Compact：把所有活物件向一端搬移、緊湊排列、更新所有指標實作較複雜（要正確更新所有指向被搬物件的指標），但消除碎片、不浪費空間。常作為 generational GC 的 old generation 策略。
Generational GC（世代 GC）#
The weak generational hypothesis：「絕大多數物件死得很早」── 數十年觀察累積的經驗法則。
於是把 heap 分世代：
+──────────────────────+
| Young generation | ← 新物件、頻繁 GC、用 copying
| Eden + Survivor |
+──────────────────────+
| Old generation | ← 撐過幾次 GC 的物件、少 GC、用 mark-compact
+──────────────────────+Minor GC：只看 young。多數物件還沒升 old ➡️ young 很快回收。 Major / Full GC：少做，看整個 heap。
效能：因為大多數物件死在 young，minor GC 又快又省。
Card table 與 write barrier#
problem：minor GC 只 scan young，但 old 的物件可能 ref young ➡️ 不能 miss。
solution：write barrier。每次寫入引用時：
void write_field(Object *parent, int slot, Object *value) {
parent->fields[slot] = value;
if (in_old(parent) && in_young(value)) {
record_old_to_young(parent); // 加進 remembered set
}
}minor GC 時，把 remembered set 也當成 root ➡️ 安全。
代價：每次寫 reference 都付 barrier（編譯期可消除部分）。對寫密集程式有真實開銷。
代表：JVM、CRuby（3.2+）、V8、.NET。
Incremental GC#
「stop the world」對互動性糟糕（GUI、遊戲）。incremental GC 把 mark 切成多次小步驟：
原本：mark 全部 → sweep 全部
incremental：mark 一點 → 跑 user code 一點 → mark 一點 → ... → sweep挑戰：在 mark 進行時 user code 可能改 reference graph，破壞 tri-color invariant。靠 write barrier 保持：
黑物件不能直接指向白物件
實作：寫入時，如果 parent 是黑、child 是白 ➡️ 把 parent 變回灰（重新走訪）或把 child 變灰。
代表：Lua 5.x（incremental mark-sweep）、Go runtime、Erlang。
Concurrent GC#
在另外的 thread 跟 user code 並行做 mark / sweep。基本上是 incremental 的並行版。
代表：JVM G1、Shenandoah、ZGC、.NET Server GC。
ZGC、Shenandoah 號稱 sub-millisecond pause（堆即使數百 GB）── 靠 read barrier、coloured pointer 等先進技巧達成。實作極為複雜。
Bump-pointer 配置 + region#
現代 GC（G1、ZGC）把 heap 切成許多 region：
+─────────────────────────────────+
| R1 | R2 | R3 | R4 | R5 | R6 | ...| 各 1~32 MB
+─────────────────────────────────+每個 region 內部 bump pointer 配置。整個 region 滿了 ➡️ 標記為 candidate，之後集中回收。
可以靈活把 region 分配為 eden / survivor / old / humongous。回收時也可以挑 region（Garbage-First：先收最髒的）。
引用計數 vs Tracing：實務取捨#
| 維度 | RC | Tracing |
|---|---|---|
| 單次回收延遲 | 確定（dec ➡️ free） | 集中（不可預測） |
| 整體吞吐 | RC overhead 可能輸給 tracing | 通常較好 |
| 循環處理 | 需要額外機制 | 自然處理 |
| 實作複雜度 | 簡單 | 複雜 |
| 執行緒安全 | 需 atomic | 多執行緒下也複雜 |
RC 適合 可預測性 > 吞吐 的場景（iOS、嵌入式）。Tracing 適合 吞吐 > 個別延遲 的場景（伺服器、後端）。
物件頭與 GC 配合#
每個 GC-managed 物件需要 metadata：
struct Object {
Class *klass;
uint32_t flags; // mark bit, gen, lock, hash...
Object *next; // GC scan 鏈，或 forward pointer
};Java 的 object header 16 bytes（hash、lock、class、age）── 對小物件是顯著 overhead。compressed oop / sparse layouts 都是減 header 的努力。
V8 用 hidden class + tagged value 把 header 壓到 8 bytes。CRuby 12~16 bytes。
Roots 是什麼#
GC 從 root 開始 scan，root 是「絕對活著的」：
- VM 的 stack（所有 frame 的 locals + operand stack）
- 全域變數 / module dict
- 所有 thread 的 current frame
- C 程式碼持有的 reference（必須登記給 GC）
- finalizer 待執行的物件
最後一條最容易出錯：原生 C 程式碼建了 VM 物件，還沒放到任何 VM 可見處，這時觸發 GC ➡️ 物件被誤殺。所以所有 native 函式都要把暫時持有的物件放在 GC visible 的位置（如 vm->sp、handle table）。
寫 GC 的常見地雷#
- 忘了某個 root：物件被誤殺，幾小時後在某個無關位置 segfault
- mark 後 free 而 forward pointer 沒更新：dangling pointer
- write barrier 漏掉某條 path：generational collector 漏掃
- GC 期間配置新物件：分配導致再 GC，無限遞迴
- finalizer 復活物件：原本要回收的物件又被賦值給活物件 ➡️ 必須延後回收
GC 是「失敗模式延遲很久才浮現」的代表性子系統。寫的時候要保守、要測壓力、要 fuzz。
給玩具 VM 的建議#
從零做 VM、沒打算上生產：
- 第一版：mark-sweep，遞迴 mark（不到 200 行）
- 第二版：把 mark 改成顯式 stack（避免 C stack overflow）
- 第三版：generational + write barrier（寫起來開始痛）
- 第四版：incremental（為了減少 pause）
90% 的玩具 VM 停在第一版就夠了。Crafting Interpreters 的 GC 就是第一版 + 一些細節。
嵌入式環境的取捨#
（更詳細在第十二章）
- 不能用 mark-sweep：碎片化在小 heap 上是災難
- 不能停太久：MCU 通常還在跟硬體互動，pause = miss interrupt
- 少 ref：傾向 RC（確定性、立即回收）
- 靜態配置 region：避免 fragmentation
mruby/c 的 GC：reference counting + 簡易 cycle 處理 + 區塊池。極簡。
觀測 GC#
# Java
java -verbose:gc -Xlog:gc*:file=gc.log MyApp
# Python (gc module)
python -c 'import gc; gc.set_debug(gc.DEBUG_STATS); ...'
# Ruby
ruby --dump=gc-tune script.rb
# V8 (in Chrome)
node --trace-gc script.js每個 runtime 都有 GC profiling 工具。瞭解你的 workload 對 GC 的影響（allocation rate、live size、pause）是調優前提。
小結#
GC 演化的主線：
RC → Mark-Sweep → Mark-Compact → Copying →
Generational → Incremental → Concurrent → Region-based每一步都解前一個的痛點，但帶來新的複雜度。
選擇依據：
- 玩具 VM、學習：mark-sweep
- 嵌入式、可預測性：RC
- 伺服器吞吐：generational concurrent（HotSpot G1、ZGC）
- 互動 / GUI：incremental（Go、Lua）
- iOS、桌面應用：RC（Swift ARC）
理解 GC 比實作 GC 容易得多。這章足以讓你看懂 GC 文件、調參數、判斷哪個演算法適合你的場景。
下章看 JIT ── 動態語言效能的最後一塊。