name: 垃圾回收器实现者 description: ‘实现跟踪垃圾回收器。使用场景: (1) 构建语言运行时, (2) 学习内存管理, (3) 优化内存分配。’ version: 1.0.0 tags:

运行时
垃圾回收
内存管理
系统 difficulty: 中级 languages:
C
Rust
C++ dependencies: []

垃圾回收器实现者

实现跟踪垃圾回收器（标记-压缩、代际等）。

使用场景

构建语言运行时
实现解释器/编译器
学习内存管理
优化内存分配

这个技能的作用

实现堆分配 - 对象布局和分配
构建跟踪回收器 - 标记-清除、标记-压缩、复制
处理根 - 栈和全局根
优化 - 代际、增量回收

关键概念

概念	描述
根集	初始可达引用（栈、全局）
跟踪	从根跟踪指针找到活动对象
分配	为新对象找到空间
压缩	回收后整理堆
代际	基于年龄的回收（年轻/年老）

GC算法比较

算法	优点	缺点
标记-清除	简单，无复制	碎片化，暂停
标记-压缩	无碎片化	多遍，慢
复制	快速，无碎片化	一半内存，互斥器复制
代际	短暂停，高效	复杂

提示

仔细跟踪所有根指针
特殊处理弱引用
考虑增量回收的写屏障
在生产中分析暂停时间
使用线程本地分配以提高速度

经典参考

参考	重要性
Jones & Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management” (Wiley, 1996)	垃圾回收的权威教科书
Jones, Hosking & Moss, “The Garbage Collection Handbook: The Art of Automatic Memory Management” (Chapman & Hall, 2012)	更新的全面参考
Lieberman & Hewitt, “A Real-Time Garbage Collector Based on the Lifetimes of Objects” (CACM 1983)	代际GC起源
Ungar, “Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm” (1984)	新生代/老年代
Blackburn & McKinley, “Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance” (PLDI 2008)	现代高吞吐量回收器

权衡与限制

算法权衡

算法	暂停时间	吞吐量	内存	最适合
标记-清除	中等	中等	高	嵌入式系统
标记-压缩	高	低	高	长期运行服务器
复制	低	高	50%	实时、短生命周期对象
代际	低	高	适中	通用目的
增量	可预测	较低	适中	交互式应用

何时不使用GC

对于实时系统：使用实时GC或自定义分配器
对于内存受限：使用手动内存管理或区域
对于确定性时序：避免GC暂停；使用池化
对于裸机：使用静态分配或自定义分配器

复杂度分析

标记-清除：O(n + m)，其中n = 堆对象，m = 标记
复制：O(n)，其中n = 活动对象
代际：O(n) 用于次要回收（年轻代），完整O(n) 用于主要回收
空间开销：转发指针、记住集

限制

暂停时间：停止-世界回收器导致延迟峰值
碎片化：标记-清除导致内部/外部碎片化
开销：GC通常消耗5-20% CPU时间
弱引用：需要特殊处理终结器
调试：内存泄漏更难查找（GC错误微妙）
可移植性：GC依赖于内存布局、指针格式

评估标准

高质量的GC实现应具备：

标准	检查点
正确性	从不回收活动对象
完整性	回收所有不可达对象
暂停时间	低延迟（对于实时：<1ms）
吞吐量	对互斥器开销最小
内存	高效使用堆
扩展性	在多核上工作

质量指标

✅ 好：正确、低暂停、高效 ⚠️ 警告：内存膨胀、偶尔暂停 ❌ 差：回收活动对象（内存损坏）、不终止

研究工具与实例

现实世界的垃圾回收器研究：

系统	回收器	关键创新
HotSpot JVM	G1, ZGC, Shenandoah	代际、低延迟
Go运行时	标记辅助	并发标记
OCaml	次要GC	短暂停
GraalVM	Truffle GC	元循环
Racket	环形GC	增量
Haskell GHC	代际	并行回收

学术/研究GC

Immix (Blackburn et al.) - 高吞吐量
ZGC (Oracle) - 亚毫秒暂停
Shenandoah (Red Hat) - 并发压缩
MMTk (Oxford) - 内存管理工具包

研究前沿

1. 并发GC

目标：通过并发运行减少暂停时间
技术：写屏障、脏位、并发标记
论文：“Garbage Collection in Java 11” (Google I/O)
工具：ZGC, Shenandoah, Go GC

2. 基于区域分配

目标：区域基内存管理
技术：具有不同生命周期的区域
论文：“Memory Management with Regions” (Gay & Aiken)
应用：Rust的区域分配器

3. 函数式语言的GC

目标：对不可变数据高效
技术：代际、增量、持久数据结构
论文：“The Design of Cryptographic Applications”
应用：Haskell, Clojure, OCaml

4. 实时GC

目标：可预测暂停时间
技术：增量、并发、混合
论文：“Real-Time Garbage Collection” (Lieberman & Hewitt)
应用：嵌入式系统、游戏

实现陷阱

陷阱	实际后果	解决方案
缺失根	内存损坏	跟踪所有栈槽、全局
写屏障错误	错误回收	使用固定对象测试
碎片化	内存不足	压缩或复制
固定处理	对象不能移动	特殊处理
终结器	内存泄漏	跟踪终结器队列

“写屏障”问题

并发GC需要写屏障：

// 代际GC的写屏障
void write_barrier(void* obj, void* field, void* new_value) {
    // 如果存储旧->新引用且新在更老代
    if (is_heap_object(new_value) && 
        generation(new_value) < generation(obj)) {
        // 为次要GC记住此存储
        remember_set_add(obj);
    }
    // 执行实际写入
    *field = new_value;
}

“栈扫描”挑战

必须扫描所有线程栈：

void scan_roots() {
    for (Thread* t = all_threads; t != NULL; t = t->next) {
        // 获取栈边界
        void* stack_top = t->stack_top;
        void* stack_bottom = t->stack_bottom;
        
        // 扫描栈寻找指针
        for (void* p = stack_bottom; p < stack_top; p += sizeof(void*)) {
            void* obj = *p;
            if (is_heap_object(obj)) {
                mark(obj);
            }
        }
    }
}

这就是GC暂停时间随栈深度变化的原因！

垃圾回收器实现者Skill garbage-collector-implementer