Lara

JavaScript 引擎基本原理:Shapes 和 Inline Caches

原文链接: mathiasbynens.be

本文对所有 JavaScript 引擎中常见的一些关键基础知识进行了介绍,不仅仅局限于 V8 引擎。作为 JavaScript 开发人员,深入了解 JavaScript 引擎的工作原理有助于你了解自己代码的性能特征。

JavaScript 引擎的工作流程 (pipeline)

这一切都要从你写的 JavaScript 代码开始。JavaScript 引擎解析源代码并将其转换为抽象语法树(AST)。基于 AST,解释器便可以开始工作并生成字节码。太棒了!就在此时,引擎开始真正地运行 JavaScript 代码。

为了让它运行得更快,字节码能与分析数据一起发送到优化编译器。优化编译器基于现有的分析数据做出某些特定的假设,然后生成高度优化的机器码。

如果某个时刻某一个假设被证明是不正确的,那么优化编译器将取消优化并返回到解释器阶段。

JavaScript 引擎中的解释器/编译器工作流程

现在,让我们来看实际执行 JavaScript 代码的这部分流程,即代码被解释和优化的部分,并讨论其在主要的 JavaScript 引擎之间存在的一些差异。

一般来说,JavaSciript 引擎都有一个包含解释器和优化编译器的处理流程。其中,解释器可以快速生成未优化的字节码,而优化编译器会耗费更长的时间,但最终可生成高度优化的机器码。

这个通用流程和 Chrome 和 Node.js 中使用的 Javascript 引擎, V8 的工作流程几乎一致:

V8 中的解释器称为 Ignition,负责生成和执行字节码。当它运行字节码时,它收集分析数据,这些数据可用于后面加快代码的执行速度。当一个函数变为 hot 时,例如当它经常运行时,生成的字节码和分析数据将传递给我们的优化编译器 Turbofan,以根据分析数据生成高度优化的机器代码。

Mozilla 在 Firefox 和 Spidernode 中使用的 JavaScript 引擎 SpiderMonkey ,则不太一样。它们有两个优化编译器,而不是一个。解释器先通过 Baseline 编译器,生成一些优化的代码。然后,结合运行代码时收集的分析数据,IonMonkey 编译器可以生成更高程度优化的代码。如果尝试优化失败,IonMonkey 将返回到 Baseline 阶段的代码。

Chakra,在 Edge 和 Node-ChakraCore 中使用的 Microsoft 的 JavaScript 引擎,非常相似的,也有2个优化编译器。解释器优化代码到 SimpleJIT(JIT 代表 Just-In-Time 编译器,即时编译器),SimpleJIT 会生成稍微优化的代码。而 FullJIT 结合分析数据,可以生成更为优化的代码。

JavaScriptCore(缩写为 JSC),在 Safari 和 React Native 中使用的 Apple 的 JavaScript 引擎,它通过三种不同的优化编译器将其发挥到极致。低层解释器 LLInt 优化代码到 Baseline 编译器中,然后优化代码到 DFG(Data Flow Graph)编译器中,DFG(Data Flow Graph)编译器又可以将优化后的代码传到 FTL(Faster Than Light)编译器中。

为什么有些引擎有更多的优化编译器?这是权衡利弊的结果。解释器可以快速生成字节码,但字节码通常效率不高。另一方面,优化编译器需要更长的时间,但最终会产生更高效的机器代码。在快速让代码运行(解释器)或花费更多时间,但最终以最佳性能运行代码(优化编译器)之间需要权衡。一些引擎选择添加具有不同时间/效率特性的多个优化编译器,允许在额外的复杂性的代价下对这些权衡进行更细粒度的控制。另一个需要权衡的方面与内存使用有关,后续会有专门的文章详细介绍。

我们刚刚强调了每个 JavaScript 引擎中解释器和优化编译器流程中的主要差异。除了这些差异之外,在高层上,所有 JavaScript 引擎都有相同的架构:那就是有一个解析器和某种解释器/编译器流程。

JavaScript 的对象模型

让我们通过放大一些方面的实现来看看 JavaScript 引擎还有什么共同点。

例如,JavaScript 引擎如何实现 JavaScript 对象模型,以及它们使用哪些技巧来加速访问 JavaScript 对象的属性?事实证明,所有主要引擎在这一点上的实现都很相似。

