关于垃圾回收

前言

垃圾回收（Garbage Collection，以下简称 GC），就是释放不用的内存，目的是防止内存泄漏。C/C++ 等较底层的语言需要在分配内存后手动释放内存，而 Java、JavaScript 等语言则可以在运行时根据需要自动释放内存，这是因为在这些语言的运行环境（如：JVM、V8 等）中有 GC 在悄悄做着一些“杂活”。

本文对网络上 GC 相关知识进行梳理，结合自己的理解，对引用计数法、标记清除法、标记整理法、标记复制法的基本机制进行概述。

引用计数法

引用计数法（Reference Counting）于 1960 年由 George E. Collins 提出，其核心思想是为每一个节点分配一个引用计数器，表示指向该节点的指针个数。节点被创建时计数器为 1，之后如果有新的节点指向该节点，则计数器加 1，反之减 1。当计数器归 0 则代表没有指针指向该节点，意味着该节点所占有的内存可以释放。

应用：

• IE 中部分对象并不是原生的 JavaScript 对象（如：BOM 和 DOM），而是使用 C++ 以 COM（组件对象模型）的形式实现的，COM 的 GC 机制就是引用计数法
• C++11 引入的智能指针概念采用了引用计数法的思想

优点：

• 当计数器归 0，即可立即回收内存资源，回收内存所需的最大停顿时间短
• 不需要从根节点遍历堆寻找垃圾

缺点：

• 每次指针更新都将导致计数器的频繁处理
• 计数器也会占用较多内存
• 对于互相引用的节点，无法判定为垃圾，从而会导致内存泄漏

由于引用计数法具有无法回收循环引用节点的问题，现已被废弃。

标记清除法

标记清除法（Mark-Sweep）于 1960 年由 John McCarthy 提出，其主要分为两个步骤：标记、清除。标记，即对所有的 GC Roots 依次遍历其后节点，所有可达的节点即为存活节点，不可达节点视为垃圾，以此规则标记出全部垃圾节点。清除，即遍历并回收所有垃圾节点的内存。

标记清除法不存在引用计数法无法回收循环引用节点的问题，并且实现简单，因此 Go V1.3 及其之前的版本使用的就是这种方法。然而标记清除法还存在以下几个问题：

• 容易导致内存碎片化，需要针对碎片的空闲内存维护一张空闲内存列表，降低了内存分配和回收的效率
• 内存碎片化在极端情况下会导致无法分配连续的存储空间，如：数组
• GC 执行期间，需要将应用逻辑暂停，即全停顿（Stop-The-World），而标记清除法的时间开销与节点数量正相关。即使在全部节点都为垃圾节点的极端情况下，标记清除法仍需遍历全部节点以释放内存，违反了“尽量减少 Stop-The-World 时间”的原则

标记整理法

标记整理法（Mark-Compact）主要解决了标记清除法多次进行 GC 操作后内存碎片化问题。其在标记清除法的标记步骤后，针对存活节点进行整理操作，即：将所有存活节点向一端移动，然后直接清空边界以外的内存。

标记整理法是对标记清除法的改进。其最关键的整理过程将原本碎片化的内存整合成了一整块内存，增加了程序吞吐量，也优化了内存分配效率。

在时间开销方面，存活节点移动的过程中会覆盖掉部分垃圾节点，并且直接清空整块内存的效率比按地址依次清空多块内存的效率高，但存活节点的移动会产生大量时间开销，且因为所有对存活节点有依赖的指针都需要在存活节点移动后更新地址信息，作为移动式回收算法的标记整理法要比作为非移动式回收算法的标记清除法有着更多的时间开销。

标记复制法

标记复制法（Mark-Copy）在另一种思路上对标记清除法进行改进，其将内存按容量平分成两块，每次只在其中一块上分配内存。当使用的这块内存无法满足分配需求时，遍历全部存活节点并按序整齐排列到另一块内存中，随后将之前的内存整块清除。

相较于标记整理法向一端依次移动节点的整理方式，标记复制法通过“左右手互相腾挪”的方式巧妙解决了标记清除法内存碎片化的问题。

在时间开销方面，由于复制过程中只关注存活节点，其时间开销只与存活节点的数量正相关，因此相比较标记清除法和标记整理法有着更少的时间开销，而代价是造成了一半的内存浪费，这是一种“以空间换时间”的方法。

