引擎V8推出“并发标记”，可节省60%-70%的GC时间

2018 年 6 月 14 日 InfoQ

作者｜V8 博客

编辑｜覃云 - 前端之巅公众号

V8 官方博客宣布 V8 引擎在 GC 技术上获得重大突破，这项技术名为“并发标记（ concurrent marking）”，在 GC 扫描和标记活动对象时，它允许 JavaScript 应用程序继续运行。测试显示，并发标记技术为主线程标记节省了 60％-70％的时间。并发标记是一个用新的平行和并发的 GC 替换旧的 GC 的项目，现在 Chrome 64 和 Node.js v10 已经默认启用并发标记。

背景介绍

标记是 V8 Mark-Compact GC 工作的一个阶段。在这个阶段中，收集器发现并标记所有活动对象。标记从一组已知的活动对象开始，如全局对象和激活函数，即所谓的 roots，收集器将 roots 标记为活动的对象，并顺着指针去寻找发现更多的活动对象。收集器继续标记新发现的对象并跟随指针移动，直到没有发现更多的对象要标记为止。在标记结束时，所有无法让应用程序访问的未标记对象，都可以安全地回收。

我们可以将标记视为图遍历（Graph traversal）。堆内存上的对象是下图中的节点，指针从一个对象指向另一个对象是图的边缘。给定图中的一个节点，我们可以使用该对象的隐藏类找到该节点的所有外边缘。

V8 使用每个对象的两个 mark-bits 和一个标记工作表来实现标记。两个 mark-bits 编码三种颜色：白色（00），灰色（10）和黑色（11）。最初所有对象都是白色的，这意味着收集器还没有发现它们。当收集器发现它并将其推到标记工作表上时，白色对象变灰。当收集器将它从标记工作列表中弹出并访问其全部字段时，灰色对象变黑，这种方案被称为三色标记法。当没有灰色对象时，标记结束。所有剩余的白色对象都可以安全地被回收。

请注意，上述标记算法仅适用于在标记进行中应用程序暂停的情况。如果我们允许应用程序在标记过程中运行，那么应用程序可以更改图形并最终诱骗收集器释放活动对象。

减少标记停顿

对大型的堆内存来说，可能需要几百毫秒才能完成一次标记。

长时间的停顿可能会导致应用程序无法响应，并导致用户体验不佳。2011 年，V8 从 stop-the-world 标记切换到增量标志。在增量标记期间，GC 将标记工作分解为更小的模块，并允许应用程序在模块之间运行：

GC 决定每个模块中执行多少增量标记以匹配应用程序的分配速率。一般情况下，这极大地提高了应用程序的响应速度。但对于大型堆内存来说，收集器试图跟上应用程序分配速率的过程中，仍然可能会有长时间的停顿。

再者增量标记并不是免费的，应用程序必须通知 GC 关于更改对象图的所有操作。V8 使用 Dijkstra-style write-barrier 来实现通知，在每次用 JavaScript 写入 object.field = value 之后，V8 插入 write-barrier 代码：

// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

增量标记很好地集成了 GC 的闲置时间（idle time）。Chrome 的 Blink 任务调度程序在主线程的闲置时间内可以调度小增量标记步骤，而且不会造成混乱。如果闲置时间可用，优化效果会非常好。

由于 write-barrier 会有消耗，增量标记可能会降低应用程序的吞吐量。通过使用额外的 worker threads 可以提高吞吐量和暂停时间。有两种方法可以在 worker threads 上进行标记：平行标记（parallel marking）和并发标记（concurrent marking）。

平行标记发生在主线程和工作线程（worker threads）上，应用程序在整个平行标记阶段暂停，它是 stop-the-world 标记的多线程版本。

并发标记主要发生在工作线程上，当并发标记进行时，应用程序可以继续运行。

以下两节将讲述如何在 V8 中添加对平行标记和并行标记的支持。

平行标记

在平行期间，我们可以假定应用程序没有运行。这大大简化了实现过程，因为我们可以假定对象图是静态的并且不会发生变化。为了平行标记对象图，我们需要确保 GC 数据结构是线程安全的，并找到一种方法有效地在线程之间共享标记工作。下图显示了平行标记所涉及的数据结构。箭头指示数据流的方向，为简单起见，该图省略了整理堆内存碎片所需的数据结构。