ECMAScript 规范基本上将所有对象定义为由字符串键值映射到 property 属性的字典。

除了 [[Value]] 本身,规范还定义了这些属性:

  • [[Writable]] 决定该属性是否能被重新赋值,

  • [[Enumerable]] 决定属性是否出现在 for in 循环中,

  • [[Configurable]] 决定属性是否能被删除。

[[双方括号]] 的符号表示看上去有些特别,但这正是规范定义不能直接暴露给 JavaScript 的属性的表示方法。在 JavaScript 中你仍然可以通过 Object.getOwnPropertyDescriptor API 获得指定对象的属性值:

const object = { foo: 42 };
Object.getOwnPropertyDescriptor(object, 'foo');
// → { value: 42, writable: true, enumerable: true, configurable: true }

这就是 JavaScript 定义对象的方式,那么数组呢?

你可以把数组看成是一个特殊的对象,其中的一个区别就是数组会对数组索引进行特殊的处理。这里的数组索引是 ECMAScript 规范中的一个特殊术语。在 JavaScript 中限制数组最多有 2³²−1个元素,数组索引是在该范围内的任何有效索引,即 0 到 2³²−2 的任何整数。

另一个区别是数组还有一个特殊的 length 属性。

const array = ['a', 'b'];
array.length; // → 2
array[2] = 'c';
array.length; // → 3

在该例中,数组被创建时 length 为 2。当我们给索引为 2 的位置分配另一个元素时,length 自动更新了。

JavaScript 定义数组的方式和对象类似。例如,所有的键值, 包括数组的索引, 都明确地表示为字符串。数组中的第一个元素,就是存储在键值 '0' 下.

“length” 属性是另一个不可枚举且不可配置的属性。

当一个元素被添加到数组中时, JavaScript 会自动更新 “length“ 属性的 [[value]] 属性.

一般来说,数组和对象非常相似。

优化属性访问

既然我们知道了对象在 JavaScript 中是如何定义的, 那么就让我们来深入地了解一下 JavaScript 引擎是如何高效地使用对象的.

总体来说,访问属性是至今为止 JavaScript 程序中最常见的操作。因此,JavaScript 引擎是否能快速地访问属性是至关重要的。

const object = {
    foo: 'bar',
    baz: 'qux',
};

// Here, we’re accessing the property foo on object:
doSomething(object.foo);
//          ^^^^^^^^^^

Shapes

在 JavaScript 程序中,多个对象有相同的键值属性是非常常见的。可以说,这些对象有相同的 shape

const object1 = { x: 1, y: 2 };
const object2 = { x: 3, y: 4 };
// object1 and object2 have the same shape.

访问拥有相同 shape 的对象的相同属性也是非常常见的:

function logX(object) {
    console.log(object.x);
    //          ^^^^^^^^
}

const object1 = { x: 1, y: 2 };
const object2 = { x: 3, y: 4 };

logX(object1);
logX(object2);

考虑到这一点,JavaScript 引擎可以基于对象的 shape 来优化对象的属性访问。下面我们就来介绍其原理。

假设我们有一个具有属性 x 和 y 的对象,它使用我们前面讨论过的字典数据结构:它包含字符串形式的键,这些键指向它们各自的属性值。

如果你访问某个属性,例如 object.y,JavaScript 引擎会在 JSObject 中查找键值 'y',然后加载相应的属性值,最后返回 [[Value]]。

但这些属性值存储在内存中的什么位置呢?我们是否应该将它们作为 JSObject 的一部分进行存储?假设我们稍后会遇到更多同 shape 的对象,那么在 JSObject 自身存储包含属性名和属性值的完整字典便是一种浪费,因为对于具有相同 shape 的所有对象,属性名都是重复的。 这是大量的重复和不必要的内存使用。 作为一种优化,引擎将对象的 Shape 分开存储。

shape 包含除了 [[Value]] 以外所有属性名和属性。另外,shape 还包含了 JSObject 内部值的偏移量,以便 JavaScript 引擎知道在哪里查找值。具有相同 shape 的每个 JSObject 都指向该 shape 实例。现在每个 JSObject 只需要存储对这个对象来说唯一的值。

