cora 实现分代垃圾回收

最近的一次提交，我把 cora 的分代垃圾回收实现了。现在的 cora 垃圾回收是一个分代+增量，不并行的垃圾回收。当前的代码量不到 1000 行，如果不是为了支持大对象，代码行数还可以砍掉 2-300 行，自我感觉是挺极致了。主要得益于用了很巧妙的对象版本设计才让实现这么精炼。

基础部分

先说一说在此之前 cora 的垃圾回收是个什么样子的。它是一个 mark non-sweep 的，non-moving 的增量垃圾回收。增量 GC 这个比较偏离主题，这里就不介绍了，有兴趣可以去读之前的博客。

每个对象都会有一个版本，而 GC 每运行一次，版本会加加，也就是说，每次分配出来的对象，它的版本都是当前时刻垃圾回收的版本号。然后在垃圾回收的 mark 阶段，对于活跃的对象，将它的版本加加，而不活跃的对象不去管它，所以它的版本就是之前时刻的版本。

sweep 过程则是不需要的，因为做完 mark 之后，整个进程的堆上面，全部活跃的对象版本都加加到了当前的 GC 的版本，而非活跃对象是可以直接作为 freelist 的。分配的时候直接去找一个版本小于当前版本的对象就可以了。

为什么 mark non-sweep 很重要呢？因为 mark 阶段的复杂度是 O(n) 其中 n 是活跃对象数量，而如果做 sweep 的话，其复杂度是 O(m) 其中 m 就是整体堆空间的大小，比如说有 10G 空间，只有 1000 个活跃对象，那么明显 O(m) 代价是远高于 O(n) 的。 所以 mark non-sweep 算法复杂度是只跟活跃对象数相关，而 mark sweep 是同时跟活跃对象数和非活跃对象数相关。

以上就是基础部分，通过对象的版本加加，来区分活跃对象和非活跃对象，节省了 sweep 操作。

它不是黑白灰那种三色标记，不过本质上也是等价的。这里面有一些小细节，GC 的版本推进其实是每次 +2 的而不是 +1，对象版本会在进队列时 +1，相当于从白色变成灰色，出队列时版本再 +1，相当于灰色变到黑色。队列就是垃圾回收的待处理队列，当对象属于活跃对象，它被处理了，但是它的孩子节点还没被处理完，它就是进队列的，也就是灰色，对应版本+1。而当它的孩子节点处理完了，也就是当它的孩子节点都进队列了，它自己就可以出队列了，对应于黑色，版本+2。

关于分代垃圾回收

分代垃圾回收的观察是基于，大量临时对象的生命期都很短，而部分永久对象的生命期则很长。通过把对象分代，新生代的 GC 只扫描新生代的对象而不是全部的堆空间，降低扫描的代价。

分代的极致其实是 G1，即不分代。我们换一个角度来思考，同样扫描一块内在区域，垃圾回收是希望只花了最少的代价(只扫描了极少量的活跃对象)，释放出来了最多的空间，还是希望花了很大的代价，却没释放出多少空间呢？当然是希望是前者，效率是最高的。这也是 G1 的思想，garbage first，就是把内存分在不同的块，最先处理掉性价比最高的块，用最小的代价释放出最多的空间。

新生代的对象的生命期规律，活跃对象数量更少，更符合 G1 的思想: 只花少量扫描代价，就可以释放出最多的空间，所以做 minor GC 的性价比很高。而 major GC 的性价比则低一些。

尽管理论上很美好，在实践上，传统的分代垃圾回收往往做得很复杂，它往往是物理分代的，即新生代和老生代在不同的物理区域，然后几轮 gc 之后存活的对象需要从新生代挪到老生代区域去。另外，对不同的代，还会使用不同的垃圾回收策略，比如说对新生代使用 copying gc，而对老生代则用 mark sweep，或者 mark compact。你看，是不是把复杂度叠满了？要涉及到好几种不同的垃圾回收算法都要实现一遍，涉及到对象 moving，复杂度是万恶之源呀。所以如果没有很方便的实现方案，我本能上是非常抗拒做分代的。

cora 中基于对象版本的实现

直到我想到了逻辑分代而不是物理分代，而且它特别适合 cora 当前的实现。对象带了不同的 version，在逻辑上其实就可以划分不同的 generation。

我们想要的是分代带来的好处，而不用纠结其细节，不需要物理上新生代和老生代在不同的内存块。那么，其实很简单，就是扫描一轮，某个对象版本加加，它活下来了，再扫下一轮，它的版本加加，又活下来了，我们是不是可以跳几个版本？不要再版本加加了，直接版本 +N。 也就是说，对于"老生代"对象，我们是降低了它的扫描频率的，因为扫描了又不能回收，就是在浪费机器资源。我们让新生代对象的被扫描频率较高，老生代对象的被扫描频繁较低，也是变相实现了 G1 的思想。

这相对于现有的代码实现，其实改动量非常小。就是把 version+1 改成了 version +N。+N 就相当于从新生代挪到了老生代，至少在接下来的N轮 minor gc 里面是不会再关注该对象了。

具体来说，假设我们每个对象都有一个 uint64 的 version 字段，和一个 uint8 的 generation，每一轮 GC 后存活的对象，让它的 generation+1，取决于分多少代，这个值有上限，过去的研究表明分太多代也没用。然后 version 那边，它不再是 +1 而是 +N，generation 越大，则 N 越大。

