并发JavaScript
它能行！

2017年8月30日

作者：Filip Pizlo

随着最近加入了SharedArrayBuffer，并发性正在进入JavaScript语言。此添加允许JavaScript程序对SharedArrayBuffer对象执行并发访问。WebKit支持SharedArrayBuffer，并在我们的编译器管道中获得完整的优化支持。不幸的是，JavaScript不允许共享SharedArrayBuffer以外的任何对象。

本文探讨了一个大胆的设想实验：将并发性扩展到整个JavaScript堆需要付出什么？在这个世界里，任何对象都可以与其他线程共享。这将是一个不小的改变。现有的JavaScript VM优化利用了只有一个执行线程的事实，因此并发性肯定会引入一些性能问题。本文关注的是这在技术上是否可行，如果可行，成本会是多少。

我们提供了一个基本的初步API来阐述我们所说的并发性。本文大部分内容关注WebKit的JavaScript虚拟机（简称JavaScriptCore或JSC）如何实现这个初步方案。实现这个初步方案将是一项巨大的工作。我们认为我们提出的实现应该能够达到以下目标：

对于不使用并发的代码，没有性能退步。
当程序在不故意共享任何对象的情况下并行运行时，实现线性可伸缩性。我们不期望两个线程的速度是单个线程的两倍，因为我们预计会有一些并发开销——但如果你有两颗CPU，那么两个线程应该比单个线程快，并有望接近单个线程的两倍。
在某些共享对象的并行代码库上实现线性可伸缩性——包括相对于最佳串行基线的加速。
合理的语义，包括一个不比现代硬件提供的内存模型弱的内存模型。
兼容性。例如，并发JavaScript程序应该能够说明如何使用DOM，而无需重写DOM实现。

我们提出的实现方案依赖于64位系统，但这主要是因为我们的引擎已经以64位为中心。

目前尚无法通过经验评估该方案的性能，但我们的实现草图确实能够直观地了解性能可能如何。具体而言，我们的方案确保大多数属性访问最多经历一次算术指令的开销（几乎免费），而少数特别棘手（且罕见）的访问会经历高达约7倍的开销。本文最后一部分将我们的方案与其他实现并发的技术进行比较。

并发JS初步方案

我们关于并发JS的初步提案是简单地添加线程。线程拥有独立的堆栈，但共享其他所有内容。线程非常适合我们的实验，因为它们非常通用。我们可以想象在线程之上实现许多其他类型的并发编程模型。因此，如果我们的VM能够支持线程，那么它可能也能够支持许多其他并发和并行编程模型。本文旨在消除技术可行性作为向JavaScript添加任何并发编程模型的限制因素。

本节将初步方案具体化，主要是为了提供其易于实现或难以实现方面的背景信息。了解API的外观有助于理解它所产生的限制。

每个程序都将从一个线程开始。线程可以启动其他线程。线程存在于同一个堆中，并且可以相互共享对象。本节展示了API，描述了内存模型，并展示了并发性如何与DOM交互。

可能的API

我们建议

一个用于创建线程的简单API，
对Atomics对象进行修改以支持构建锁对象，
一个可以在Atomics之上构建的锁和条件变量API，
一种创建线程局部变量的方法，以及
一些辅助工具，允许逐步采用。

本文将利用这个初步方案来确切了解在JavaScriptCore中实现线程所需的条件。

我们希望创建线程变得容易

new Thread(function() { console.log("Hello, threads!"); });

这将启动一个新线程，最终会打印“Hello, threads!”。请注意，即使这个简单的示例也与该线程共享许多内容。例如，函数对象捕获了创建它的线程中的词法作用域，因此当线程访问console变量时，这是对共享对象的访问。

线程可以被join，以等待它们完成并获取结果

let result = new Thread(() => 42).join(); // returns 42

在网络浏览器中，主线程不能阻塞，因此如果上述代码在主线程上，join()将抛出异常。我们可以支持阻塞操作的异步版本

new Thread(() => 42).asyncJoin().then((result) => /* result is 42 */)

您始终可以获取当前线程的Thread对象

let myThread = Thread.current;

线程可能需要彼此等待以防止竞争。这可以通过使用锁来实现。我们不只是简单地引入一个锁定API，而是建议扩展Atomics API，允许用户构建他们喜欢的任何锁。我们在建议的API中提供了一个好的锁实现，但我们希望鼓励创建其他类型的同步原语。现有的SharedArrayBuffer规范允许开发人员使用Atomics API创建自定义锁。这个API允许你这样说：

Atomics.wait(array, index, expectedValue);

和

Atomics.wake(array, index, numThreadsToWake);

目前，该数组必须是SharedArrayBuffer支持的整数类型化数组。我们建议扩展所有接受数组/索引的Atomics方法，使其改为接受对象和属性名称。由于索引是一个属性名称，这不会改变已为SharedArrayBuffer使用此API的代码的行为。这也意味着，目前接受整数值（用于存储或与类型化数组中的元素进行比较）的Atomics方法，在使用普通JavaScript属性时，现在将能够接受任何JavaScript值。Atomics.wake、Atomics.wait和Atomics.compareExchange足以仅使用一个JavaScript属性来实现任何锁。

此外，我们建议添加一个Lock API

let lock = new Lock();
lock.hold(function() { /* ...perform work with lock held... */ });

主线程上的锁定可以通过Promises实现

lock.asyncHold().then(function() { /* ...perform work with lock held... */ });

这之所以有效，是因为每个线程都有自己的运行循环。我们还可以添加一个Condition API

let cond = new Condition();
cond.wait(lock); // Wait for a notification while the lock is temporarily released.
// ...
cond.asyncWait(lock).then(function() { /* ...perform work with lock reacquired... */ });
// ...
cond.notify(); // Notify one thread or promise.
// ...
cond.notifyAll(); // Notify all threads and promises.

Condition.prototype.wait会在等待之前释放你传递给它的锁，并在返回之前重新获取它。异步变体将结果Promise与条件变量关联起来，这样如果条件被通知，Promise将在当前线程上被履行。

使用Thread.current和WeakMap，任何人都可以实现线程局部变量。尽管如此，底层运行时有时可以做一些更巧妙的事情。我们不希望所有JavaScript程序员都知道如何使用WeakMap实现线程局部变量。因此，我们提出一个简单的API：

let threadLocal = new ThreadLocal();
function foo()
{
    return threadLocal.value;
}
new Thread(function() {
    threadLocal.value = 43;
    print("Thread sees " + foo()); // Will always print 43.
});
threadLocal.value = 42;
print("Main thread sees " + foo()); // Will always print 42.

最后，我们希望让用户能够轻松地声明对象停留在单个线程上

var o = {f: "hello"}; // Could be any object.
Thread.restrict(o);
new Thread(function() {
    console.log(o.f); // Throws ConcurrentAccessError
});

任何被Thread.restrict限制的对象，如果由非调用Thread.restrict的线程执行任何可代理操作，都应抛出ConcurrencyAccessError。

内存模型

处理器和编译器喜欢重排内存访问。处理器和编译器都喜欢提升从内存加载的操作。这是因为以下代码

