评价 GC 算法好坏的几个标准

大学时候读《松本行弘的程序世界》的时候，粗略的了解了一下垃圾回收算法，写过一篇 介绍三种最基本的垃圾回收算法的文章 。最近在看《垃圾回收的算法与实现》，接触到了这些垃圾回收算法的实现细节。粗略了解的话，基本的原理就是之前这篇博客介绍的内容，这样说出来很简单，也容易理解。但是实现起来就有很多细节了，首先要用到很多指针，所有的对象和引用的基础都是指针。然后会用到链表来保存一些可用内存，用堆来分配对象等。

其实在学校的时候学了很多数据结构，工作了发现一只在 CURD，但是研究 GC 这个话题会用上那些复杂的数据结构和算法，优化的空间也很大，非常有意思。

从这些算法细节也可以看出这些不同的算法其实都有一些强大的地方和弱点。好在评价一个垃圾回收算法的好坏有比较明确的标准，这篇文章就参考《垃圾回收的算法与实现》这本书谈一下评价标准。

吞吐量

垃圾回收算法（6 个字太长了，以下简称 GC）算是对程序完成它想做的事情的一种辅助，并不是程序的主要目的（废话）。所以 GC 占用的时间越少越好，程序花在正事上面的时间越多越好。

这个标准严格定义应该是 需要处理的堆大小 ÷ GC 占用时间。书中称为“吞吐量”。

这个指标其实很好理解。举个例子吧，标记清除算法要遍历两次，第一次遍历所有活跃的对象，将它们标记为“不是垃圾”。第二次遍历所有的对象，将没有被标记的垃圾回收掉。复制收集算法只需要遍历一次，将活跃的对象从内存的一般复制到另一半。所以从这个指标的角度讲，复制收集算法完爆标记清除。

但实际上，这个指标是不能“静态衡量”的。依然是上面两种算法，标记清除遍历的时候速度很快，只要写一个标记就可以了。而复制收集算法要有 copy 操作。虽然堆中活动对象的增加，甚至会出现复制收集吞吐量小于标记清除的情况。

内存使用率

这个指标也比较好理解，GC 算法需要一些标记，但是如果算法本身所使用的内存占得很多，就得不偿失了。这个算法本身的目的就是回收内存，本身却占用了很多内存，听起来就不合理。

其实，从算法的角度讲，内存是空间，吞吐量是时间。算法上有“用空间换时间”的策略，自然 GC 也会有。这是一种 Trade off，很多情况不可兼得。

拿引用计数来说，用几个位来表示引用计数是门学问。简单的话，占用 8 个位表示，那每个对象 1byte 就没有了。假设是占用 2 个字节的对象，那么内存占用就扩大了整整 1.5 倍。 而大多数对象仅仅会被引用 1 次而已。所以引用计数方法就发展出一些优化措施，减少引用计数占用的内存，配合其他算法来处理计数器溢出的问题。有一种极端的方式是只使用 1 位来计数（倒不如说这是一种标记了）。叫做 1位引用计数。具体的原理，这篇文章就不展开说了。

复制清除算法每次只能使用一半的空间，所以这个算法的内存使用率也是很低的。

最大暂停时间

这个指标和“吞吐量”看起来有些像，GC 算法速度越快，时间就越小。但是吞吐量指的是总体的速度，最大暂停时间指的是 GC 算法执行的时候，程序在等待 GC 完成的最大时间。这段时间由于 GC 的运行程序无法做其他的事情。

为什么这个指标会重要呢？有些程序可能可以忍受吞吐量不高，但是实时性要求很强的。比如说，A 算法每分钟暂停 1 次，一次暂停 1 秒，一小时一共暂停 60s。另一个 B 算法每小时暂停 1 次，一次暂停 30s。可想而知，如果是用户程序暂停时间长是体验很糟糕的，另外比如机器人控制程序，迈开一只腿这时候到了暂停时间，机器人就摔倒了。

引用计数的最大暂停时间是最好的，因为对象的引用到 0 的时候立即会回收，这个过程不需要暂停程序。而复制算法和标记清除算法需要在无法申请出更多内存的时候，暂停程序，开始清除阶段/复制阶段。

连续性（缓存友好程度）

我们知道，越快的存储价格就越高。CPU 寄存器速度最快，但是只有几个寄存器。高速缓存非常快，但是极其昂贵。然后是内存、硬盘等。

如果程序在执行的时候缓存命中率高，那么运行效率就会高。

在这篇文章中，我们可以将程序粗略的分成两部分：GC 运行的部分和程序运行的部分。如果 GC 运行的时候需要频繁寻找对象，然后对象的引用又在很远的地方，那么缓存命中率就会很低；另一方面说，如果 GC 算法将程序的对象变得很离散，那么程序在运行的时候，互相引用的对象离得很远，效率就会很低。

标记清除算法会造成内存的碎片，对缓存不友好。复制收集算法由于是拷贝不是垃圾的对象，所以在一次拷贝操作之后，垃圾对象被释放，非垃圾对象都在一起了，所以命中率会高。另外上面提到的 1 位引用计数算法由于只拷贝指针，而不需要去找到对象，所以缓存命令率也会高。

是否写入操作（copy-on-write 友好程度）

Copy-on-write 在现代计算机技术中是比较常用的。简单来说，如果你 fork 出 4 个进程，而这 4 个进程都只是在读同一片内存，系统将会将这一片内存共享给 4 个进程，如果有其中一个进程想要写入的时候，系统才会复制出来这部分内存给这个进程写入。

这里特别要“批评”的是引用计数，因为引用计数的原理是每一个对象记住有多少个对象指向了自己。这就意味着，即使我们没有更改这个对象，只是读（应用）了这个对象，相关的内存就有了写入操作，这部分内存就会被复制。

2017 年 Instagram 发表的这篇 关闭 Python 的 GC 来提高性能 的文章，原理就是这样。

以上内容现学现卖，如有错误欢迎指出。