Doligez-Leroy Concurrent GC — ML 线程运行时里的准实时垃圾回收

待复核

是什么

这篇论文讲的是：怎样让一个带线程的 ML 语言一边运行程序，一边回收垃圾内存，尽量不要让所有线程长时间停住。日常类比：餐厅不能等客人全走光再打扫卫生，而是要服务员边营业边收盘子，只在极短时间提醒客人让一下路。

作者 Damien Doligez 和 Xavier Leroy 在 Concurrent Caml Light 里做了一个 “quasi real-time” 垃圾回收器。它把堆分成两代：年轻代用快速异步 copying collector，老年代用 concurrent marking collector。

关键洞见是 ML 语言能在编译期区分可变对象和不可变对象。这让运行时不必对所有写入都同样紧张，可以把同步成本压到较小范围。

所以它不是单纯”换一个回收算法”，而是把语言特性、编译器信息和运行时协议绑在一起设计。从学习角度看，它适合放在 generational-gc 之后读：先懂”为什么分代”，再看”多线程时如何不暂停太久”。

为什么重要

不理解这篇，很难解释这些问题：

为什么垃圾回收一遇到多线程就变难——线程可能一边跑一边改对象关系。
为什么 “stop-the-world” 会影响交互式程序——暂停越长，用户越能感觉到卡顿。
为什么分代 GC 常和并发 GC 组合出现——年轻对象多、死得快，老对象少但扫描成本高。
为什么语言的类型和可变性信息能帮运行时优化——编译器知道的事，GC 也可以利用。

核心要点

年轻代快速复制：新对象先进入年轻代，收集时把活对象复制出去。类比：桌面上的便签每天清一次，没用的直接扔，有用的归档。
老年代并发标记：老对象不频繁移动，回收器可以和程序线程交替标记可达对象。类比：仓库盘点不关门，只给员工几条规则，保证盘点员不会漏掉刚搬动的箱子。
可变性降低屏障成本：不可变对象创建后不会再改指针，可变对象才需要重点监控。类比：封箱的包裹不用反复检查，只有还在装货的箱子要贴提醒标签。

实践案例

案例 1：为什么普通标记会被线程搞乱

(* 伪代码：线程 A 和 GC 同时看对象图 *)
let a = ref old_obj
let b = new_obj ()
a := b

逐部分解释：a 原来指向老对象，GC 可能已经扫描过它。线程把 a 改成指向新对象后，如果 GC 没有记录这次写入，就可能以为 b 不可达，提前回收。

并发 GC 的核心问题就是这个：程序线程叫 mutator，因为它会修改对象图；GC 线程看到的是一个不断变化的地图。

如果没有额外规则，GC 的判断就像边走边画地图：你刚标过一条路，别人又把路改了，最后很容易漏掉还在使用的对象。这就是写屏障、读屏障和同步点存在的直觉来源。

案例 2：分代为什么有用

young generation:  request objects, tuples, short lists
old generation:    long-lived closures, tables, shared state

逐部分解释：大部分对象很快死亡，所以年轻代可以频繁、小范围回收。活得久的对象晋升到老年代，老年代再用更温和的并发标记处理。

这比每次都扫描整个堆更像”先清桌面，再整理仓库”。桌面清得快，仓库慢慢来，程序的暂停时间就更容易控制。

论文里的 young collector 是 asynchronous copying：它仍然要复制活对象，但目标是让常见的小回收足够快，不把全部线程拖进长暂停。评估这类系统时，最重要的不是平均速度一个数字，而是暂停分布、分配路径成本和最坏情况下是否还能接受。

案例 3：为什么 ML 的不可变对象很香

let pair = (x, y)      (* 不可变 pair *)
let cell = ref x       (* 可变 cell *)
cell := y              (* 只有这里会改变指针关系 *)

逐部分解释：pair 创建后里面的指针不会变，GC 一旦扫描过它，就不用担心它偷偷指向新对象。cell 会被赋值，所以写入时需要屏障或记录。

论文利用的正是这个语言特性：不是所有对象都需要同等代价的并发保护。函数式语言里大量对象不可变，运行时就能省下很多同步成本。

这也是为什么 GC 论文经常要说明语言模型：同样叫”对象”，在不同语言里能不能改、什么时候改、谁能看到改动，都不一样。换句话说，GC 从来不是孤立模块，它吃的是语言语义给它留下的信息。

踩过的坑

以为并发 GC 等于没有暂停：仍然需要短暂停顿做同步、切换和某些根扫描，只是目标是把暂停压短。
只看算法不看语言：这套设计依赖 ML 的可变/不可变区分，搬到任意语言都要重新评估写屏障成本。
把 young 和 old 当物理年龄：分代里的”年轻”指分配历史和存活概率，不是业务对象的新旧。
忽略 mutator 协作：并发收集不是 GC 单方面努力，程序线程必须遵守写屏障、分配协议和同步点。

适用 vs 不适用

适用：

函数式或偏不可变语言的运行时，例如 ML、OCaml、某些托管语言实现。
需要降低交互延迟，而不是只追求最高吞吐的程序。
多线程共享堆、对象生命周期差异明显的运行时。
想理解现代 concurrent/generational GC 的早期工程原型。

不适用：

手动内存管理的 C/C++ 程序，问题模型完全不同。
对象大量原地修改、写屏障成本极高的语言实现。
极小嵌入式运行时，连并发线程和完整堆管理都没有。
只关心批处理吞吐、不在乎暂停时间的场景。

历史小故事（可跳过）

1978 年，Dijkstra 等人提出 on-the-fly garbage collection，奠定并发标记的经典问题。
1980s 到 1990s，ML、Lisp、Smalltalk 等托管语言开始认真面对交互式程序的暂停问题。
1993 年，Doligez 和 Leroy 在 POPL 发表这篇论文，把分代和并发思路放进 Concurrent Caml Light。
1990s 后期到 2000s，Java、OCaml、Go 等运行时继续发展分代、增量、并发和低延迟 GC。
今天看这篇，它像一张老照片：现代 GC 的很多关键词已经出现，但工程约束还非常清晰。

学到什么

GC 是协作协议：并发回收不是后台线程偷偷干活，而是 mutator 和 collector 遵守同一套对象图规则。
语言设计影响运行时：不可变对象越多，GC 越容易减少屏障和同步成本。
分代是经验假设工程化：多数对象很快死亡，这条经验能直接换来更短的常见暂停。
准实时不是实时：quasi real-time 强调暂停短、可接受，不等于硬实时系统那种严格 deadline。
老论文仍然有工程味：它没有只讲漂亮不变量，而是一直在权衡复制成本、屏障成本、暂停时间和实现复杂度。
读 GC 要读约束：对象模型、线程模型和硬件成本，往往比算法名字更决定最终设计。

关联

generational-gc —— 这篇直接把分代思路用于 Concurrent Caml Light。
ocaml —— Concurrent Caml Light 是 OCaml 生态早期运行时探索的一部分。
standard-ml —— ML 家族的类型和不可变性传统，是这篇能成立的语言背景。
dijkstra-on-the-fly-gc —— 并发标记必须解决 mutator 和 collector 同时工作的正确性问题。
immix-mark-region —— 另一种把标记和局部整理组合起来的 GC 设计。
go-gc —— 现代工业并发 GC，可以对照看暂停时间目标如何演进。

反向链接

（暂无反向链接）