一个语言的诞生（Act III）

第三幕 垃圾回收

看过微软 .net coreclr 的源代码后，觉得 Lua、PHP 和 Python 的垃圾回收代码与之相比简直就是个玩具。而 Hotspot JVM 的垃圾回收算法更加复杂。

常见的垃圾回收技术能大致分成：引用计数、标记清理、标记缩并和节点复制几种。高级的技术有垃圾分代收集、渐进及并发收集、分布式垃圾收集。复杂的垃圾回收算法会根据对象的性质和内存的使用情况来选择不同的垃圾回收算法。

引用计数

PHP、Python、Objective-C 以及一些 Lisp 实现都使用了该算法。引用计数算法的特点是简单、无卡顿；缺点是存在循环引用垃圾无法回收。

算法原理很简单：为每个对象保存一个引用计数器。当对象被引用时，计数器加一；当对象被解除引用时，计数器减一。当计数器归零时，即对该对象进行回收。

引用计数算法之所以无卡顿并不是因为它的算法高效，而是因为它将回收的运算成本分摊到平时的运行中去了。另外，如果要支持多线程，则要使用原子操作来访问计数器，这样会使得性能变得很差。

标记清理

Lua 使用的就是最典型的标记清理算法：将所有的对象使用链表连接起来。当启动回收算法时，从Root 对象出发，遍历所有被引用的对象并做上标记。通过链表再次遍历所有对象并检查标记位，回收那些没有被做上标记的对象。

标记缩并

该算法的对象是连续存放的，所以内存分配操作非常高效，适用于生命周期短、频繁创建的小对象。为保持对象紧密排列，垃圾回收后，所有存活的对象会向前移动，挤走已回收对象的空闲空间，这就是“缩并”的由来。这会导致对象的地址发生改变，所以必须重写所有指向对象的指针。

节点复制

该算法的对象也是连续存放的。在垃圾回收时将被引用的对象复制到新的内存区域，回收操作结束后将旧的区域的对象统统清理掉。缺点是需要两倍的内存空间。

对象分代

对象分代原理基于哥白尼原则：从统计角度而言，一个事物已经持续的时间越长，我们的观察点距离寿命终结点的绝对时间就越长，也就是说：持续时间越长的事物，就越有可能持续更长的时间。对于垃圾回收而言，对象在第一次GC的时候没有被回收，那么他可能会拥有更长的生命周期。那么下一次GC的时候就可以不用去管它了。直到内存耗尽来一次FullGC。

除此之外，还有并发式回收和分布式回收等等。暂且不谈。

从对象分配性能角度考虑，节点复制和标记缩并是最快的，因为对象分布是连续的，分配内存只是更改一下某个指针的指向而已。缺点是如果分配的大对象，当回收时移动会花上些时间。所以 CLR 的处理方式是：小对象（小于 8500 字节）分配在 SOH（Small Object Heap） 上，该堆是通过标记缩并算法来管理的；大对象（大于 8500 字节）分配在 LOH（Large Object Heap） 上，该堆是通过标记清理算法来管理的，通过 Free List 链表来分配内存。

CLR 会申请一大块连续内存作为 SOH 的空间，当 SOH 内存耗尽会触发 GC，如果 GC 后还是没有空闲的内存，则触发 OutOfMemoryException 异常。在 Windows 下可以通过 VirtualAlloc 来申请一块保留内存，保留内存并不实际占用物理内存，只是“占位”而已。SOH 中的内存块是按需“提交”的，每次 GC 后还会“归还”多余的内存。在 Linux 下可以使用 mmap 来实现类似操作。

如果要将语言设计成嵌入式的话，CLR 的内存管理策略显然不合适。一次性性申请一大块保留内存可能会让宿主程序无内存可用。所以需要将 SOH 设计成分页形式。这样虽然会提高 GC 算法的复杂度，但实际性能损失应该不大。

大对象的话还是按照普通的 Free List 链表的方式来分配内存，可以使用系统的 malloc 或者自己实现一个堆管理器。