GC 基础算法：标记-清除、标记-整理、复制收集、引用计数

所有现代 GC 都建立在四种基础算法之上：标记-清除、标记-整理、复制收集、引用计数。理解它们的原理、优缺点和适用场景，是理解 G1、ZGC 等复杂收集器的前提。

目录

可达性分析

所有追踪式 GC（标记-清除/整理/复制）的第一步都是找出哪些对象是存活的。

GC Roots（根集合）

从以下"根"出发，可达的对象都是存活的，不可达的是垃圾：

GC Roots 包括：栈帧局部变量、静态变量、JNI 引用、活跃线程对象。

可达性 vs 引用计数

可达性分析（Reachability Analysis）和引用计数（Reference Counting）是判断"存活"的两类思路：

标记-清除

Mark-Sweep，1959 年 McCarthy 为 Lisp 发明，是所有 GC 算法的始祖。

两个阶段

标记阶段（Mark）： 从 GC Roots 出发，遍历所有可达对象，打上标记；清除阶段（Sweep）： 扫描整个堆，回收未标记的对象。

核心问题：内存碎片

碎片导致大对象分配失败，并触发更频繁的 GC。例如：回收 B、C 后总空闲 35B，但无法分配连续 25B 的对象。

标记-整理

Mark-Compact，在标记-清除基础上增加整理（Compact） 阶段，解决碎片问题。

三个阶段

代价

整理需要移动对象，移动后所有指向这些对象的引用都需要更新——这是一个昂贵的操作，通常需要 STW（Stop-The-World，暂停所有应用线程）。

复制收集

Copying Collection，将堆分为两个等大的半区，每次只使用一半。

工作原理

优缺点

优点：

• 分配极快（指针碰撞，bump pointer）
• 回收后空间连续，无碎片
• 只需遍历存活对象，垃圾多时反而快

缺点：

• 内存利用率只有 50%
• 存活对象多时复制开销大

这就是为什么复制收集主要用于年轻代（朝生夕死，存活率低，复制开销小）。

引用计数

每个对象维护一个计数器，记录有多少引用指向它。计数降为 0 时立即回收。

工作原理

# Python 引用计数示意
a = [1, 2, 3]   # 列表对象引用计数 = 1
b = a            # 引用计数 = 2
del a            # 引用计数 = 1
del b            # 引用计数 = 0 → 立即回收

循环引用问题

# 循环引用导致内存泄漏
a = {}
b = {}
a['b'] = b   # b 的引用计数 = 2（变量 b + a 字典内的引用）
b['a'] = a   # a 的引用计数 = 2（变量 a + b 字典内的引用）

del a        # a 的引用计数 = 1（b 字典仍然引用它，从 2 降到 1）
del b        # b 的引用计数 = 1（a 字典仍然引用它，从 2 降到 1）
# 计数无法降为 0，触发不了回收
# 但它们从任何 GC Root 都不可达
# → 内存泄漏！

Python 用分代循环检测（cyclic garbage collector）解决这个问题，周期性地检测不可达的循环引用。

Swift ARC（自动引用计数）

class Node {
    var next: Node?   // strong 引用：计数 +1

    // 循环引用的解决：weak 引用不增加计数
    weak var parent: Node?
}

var a: Node? = Node()   // 引用计数 = 1
var b: Node? = a        // 引用计数 = 2
a = nil                 // 引用计数 = 1
b = nil                 // 引用计数 = 0 → 释放

算法对比

现代 GC 都是组合算法： G1 在年轻代用复制收集，在老年代用标记-整理；ZGC 在标记-整理的基础上引入染色指针和读屏障实现并发移动。

参考资料

• 《深入理解 Java 虚拟机》第 3 章 — 周志明
• 《垃圾回收算法手册》— Richard Jones et al.（GC 领域最全面的教科书）
• 分代假说与分代收集
• CMS 收集器