跳到主要内容

垃圾话：Orinoco垃圾回收器

· 阅读需 13 分钟
Peter “垃圾” Marshall ([@hooraybuffer](https://twitter.com/hooraybuffer))

在过去的几年里，V8垃圾回收器（GC）发生了很大的变化。Orinoco项目将一个顺序的、全停式的垃圾回收器转变成了一个大部分并行和并发的回收器，具备增量回退功能。

备注

注意： 如果你更喜欢观看演讲而非阅读文章，请欣赏下面的视频！如果不是，可以跳过视频继续阅读。

任何垃圾回收器都有一些定期需要完成的基本任务：

  1. 识别存活/死亡对象
  2. 回收/重用被死亡对象占用的内存
  3. 压缩/整理内存（可选）

这些任务可以按顺序执行，也可以随意交错进行。一个直接的方法是暂停JavaScript的执行，然后在主线程上按顺序执行这些任务。这可能会导致主线程上的卡顿和延迟问题，我们已经在之前的 博客文章中讨论过，还会降低程序的整体吞吐量。

主GC（全标记-汇集）​

主GC从整个堆中回收垃圾。

主GC分为三个阶段：标记、清除和压缩。

标记​

确定哪些对象可以被回收是垃圾回收的重要部分。垃圾回收器通过使用可达性作为“存活性”的代理来完成这项工作。这意味着任何当前在运行时可达的对象都必须保留，而任何不可达的对象都可以被回收。

标记过程是找到可达对象的过程。GC从一组已知的对象指针集开始，称为根集。这包括执行栈和全局对象。然后它跟踪每个指针到一个JavaScript对象，并将该对象标记为可达。GC继续遍历该对象中的每个指针，并递归执行此过程，直到找到并标记运行时所有可达的对象。

清除​

清除是一个将死亡对象留下的内存空隙加入到一个叫做空闲列表的数据结构的过程。一旦标记完成，GC查找不可达对象留下的连续内存空隙，并将它们加入到适当的空闲列表中。空闲列表根据内存块的大小进行分隔以便快速查找。以后当我们需要分配内存时，只需查看空闲列表并找到合适大小的内存块即可。

压缩​

主GC还会根据一个碎片化评估标准选择疏散/压缩某些页。你可以将压缩过程想象成旧电脑上的硬盘碎片整理。我们将存活下来的对象复制到没有正在被压缩的其它页面中（使用该页面的空闲列表）。这样，我们可以利用死亡对象留下来的内存中的小而分散的空隙。

一个复制存活对象的垃圾回收器潜在的弱点是，当我们分配了大量长寿命对象时，复制这些对象的成本会很高。这就是为什么我们只选择压缩一些高度碎片化的页面，而对其他页面仅执行清除操作，这样不会复制存活对象。

分代布局​

V8中的堆被划分为不同的区域，称为分代。堆中有一个青年代（进一步分为“新生代”和“中间代”子代），以及一个老年代。对象首先分配到新生代。如果它们在下一次GC中存活下来，它们继续留在青年代，但被视为“中间”状态。如果它们再一次存活GC，它们被移动到老年代。

V8堆被划分为分代。当对象在GC中存活时，它们会在分代间移动。

在垃圾回收中，有一个重要的术语：“分代假说”。这基本上表明大多数对象很快就会死亡。换句话说，从GC的角度来看，大多数对象在分配后会立即变得不可达。这不仅适用于V8或JavaScript，也适用于大多数动态语言。

V8 的分代堆布局设计旨在利用对象生命周期的这一特点。GC 是一个压缩/移动 GC，这意味着它在垃圾回收时会复制存活的对象。这似乎违反直觉：在 GC 时复制对象是昂贵的。但根据分代假设，我们知道只有极少数的对象实际上会在垃圾回收后存活下来。通过仅移动存活的对象，其他所有分配的对象都变成了‘隐性的’垃圾。这意味着我们的成本（复制的开销）仅与存活对象的数量成正比，而不是与分配的对象数量成正比。

Minor GC（清理器）​

V8 中有两个垃圾回收器。Major GC （标记-压缩） 回收整个堆中的垃圾。Minor GC （清理器） 回收年轻代中的垃圾。Major GC 在回收整个堆时非常有效，但分代假设告诉我们，新分配的对象很可能需要垃圾回收。

在只在年轻代进行清理的清理器中，存活的对象总是被迁移到新页面。V8 对年轻代使用了‘半空间’设计。这意味着总会有一半空间是空的，用来进行迁移步骤。在清理过程中，这个最初为空的区域被称为‘To-Space’。我们复制到的区域被称为‘From-Space’。在最坏的情况下，每个对象都可能在清理中存活，我们需要复制每个对象。

为了进行清理，我们还有一组额外的根，即由老年代指向新生代的引用。这些是老空间中指向年轻代对象的指针。与其在每次清理时追踪整个堆图，我们使用写屏障来维护一组由老指向新的引用列表。当与堆栈和全局变量结合时，我们可以知道每个指向年轻代的引用，而无需追踪整个老年代。

迁移步骤将所有存活对象移动到内存的连续块中（在某个页面内）。这完全消除了由死对象留下的碎片的优点。然后我们交换这两个空间，即 To-Space 变为 From-Space，反之亦然。一旦 GC 完成，新对象的分配将发生在 From-Space 中的下一个空闲地址。

清理器将存活的对象迁移到一个新页面。

单靠这种策略，我们很快就会耗尽年轻代的空间。存活第二次 GC 的对象被迁移到老代，而不是 To-Space。

清理的最后一步是更新引用原始对象的指针，因为这些对象已经被迁移了。每个复制的对象都会留下一个转发地址，用于更新原始指针以指向新位置。

清理器将‘中间’对象迁移到老代，将‘新生’对象迁移到一个新页面。

在清理过程中，我们实际上将这三个步骤——标记、迁移和指针更新——交替进行，而不是分为独立的阶段。

Orinoco​

这些算法和优化大多是垃圾回收文献中的常见内容，可以在许多具有垃圾回收功能的语言中找到。但最先进的垃圾回收已经走了很长的路。衡量垃圾回收所花费时间的一个重要指标是主线程在进行 GC 时暂停的时间。对于传统的‘全停式’垃圾回收器，这段时间可以累积起来，直接影响用户体验，表现为页面卡顿以及渲染和延迟表现不佳。

Orinoco 的 Logo，V8 的垃圾回收器

Orinoco 是一个 GC 项目的代号，它利用了最新和最先进的并行、增量和并发技术进行垃圾回收，目的是解放主线程。这里有些术语在 GC 环境中有特定意义，值得详细定义。

并行​

并行是指主线程和辅助线程同时完成几乎相等的工作。这仍然是一种‘全停式’的方法，但总暂停时间现在被参与的线程数量（加上一些同步开销）分摊了。这是三种技术中最简单的一种。因为没有 JavaScript 正在运行，JavaScript 堆是暂停的，所以每个辅助线程只需要确保对另一个辅助线程可能也想访问的任何对象的访问进行同步。

主线程和辅助线程同时处理相同任务。

增量​

增量模式是指主线程间歇性地执行少量工作。我们不会在一次增量暂停中完成整个垃圾回收，而是完成垃圾回收所需总工作量的一小部分。这种方式更加复杂，因为每次增量工作结束后，JavaScript都会执行，导致堆的状态发生变化，这可能会使之前所做的增量工作失效。从图中可以看到，这并没有减少主线程花费的时间（实际上通常会略有增加），只是将这些时间分散到更长的时间段中。这仍然是一种用于解决最初问题的好技术：主线程延迟。通过允许JavaScript间歇性运行，同时继续执行垃圾回收任务，应用程序仍然可以响应用户输入并推动动画的进展。

垃圾回收任务的小块被交替插入到主线程的执行过程中。

并发​

并发模式指主线程不断地执行JavaScript，而辅助线程完全在后台执行垃圾回收工作。这是三种技术中最难的一种：JavaScript堆中的任何对象都可能随时改变，从而使我们之前的工作失效。除此之外，还需要担心读写竞争，因为辅助线程和主线程可能同时读取或修改相同的对象。这种方式的优点是主线程完全自由地执行JavaScript——尽管由于与辅助线程的一些同步操作会有微小的开销。

垃圾回收任务完全在后台运行，主线程可以自由运行JavaScript。

V8中的垃圾回收现状​

清除​

目前，V8使用并行清除来在年轻代垃圾回收期间将工作分配到辅助线程上。每个线程都接收了若干指针，并按照指针逐步清除，将任何存活对象迅速迁移到To-Space。清除任务通过原子读写、比较和交换操作进行同步，因为可能有其他清除任务通过不同路径找到了相同的对象并试图迁移它。成功迁移对象的辅助线程随后会更新指针，并留下一个转发指针，以便其他线程在发现对象时可以更新其他指针。为了快速且无同步地分配存活对象，清除任务使用线程本地分配缓冲区。

并行清除将清除工作分配到多个辅助线程和主线程上。

主垃圾回收​

V8中的主垃圾回收以并发标记开始。当堆接近动态计算的限制时，会启动并发标记任务。辅助线程分别收到若干指针，以跟随这些指针并标记所发现的所有对象及其引用。并发标记完全在后台执行，同时主线程上的JavaScript继续运行。使用写屏障来跟踪在并发标记期间JavaScript创建的对象之间的新引用。

主垃圾回收使用并发标记与清扫，以及并行压缩与指针更新。

当并发标记完成或动态分配限制被达到时，主线程会执行一个快速的标记终结步骤。在这一阶段主线程暂停一次。这代表了主垃圾回收的总暂停时间。主线程再次扫描根，以确保所有存活对象都被标记；然后与若干辅助线程一起启动并行压缩和指针更新。在老年代空间中的并非所有页面都可以进行压缩——那些不适合的页面将使用前面提到的自由列表进行清扫。在暂停期间，主线程会启动并发清扫任务。这些任务同时与并行压缩任务和主线程自身体同时运行——它们甚至可以在主线程运行JavaScript时继续完成。

空闲时间垃圾回收​

JavaScript的用户不能直接访问垃圾回收器；垃圾回收器的实现是完全由实现定义决定的。但是，V8确实提供了一种机制，允许嵌入者触发垃圾回收，即使JavaScript程序本身不能。垃圾回收器可以发布‘空闲任务’，这些任务属于后续本应被触发的非强制性工作。例如，在Chrome中，如果动画每秒60帧，每帧的动画渲染时间大约为16.6毫秒。如果动画工作提前完成，Chrome可以选择在下一帧之前利用空闲时间运行垃圾回收器创建的一些空闲任务。

空闲垃圾回收利用主线程的空闲时间主动执行垃圾回收工作。

有关更多详情，请参考我们关于空闲时间垃圾回收的深入报告。

关键点​

V8 的垃圾回收器自其诞生以来已经取得了长足的进步。为现有的垃圾回收器添加并行、增量和并发技术是数年的努力，但已经收获了成果，将大量工作转移到了后台任务上。这大大改进了暂停时间、延迟和页面加载，使动画、滚动和用户交互更加流畅。并行 Scavenger 根据工作负载的不同，将主线程年轻代垃圾回收的总时间减少了大约 20%-50%。空闲时间垃圾回收 在 Gmail 处于空闲状态时，可以将其 JavaScript 堆内存减少 45%。并发标记和清理 将 WebGL 重型游戏中的暂停时间减少了最多 50%。

但这项工作还没有结束。减少垃圾回收的暂停时间对于为用户提供最佳的网页体验仍然很重要，我们正在研究更多高级的技术。除此之外，Blink（Chrome 的渲染器）也有一个垃圾回收器（称为 Oilpan），我们正在努力改进这两个回收器之间的协作，并将 Orinoco 中的一些新技术移植到 Oilpan。

大多数开发者在开发 JavaScript 程序时不需要专门考虑垃圾回收器，但了解一些内部机制可以帮助更好地考虑内存使用和有益的编程模式。例如，对于 V8 堆的分代结构，短生命周期对象实际上从垃圾回收器的角度来看是非常廉价的，因为我们仅需为那些存活过回收的对象付出代价。这类模式不仅适用于 JavaScript，还适用于许多使用垃圾回收的语言。