let x = o.f
o.g = 42
let y = o.f

可能会被编译器或处理器转换为

let x = o.f
o.g = 42
let y = x

实际上，这意味着加载到y的操作被移到了存储到o.g的操作之上。处理器将动态地执行相同的优化，通过缓存o.f的加载结果并在第二次加载时重用缓存的结果。

处理器和编译器喜欢下沉存储到内存的操作。这是因为以下代码

o.f = 42
let tmp = o.g
o.f = 43

可能会被编译器或处理器转换为

let tmp = o.g
o.f = 43

这“就像是”o.f = 42语句被移到了o.f = 43之前。即使编译器不执行这种转换，处理器也可能缓冲存储并在方便时执行它们。这也可能意味着o.f = 42可能会在let tmp = o.g之后执行。

对于我们的初步方案来说，最合理的做法是遵循现有的SharedArrayBuffer内存模型。使用SharedArrayBuffer已经可以编写具有有限非确定性行为的多线程代码，我们不会完全阻止此类代码。但是JavaScript的对象比缓冲区复杂得多，因此在面临竞争时保证JS对象模型的基本不变性是非同小可的。我们建议修改JavaScript对象存储的操作原子执行。原子性意味着，如果许多线程并发执行这些操作，那么每个操作的行为都将如同它们都在某个序列中执行而没有并发性。JS可以对对象执行的每个底层操作都应该是原子的：

添加属性。
删除属性。
获取属性值。
设置属性值。
更改属性配置。
快照属性名集合。

这并不总是意味着表达式o.f是原子的，因为这个表达式可能做的远不止加载属性值。特别是：

如果o.f是o上的直接普通属性，那么它是原子的。
如果o.f是原型访问，那么加载原型与从原型加载f是分开的。
如果o.f是一个getter，那么加载getter是一个步骤（如果getter直接在o上，这将是原子的），但调用getter不是原子的，因为getter可能执行任意代码。

我们建议低级对象操作是原子的。某些操作，例如获取和设置属性值，可能使用允许重排序的硬件原语实现。我们建议允许get/set访问相互重排序，但须遵循与SharedArrayBuffer的get/set访问相同的内存模型。虽然我们的初步方案确实允许竞争和一些内存模型怪异现象，但它不允许JavaScript对象模型的不变性被破坏。对于任何由并发JS程序创建的堆，都应该能够编写一个创建不可区分堆的顺序JS程序。

最后，我们建议并发JS堆的内存管理应与其他支持垃圾回收的多线程语言一样。简单来说，垃圾回收必须以原子方式进行，并且只能在明确定义的安全点发生，例如循环回边、分配点以及调用不触及堆的本地代码期间。这一要求可以通过诸如HotSpot或MMTk等流行的垃圾回收算法来满足。它也适用于经典的标记-清除和半空间算法，甚至在没有全局 stop-the-world阶段的垃圾回收器中也适用，包括那些完全无锁，甚至无需停止线程来扫描其堆栈的垃圾回收器。WebKit的Riptide GC由于我们的JIT线程可以访问堆，因此已基本支持多线程。

与DOM的交互

将并发性扩展到所有JavaScript将很困难；将其扩展到所有DOM将更加困难。我们对线程进行了足够多的推理，以便DOM能够使这个初步方案有用。

我们建议，默认情况下，DOM对象在响应来自非主线程的任何可代理操作时，会抛出ConcurrentAccessError，就如同主线程已对它们调用了Thread.restrict一样。

然而，少数对象必须允许并发访问，以使语言行为正常。例如显而易见的

new Thread(function() { console.log("Hello, threads!"); });

需要对DOM对象进行并发访问。在WebKit中，DOM全局对象负责存储window的变量状态。全局对象的普通JS属性（包括console、Object等）必须可供并发线程访问，因为这些属性是脚本的全局变量。来自其他线程对全局对象的特殊属性或全局对象原型属性的访问可能会抛出错误。非主线程尝试向全局对象添加新属性或从中删除属性也可能抛出错误。这些限制意味着在WebKit中，处理DOM全局对象有限的并发属性访问类型，并不比处理普通JS对象的相同访问困难多少。

此外，命名空间对象，例如console，可以被并发线程访问，因为它们可以直接使用JS对象模型。没有理由将它们限制在主线程上，并且由于console对于调试的实用性，它能够被访问很重要。

初步方案总结

本节提出了一个用于JavaScript中线程化的初步API。这个API足够强大，可以实现自定义同步原语。它也足够强大，允许执行存在竞争的程序，但它不允许竞争破坏语言。线程足够通用，可以在它们之上实现许多其他类型的编程模型。

在WebKit中实现并发JS

本节展示了我们如何在不禁用JavaScriptCore任何基本性能优化的情况下，实现基于线程的初步方案。我们的方案旨在实现接近零的开销，即使是在多线程读写同一对象的程序中也是如此。

JavaScript与Java和.NET等已支持线程的语言有很多共同点。以下是这些语言与JavaScript的一些共同之处：

像JavaScript一样，这些语言使用基于追踪的垃圾回收器。我们的GC大部分支持多线程，因为JIT线程已经允许读取堆。最大的缺失部分是线程局部分配，它实现了并发分配。对于我们的GC来说，这意味着每个分配器都有一个独立的FreeList。我们的GC有固定数量的分配器，并且我们已经有了快速的线程局部存储，因此这将是一个机械性的更改。
像JavaScript的实现一样，这些语言的实现也使用多层JIT和可能的解释器。我们的WebAssembly VM已经支持从BBQ（快速构建字节码）到OMG（优化机器码生成）的多线程分层提升。我们不担心JavaScript也能做到这一点。
像JavaScript的实现一样，这些语言的实现也使用内联缓存来加速动态操作。我们将不得不对内联缓存进行一些更改以支持并发性，我们将在本文后面的部分中描述这些更改。这不是添加并发性最困难的部分，因为它不是新领域——以前已经做过。

这些相似之处表明，许多已用于使Java虚拟机支持并发的技术可以被重用以使JavaScript并发。

困难之处在于JavaScript动态重新配置对象的能力。虽然Java和.NET拥有固定大小的对象（一旦分配，对象大小不变），JavaScript对象往往是变长的。这些静态类型语言中的并发性依赖于以下事实：对固定大小对象的并发访问，在机器指针宽度范围内，默认是原子的（因此，64位系统默认原子执行64位属性访问）。Java和.NET中的指针值是指向存储对象数据的连续内存块的地址，并且只需要一些地址算术（如添加偏移量）和一条内存访问指令即可读/写任何字段。即使内存模型允许令人惊讶的重排序，同一字段（或同一对象的不同字段）的竞争访问指令也绝不会损坏整个对象或导致崩溃。另一方面，JavaScript的变长对象意味着在某些情况下对象访问需要多条内存访问指令。默认情况下，涉及多次内存访问的操作序列不是原子的。在最坏的情况下，VM可能会因为内部对象状态损坏而崩溃。即使这没有发生，竞争也可能导致写入丢失或发生时间旅行（先写入A再写入B到某个字段，可能导致读取该字段时先看到A，然后是B，然后又是A）。