当我们有多个对象时,好处就显而易见了。不管有多少个对象,只要它们有相同的 shape,我们只需要存储 shape 和属性信息一次!

所有的 JavaScript 引擎都使用了 shapes 作为优化,但称呼各有不同:

  • 学术论文称它们为 Hidden Classes(容易与 JavaScript 中的 class 混淆)

  • V8 称它们为 Maps (容易与 JavaScript 中的 Map 混淆)

  • Chakra 称它们为 Types (容易与 JavaScript 中的动态类型以及 typeof 混淆)

  • JavaScriptCore 称它们为 Structures

  • SpiderMonkey 称它们为 Shapes

本文中,我们将继续使用术语 shapes.

转换链和树

如果你有一个具有特定 shape 的对象,但你又向它添加了一个属性,此时会发生什么? JavaScript 引擎是如何找到这个新 shape 的?

const object = {};
object.x = 5;
object.y = 6;

这些 shapes 在 JavaScript 引擎中形成所谓的转换链(transition chains)。下面是一个例子:

该对象开始没有任何属性,因此它指向一个空的 shape。下一个语句为该对象添加一个值为 5 的属性 "x",所以 JavaScript 引擎转向一个包含属性 "x" 的 shape,并在第一个偏移量为 0 处向 JSObject 添加了一个值 5。 下一行添加了一个属性 'y',引擎便转向另一个包含 'x' 和 'y' 的 shape,并将值 6 添加到 JSObject(位于偏移量 1 处)。

我们甚至不需要为每个 shape 存储完整的属性表。相反,每个shape 只需要知道它引入的新属性。例如,在本例中,我们不必将有关 “x” 的信息存储在最后一个 shape 中,因为它可以在更早的链上找到。要实现这一点,每个 shape 都会链接回其上一个 shape:

如果你在 JavaScript 代码中写 o.x,JavaScript 引擎会沿着转换链去查找属性 "x",直到找到引入属性 "x" 的 Shape。

但是如果没有办法创建一个转换链会怎么样呢?例如,如果有两个空对象,并且你为每个对象添加了不同的属性,该怎么办?

const object1 = {};
object1.x = 5;
const object2 = {};
object2.y = 6;

在这种情况下,我们必须进行分支操作,最终我们会得到一个转换树而不是转换链。

这里,我们创建了一个空对象 a,然后给它添加了一个属性 ‘x’。最终,我们得到了一个包含唯一值的 JSObject 和两个 Shape :空 shape 以及只包含属性 x 的 shape。

第二个例子也是从一个空对象 b 开始的,但是我们给它添加了一个不同的属性 ‘y’。最终,我们得到了两个 shape 链,总共 3 个 shape。

这是否意味着我们总是需要从空 shape 开始呢? 不一定。引擎对已含有属性的对象字面量会进行一些优化。比方说,我们要么从空对象字面量开始添加 x 属性,要么有一个已经包含属性 x 的对象字面量:

const object1 = {};
object1.x = 5;
const object2 = { x: 6 };

在第一个例子中,我们从空 shape 开始,然后转到包含 x 的shape,这正如我们之前所见那样。

在 object2 的例子中,直接在一开始就生成含有 x 属性的对象,而不是生成一个空对象是有意义的

包含属性 ‘x’ 的对象字面量从含有 ‘x’ 的 shape 开始,有效地跳过了空 shape。V8 和 SpiderMonkey (至少)正是这么做的。这种优化缩短了转换链并且使从字面量构建对象更加高效。

Benedikt 的博文 surprising polymorphism in React applications 讨论了这些微妙之处如何影响真实世界的性能。

下面是一个包含属性 ‘x'、'y' 和 'z' 的 3D 点对象的示例。

const point = {};
point.x = 4;
point.y = 5;
point.z = 6;

正如我们之前所了解的, 这会在内存中创建一个有3个 shape 的对象(不算空 shape 的话)。 当访问该对象的属性 ‘x’ 的时候,比如, 你在程序里写 point.x,javaScript 引擎需要循着链接列表寻找:它会从底部的 shape 开始,一层层向上寻找,直到找到顶部包含 ‘x’ 的 shape。

