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

未分类

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

背景

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

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

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

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

减少标记停顿

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

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

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

再者增量标记并不是免费的，应用程序必须通知垃圾收集器关于更改对象图的所有操作。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);
  }
}

write-barrier不允许黑色对象指向白色对象。这也被称为强三色不变性（strong tri-color invariant），它保证应用程序不能在垃圾收集器隐藏活动对象，因此标记结束时，所有白色对象对于应用程序来说都是不触及的，并且可以安全地得到释放。

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

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

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

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

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

平行标记

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

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

标记工作表和工作窃取（work stealing）

标记工作表的实现对性能至关重要，它可以决定分配给其他线程的工作量，以快速地平衡本地线程性能。

图6显示了V8如何通过使用基于字段的本地线程插入和删除标记工作表来平衡这些需求。一旦一个变满，它就会被弹到到一个共享的全局池中，以供窃取。通过这种方式，V8允许标记线程在没有任何同步的情况下尽可能长时间在本地操作，并且仍然可以处理单个线程访问对象的新子图的情况。

并发标记

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

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

• 对象分配

• 写入一个对象字段

• 对象布局更改

• 从snapshot中反序列化

• Materialization during deoptimization of a function.

• 在新一代垃圾收集器中疏离（Evacuation）

• 代码修补

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

Write barrier

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

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

将它与以前进行比较：

// 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);
  }
}

有两个变化：

• 源对象的颜色检查（color(object) == black）消失了

• value从白色到灰色的颜色转变都是原子级别的

如果没有源对象颜色检查，write barrier会变得更加保守，它可能会将对象标记为有效，即使这些对象不可访问。我们删除了该检查，避免了写入操作和write barrier之间昂贵的memory fence：

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

没有了memory fence，对象颜色加载操作可以在写入操作之前重新排序。如果我们不阻止重新排序，那么当工作线程在未看到新值的情况下会标记对象，write barrier可能会观察灰色对象的颜色并释放出来。

保释清单（Bailout worklist）

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

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

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

更改对象布局

对象的字段可以存储三种值：标记的指针、标记的小整数（也称为Smi），或未标记的值（如拆箱的浮点数）。指针标记是很有名的技术，它可以有效地表示未拆箱的整数。在V8中，标记值的最低有效位将显示它是指针还是整数。

通过将对象转换为另一个隐藏类，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）标记工作表以加快主线程标记进度。主线程偶尔也会通过处理保释清单和标记工作表参与标记。标记工作表变空后，主线程完成垃圾收集。在最终确定之前，主线程重新扫描 roots ，可能会发现更多的白色对象，这些对象在工作线程的帮助下被平行标记。

结果

测试结果显示移动和桌面上每个垃圾回收周期的主线程标记时间分别减少了65％和70％。

并发标记也减少了Node.js中的垃圾收集jank。这点尤其重要，因为Node.js从未实现在空闲时间内进行垃圾收集调度的机制，因此它也从没在ank-critical阶段隐藏标记时间。最后，我们需要说的是Node.js v10现已支持并发标记。