防版本值越界回绕

如果用 uint64 表示version，是不需要担心 version 加加到溢出的，哪怕 1s 执行一次 GC，让版本加加，uint64 对应的有5800多亿年。不过问题是每个对象都 uint64 的 version 内存浪费比较大，所以我想优化一下，比如 version + generation 打包到一起占一个 uint8 空间。 具体来讲，用 2bits 给 generation 使用，6bits 给 version 使用，那么这时就需要考虑防回绕了。

6位的 version 多最取值范围是 0 到 64，版本不停地往前在走，63 之后它就绕回到 0 了。在有回绕的情况下，假设当前版本是 10，我没法判断 58 是小于它的，还是大于它的。因为它有可能是活跃老对象，从 10 经过 +N 直接加到了 58，也有可能是 stale 对象，版本从 58 到 63 到 10，而该对象还没被清理掉。

这里采取的做法是，每隔 30 轮 GC，将 stale 版本耗尽一次。可以理解成每隔 30 轮的 mark 之后，做一轮 sweep。因为只做 mark non-sweep 会让系统中存在落后当前版本许多的对象，这些对象实际上是垃圾，它的版本已经远远落后了，而做一轮 sweep 可以将这类的对象全部消除掉，比如将对象的类型变成 unused，这样它的版本就不需要关心了。有了这个操作之后，我们可以保证系统中，不存在比自己版本小 30 以上的对象。如果有，那一定是比它大而不是比它小的。

有了这个保证之后，我们把版本分 0-31 和 32-63 两个区间来看，当前版本是 0-31 区间时，比如说当前值是 10, 往前数 30 个以内，一定是比它小的，往后数 30 个以内，一定是比它大的。于是我们可以判断 58 是往前数 30 个以内，于是 58 是小于 10 的。同样我们换一个 32-63 区间的值，以 58 为例吧，往前数 30 个以内，一定是比它小的，而往后数 30 个以内，一定是比它大的。所以 10 是大于 58 的。

然后 version +N 的 N，上限也需要限制到 30，这样加完之后不会越界到无法对比版本。

write barrier

增量的垃圾回收需要引入 write barrier，而分代的垃圾回收也得引入 barrier。具体来讲就是老生代对象，引入新生代对象的时候，需要特殊处理。

因为，如果有一个新生代对象 a，它是被一个老生代对象引用了，那它其实是活跃对象，不应该被 GC。但是我们在做 minor gc 的时候，只扫描新生代区域不扫描老生代，而对象 a 只被老生代引用，而没被新生代引用的话，就会出现将它判定为垃圾并清理掉的问题。

传统的处理方式就是加 barrier 来捕获发生老生代引用新生代的情况，然后进行特殊处理。比如说可以维护一个 remember set，把 barrier 捕获到的老生代到新生代的对象都记录到 remember set 里面，每一轮做完 minor gc 的时候都去处理 remember set 从而让对象不被误杀。

如果不维护 remember set，也有另外比较简单的模式是，一旦发生老生代引用新生代对象，直接将新生代对象移动到老生代对象去。这样也可以避免误删活跃对象的，当然，仍然需要 barrior 来捕获到老生代对新生代的引用。

放到 cora 的具体例子里面，老生代对象引用新生代对象，就是版本比较大的对象引用到了版本号比较小的对象，这种情况是需要避免的。比如说当前的版本是 10，然后有一个版本 20 的对象，它引用了一个版本 10 的对象，当我们做 GC 的时候，这一轮 GC 只会顺着对象树型结构做 mark，当它 mark 到这个版本 20 的对象时，会跳过它，因为当前版本 10 我们不会处理版本号更高的对象，只有到当前 GC 版本走到 20 的时候才会处理。注意，由于跳过了 20 的这个对象，它的孩子也一样被跳过了！也就是引用的版本 10 的对象被跳过了。20->10 其实这个对象属于活跃对象，却被误清理掉了，就是 bug。

我们只需要保证，没有 20->10 这种情况出现。如果发现了版本号高的对象，引用了版本号低的对象，就将版本号低的对象的版本，加到跟高版本一样，这就是 barrier。

cora 是一个非常函数式的语言，带副作用的操作很少，所以基本上就是只有 vector-set 这个操作需要加上 barrier。还有另外一处需要 barrier 的地方是，垃圾回收标记的时候，如果我们将一个对象的 version +N，那么一定注意是要将该对象的孩子节点整颗树都 +N，否则就可能出现它 +N 而孩子加的小于 N，于是出现版本号较大的对象，引入到版本号较小的对象，也就是老生代引用新生代的问题。

以上就是全部内容了，防回绕和 write barrier 相对复杂一点，但是如果理解分代GC的话，原理上也不太复杂。最重要的是，这里巧妙地用了对象版本，进行逻辑分代而不是物理分代，代码的实现其实是非常简单的。说白了就是把 version +1 变成 version +N 这么小小的改动。

具体效果方面还没有去测试，如果严谨的工作，是需要去前后对比的。因为分代毕竟是引入了复杂度，而带来的好处其实不一定，最近 Andy Wingo 就对他做的分代的实验结果比较困惑，至少这里是需要去 tuning，那都是后面的工作了。