微信号:infoqchina

介绍:有内容的技术社区媒体

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

2018-06-14 08:19 覃云 译
作者|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 ,可能会发现更多的白色对象,这些对象在工作线程的帮助下被平行标记。

结   果

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

最后,我们需要说的是 Node.js v10 现已支持并发标记。

原文链接

https://v8project.blogspot.com/2018/06/concurrent-marking.html


 
InfoQ 更多文章 网易有道周枫:曾梦想执笔去教书,却转岗当上CEO 技术人应该如何投资时间? 迅雷创始人程浩:流量、资本红利已成过去式,中国互联网下一个十年属于…… GitHub被收购,Stack Overflow在裁员:后开源时代,开源的未来往哪边? 程序员练级攻略
猜您喜欢 深入讲解Android中Activity launchMode 开源浏览器插件:GitHub 显示用户编程语言排名 Go 语言如果按这样改进,能火过 Java 吗? 【MySQL】日志管理 陈磊-大数据风控:拍拍信的AI视角