Orinoco：年轻代垃圾回收
在V8中，JavaScript对象被分配到由V8垃圾回收器管理的堆上。在之前的博客文章中，我们已经讨论了如何减少垃圾回收暂停时间（不止一次）以及内存消耗。在这篇博客文章中，我们介绍了并行Scavenger，这是V8的主要并发和并行垃圾回收器Orinoco的最新功能之一，并讨论了设计决策以及我们实施的一些备选方法。
V8将其管理的堆分为不同的代，其中对象最初被分配到年轻代的“育苗室”。若对象在一次垃圾回收后存活下来，它们会被复制到年轻代的中间代。若它们在另一轮垃圾回收后仍然存活，便会被移至老年代（见图1）。V8实现了两个垃圾回收器：一个频繁回收年轻代，另一个则回收全堆，包括年轻代和老年代。从老年代到年轻代的引用是年轻代垃圾回收的根。这些引用已被记录，以便在对象移动时提供有效的根识别和引用更新。
由于年轻代相对较小（在V8中最多16MiB），它会很快填满对象并需要频繁回收。在M62之前，V8使用了Cheney半空间复制垃圾回收器（见下文），它将年轻代分为两部分。在JavaScript执行期间，年轻代只有一半可用来分配对象，而另一半保持空闲。在一次年轻代垃圾回收中，活跃对象从一个半空间被复制到另一个半空间，同时对内存进行动态压缩。已经复制过一次的活跃对象被视为中间代的一部分，并被提升到老年代。
从v6.2开始，V8将年轻代的默认垃圾回收算法切换到并行Scavenger，类似于Halstead的半空间复制回收器，但不同之处在于V8使用动态而非静态的跨线程工作窃取。接下来我们解释三种算法：a）单线程Cheney半空间复制回收器，b）并行标记-清除方案，c）并行Scavenger。
单线程Cheney的半空间复制
在v6.2之前，V8使用了Cheney的半空间复制算法，它非常适合单核心执行和分代方案。在一次年轻代回收之前，内存的两个半空间都被提交并分配了正确的标签：包含当前对象集合的页面被称为_源空间_（from-space），而对象被复制到的页面被称为_目标空间_（to-space）。
Scavenger将调用栈中的引用以及从老代到年轻代的引用视为根。图2展示了该算法，Scavenger最初扫描这些根并将未复制到_目标空间_的从空间中可达对象复制到目标空间。已经存活过一次垃圾回收的对象会被提升（移动）到老年代。经过根扫描和第一次复制后，刚分配到的目标空间中的对象将被扫描以检查其引用。同样，所有被提升的对象也会被扫描，以检查它们是否存在指向_源空间_的新引用。这三个阶段在主线程上交替进行。该算法会持续运行，直到不再有新对象可从目标空间或老年代可达为止。此时源空间仅包含不可达对象，即垃圾。
并行标记-清除
我们基于V8的完整Mark-Sweep-Compact回收器实验了一种并行Mark-Evacuate算法。其主要优点是可以利用已经存在的完整Mark-Sweep-Compact回收器的垃圾回收基础设施。该算法由三个阶段组成：标记、复制和更新指针，如图3所示。为了避免对年轻代的页面进行清扫以维护空闲列表，年轻代依然通过一个半空间来维护，并在垃圾回收时通过将存活的对象复制到_to-space_中保持紧凑。年轻代最初是并行标记的。标记之后，存活的对象被并行复制到它们对应的空间。工作根据逻辑页面分配。参与复制的线程保持它们自己的本地分配缓冲区（LABs），在完成复制后被合并。在复制之后，同样的并行化方案被应用于更新对象间的指针。这三个阶段以同步步调执行，也就是说，虽然阶段本身是并行执行的，但线程必须同步后才能进入下一阶段。
并行清理（Parallel Scavenge）
并行Mark-Evacuate回收器将计算存活性、复制存活对象和更新指针的阶段分离开来。一个明显的优化是合并这些阶段，从而得到一种可以同时标记、复制和更新指针的算法。通过合并这些阶段，我们实际上获得了V8使用的并行清理器（Scavenger），这是一种类似于Halstead的半空间收集器的版本，不同之处在于V8使用了动态工作窃取和一个简单的负载平衡机制来扫描根集合（见图4）。像单线程的Cheney算法一样，阶段包括：扫描根集合、在年轻代中复制、提升到老年代以及更新指针。我们发现根集合中的大多数通常是老年代对年轻代的引用。在我们的实现中，按每页维护回忆集合（remembered sets），这自然而然地将根集合分配到垃圾回收线程中。对象接着被并行处理。新发现的对象被添加到一个全局工作列表中，垃圾回收线程可以从中窃取。这份工作列表既提供快速的任务本地存储，又提供全局存储用于共享工作。一种屏障机制确保在当前处理的子图不适合进行工作窃取（例如线性对象链）时任务不会过早终止。所有阶段以并行方式执行，并在每个任务中交叉进行，最大化工作线程的利用率。
结果与成果
清理器算法起初是为了在单核心上的最佳性能而设计的。而如今，世界已经改变。即使在低端的移动设备上，CPU核心往往也很充足。更重要的是，通常这些核心实际上都是启用运行的。为了能够充分利用这些核心，V8垃圾回收器中最后一个串行的组件——清理器必须进行现代化改造。
并行Mark-Evacuate回收器的一个大优势是能够提供准确的存活信息。例如，这些信息可以用来通过仅移动和重新链接包含大部分存活对象的页面完全避免复制，完整的Mark-Sweep-Compact回收器也执行了这种操作。然而在实际使用中，这种情况主要在合成基准测试中可观察到，而在真实网站中较少出现。并行Mark-Evacuate回收器的缺点是执行三个独立同步阶段的开销。这种开销在垃圾回收器作用于包含大多数无用对象的堆时尤为明显，而在现实中的许多网页上正是这种情况。需要注意的是，在包含大多数无用对象的堆上调用垃圾回收实际上是理想的场景，因为垃圾回收通常受存活对象的大小限制。
并行清理器通过在小型或几乎为空的堆上提供接近优化的Cheney算法的性能，并在堆变大且有大量存活对象时仍保持高通量，从而填补了这一性能差距。
V8支持许多平台，其中包括Arm big.LITTLE。虽然将工作负载转移到小核心有助于延长电池寿命，但当小核心的工作负载过大时可能会导致主线程停滞。我们观察到，对于年轻代垃圾回收，由于页面数量有限，页面级并行性未必能在big.LITTLE架构下实现负载均衡。清理器通过使用显式的工作列表和工作窃取提供中粒度的同步，自然地解决了这一问题。