在我们的初步方案中，并发JavaScript意味着添加新属性、更改属性值、读取属性和删除属性等基本操作都原子地进行。任何竞争都不应导致VM崩溃、写入丢失或属性值出现时间旅行。

我们提出了一种算法，该算法允许大多数JavaScript对象访问实现无等待，并且与我们现有的串行JS实现相比，只需最小的开销。无等待操作在不阻塞的情况下执行，并且无论竞争如何，都在有限的步骤内完成。该算法借鉴了实时垃圾回收、锁定算法和类型推断的思想。我们计划采用分层防御来应对并发带来的开销：

我们建议使用我们现有的基于多态内联缓存的类型推断系统来推断对象（及其类型）的宽松线程局部性概念，我们称之为转换线程局部性（TTL）。TTL对象将使用与今天相同的对象模型，并且对这些对象的访问将享有接近零的开销。TTL不意味着真正的线程局部性；例如，即使被多个线程读写的对象也可能被推断为TTL。
我们建议对未能通过TTL推断的对象使用分段对象模型。这将在属性访问的快速路径中引入额外的加载指令和一些算术运算。我们担心单凭此技术不足以满足我们的性能目标——但由于分段对象模型仅对那些未能通过TTL推断的对象（或对象类型）进行“外科手术式”应用，我们怀疑其净成本将足够小，具有实用性。
对于那些不受分段对象模型益处的非TTL对象操作，将使用锁。在开发Riptide并发GC期间，我们为每个对象添加了一个内部锁。该锁仅占用2位，并允许锁定/解锁的快速路径仅需一个原子比较并交换（CAS）和一个分支。

在深入细节之前，我们首先为该拟议系统将运行的硬件设定一些预期。然后我们逆向描述这个提案。我们考虑仅使用每对象锁定的成本。接着我们回顾现有的JSC对象模型，并描述在此模型中哪些操作已经原子化。接下来我们引入分段蝴蝶，它们是允许动态重新配置对象的关键。然后我们展示我们的TTL推断将如何使我们能够将现有对象模型用于JavaScript堆的大部分。本节随后考虑了一些悬而未决的问题，例如如何并发地进行内联缓存、可调整大小的数组如何适应TTL和分段蝴蝶、如何使用局部优化器锁（LOL）处理大量线程，以及最后如何处理非线程安全的本地状态。

硬件预期

本文描述了如何将JavaScriptCore转换为支持并发JavaScript。JSC目前已针对64位系统进行优化，我们现有的大部分并发支持（并发JIT、并发GC）也仅在64位系统上工作。本节简要总结了我们期望64位系统能够使用我们方案的条件。

JSC针对x86-64和ARM64进行了优化。此方案假设两者中较弱的内存模型（ARM64），并假定以下原子指令足够廉价，以至于将其作为锁定的优化是可行的：

64位加载和存储默认是原子的。我们预期这些访问可能会在其他访问周围重新排序。但我们也预期，如果内存访问指令B对内存访问指令A存在数据流依赖，那么A将始终在B之前执行。例如，在像a->f->g这样的依赖加载链中，a->f将始终在_->g之前执行。
64位CAS（比较并交换）。JSC使用64位字来表示JavaScript属性以及对象头中两个重要的元数据字段：类型头和蝴蝶指针。我们希望能够原子地对任何JS属性以及对象头中的任一元数据属性进行CAS操作。
128位DCAS（双字比较并交换）。有时，我们希望对JS对象内部的所有元数据进行CAS操作，这意味着同时对64位类型头和相邻的64位蝴蝶指针进行CAS。

每对象锁定

JSC中的每个对象都已拥有一个锁，我们用它来将某些基本JavaScript操作与垃圾回收器同步。我们可以使用这个锁来保护需要在JavaScript线程之间同步的任何操作。本文的其余部分将讨论允许我们避免此锁的优化。但让我们精确地考虑锁的成本。我们内部的对象锁算法需要一个原子比较并交换（CAS）和一个分支来加锁，以及另一个CAS和一个分支来解锁。在最佳情况下，CAS就像执行至少10个周期。这是假设CAS成功时的摊销成本。在某些硬件上，成本要高得多。假设一个分支是一个周期，这意味着每个需要锁的对象操作至少会增加22个额外周期。一些罕见的操作已经足够昂贵，22个周期不算糟糕，但许多快速路径操作无法承受这样的开销。下面我们考虑一些操作，以及如果它们必须使用锁定，它们会受到多大影响。

添加新属性目前在优化后的快速路径上只需一次加载、一个分支和两次存储。每个操作都是一个周期，在最快的情况下总共大约4个周期。添加锁定会使其膨胀到26个周期——大约7倍的减速。在某些情况下，添加新属性可以优化到只进行一次存储。在这些情况下，添加锁定会造成23倍的性能下降。
更改现有属性的值需要一次加载、一个分支和一次存储。在最快的情况下，这需要3个周期。添加两个CAS和两个分支会使其膨胀到25个周期——8倍的减速。在某些情况下，我们可以将属性存储优化到只需一条存储指令。对其进行锁定则会造成23倍的性能下降。
加载现有属性的值需要一次加载、一个分支和另一次加载。添加锁定会导致8倍的减速，或者在我们只优化到一条加载指令的情况下是23倍的减速。
删除属性本身就很慢。我们乐意对其进行加锁。删除属性相对罕见，但我们必须支持它。
字典查找——JSC术语中指那些我们动态执行，不使用任何内联缓存或编译器优化的属性访问——将因锁定而产生少量开销。这些代码路径本身已经足够昂贵，因此添加锁定不太可能成为问题。
属性集快照不变。JSC中并发线程已经可以对任何对象的属性集进行快照，这得益于我们为并发垃圾回收实现的锁定。

尽管删除等某些操作已经足够昂贵，以至于加锁不是问题，但我们认为将如此巨大的成本添加到JavaScript对象访问的快速路径中是不切实际的。由此产生的编程语言会太慢。

设计一个快速的并发JS实现需要引入新的属性访问算法，这些算法可以并发运行，除极少数情况外不需要任何锁定。在接下来的部分中，我们将描述这样一种算法。首先，我们回顾JavaScriptCore的对象模型。然后，我们展示JavaScriptCore对象模型已经表现得像具有固定大小对象的情况；这些情况绝不需要锁定。接下来，我们展示一种称为分段蝴蝶的技术，它允许实现大多数无等待的并发对象访问。单凭这种技术，对我们来说仍然太昂贵。因此，我们展示如何推断哪些对象类型是转换线程局部（TTL）的，以避免在对象转换时进行同步。这使我们能够将平面蝴蝶（我们现有的对象模型）用于大多数对象。然后，我们描述如何处理删除、字典查找、内联缓存、数组和线程不安全的对象。

JavaScriptCore对象模型

JavaScriptCore的对象模型允许四种状态，每种都是可选的：

使用普通C++对象表示的原生状态。
我们静态猜测对象会具有的命名对象属性（如o.f）的数据。
动态添加的命名对象属性数据，这迫使我们更改对象的大小。
索引对象属性的数据。这些属性可以通过多种方式改变对象的大小。

