#compilers #运行时
本页目录

垃圾回收

运行时自动判定哪些对象不再可达并回收——从 mark-sweep 到分代到并发三色标记,每种 GC 算法都在吞吐和延迟之间取不同的平衡点,而 write barrier 必须由编译器嵌入到每处指针写入。

概述

手动内存管理(C/C++ 的 malloc/free,Rust 的所有权系统)把释放内存的责任放在程序员或类型系统上。垃圾回收(GC)换了一条路:⁠运行时自动判定哪些对象不再可达,回收它们占用的内存⁠。GC 是所有带 GC 的语言(JVM/Go/.NET/JS/Python)的运行时基础——编译器不仅要生成代码,还要在生成代码里嵌入 GC 协作点⁠(safepoint、write barrier),这篇讲四个核心 GC 算法和它们给编译器施加的要求。

核心概念:可达性与根集

GC 的基础问题是:⁠哪些对象还是活的⁠?定义:从根集(root set)——全局变量、栈上的局部变量、寄存器——出发,通过指针能到达的所有对象是活的;其余是垃圾。

根集 = {全局变量, 各线程的栈上的每个 word, 活跃寄存器}
从根集出发, BFS/DFS 追踪指针 → 到达的对象标记为 live
未到达的 → 垃圾, 可回收

任何 GC 都做这个遍历。区别在于什么时候做、怎么回收未到达的对象、以及对 mutator(应用程序代码)的影响⁠。

四个核心算法

1. Mark-Sweep:基础

mark 阶段:
  从根集出发, 遍历对象图, 对每个到达的对象设置 mark-bit

sweep 阶段:
  遍历整个堆, 回收所有未标记的对象, 清空 mark-bit (为下一轮)
  • 代价:mark 阶段遍历活对象的量;sweep 遍历整个堆(含死对象),大量未使用内存也要扫。
  • 不移动对象 → 无需更新指针 → 简单,适合 C/C++ 这类不能移动对象的语言(如 Boehm GC)。
  • 致命缺陷:⁠碎片化⁠——分配和回收交替进行,堆逐渐碎成小块,即使总空闲足够,大对象也可能分配失败。

2. Copying (Semispace, Cheney):用空间换时间和紧凑

把堆分成两半(from-space 和 to-space),任何时刻只用一半:

收集:
  从根集出发, BFS/DFS 遍历活对象
  把活对象从 from-space 复制到 to-space (紧凑地排在一端)
  更新所有指向这些对象的指针 (从旧地址 → 新地址)
  回收整个 from-space (对 OS 来说就是一大块内存)
  from 和 to 角色互换
  • 紧凑(compaction)——活对象被紧密排布,没有碎片。
  • 遍历过程就是 BFS − Cheney 的 copying collector 用 BFS 遍历,同时自然做到了紧凑。
  • 代价:⁠只用一半堆⁠,内存利用率 50%。对带 GC 的语言(JVM, Go),这个代价换来无碎片 + 分配只挪指针(bump allocator),取舍值得。

3. Generational GC:利用"大多数对象早死"

经验观察(weak generational hypothesis):⁠绝大多数对象在分配后很快就变成垃圾⁠(如循环体里分配的临时对象);少数活久的对象倾向于继续活下去。

分代 GC 把堆分成年轻代(nursery)⁠和老年代(tenured):

年轻代: 频繁收集(如每几 MB 分配就触发), 用 copying——活下来的少, 复制代价低
老年代: 低频收集(如内存快满才触发), 用 mark-sweep 或 mark-compact
对象在年轻代活过 N 次收集 → 晋升到老年代

关键工程:⁠跨代引用⁠。老年代对象指向年轻代对象时,只扫年轻代会漏掉这条引用(因为根集不包括老年代)。解法:老年代有个 remembered set——记录"哪些老年代卡片(card)可能含指向年轻代的指针"。年轻代 GC 时,remembered set 中的老年代卡片被加到根集。

写入屏障(write barrier):维护跨代引用

每次指针写入(*p = q)被编译器插入一段小代码:

write_barrier(p, q):
    if p 在老年代 and q 在年轻代:
        标记 p 所在的 card 为 dirty → GC 会扫这块
    *p = q

这个屏障直接由编译器在每次指针写入时生成⁠——不是在运行时解释执行,而是作为机器码嵌入。JVM 的 G1/Shenandoah、Go 的 GC、V8 的 Oilpan,都靠编译器插入 write barrier。

编译器优化对 write barrier 友好:如果编译器能证明 p 是刚分配的(一定在年轻代),就跳过 barrier;如果在循环里同一 p 写多次,编译器可能只保留第一次 barrier(后续写不改变 card 状态)。

并发 GC:mutator 不暂停(或短暂停)

mark-sweep 和 copying 都要求"扫描时 mutator 不能修改对象图"——这意味 stop-the-world(STW) 暂停。现代 GC 的大部分工作允许与 mutator 并发运行:

三色不变量(tri-color invariant)

并发 mark 算法的理论基础,把对象分三类:

  • 白色⁠:尚未被标记(初始状态,也可能是垃圾)
  • 灰色⁠:已被标记,但其内部的指针还未扫描(在 worklist)
  • 黑色⁠:已被标记且所有内部指针已被扫描

不变量:在 mark 结束时,没有任何黑色对象持有指向白色对象的指针。 一旦这个不变量被违反(如 mutator 把白色对象指针写到已标记完成的黑色对象里),那个白色对象就可能被漏标→被错误回收。

维持不变量的方式:要么在扫描过程中拦截破坏不变量的写⁠(用 write barrier 捕获"黑→白"的指针联系),要么允许短暂漏标,后续 fix-up(当 mutator 写 p.field = q 且 p 是黑色,q 是白色,把 q 标记为灰色重新入队)。Go 的 GC 用第二种。

读屏障(read barrier)

write barrier 拦截"写",read barrier 拦截"读":⁠读取一个白色对象时,先把它标记为灰色⁠。Baker 的 concurrent copying collector 用 read barrier——mutator 读到的所有指针必须指向 to-space,在读的瞬间做 forwarding。

选择 write barrier vs read barrier 取决于写多还是读多⁠——大多数系统选 write barrier(写比读少,barrier 开销更低)。

GC 对编译器的要求

GC 不是编译器写完就行的独立模块——编译器必须在生成代码时嵌入 GC 支持:

  • safepoint:不是任何时刻都能 GC——编译器在回边(循环头)或函数调用处插入 safepoint 检查,GC 只在 safepoint 挂起线程。
  • 根映射(root map):编译器为每个 safepoint 生成本地变量/寄存器的活跃指针映射⁠(哪些寄存器/栈位置当前存的是 GC 可见指针),GC 据此扫根集。
  • write barrier 内联⁠:barrier 如果做过大开销(每次都函数调用)会把写密集代码拖慢 10×→ 编译器把 barrier 做成内联的几条指令,只在需记录时才走 slow path。

参考

  • Jones/Hosking/Moss: "The Garbage Collection Handbook" — GC 领域的权威参考
  • Wilson (1992): "Uniprocessor Garbage Collection Techniques" — GC 早期综述
  • Go GC: src/runtime/mgc.go — 工业级并发标记,有清晰设计文档

Keywords: garbage collection, GC, mark-sweep, copying, semispace, Cheney, generational GC, weak generational hypothesis, write barrier, read barrier, card marking, remembered set, tri-color invariant, concurrent GC, stop-the-world, STW, safepoint, root map, compaction, fragmentation, bump allocator, nursery, tenure

相关页面

© 2026 liz's doc