总结

以上介绍了四种常见 GC 方法的主要流程，其中引用计数法由于自身的缺陷已被废弃。标记清除法不存在引用计数法的问题，却会导致内存碎片化。标记整理法解决了内存碎片化的问题，但节点的遍历和移动成本较高。标记复制法同样解决了内存碎片化的问题，并且相较于标记整理法时间开销更少，但其设计直接导致了一半内存的浪费。

不难看出，除开引用计数法，标记清除法、标记整理法和标记复制法都存在着不同方面的问题，因此需要根据具体使用需求来决定 GC 的具体实现方式。比如，在更关注停顿时长的场景下选择标记清除法，在更关注程序吞吐量的情况下选择标记整理法，又或者在通常情况下使用标记清除法，而在内存碎片化严重时使用标记整理法重新整理一遍内存。

当然，实际的 GC 实现往往更加复杂，不同程序语言的 GC 实现通常会根据不同的需求采用多种优化后的算法进行组合。

拓展：V8 GC 的实现概述

上面介绍了引用计数法、标记清除法、标记整理法、标记复制法的基本机制。我们也了解到真实的 GC 通常根据需求由多种算法组合实现。下面我们将简单了解 V8 所采用的 GC 机制来对不同 GC 的特性做一个整体的把握。

在此之前，我们先了解一下 V8 的内存分区结构。一个正在运行的程序存储在 V8 分配的内存中，这段内存被称为驻留集（Resident Set）。驻留集内部进一步被划分为如下几个部分：

Resident set
	|- Heap memory
		|- New space（Young generation）
			|- Semi space
			|- Semi space
		|- Old space（Old generation）
			|- Old pointer space
			|- Old data space
		|- Large object space
		|- Code space
		|- Cell space
		|- Property cell space
		|- Map space
	|- Stack

首先，驻留集被分为堆和栈两个部分。其中栈存储方法中的局部变量等函数上下文信息，包括参数与返回值。栈的分配与收回在程序运行时由系统控制，在此不作讨论。堆存储对象和动态数据，所以这也是程序的内存区域中最大的空间，本文讨论的 GC 也发生在这里。

堆内部又被进一步划分为：

• New space（Young generation）：新生代区域，空间较小，存储的数据生命周期短，内部又被划分为两个容量相等的空间 Semi space
• Old space（Old generation）：老生代区域，空间大，可增量，存储的数据生命周期长
  • Old pointer space：存储引用其他对象的老生代
  • Old data space：存储不引用其他对象的老生代
• Large object space：存储超过一定大小的对象，默认为 256KB
• Code space：存储来自即时编译器（JIT）的已编译代码
• Cell space：存储小而大小固定的对象，如 Number 和 Boolean
• Property cell space：存储特殊的对象，如访问器和一些内部对象
• Map space：存储对象的元信息和其他内部数据结构，如 Map 和 Set

其中 GC 作用的只有 New space 和 Old space 两个区域（以下简称“新生代”和“老生代”）。

为什么有新生代和老生代两个区域？因为 V8 的 GC 采用了分代策略。

什么是分代策略？

首先一切基于一个既定结论：不同的对象的生命周期是不一样的。

同时与既定结论并存的还有两个分代假说：

• 弱分代假说：绝大多数对象都是朝生夕灭的
• 强分代假说：熬过越多次 GC 过程的对象就越难以消亡

以分代假说为依据，绝大多数新分配内存的对象在第一次 GC 过程中就会消亡（IBM的专项研究表明，消亡对象的占比大约为整体的 98%），这意味着可以将这些对象集中管理，每次 GC 只关注于保留少量的存活对象，这样就能以较低的代价回收大量的内存。而经历过多次 GC 过程的对象则更加稳定，存活率更高，因此也将这些对象集中管理，就可以以较低的频率执行 GC 操作。

按照以上思路，将内存分为新生代和老生代，新分配内存的对象都进入新生代，只有经历过一定次数 GC 过程的对象才会进入老生代。根据新生代和老生代的特点，分别使用合适的 GC 方式进行内存管理，就可以同时兼顾 GC 的时间开销和空间利用。