前两种状态不涉及对象大小调整。后两种状态需要调整大小。在JSC中，固定大小的状态直接存储在对象的cell中。cell是对象指针所指向的地方。在cell中，有一个蝴蝶指针，可用于在蝴蝶中存储动态分配和可调整大小的状态。蝴蝶在蝴蝶指针指向的位置的左侧存储命名属性，作为out-of-line slots，并在右侧存储索引属性，作为array elements。这些位置中的每一个都可以存储一个带标签的JavaScript值，该值可以是数字、指向另一个cell（表示字符串、符号或对象）的指针，或一个特殊值（true、false、null或undefined）。

每个对象都拥有一个结构，其中包含用于将属性名映射到对象槽的哈希表。对象通常与其他看起来相似的对象（例如，具有相同属性和相同顺序等要求）共享同一个结构。该结构通过一个32位索引引用结构表。我们这样做是为了节省空间。索引和单元格状态字节有一些备用位。我们在索引字节中使用了两个备用位来支持每对象锁定。蝴蝶指针中也有备用位，因为在64位系统上，指针不需要所有64位。

蝴蝶是可选的。许多对象没有蝴蝶。当分配蝴蝶时，两边都是可选的。蝴蝶的左侧容纳了行外槽位。只分配这部分是可能的；在这种情况下，蝴蝶指针将指向蝴蝶内存末尾右侧8字节处。蝴蝶的右侧容纳了数组元素和数组头。公共长度是array.length报告的长度，而向量长度是已分配的数组元素槽位的数量。

额外优势

在这个对象模型中，对单元格内任何内容的访问默认都是原子的，就像Java中对对象的访问默认是原子的一样。这是一个重大优势，因为我们的优化器通常能够成功地将最重要的对象字段内联到单元格中。主要依赖于最终存储在单元格内数据的并发JS程序，与它们的串行等效程序相比，几乎不会产生任何开销。

此外，如果我们知道蝴蝶永远不会再次重新分配（即蝴蝶指针是不可变的），那么我们可以直接访问它，没有任何问题。这些访问默认是原子的。

或者，如果我们知道只有当前线程会调整蝴蝶的大小，而所有其他线程只会读取它，那么对蝴蝶的访问将默认是原子的。

当一个线程尝试转换对象（即添加属性和/或重新配置蝴蝶），而其他线程正在写入该对象（或也正在转换该对象）时，就会出现问题。如果我们在并发设置中使用当前的对象访问实现，一个线程上的转换可能会导致竞争，从而产生不符合我们提出的规范的行为。

由另一个线程进行的写入可能会消失或出现时间旅行。这种竞争发生的原因是，正在转换的线程可能首先完成蝴蝶的复制，然后转换对象，而另一个线程在这两个步骤之间对对象进行更多写入。如果第三个线程通过重复读取正在写入的字段状态来观察正在发生的事情，那么它将首先看到任何写入之前的状态，然后看到写入，然后一旦转换完成，它将再次看到原始状态。
同时执行的两次转换可能导致蝴蝶指针和对象的类型不匹配。蝴蝶的格式由对象头中不在与蝴蝶指针相同的64位字内的字段决定。我们不能允许蝴蝶和头部不同步，因为这会导致内存损坏。
即使不涉及蝴蝶，同时执行的两次转换也可能导致一些轻微的堆损坏。如果涉及内联属性的转换分两步进行——首先，更改对象的类型，然后，存储新属性——那么添加两个不同属性的两次竞争转换可能导致添加了一个属性，其值最终成为另一个属性的预期值。例如，o.f = 1和o.g = 2之间的竞争可能导致o.f == 2和"g" in o == false。

在下一节中，我们将展示如何创建一个没有此类竞争但会付出一定代价的对象模型。之后，我们将展示如何使用TTL推断来在大多数情况下使用我们现有的对象模型，即使在线程之间共享对象的程序中也是如此。

分段蝴蝶

转换对象意味着分配一个新的蝴蝶，并将旧蝴蝶的内容复制到新蝴蝶中，而其他线程可能正在读取或写入旧蝴蝶。我们希望这个复制过程看起来像是在一个原子步骤中发生的。在实时垃圾回收器的背景下，已经有大量研究支持对象的并发复制。我们建议使用的方法基于Schism实时垃圾回收器的arraylet对象模型。本节回顾了Schism arraylet对象模型，然后展示了它如何用于蝴蝶转换。

Schism试图解决实现一个复制式垃圾回收器的问题，其复制阶段与应用程序完全并发。它的基础是观察到，如果对象是不可变的，那么并发地复制对象与其他线程访问对象很容易。只有当对象可以被其他线程写入时，这才会变得困难。Schism通过将可变状态装箱到小的固定大小的片段中（论文中为32字节），解决了并发复制可变对象的问题。被复制的对象是作为查找片段索引的主干。所有对象访问都使用额外的间接寻址来查找包含正在访问的数据的片段。主干是不可变对象，因为它们指向的片段从不移动。

WebKit在WTF::SegmentedVector类模板中也使用了类似arraylets的东西。我们用它来防止向量调整大小时C++对象需要移动。我们也用它来实现JSGlobalObject的变量存储（用于全局作用域中的var语句）。arraylets这个术语是由Bacon、Cheng和Rajan提出的，他们用它来控制Metronome垃圾回收器中的碎片化。大量arraylet研究表明，额外的间接寻址开销很高（通常为10%或更多）。也就是说，如果你通过增加一个额外的间接寻址使每次数组访问的成本翻倍，那么程序的总运行时间将增加10%。

**分段蝴蝶。**分段蝴蝶包含一个主干（可调整大小但只包含不可变状态）和零个或多个片段（不可调整大小但可变）。将可调整大小的状态与可变状态分离以实现并发布局更改是并发垃圾回收中一项成熟的技术。片段的形状与未分段蝴蝶的形状匹配，我们将利用这一点进行一些额外的优化。

我们可以将这个技巧用于蝴蝶。一个分段蝴蝶有一个主干，它包含指向包含可变数据的片段的指针。如果我们需要添加新属性并且这些属性无法容纳在现有片段中，我们可以增长主干并分配更多片段。增长主干意味着重新分配它。我们可以安全地分配一个新的主干，并将旧主干的内容memcpy到新主干中，因为主干的内容永不改变。在这个世界中，当蝴蝶正在转换时，没有写入会丢失或经历时间旅行。与转换竞争的访问要么使用旧主干访问片段，要么使用新主干访问片段；由于两个主干将包含转换前存在的属性的相同片段地址，因此每种可能的交错都会导致线程读写相同的片段。

实现分段蝴蝶最自然的方法可能是像Schism中那样使用32字节的片段，因为这对我们的GC来说也是一个最佳点。向量长度将位于蝴蝶主干内部，因为这是该主干的一个不可变属性。向量长度允许主干自行识别其右侧的大小。公共长度是可变的，所以我们希望将其放入其中一个片段中。请注意，第一个片段还包含旧向量长度。当我们使用分段蝴蝶时，此属性是未使用的。它允许我们通过让主干指向平面蝴蝶的切片来将平面蝴蝶转换为分段蝴蝶；我们将在后面的部分中更详细地讨论这种优化。