当这样的操作更频繁时, 速度会变得非常慢,特别是当对象有很多属性的时候。寻找属性的时间复杂度为 O(n), 即和对象上的属性数量线性相关。为了加快属性的搜索速度, JavaScript 引擎增加了一种 ShapeTable 的数据结构。这个 ShapeTable 是一个字典,它将属性键映射到描述对应属性的 shape 上。

等等,现在我们又回到字典查找了…… 我们添加 shape 就是为了对此进行优化!那我们为什么要去纠结 shape 呢?

原因是 shape 启用了另一种称为 Inline Caches 的优化。

Inline Caches (ICs)

shapes 背后的主要动机是 Inline Caches 或 ICs 的概念。ICs 是让 JavaScript 快速运行的关键要素!JavaScript 引擎使用 ICs 来存储查找到对象属性的位置信息,以减少昂贵的查找次数。

这里有一个函数 getX,该函数接收一个对象并从中加载属性 x:

function getX(o) {
    return o.x;
}

如果我们在 JSC 中运行该函数,它会产生以下字节码:

The generated bytecode is get_by_id loc0, arg1, x.

第一条 get_by_id 指令从第一个参数(arg1)加载属性 ‘x’,并将结果存储到 loc0 中。第二条指令将存储的内容返回给 loc0。

JSC 还将一个 Inline Cache 嵌入到 get_by_id 指令中,该指令由两个未初始化的插槽组成。

现在, 我们假设用一个对象 { x: 'a' },来执行 getX 这个函数。正如我们所知,,这个对象有一个包含属性 ‘x’ 的 shape, 该 shape存储了属性 ‘x’ 的偏移量和特性。当你在第一次执行这个函数的时候,get_by_id 指令会查找属性 ‘x’,然后发现其值存储在偏移量为 0 的位置。

嵌入到 get_by_id 指令中的 IC 存储了 shape 和该属性的偏移量:

对于后续运行,IC 只需要比较 shape,如果 shape 与之前相同,只需从存储的偏移量加载值。具体来说,如果 JavaScript 引擎看到对象的 shape 是 IC 以前记录过的,那么它根本不需要接触属性信息,相反,可以完全跳过昂贵的属性信息查找过程。这要比每次都查找属性快得多。

高效存储数组

对于数组,存储数组索引属性是很常见的。这些属性的值称为数组元素。为每个数组中的每个数组元素存储属性特性是非常浪费内存的。相反,默认情况下,数组索引属性是可写的、可枚举的和可配置的,JavaScript 引擎基于这一点将数组元素与其他命名属性分开存储。

思考下面的数组:

const array = [
    '#jsconfeu',
];

引擎存储了数组长度(1),并指向包含偏移量和 'length' 属性特性的 shape。

这和我们之前看到的很相似……但是数组的值存到哪里了呢?

每个数组都有一个单独的元素备份存储区,包含所有数组索引的属性值。JavaScript 引擎不必为数组元素存储任何属性特性,因为它们通常都是可写的、可枚举的和可配置的。

那么,在非通常情况下会怎么样呢?如果更改了数组元素的属性特性,该怎么办?

// Please don’t ever do this!
const array = Object.defineProperty(
    [],
    '0',
    {
        value: 'Oh noes!!1',
        writable: false,
        enumerable: false,
        configurable: false,
    }
);

上面的代码片段定义了名为 “0” 的属性(恰好是数组索引),但将其特性设置为非默认值。

在这种边缘情况下,JavaScript 引擎将整个元素备份存储区表示成一个字典,该字典将数组索引映射到属性特性。

即使只有一个数组元素具有非默认特性,整个数组的备份存储区也会进入这种缓慢而低效的模式。避免对数组索引使用Object.defineProperty!(我不知道你为什么想要这么做。这似乎是一件奇怪且毫无价值的事情。)

几点建议

我们已经了解了 JavaScript 引擎如何存储对象和数组,以及 shape 和 ICs 如何优化对它们的常见操作。基于这些知识,我们确定了一些可以帮助提高性能的实用的 JavaScript 编码技巧:

  • 始终以相同的方式初始化对象,这样它们就不会有不同的 shape。

  • 不要弄乱数组元素的属性特性,这样可以有效地存储和操作它们。