Garbage Collection
最近在读松本行弘（Matz）的《代码的未来》，作者是 Ruby 编程语言的发明者。本书作者对许多技术话题都有探讨，观点犀利、内容扎实，他对编程语言的发展趋势做出了自己的预测。虽然本书出版于 2013 年，但其内容却并不过时。
本次分享的内存管理部分的垃圾回收（Garbage Collection，简称 GC）机制。
在 C 和 C++ 中，内存空间是由人手动管理的。当需要内存空间时，要请求操作系统进行分配，不需要的时候要返还给操作系统。 因为“不再需要”而返还给操作系统的内存空间，会被操作系统重新利用，这意味这里面的数据会被改写，如果程序还去访问不再需要的内存空间，就会造成异常甚至崩溃。 而如果认为某些内存空间”可能还要用到“就不还给操作系统，或者用完了忘记还，这些无法访问的空间就会一直保留下来，造成内存浪费，最终引发性能下降和产生抖动。 因此，让人来管理大量分配的内存空间，是非常困难的。
将内存空间的释放实现自动化，就是 GC 。
三种基本方式
术语定义
讲解 GC 技术之前，先定义两个术语。
- 垃圾： 所谓垃圾（Garbage），就是需要回收的对象。如果程序直接或间接地引用一个对象，那么这个对象就被视为“存活”；相反，已经已经不被引用地对象视为“死亡”。将“死亡”对象找出来，然后作为垃圾进行回收，就是 GC 的本质。
- 根： 所谓根（Root），是判断对象是否可被引用地起始点。至于哪里是根，不同的语言和编译器有不同的规定，但基本上是将变量和运行栈空间作为根。
标记清除方式
标记清除（Mark and Sweep）是最早开发出的 GC 算法（1960 年）。 其原理非常简单，首先从根开始将可能被引用的对象用递归的方式进行标记，然后将没有标记到的对象作为垃圾进行回收。
(1) 显示了一些对象的状态，一个对象可以对其他对象引用。 (2) GC 开始，从根开始对被引用的对象打上“标记”。我们涂黑被标记的对象。 (3) 被标记的对象能够引用的对象也打上标记。重复这一步，直到所有可能被间接引用到的对象全部打上标记。至此，成为标记阶段（Mark phase）。 (4) 将全部对象扫描一遍，将没有被标记的对象回收。这一操作被称为清除阶段（Sweep phase）。扫描的同时，还需要将存活对象的标记清除调，以便下次 GC 操作做好准备。
标记清除算法的处理时间，是和存活对象数与对象总数的总和相关的。
还有一种算法叫做标记压实（Mark and Compact），它不是将被标记的对象清除，而是将它们不断压紧凑。
复制收集方式
如果分配了大量对象，而其中只有一小部分存活的情况下，标记清除算法的效率是不高的。
复制收集（Copy and Collection）试图克服这个缺点。这种算法是，将从根开始被引用的对象复制到另外的空间中，然后再将复制的对象所能引用的对象用递归方式复制下去。
(1) GC 开始前的内存状态。 (2) 准备一块“新空间”，将从根被引用的对象复制到新空间中。 (3) 从已经复制的对象开始，再将被引用的对象像糖葫芦一样复制到新空间中，复制完成后， “死亡”对象被留在了就空间中。 (4) 将旧空间废弃，就可以将死亡对象一次全部释放，而没必要再次扫描每个对象。下次 GC 时，现在的新空间就变成将来的旧空间。
复制收集方式不存在全部扫描一遍的开销。 和标记相比，将对象复制一份所需的开销比较大，因此在“存活”对象比例较高的情况下，这样做反而不利。 这种算法的另一个好处是它具有局部性（Locality）。 在复制收集过程中，会按照对象被引用的顺序将对象复制到新空间中。因此关系较近的对象更可能被放在距离较近的内存空间，这成为局部性。局部性高的情况下，内存缓存会更容易有效运作，程序的运行性能也能得到提高。
引用计数方式
引用计数（Reference Count）方式是 GC 算法中最简单也是最容易实现的一种，它和标记清除方式同期发明出来的。 它的原理是，在每个对象中保存该对象的引用计数，当引用发生增减时对计数进行更新。 引用计数的增减，一般发生在变量赋值、对象内容更新、函数结束（局部变量不再被引用）等时间点。当一个对象引用计数变成 0 时，说明它将来不会再被引用，因此可以释放相应的内存空间。
(1) 所有对象中都保存着自己被多少个其他对象进行引用的数量（引用计数）。 (2) 当对象引用发生变化时，引用计数随之改变： - B 到 D 引用失效，D 的引用计数变为 0 被释放。 - D 到 C 和 E 的引用数也相应减少。 - 对象 E 引用计数变为 0 ，也被释放掉。 (3) 引用计数为 0 的对象被释放，“存活”对象会保留下来。整个 GC 过程中，并不需要对所有对象进行扫描。
实现容易是引用计数算法最大的优点。 标记清除和复制收集在实现上都有一定难度。 初次之外，当对象不再被引用的瞬间旧会释放，也是一个优点。其他 GC 机制中，要预测一个对象何时会被释放是很困难的，而引用计数方式中是立即被释放。 由于释放操作是针对每个对象执行的，因此和其他算法相比，由 GC 而产生的中断时间（Pause Time）就比较短。
引用计数方式的缺点
引用计数最大的缺点，就是无法释放循环引用的对象。
图中 A、B、C 三个对象互相之间循环的引用，因此它们的计数永远不会为 0 ，结果就是这些对象永远不会被释放。
第二个缺点，就是必须发生增减时对引用计数做出正确的增减。如果漏掉了某个增减，就会引发很难找到的内存错误。编译器对引用计数进行管理就还好，如果手动管理引用计数，容易产生 bug 。 最后一个缺点，引用计数不适合并行处理。多线程对引用计数增减，很可能产生不一致的问题。为了避免这种情况的发生，对引用计数的操作必须采用独占的方式。如果引用操作频繁发生，每次都要使用加锁等并发控制机制，其开销也不容小觑。
综上，引用计数的原理和实现虽然简单，但是缺点也很多，因此基本上不再使用了。 依然采用引用计数方式的语言主要有 Perl 和 Python ，但是它们为了避免循环引用的问题，都配合使用了其他的 GC 机制。
进一步改良
GC 的基本算法，大体逃不出上述三种方式及它们的衍生品。现在通过对三种方式融合，出现了一些更加高级的方式。下面介绍最有代表性的三种，即分代回收、增量回收和并行回收。
分代回收
分代回收（Generational GC）的目的是在程序运行期间，将 GC 所消耗的时间尽量缩短。
其基本思路，是利用一般程序所具备的性质，即大部分对象都会在短时间内成为垃圾，而经过一定时间仍然存活的对象往往拥有较长的寿命。有了这个前提，怎样让 GC 更高效？如果对象分配不久，诞生时间较短的“年轻”对象进行重点扫描，应该可以更有效地回收大部分垃圾。
分代回收中，对象按照生成时间进行分代，分为新生代（Young generation）和老生代（Old generation）。不同的实现方式可能划分更多的代，我们就限定两代方便讲解。如果上述关于对象寿命的假说成立的话，那么只要扫描新生代对象，就可以回收掉很大一部分对象。
这种只扫描新生代对象的回收操作，称为小回收（Minor GC）。小回收的步骤如下：
- 从根开始一次常规扫描，找到“存活”对象。（这一步采用标记清除或者复制收集算法都可以，但大多数分代回收的实现都采用了复制收集算法。）需要注意的是，扫描过程中，如遇到老生代对象，则不对该对象递归扫描，这样可以大幅减少需要扫描的对象。
- 将第一次扫描的对象划分到老生代。
- 如果用复制收集算法，只要将复制目标空间设置为老生代即可。
- 如果用标记清除算法，大多采用在对象上设置某种标识的方式。
仅上面这两步是不够的，会出现问题，从老生代对象对新生代对象的引用怎么办？如果只扫描新生代区域，那么从老生代对新生代的引用就不会被检测到。这样一来，如果一个“年轻”对象只有来时老生代的引用，就会被误认为已经“死亡”。 因此，在分代回收中，要对对象的更新进行监视，将从老生代对新生代的引用，记录在一个叫做记录集（remembered set）的表中。在执行小回收的过程中，这个记录集也作为一个根来对待。
要让分代回收正确工作，就必须是记录集保持更新。为此，在老生代到新生代引用的瞬间，就必须让改引用被记录，负责执行记录操作的子程序，需要被嵌入到所有涉及对象更新操作的地方。
负责记录引用的子程序这样工作：设有两个对象 A 和 B ，当对 A 的内容进行改写，并加入对 B 的引用时，如果 A 属于老生代，B 属于新生代，则将改引用添加到记录集中。 这种检查程序需要对所有涉及修改对象内容的地方进行保护，因此被称为写屏障（Write barrier）。写屏障不仅用于分代回收，同时也用在许多其他的 GC 算法中。
虽说老生代区域中的对象寿命比较长，但绝不是“不老不死”的。随着程序运行，老生代区域中的“死亡”对象也在不断增加。要回收这部分对象，需要对包括老生代区域在内的全部区域进行一次扫描回收。像这样以全部区域为对象的 GC 操作称为完全回收（Full GC）或者大回收（Major GC）。
分代回收通过减少 GC 中扫描的对象数量，达到缩短 GC 带来的平均中断时间的效果。但由于还是需要进行大回收，因此最大中断时间并没有得到什么改善。 从吞吐量来看，在对象寿命假说能够成立的程序中，由于扫描对象数量的减少，可以达到非常不错的成绩。但是，其性能会被程序行为、分代数量、大回收触发条件等因素大幅左右。
增量回收
有些程序对实时性要求很高，比起缩短 GC 的平均中断时间，往往更重视缩短 GC 的最大中断时间。例如，在机器人姿态控制程序中，如果因为 GC 而让程序中段了 0.1 秒，机器人可能就摔倒了。车辆控制程序因为 GC 而带来延迟的话，后果更不堪设想。
在这些实时性要求很高的程序中，必须能够对 GC 产生的中断时间做出预测。例如，可以将“最多终端 10 毫秒”作为附加条件。 一般的 GC 算法作不出这样的保证，因为 GC 产生的中断时间与对象的数量和状态有关。 因此，为了维持程序的实时性，不等到 GC 全部完成，而是将 GC 操作细分成多个部分逐一执行。这种方式被称作增量回收（Incremental GC）。
在增量回收中，由于 GC 过程是渐进的，回收过程中程序本身会继续执行，对象之间的引用关系也可能发生变化。如果已经完成扫描和标记的对象被修改，对新的对象产生了引用，这个新对象就不会被标记，明明是“存活”的新对象却被回收掉了。 为了避免这样的问题，增量回收也采用了写屏障。当已经被标记的对象的引用关系发生变化时，通过写屏障会将新被引用的对象作为扫描的起始点记录下来。
增量回收的过程是分步渐进式的，可以将中断时间控制在一定长度之内。另一方面，由于中断操作需要消耗一定的时间， GC 消耗的总时间就会相应增加，正所谓有得必有失。
并行回收
多核心 CPU 已经普及。并行回收正是通过最大限度利用多 CPU 的处理能力来进行 GC 操作的一种方式。
并行回收的基本原理是，在原有的程序运行的同时进行 GC 操作，这一点和增量回收相似。不过，相对于在一个 CPU 上进行 GC 任务分割的增量回收来说，并行回收可以利用多 CPU 的性能，尽可能让这些 GC 任务并行进行。 因为软件运行和 GC 操作是同时进行的，也会遇到和增量回收相同的问题。为了解决这个问题，并行回收也需要写屏障来对当前的状态信息保持更新。 不过，让 GC 操作完全并行，而丝毫不影响原有程序的运行，是做不到的。因为在 GC 操作的某些特定阶段，还是需要暂停原有程序的运行。
多核化快速发展，并行回收成了一个重要的话题，它的算法也在不断完善。在硬件系统的支持下，无需中断原有程序的完全并行回收器也呼之欲出。
GC 大统一理论
像标记清除和复制收集这样，从根开始进行扫描以判断对象生死的算法，被称作跟踪回收（Tracing GC）。相对的，引用计数算法则是当对象之间的引用关系发生变化时，通过对引用计数进行更新来判断对象生死。
美国 IBM 公司沃森研究中心的 David F. Bacon 等人，与 2004 年发表了一篇题为 “垃圾回收的统一理论” （A Unified Theory of Garbage Collection）的论文，稳重阐述了一种理论，即： 任何一种 GC 算法，都是跟踪回收和引用计数回收两种思路的组合。对其中一方进行改善的技术中，必然存在对另一方进行改善的技术，而其结果只是两者组合而已。
例如用于改善分代回收和增量回收等跟踪回收算法的写屏障机制，从对引用状态变化进行记录这个角度来看，就是吸收了引用计数回收的思路。相对的，引用计数算法也吸收了分代回收算法的思路而进行了一些改进，如来自局部变量的引用变化不改变引用计数等。
Unified Theory 来源于物理学中的大统一理论 （Grand Unified Theory， 简称 UGT）一词。正如大统一理论试图解释自然界中四种基本作用力，这个理论试图统一解释跟踪回收和引用计数回收的理论，也就命名为 GC 大统一理论。