这仍然留下了并发转换的问题。转换必须重新分配主干，更改类型头中的一些数据，并存储属性值。重新分配主干是可选的，因为通常某个片段已经有备用槽位。更改类型也是可选的，例如在数组调整大小的情况下。类型头和蝴蝶可以使用DCAS（双字比较并交换；64位系统通常支持128位CAS）原子地设置。但这还不够，因为无论我们是在DCAS之前还是之后设置属性值，都会发生竞争。属性的槽位可以位于内存中的任何位置，因此无法使用CAS同时完成整个转换。

如果我们在更改其他所有内容之前设置新添加的值槽，我们面临一种竞争风险：一个线程尝试使用某个对象槽来添加字段f，而另一个线程尝试使用相同的槽来添加字段g。如果我们不小心，第二个线程可能赢得类型竞争（所以所有人都认为我们添加了属性g），而第一个线程赢得属性竞争（所以我们得到线程1为属性f设置的预期值，表现得像是线程2将其存储到了g中）。

如果我们在更改所有其他内容之后设置新添加的值槽，那么所有加载都必须处理槽可能存在“空洞”的可能性。换句话说，在任何时候，一个对象都可能声称其类型包含属性f，即使该对象尚未拥有f的值。我们可以修改语言来允许这种情况：将新属性放入对象将首先将其定义为undefined，然后存储真实值。

我们选择在转换周围设置一个锁。这个锁不是为了保护转换与其他访问之间的竞争，因为由于分段蝴蝶，这些访问默认是原子的——它是为了保护转换彼此之间不发生冲突。为了确保对象没有空洞，转换在更改类型之前存储新属性的值。转换可以使用以下算法：

分配所有需要分配的内存。
获取锁。
确定我们是否分配了正确数量的内存；如果没有，释放锁并返回步骤1。
存储新属性的值。
更改类型和蝴蝶。
释放锁。

这将导致以下成本模型：

转换的成本约为7倍，因为它们现在需要锁定。
读取或写入现有属性槽需要额外的加载。
删除和字典查找仍然有效（我们将在后面章节中展示细节）。

回想一下，arraylet研究表明，如果数组使用分段对象模型，成本会增加10%或更高。我们建议也将其用于普通属性，如果这些属性以足够巧妙的方式添加，以至于我们无法将它们内联到单元格中。安全地假设，如果我们照字面实现这一点，我们将至少承担10%的性能下降。我们希望实现接近零的开销。下一节将展示我们认为如何实现这一目标。

转换线程局部性和平面蝴蝶

分段蝴蝶只在以下情况有必要：

分配对象的线程以外的某个线程尝试转换该对象。
分配对象的线程尝试转换它，并且其他线程可能正在写入它。

当我们知道这些情况尚未发生时，我们可以使用平面蝴蝶——我们现有的对象模型。本节描述了一种混合对象模型，它根据是否检测到可能的写-转换竞争来使用平面蝴蝶或分段蝴蝶。这种对象模型还允许我们在进行多次转换时避免锁定。

在64位系统上，蝴蝶指针包含48位的指针信息，其高16位为零。16位足以存储：

分配对象的线程ID。我们称之为蝴蝶TID。
一个位，指示除了分配线程之外的任何线程是否尝试写入蝴蝶。我们称之为蝴蝶共享写入（SW）位。

某些系统有超过48个指针位。在后面的章节中，我们将展示即使我们不得不使用更少的位，如何使这个方案仍然有用。此外，如果我们真的想要16个备用位，我们可以将蝴蝶分配限制在较低的2⁴⁸地址。

假设这些位的编码如下：

static const uint16_t mainThreadTID = 0; // Occassionally, we can optimize a bit more for the main thread.
static const uint16_t notTTLTID = 0x7fff; // For when the thread is no longer transition-thread-local.

static inline uint64_t encodeButterflyHeader(uint16_t tid, bool sharedWrite)
{
    ASSERT(tid <= notTTLTID); // Only support 2^15 tids.
    return (static_cast<uint64_t>(tid) << 48)
         | (static_cast<uint64_t>(sharedWrite) << 63);
}

static inline uint64_t encodeButterfly(Butterfly* butterfly, uint16_t tid, bool sharedWrite)
{
    return static_cast<uint64_t>(bitwise_cast<uintptr_t>(butterfly))
         | encodeButterflyHeader(tid, sharedWrite);
}

当TID与当前线程匹配时，我们可以使用平面蝴蝶——我们现有的对象模型。我们设置SW位并使用一个特殊TID值（所有位都置位）来指示蝴蝶是分段的。本节展示了如何使用这些位，以便在我们知道不会发生转换竞争时，随时允许使用平面蝴蝶。我们称之为转换线程局部性推断。

任何时候，当一个线程尝试写入蝴蝶并且TID与当前线程匹配时，它可以简单地写入蝴蝶而无需进行任何特殊操作。

任何时候，当一个线程尝试写入蝴蝶，并且TID不匹配，但SW位已设置时，它也可以简单地写入蝴蝶。

任何时候，当一个线程尝试读取蝴蝶时，它只需检查TID以确定读取是否应该分段（额外间接寻址）或不分段。

任何时候，如果读或写遇到TID = notTTLTID且SW = true，它就知道要使用分段对象模型。

以下情况需要特殊处理：

TID标识的线程以外的线程尝试写入蝴蝶且SW位尚未设置。在这种情况下，它需要设置SW位。这并不意味着蝴蝶需要变为分段。它只意味着SW位必须设置，以便拥有线程未来任何尝试转换蝴蝶的操作都会触发向分段蝴蝶对象模型的转换。
TID标识的线程以外的线程尝试转换蝴蝶。在这种情况下，它需要设置SW位和所有TID位，并执行分段蝴蝶转换。我们将在下面详细描述此过程。
一个线程尝试转换一个已设置SW位的蝴蝶。这也需要进行分段蝴蝶转换。
即使是TID = current且SW = false的转换也需要锁定，以确保在转换期间这些假设不会被违反。

接下来的章节将展示进一步的改进，以进一步降低开销。首先，我们考虑如何避免在每次操作时都检查TID和SW位。接下来，我们展示如何使用结构监视点来避免在最常见的转换上加锁。然后，我们展示如何处理数组大小调整。最后，我们更详细地解释平面蝴蝶如何转换为分段蝴蝶。

快速检查TID和SW位

本节将展示如何通过简单地扩展JavaScriptCore已使用的优化，使并发JS在许多最重要的用例中与串行JS一样快。

JSC使用内联缓存来优化堆访问的代码。我们使用内联缓存来访问命名属性（如o.f）和数组访问（如a[i]）。