回到 V8 的设计。新生代的存活对象少，因此只需要分配较小的内存就能应付存储需求，但新分配内存的对象都会先进入新生代，新生代很快会变满，所以需要频繁进行 GC 回收大占比的垃圾对象。老生代较新生代更加稳定，存活对象多且较难回收，因此需要分配较大的内存。

在 v12 以后，新生代中一个 Semi space 的大小在 64 位和 32 位系统中分别为 16MB 和 8MB，即新生代的大小分别为 32MB 和 16MB，可以通过 --max-semi-space-size 配置。老生代的大小默认不做限制，会根据可用内存进行分配，可以通过 --max-old-space-size 配置。

注：分配的内存大小并非越大越好，大的内存分配意味着 GC 的扫描时间变长，除了针对具体业务场景进行优化（如：大文件上传、项目打包等），大部分情况下无需进行修改。

不难看出：

标记复制法的时间开销只与存活对象的数量正相关，而与整体对象数量无关，因此即使需要频繁的在新生代进行 GC 操作，使用标记复制法的效率仍然是可观的。标记复制法的缺点在于浪费了一半的内存，但新生代本身分配的内存就较小，这就极大的降低了标记复制法的浪费程度。所以新生代使用标记复制法进行 GC 是合适的。

而标记复制法用于老生代的 GC 则不合适。一是因为老生代内存较大，使用标记复制法内存浪费较多；二是因为老生代存活对象多，使用标记复制法所带来的性能优势有限。所以老生代使用标记清除法和标记整理法进行 GC 更加合适，不过这里具体使用的经过优化后的方法。

老生代的 GC 方法：

首先，老生代采用标记清除法和标记整理法相结合的方法，即当标记清除法造成的内存碎片化到达一定程度时，才会进行一次标记整理，整理碎片的同时回收一部分内存。这种结合将标记整理法移动对象的时间开销降到最少，也兼顾了标记清除法会使内存变得碎片化的问题。

然而标记清除法和标记整理法都是一种全停顿的回收方法（Stop-The-World GC），对于拥有较大内存的老生代来说，GC 过程会带来较大时长的停顿。为了使 GC 过程不会对程序的执行造成明显的影响，V8 通过增量标记和三色标记法对标记过程进行了优化。

增量标记是将原本一次性标记完全部垃圾对象的过程进行拆分，拆分的多个小过程与应用逻辑交叉执行，这样每个小过程的带来的停顿就感受不到了。三色标记法是对增量标记的实现，其将对象进行黑白灰的三色区分。如白代表初始状态，灰代表经过遍历但其直接引用对象尚未被遍历的状态，黑代表已遍历的状态。步骤如下：

• 初始，全部对象染白，以 GC Root 为根进行一层广度优先遍历，遍历到的对象染灰
• 下一过程，以灰色对象为根，依次进行一层广度优先遍历，遍历到的对象染灰
• 将上一轮灰色的对象染黑，跳至第二步

当过程全部结束，所有白色的对象就是被标记出的垃圾对象了。在标记完垃圾对象后，并不会立刻进行清理操作，GC 会优先将资源让给应用逻辑执行。只有在需要的时候 GC 才会按需清理内存，即所谓的懒清理（Lazy sweeping）。

此外在 2018 之后，GC 又引入了并发标记与并行标记两种优化技术，本文在此不多赘述。

综上所述，V8 使用标记复制法作为新生代的 GC 方法，使用优化后的标记清除法和标记整理法相结合的方法作为老生代的 GC 方法。前者被称为 Minor GC，后者被称为 Major GC。一个新分配内存的对象被放入新生代，随着新生代变满，触发 Minor GC，该对象如果存活，则被放入新生代中的另一个 Semi space，否则释放资源。而当一个对象经历了两次 Minor GC 仍然存活，就会被转移到老生代。

Minor GC 虽然经常被触发，但由于空间小并且使用了标记复制法，加之并行的辅助线程，所以速度很快。Major GC 管理的是经过 Minor GC 过滤后的老生代对象，其数量增长较新生代对象慢，因此 GC 频率要低很多，再加之使用优化后的混合式 GC 方法，效率也十分可观。V8 就是这样利用不同特性，将两个类型、三种不同的算法取长补短，构成一个兼顾时空效率的完成垃圾回收机制的。