需要注意的是，线程只能从对象图中读取并且不会被更改。对象的标记位点和标记工作表必须支持读取和写入的访问。

并发标记

当工作线程正访问堆内存上的对象时，并发标记允许 JavaScript 在主线程上运行，这为许多潜在的数据竞争（data races) 打开了大门。例如，当工作线程正在读取字段时，JavaScript 可能正在写入对象字段。数据竞争可能会让 GC 错误地释放活动对象或将原始值与指针混合在一起。

主线程上每个更改对象图的操作都是数据竞争的潜在来源。由于 V8 是一款高性能引擎，具有许多对象布局优化功能，因此潜在的数据竞争来源很多。以下是可能导致的部分结果：

对象分配
写入一个对象字段
对象布局更改
从 snapshot 中反序列化
Materialization during deoptimization of a function.
在新一代 GC 中疏离（Evacuation）
代码修补

主线程需要与工作线程同步，同步的成本和复杂程度取决于操作。

Write barrier

写入对象字段导致的数据竞争，可将写入操作调整为 atomic write，并调整 write barrier 来解决：

保释清单（Bailout worklist）

某些操作（例如代码修补）需要独家访问该对象。早期，我们决定避免对象锁定，因为它们可能导致优先级逆转（ priority inversion）问题，在这个过程中，主线程必须等待一个因为持有锁定对象而被取消调度的工作线程。我们不锁定对象，而是允许工作线程访问该对象。工作线程通过将对象推入保释清单来完成该工作，这个过程只能由主线程来处理：

工作线程保释了优化的代码对象、隐藏类和 weak collections，因为访问它们需要锁定或高昂的同步协议。

回顾过去，保释清单对增量开发来说非常有用，我们开始使用工作线程来释放所有对象类型并逐个添加并发标记。

更改对象布局

对象的字段可以存储三种值：标记的指针、标记的小整数（也称为 Smi），或未标记的值（如拆箱的浮点数）。

通过将对象转换为另一个隐藏类，V8 中将对象字段从标记的状态变为未标记的状态（反之亦然），这种更改对象布局的方式对并发标记来说是不安全的。

如果在工作线程中使用旧的隐藏类访问对象时发生更改，则可能会出现两种类型的错误。首先，worker 可能会错过一个指针，认为这是一个没有标记的值。write barrier 可以防止这种错误。其次，worker 可能会将未标记的值视为指针并放弃引用它，这会导致无效的内存访问，通常会导致程序崩溃。为了处理这种情况，我们使用在对象标记位上同步的 snapshotting 协议。协议涉及两方面：主线程将对象字段从标记变为未标记，然后工作线程访问该对象。在更改字段之前，主线程会确保该对象被标记为黑色，并将其推入保释清单中供以后访问：

atomic_color_transition(object, white, grey);
if (atomic_color_transition(object, grey, black)) {
  // The object will be revisited on the main thread during draining
  // of the bailout worklist.
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

如下面的代码片段所示，工作线程首先加载对象的隐藏类，并使用 atomic relaxed 加载操作来快照（snapshots）隐藏类指定对象中的所有指针字段。然后它会尝试使用 atomic compare 和 swap 操作将对象标记为黑色。如果标记成功，则意味着快照必须与隐藏类一致，因为主线程在更改其布局之前会将对象标记为黑色。

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
  pointer = atomic_relaxed_load(object + field_offset);
  snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
  visit_pointers(snapshot);
}

放在一起

我们将并发标记整合到现有的增量标记基础设施中，主线程通过扫描 roots 并填充标记工作表来启动标记。之后，它会在工作线程上发布并发标记任务。工作线程通过合作清空（draining）标记工作表以加快主线程标记进度。主线程偶尔也会通过处理保释清单和标记工作表参与标记。标记工作表变空后，主线程完成 GC。在最终确定之前，主线程重新扫描 roots ，可能会发现更多的白色对象，这些对象在工作线程的帮助下被平行标记。