具有相同偏移量处相同属性的对象通常会共享相同的结构，该结构由对象类型头中的32位标识。如果属性访问倾向于看到相同的结构，那么我们将为该属性访问生成新的机器码，该机器码会检查对象是否具有预期的结构，然后直接访问属性。投机失败会导致内联缓存的重新编译。如果内联缓存长时间保持稳定（没有太多重新编译），并且包含它的函数符合优化JIT编译的条件，那么优化JIT编译器可能会直接在其IR中表达内联缓存的代码，这会产生两种结果：如果结构检查失败（导致优化代码执行突然终止），则分支到OSR退出；并且内联缓存的所有代码（结构检查、内存访问和任何其他步骤）都符合我们DFG和B3 JIT编译器管道的低级优化条件。我们的编译器擅长使类型稳定的JavaScript属性访问表现出色。

数组访问使用类似的技术来检测对象是否具有数组元素，以及如果具有，它们的格式如何。我们根据数组元素的用法支持多种存储类型。内联缓存检测每次数组访问正在访问哪种类型的数组，然后我们发出针对该类型数组访问进行推测的代码。

我们已经使用的另一种技术是虚拟内存。例如，我们的WebAssembly实现使用虚拟内存技巧免费检查线性内存访问的边界。我们可以使用POSIX信号处理程序或Mach异常来捕获页面错误。处理程序将知道故障发生时的精确机器状态，并有能力将执行转移到它喜欢的任何状态。WebAssembly使用它来抛出异常，但我们可以用它将控制流转移到处理内存访问通用情况的慢速路径。本质上，这意味着如果我们可以将被检查的条件表达为导致虚拟内存系统发出页面错误的东西，我们就可以节省安全检查的周期。并发JS将需要结合内联缓存和虚拟内存技巧，以使TID和SW检查成本低廉。

内联缓存意味着为每个属性访问发出不同的代码，然后随着我们了解有关此属性访问可能执行的新信息，可能会多次重新编译每个属性访问。内联缓存能够获得有关每个属性访问行为的极其精确的信息，因为我们总是发出一个只能处理到目前为止我们所见到的那些情况的快速路径访问。我们通过记录我们所知道的那些未能通过快速路径的访问的所有信息来学习新信息。然后将失败访问的完整日志进行LUB（最小上界）合并，以创建一组最小的AccessCase。我们可以通过考虑特定访问点可能特殊以及因此可以特殊优化的方式，为新型属性访问（例如必须检查TID和SW位的访问）实现优化。下面是可能遇到的条件列表，以及内联缓存如何测试此条件并处理它的策略。

可能许多对象访问总是看到TID = current和SW = false。这些访问在访问蝴蝶之前可以简单地从蝴蝶中减去encodeButterflyHeader(currentTID, 0)。如果推测错误，虚拟内存子系统将因非零高位而发出页面错误。我们可以将其捕获为Mach异常或POSIX信号，并将执行转移到慢速路径。这种常量的减法通常可以直接编码到后续的蝴蝶访问指令中。因此，与当前相比，这些类型的访问在并发JS中不会经历任何开销。请注意，此优化不适用于转换，转换必须安装新的蝴蝶，同时原子地断言没有发生任何不好的事情——我们将在下面进一步讨论。请注意，此优化略微偏爱主线程（以及所有单线程程序），因为如果currentTID = 0，则我们无需添加任何内容。
可能许多对象访问总是看到TID = current且SW = true。这些可以与前一种情况进行相同的优化。这种状态适用于我们已知可以被多个线程写入的对象，但这只发生在当前线程上次转换对象之后。
可能许多对象读取会看到TID != notTTLTID且SW = anything。这些只需检查蝴蝶的高位是否不是notTTLTID。这可以通过一次比较/分支完成。除此之外，它们可以像在我们当前引擎中那样精确地进行。
可能许多对象写入会看到TID != notTTLTID且SW = true。这意味着该对象正在被多个线程写入。我们也在写入它，但我们不需要设置SW位，因为它已经设置。这个检查也可以通过一次比较/分支完成。结合上述读取优化，这意味着共享对象的并发JS程序通常在蝴蝶访问时只会经历一个额外的周期（用于融合比较/分支）。
有时，对象写入会看到TID != notTTLTID且SW = false。这意味着必须使用DCAS来设置SW位，DCAS在断言类型头未更改的同时设置SW位。这些访问将比它们的同类更昂贵，但这只在任何线程首次写入共享对象时发生。我们的内联缓存基础设施可能会使得有时看到SW = false，有时看到SW = true（并且不一定看到TID = current但从不notTTLTID）的写入变得具有分支性：它们将有一个SW = true的快速路径和一个稍慢但仍然内联的SW = false路径。在下一节中，我们将描述当任何该结构对象的SW位首次设置时，需要调用结构上函数的优化。由于此内联缓存在生成时就知道结构，因此它可以确保结构已经得知其类型的对象可能已设置SW位。
可能有些对象访问会看到TID = notTTLTID且SW = true。根据约定，我们将认为不可能出现TID = notTTLTID且SW = false的情况（在我们的虚拟机内部，技术上可能在不“写入”的情况下转换对象，但我们仍将其视为写入）。这些访问可以在访问蝴蝶之前从蝴蝶中减去encodeButterflyHeader(notTTLTID, true)，然后它们在从蝴蝶读取时必须执行额外的加载。额外加载是必要的，因为分段对象模型：蝴蝶指针指向一个主干，我们可以使用它来找到包含我们感兴趣值的片段。这比一个额外的周期开销要多一些，因为它引入了加载-加载依赖。

这些优化留下了一个未解决的问题：转换。转换现在需要获取和释放锁。每当我们添加任何属性时，都必须这样做。在下一节中，我们将展示如何使用监视点来解决这个问题。然后，我们将描述如何实现需要从平面蝴蝶创建分段蝴蝶的转换。

监视点优化

转换很难优化。每次转换，包括那些看到TID = current的转换，都需要获取对象的内部锁，以确保它们在一个原子步骤中设置蝴蝶、调整对象的类型头并存储属性的新值。幸运的是，我们可以通过使用引擎的结构监视点基础设施显著提高转换的性能。

每个对象都有一个结构。许多对象将共享相同的结构。大多数内联缓存优化都从检查对象的结构是否与内联缓存的预期匹配开始。这意味着当内联缓存被编译时，它手中有一个指向Structure对象的指针。每个结构都可以包含任意数量的监视点集。监视点集只是一个布尔字段（开始时为有效，然后变为无效）和一组监视点。当该集合被触发（字段从有效变为无效）时，所有监视点都会被调用。我们可以向Structure添加两个监视点集：

transitionThreadLocal。只要所有具有此结构的对象都拥有TID != notTTLTID，此字段就保持有效。
writeThreadLocal。只要所有具有此结构的对象都拥有SW = false，此字段就保持有效。

这在上述内联缓存优化的基础上，实现了以下优化：

只要结构的transitionThreadLocal和writeThreadLocal监视点集都仍然有效，TID = current且SW = false的转换就可以像在我们现有引擎中一样进行。这意味着在转换对象时无需进行任何额外的锁定甚至CAS。即使其他线程正在并发读取对象，这也有效。即使在构建一个最终会被其他线程读写的对象时，这也有效，因为在这种情况下，writeThreadLocal监视点集仅在用于构建对象的最终转换的目标结构上触发。上次转换可以在没有锁定的情况下进行，因为转换源的监视点集仍然有效。
如果结构的transitionThreadLocal监视点集仍然有效且已安装监视点，则可以省略所有对TID != notTTLTID的检查。
如果结构的writeThreadLocal监视点集仍然有效且已安装监视点，则可以省略所有对SW == false的检查。

