Chrome V8 javascript engine 的3种垃圾回收算法原创
V8 中的 JavaScript 对象分配在由 V8 的垃圾收集器管理的堆上。 在这篇文章中，我们将介绍并行 Scavenger，这是 Orinoco 的最新功能之一，V8 主要是并发和并行垃圾收集器，并讨论我们在此过程中实现的设计决策和替代方法。
V8 将其托管堆划分为几代，最开始，会在年轻代的“托儿所”中分配对象。 在垃圾回收之后，对象被复制到中间代，中间代仍然是年轻代的一部分。 在经过另一次垃圾回收后，这些对象被移入老年代（参见图 1）。 V8 实现了两种垃圾收集器：一种经常收集年轻代，另一种收集包括年轻代和老年代在内的整个堆。 老年代对年轻代的引用是年轻代垃圾回收的根源。 记录这些引用以在移动对象时提供有效的根标识和引用更新。
图 1：分代垃圾收集
由于年轻代相对较小（在 V8 中高达 16MiB），它很快就会被对象填满，并且需要频繁的收集。 在 M62 之前，V8 使用切尼半空间(Cheney semispace)复制垃圾收集器（见下文），将年轻代分为两半。 在 JavaScript 执行期间，只有一半的年轻代可用于分配对象，而另一半保持为空。 在年轻垃圾回收期间，活动对象从一半复制到另一半，动态压缩内存。 已经被复制一次的活动对象被认为是中间代的一部分，并被提升到老一代。
从 v6.2 开始，V8 将用于收集年轻代的默认算法切换为并行 Scavenger，类似于 Halstead 的半空间复制收集器，不同之处在于 V8 使用跨多个线程的动态而不是静态工作窃取。 下面我们解释3种算法：
- V8 年轻代切尼半空间复制垃圾回收算法
- V8 年轻代并行 Mark-Evacuate 垃圾回收算法
- V8 年轻代并行 Scavenger 垃圾回收算法
V8 年轻代切尼半空间复制垃圾回收算法
在 v6.2 之前，V8 使用切尼的半空间复制算法，该算法非常适合单核执行和分代方案。 在年轻代收集之前，内存的两个半空间半部分都被提交并分配了适当的标签：包含当前对象集的页面称为 from-space，而对象复制到的页面称为 to-space。
Scavenger 将调用堆栈中的引用以及从旧代到年轻代的引用视为根。 图 2 说明了最初 Scavenger 扫描这些根并复制从空间中可到达但尚未复制到目标空间的对象的算法。 已经在垃圾回收中幸存下来的对象被提升（移动）到老年代。 在根扫描和第一轮复制之后，扫描新分配的 to-space 中的对象以查找引用。 类似的，扫描所有晋升的对象以查找对来自空间的新引用。 这三个阶段在主线程上交错。 该算法继续进行，直到不再有新对象可以从 to-space 或老年代到达。 此时，从空间只包含无法访问的对象，即它只包含垃圾。
图 2：V8 年轻代切尼半空间复制垃圾回收算法
处理顺序
V8 年轻代并行 Mark-Evacuate 垃圾回收算法
我们试验了一种基于 V8 完整的 Mark-Sweep-Compact 收集器的并行 Mark-Evacuate 算法。主要优势是利用完整的 Mark-Sweep-Compact 收集器中已经存在的垃圾收集基础设施。该算法包括三个阶段：标记、复制和更新指针，如图 3 所示。为了避免在年轻代中清扫页面以维护空闲列表，年轻代仍然使用半空间来维护，该半空间始终通过复制保持紧凑在垃圾收集期间将对象放入到空间中。年轻代最初是并行标记的。标记后，活动对象被并行复制到其相应的空间。工作是基于逻辑页面分布的。参与复制的线程保留自己的本地分配缓冲区 (LAB)，这些缓冲区在完成复制时被合并。复制之后，应用相同的并行化方案来更新对象间指针。这三个阶段是同步执行的，也就是说，虽然这些阶段本身是并行执行的，但线程必须在继续下一个阶段之前进行同步。
图 3：V8 年轻代并行 Mark-Evacuate 垃圾回收算法
处理顺序
V8 年轻代并行 Scavenger 垃圾回收算法
并行 Mark-Evacuate 收集器将计算活跃度、复制活跃对象和更新指针的阶段分开。一个明显的优化是合并这些阶段，从而产生一种同时标记、复制和更新指针的算法。通过合并这些阶段，我们实际上得到了 V8 使用的并行 Scavenger，这是一个类似于 Halstead 的半空间收集器的版本，不同之处在于 V8 使用动态工作窃取和简单的负载平衡机制来扫描根（参见图 4）。与单线程切尼算法一样，这些阶段是：扫描根、在年轻代内复制、升级到老年代和更新指针。我们发现大部分根集通常是从老年代到年轻代的引用。在我们的实现中，记忆集是按页面维护的，这自然会在垃圾收集线程之间分配根集。然后并行处理对象。从可被窃取的垃圾回收线程中新发现的对象会被添加到全局工作列表。此工作列表提供快速的任务本地存储以及共享工作的全局存储。当当前处理的子图不适合work stealing（例如，对象的线性链）时，屏障确保任务不会过早终止。所有阶段在每个任务上并行执行并交错执行，最大限度地提高工作任务的利用率。
图 4：V8 年轻代并行 Scavenger 垃圾回收算法
处理顺序
结果
Scavenger 算法最初的设计考虑了最佳的单核性能。 从那时起，世界发生了变化。 CPU 内核通常很丰富，即使在低端移动设备上也是如此。 更重要的是，这些内核通常实际上已经启动并正在运行。 为了充分利用这些核心，V8 垃圾收集器的最后一个顺序组件 Scavenger 必须进行现代化改造。
并行 Mark-Evacuate 收集器的一大优势是可以获得准确的活动信息。 该信息可以例如 用于通过移动和重新链接包含大部分活动对象的页面来完全避免复制，这也由完整的 Mark-Sweep-Compact 收集器执行。 然而，在实践中，这主要是在综合基准上观察到的，很少出现在真实网站上。 并行 Mark-Evacuate 收集器的缺点是执行三个单独的锁步阶段的开销。 当垃圾收集器在大部分是死对象的堆上调用时，这种开销尤其明显，许多现实世界的网页都是这种情况。 请注意，在大多数死对象的堆上调用垃圾收集实际上是理想的场景，因为垃圾收集通常受活动对象大小的限制。
并行 Scavenger 通过在小堆或几乎为空的堆上提供接近优化的 Cheney 算法的性能来缩小这一性能差距，同时在堆变大且存在大量活动对象的情况下仍提供高吞吐量。
在许多其他平台中，V8 支持 Arm big.LITTLE。 虽然卸载小核心上的工作有利于电池寿命，但当小核心的工作包太大时，它可能导致主线程停滞。 我们观察到，由于页面数量有限，对于年轻代垃圾收集，页面级并行不一定在 big.LITTLE 上工作。 Scavenger 通过使用显式工作列表和工作窃取提供中等粒度的同步自然地解决了这个问题。
图 5：各个网站的年轻代垃圾收集总时间（以毫秒为单位）
V8 现在附带了并行 Scavenger，它在大量基准测试中将主线程年轻代垃圾收集的总时间减少了大约 20%–50%（我们的 perf 瀑布的详细信息）。 图 5 显示了各种现实世界网站的实现比较，显示改进了大约 55% (2x)。 可以在最大和平均暂停时间上观察到类似的改进，同时保持最小暂停时间。 并行 Mark-Evacuate 收集器方案仍有优化的潜力。
相关阅读：