我们可以省略TID != notTTLTID和SW == false检查这一事实意味着，对这些对象的读写实际上不必检查任何东西；它们只需要遮蔽蝴蝶的高位。

最重要的是，这意味着只要所涉及的结构具有有效的transitionThreadLocal和writeThreadLocal监视点集，在分配对象的同一线程上发生的转换就不需要任何锁定。我们的引擎会动态推断结构，使其与创建这些对象的代码紧密相关。因此，如果你编写一个构造函数，向this添加了一堆字段但没有使其逸出，那么构造函数中发生的转换链所对应的所有结构都将具有有效的transitionThreadLocal和writeThreadLocal监视点集。为了确保对象继续拥有平面蝴蝶，你必须要么永远不动态地向对象添加属性，要么除了构建对象的线程之外，永远不在任何其他线程上写入该对象。遵循这些规则的对象将几乎不产生并发开销，因为属性访问在快速路径上最多只会增加一条指令（一个掩码）。

观察点以及导致其触发的操作将在安全点（safepoint）下执行：如果我们执行某个操作，发现它必须使观察点失效，那么它将在所有其他线程都停止的情况下（如同进行垃圾回收一样）执行该操作。这意味着，如果某些优化代码正在执行涉及某些结构的非原子转换，并且其他某个线程尝试写入或转换使用这些结构的对象，那么在优化代码到达安全点并失效之前，它实际上不会执行写入。大多数情况下，即使在优化JIT编译器尝试安装任何观察点之前，观察点集也会告诉我们它们已经失效。我们预计在稳定状态下，观察点失效的情况很少。

总结一下，如果我们的优化器能够在分配时猜测您将向对象添加哪些属性，那么您的对象访问成本模型根本不会改变，因为内联属性免费获得了并发性。如果您确实拥有非内联属性，那么只要对象仅由创建它的线程写入（并且任何人都可以读取），或者创建后没有向对象添加新属性（在这种情况下，任何人都可以读取和写入它），它们的性能将几乎与现在完全相同（偶尔，计算蝶形访问时会涉及额外的算术指令）。如果您打破这种模式，那么转换成本将增加约7倍，所有其他对象访问成本将增加2倍。这种减速将极其精确：只有访问分段蝶形结构的属性访问才会经历这种减速。该系统旨在让您动态、并发地向对象添加内容，我们希望如果您适度地这样做，性能不会有太大变化。

数组

数组元素访问将像命名属性访问一样从TTL中受益

对TTL数组的访问速度将与现在大致相同。
对非TTL数组的访问将需要一次额外的间接寻址。

我们对数组转换做了一些特殊处理。JavaScriptCore中许多数组转换已经使用了锁定，因为它们需要避免与垃圾回收器发生竞争。为剩余的数组转换添加锁定可能会导致性能问题，因此本节考虑一种替代方案。

响应越界存储或像array.push之类的操作而调整数组大小是最常见的数组转换类型。幸运的是，这种转换不会改变对象的类型头中的任何内容——它只改变蝶形指针。蝶形结构是否包含数组元素体现在其结构中。因此，我们只需对蝶形指针使用CAS（Compare-and-Swap）操作，然后规定：即使对象锁已被持有，对包含数组元素的对象的蝶形指针的任何更改也需要CAS。由于数组结构的transitionThreadLocal和writeThreadLocal观察点不太可能保持完整（任何共享数组的使用都会使它们失效，因为数组共享结构），我们预计即使是TTL数组上的转换，在一般情况下也必须使用CAS。这种蝶形指针CAS足以确保同时尝试使数组变为非TTL的操作不会被我们的调整大小操作混淆。

一次用于数组调整大小的CAS操作可能足够便宜，以至于实用。相对于当前调整大小的成本（涉及分配、复制数据和初始化新分配的内存），CAS可能相对便宜。

既有命名属性又有数组元素的对象现在必须在涉及命名属性的某些转换上同时使用锁定和CAS。幸运的是，同时拥有数组元素和命名属性的对象非常不常见，所以我们增加一点它们的命名属性转换成本可能没问题。

从扁平到分段的快速转换

将扁平蝶形结构转换为分段蝶形结构需要一种特殊类型的转换。幸运的是，这种转换成本很低。蝶形片段只包含数据。它们看起来就像扁平蝶形结构有效载荷的片段（固定大小的切片）。因此，我们可以通过分配一个主干（spine）并将其片段指针指向原始扁平蝶形结构，从而将扁平蝶形结构转换为分段蝶形结构。

在蝶形结构转换为分段期间，对扁平蝶形结构的任何读写，对分段蝶形结构的用户来说，都像是发生在片段上。换句话说，尽管有些线程可能会错误地认为蝶形结构仍然是扁平的，但即使蝶形结构已经分段，他们对该蝶形结构的访问仍然是可靠的。

为了使这正常工作，需要确保分段蝶形结构的片段与它们转换自的扁平蝶形结构共享相同的内存布局。因此，第一个数组片段包含公共长度和旧的向量长度；它将永远记住扁平蝶形结构使用的向量长度，而实际的向量长度将在分段蝶形结构的主干中。这确保了如果扁平蝶形数组访问与扁平到分段转换之间存在竞争，那么扁平蝶形访问将正确知道扁平蝶形的大小，因为其向量长度不会改变。为了使对象模型对齐，我们还在非内联片段中反向存储非内联属性，以匹配扁平蝶形结构的做法。

只要扁平蝶形访问在转换发生之前加载了它们的蝶形指针，这就有效。如果它们稍后加载，那么它们的TID检查将失败，可能是以访问蝶形结构时发生页面错误的形式。

删除和字典查找

JavaScriptCore尝试尽可能让对象共享结构。这依赖于结构的两个特性：

结构是不可变的。
当需要新结构时，我们通常对其进行哈希共享（hash cons）。

如果它确实导致对象重用结构，这是一个很好的优化。但有些对象无论虚拟机如何尝试，都将拥有一个独特的结构。JavaScriptCore尝试检测何时发生这种情况，并将对象置于字典模式。在字典模式下，结构与对象之间存在1:1映射。此外，结构变为可变。添加和删除属性意味着同时编辑结构和对象。

删除与字典模式密切相关，因为删除会立即将对象置于字典模式。

对字典的修改已经需要持有结构的锁。这是支持并发JIT和并发GC所必需的。

为了支持并发JS，我们只需要进行以下更改：

从字典读取需要持有结构的锁，以防其他线程正在更改字典。
对象进入字典模式之前添加的属性必须通过删除进行特殊处理。

我们不担心对字典的所有读取都获取锁带来的性能损失。读取字典本身就相对昂贵。

现有安全转换对象的机制将自然支持转换到字典模式。通常，字典转换不涉及删除属性。它们发生在我们检测到程序正在向对象添加过多属性，以至于它作为字典可能会表现得更好时。在这种情况下，其他线程可能正在访问此对象而未持有任何锁的事实无关紧要。对于非字典对象，我们要求只有转换才获取锁。读写涉及检查对象类型、加载蝶形结构，然后访问蝶形结构的不同步骤。但是，如果在字典转换之前添加的属性都没有被删除，那么其他线程在访问这些旧属性时进行竞争是没问题的。我们称之为迟滞访问现象。尽管这些迟滞访问不进行任何锁定，但它们是正确的，原因与对象成为字典之前正确的原因相同。这个问题取决于蝶形对象模型，它将是扁平或分段的，取决于对象是否仍是TTL。字典模式独立于TTL推断和蝶形结构运行。

但是，如果字典转换之前添加的任何属性被删除，那么我们必须特殊处理此删除操作。通常，删除会使已删除的槽位变得可重用。我们不能在这里这样做，因为这样对某些已删除属性f的迟滞读取可能会最终读取到某些新添加属性g的值。或者，对某些已删除属性f的迟滞写入可能会最终覆盖某些新添加属性g的值。如果这些属性是在字典转换之前添加的，则通过简单地不重用已删除属性释放的空间来防止这两种不良结果。

这不会导致无限内存使用。当GC（垃圾回收器）到达其安全点时，它已经知道所有内存访问都已完成。因此，最简单的实现是让GC在访问对象时更改这些已删除属性的状态。一旦GC在安全点标记了这些属性槽，将来的属性添加就可以重用这些槽位。

内联缓存

一旦我们启用并发，重新编译内联缓存变得更难，因为在更改可能正在另一个CPU上执行的代码时需要小心。我们计划对此问题进行分层防御：我们将推断代码的线程局部性，以便尽可能使用与现在相同的内联缓存；在安全的情况下，我们将缓冲内联缓存的更改；最后，如果内联缓存需要立即重置，我们将依赖安全点。

我们预计在许多程序中，内联缓存将在代码在多个线程上执行之前达到稳定状态。因此，我们计划让每个代码块跟踪其线程局部性。只要它只在一个线程上执行过，它就会记住这一点并在进入时进行检查。只要这是真的，该代码中的任何内联缓存都可以修改，而无需任何额外的同步。我们可以根据需要跟踪线程局部性，粒度可以很细；例如，它甚至可以是每个基本块。如果我们使用JavaScriptCore的CodeBlock概念作为粒度，那可能是最自然的；这大致对应于源代码中的函数。

一旦代码的线程局部性被破坏，我们可以切换到缓冲内联缓存更改。我们的PolymorphicAccess内联缓存基础设施已经缓冲了更改，因为即使我们不必进行昂贵的同步，这也是最有效的。对于可能全局执行的内联缓存，我们可以全局缓冲所有更改。例如，VM可以每毫秒执行一次安全点，将更改刷新到所有全局内联缓存。

有时，我们需要立即更改内联缓存。当发生这种情况时，我们将依赖我们使系统达到安全点的能力——即在我们可以计算每个线程状态的点停止所有线程。当线程很多时，这不是一个快速操作。Java虚拟机已经需要为类层次结构失效和偏向锁执行类似操作。根据设计，这些主动失效不太可能发生。只有在我们有分析数据表明主动失效不太可能发生时，我们才会执行可能导致主动失效的优化。

局部优化器锁

到目前为止，该算法依赖于能够将16位信息悄悄地放入蝶形指针的高位。某些硬件不允许我们这样做。例如，虚拟内存中用于全零检查的指针高位可能少于16位。如果系统只允许8个已检查的高位，那么我们将只能支持127个线程。即使并发JavaScript有127个线程的硬限制，它可能仍然有用，但这将在语言层面施加一个异常低的限制。本节展示了如何克服这个限制。

如果对象模型只能处理127个线程的线程局部性推断，那么我们可以选择让第127个线程不获得线程局部性推断，或者我们可以尝试将多个逻辑线程映射到同一个线程标识符。映射到同一个TID的线程将无法彼此并发执行。为此，我们可以借鉴Python的GIL（全局解释器锁）的思想。CPython实现一次只允许1个原生线程解释执行Python代码。它通过一个保护解释器的锁（即GIL）来实现这一点。锁定期释放和重新获取，从而呈现出并发的假象。由于我们也可以在任何可能阻塞的操作周围释放锁，我们甚至可以避免由于并发不足引起的死锁。我们可以将此技术应用于此：如果我们将线程数量限制为127个，那么我们可以有127个锁来保护JS执行。只要线程数量少于或等于127个，这个锁就不会起作用；任何时候我们尝试释放它，我们都不会做任何事情，因为锁会告诉我们没有人等待获取它。“释放和重新获取”锁实际上将是一个廉价的加载和分支操作，以验证是否不需要释放它。

这个锁将局部于线程池而非全局于整个引擎，并且它将保护我们所有的优化路径，而不仅仅是保护解释器。因此得名：局部优化器锁，简称LOL。

线程不安全对象

DOM对象行为类似于JavaScript对象，但实际上是C++中复杂逻辑的代理。该逻辑通常不是线程安全的。支持DOM的原生代码会传递性地使用许多旨在只能从主线程使用的原生API。使DOM完全线程安全需要大量工作。我们的初步提案只要求使DOM全局对象能够处理对自身属性的查找，我们则需要它来允许线程访问像Object和Thread这样的全局JavaScript属性。

在WebKit中，JSDOMWindow上的变量解析和自身属性解析主要遵循依赖现有JS属性查找机制的模式。当窗口具有空frame时，它使用特殊行为。我们已经支持在frame非空时安装观察点。因此，我们可以通过让线程使用现有的观察点集合来支持对JSDOMWindow属性的快速并发访问，同时尊重frame特殊情况。这意味着JSDOMWindow的某些慢速路径需要锁定，但这可能是可以接受的，因为大多数全局对象访问都是内联缓存的。

希望涉足并发JS的原生应用也可能希望限制某些类的共享。访问对象时的线程亲和性检查需要在VM本身中实现，以便我们的编译器能够将其优化掉。这意味着可以将此功能暴露给C/Objective-C API客户端。

总结

我们认为，我们可以实现在WebKit中并发执行JavaScript，同时提供足够好的性能，让开发者乐于使用此功能。这项技术的核心是分段蝶形结构、转换线程局部性推断以及大量廉价的每对象锁的结合。只要程序遵守某些行为，它们将经历微小的开销：属性访问的成本与今天大致相同，并且对象不需要任何额外的内存。如果某些对象决定不遵守我们的规则，它们将获得略高的开销。

结论

本文展示了WebKit的JavaScript实现如何修改以支持线程。我们的方案允许所有JavaScript对象被共享。我们的方案避免在快速路径上加锁，例如属性访问的快速路径。我们期望能够以低开销实现此方案。串行代码将不会有开销，而并发代码只有在向多个线程正在写入的对象添加属性时才会经历大的开销。

这个大胆的思维实验的下一步是尝试实现它并看看它是否有效。我们将在bug 174276下跟踪进展。

更新：本文的原始版本没有引用Daloze等人关于Truffle中并发支持的OOPSLA '16论文。我们已经更新了本文，包含了我们的方案与他们方案的比较。