JavaScript引擎基础原理：Shapes and Inline Caches

[xwcoder]

[TOC]

这篇内容主要翻译整理自以下两个演讲及其对应的文章：

• video: JavaScript Engines: The Good Parts™ - Mathias Bynens & Benedikt Meurer - JSConf EU 2018
• video: A Tale of Types, Classes, and Maps by Benedikt Meurer · JSCamp Barcelona 2018
• post: JavaScript engine fundamentals: Shapes and Inline Caches
• post: JavaScript engine fundamentals: optimizing prototypes

尝试在一个较高的维度介绍JavaScript引擎内部如何表示JS对象，以及常用优化手段之一Inlin Caches(ics)。

问题

ECMAScript定义object本质上是字典，key是string或Symbol。

我们知道，对象的属性也有一些特性，比如[[Writable]], [[Enumerable]]等，通过Object.defineProperty可以设置这些特性。

Object.defineProperty(obj, 'key', {
  enumerable: false,  
  configurable: false,
  writable: false,
  value: 'static'
});

内存

应用程序中经常会构造大量具有相同结构的对象，比如表示平面上坐标点的对象const p1 = {x: 5, y: 6}，const p2 = {x: 10, y: 10}。对于具有相同结构的对象，其同名属性的[[Writable]], [[Enumerable]], [[Configurable]]特性信息都是相同的，只有[[Value]]不同，如果这些特性信息都单独存储在每一个JSObject上，会造成大量内存浪费。问题1：这些objects能不能共享properties的信息，从而节省内存？

属性访问速度

如图所示，当访问属性y，需要在object查找y，然后访问y的Property attributes，最后在attributes中获取[[Value]]并返回。字典查找的速度比较慢，而属性访问又是程序中频繁使用的操作，问题2：有没有办法可以加快属性的访问速度？

Shape/HiddenClass

什么是Shape

先看问题1，很容易想到，我们可以把相同的信息单独存储一份，将[[Value]]的值存储在JSObject中，这样就可以达到优化内存的目的。JavaScript引擎也是这样处理的。单独存储的结构信息称为Shape，它是对object的描述。Shape还有一个更为熟知的名字：HiddenClass。不同引擎中它会被称为不同的名字，但都指的是同一种优化手段：

• 学术论文中被称为HiddenClass。
• 在v8中被称为Mpas，（在这篇问题中的map属性）。
• 在Chakra中被称为Types。
• 在JavaScriptCore中被称为Structures。
• 在SpiderMonkey中被称为Shapes。

原演讲中使用Shape，所以这篇内容也使用Shape这个名字。

Shape中保存属性名和对应的信息，但是不保存[[Value]]，[[Value]]存储在JSObject中。属性信息中会保存一个特殊值offset，它是对应[[Value]]在JSObject中的偏移量，如果JSObject中使用数组保存属性值，那么offset就是数组下标。

这样具有相同结构的object就可以共享一份Shape。

转换链/转换树(Transition chains and trees)

转换链(Transition chains)

当在object上添加、删除属性时，其Shape也会改变。从一种Shape转换到另一种Shape，旧Shape保留对新Shape的引用，从而形成了转换链(transition chains)。

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

开始object是空对象，所以它指向一个空shape。之后在object上添加了属性x，所以它指向了一个新的shape，新shape包含属性x及其信息，x的值5存储在JSObject中offset为0的位置。最后在object上添加了属性y，JSObject又指向了一个新的shape，新shape包含属性x和y及其信息，y的值6存储在JSObject中offset为1的位置。

从以上转换过程可以看到，shape和属性添加的顺序相关，所以{x: 5, y: 6}和{y: 6: x: 5}具有不同的shape。

每个Shape可以只存储引入的新属性，而不必存储全部属性。每个Shape只需要添加对上一个Shape的引用，就可以访问到全部属性信息。本例中，最后一个Shape只存储属性y的信息。

转换树(Transition trees)

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

本例中object1和object2会共享同一个空shape，之后由于添加不同属性，分别转换到不同的shape，形成树形结构。

并不是所有对象都从空Shape开始。对于定义时就包含属性的对象，其Shape从非空Shape开始。对于如下示例：

const a = {};
a.x = 6;
const b = { x: 6 };

对象a从空Shape开始，之后添加属性x，其Shpe转换到包含x的Shape。对象b定义时就包含属性x，所以其Shape从包含x的Shape开始。

考虑下面的例子：

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

除了空Shape外，JS引擎会创建三个Shape。

当我们通过point.x访问属性x时需要遍历Shape链，时间复杂度是O(n)。为了提高查找速度，JavaScript引擎又引入了被称为ShapeTable的字典结构，key是属性名，value是属性对应的Shape。开头提到过字典的查找速度也比较慢。

JS引擎使用一种被称为Inline Caches(ICs)的技术手段来优化访问速度。

Inline Caches

ICs是优化js执行速度的关键手段，也是引入Shape的主要目的，其原理是记录下属性的位置和Shape信息，从而减少之后运行时的查找次数。

考虑如下代码:

function getX(o) {
	return o.x
}

在JavaScriptCore中，会生成如下字节码:

第一条指令是get_by_id，它会从第一个参数arg1中获取属性x并存储在loc0，第二条执行返回loc0存储的值。

如图，指令get_by_id后有两个插槽(slot)，即ICs。

假设调用getX({ x: 'a' })。我们知道，对象{ x: 'a' }会有一个关联Shape，Shape上存储了属性x的特性和offset信息。

当第一次执行getX({ x: 'a' })时，get_by_id会查找属性x，并将Shape和offset记录在插槽中。

之后再调用getX时，ICs只需要比较参数的Shape和之前记录的Shape是否是同一个，如果相同，那么就可以通过记录的offset值访问属性值，省去了耗时的查找过程。

如果以不同对象作为参数调用getX就会使IC优化失效。例如执行getX({ x: 'x', y: 'y' })记录了Shape和Offset，再以{ y: 'y', x: 'x' }调用则会使IC失效，因为{ x: 'x', y: 'y' }和{ y: 'y', x: 'x' }具有不同的Shape。

编码时，对于拥有相同结构的对象，尽量保证属性添加的顺序也一致。

prototype属性访问优化

前面介绍了Shape和Inline Caches，这部分介绍prototype上的属性访问优化。

JavaScript是基于原型(prototype)的语言，ES6添加的class语法可以看做是prototype的语法糖。

如下代码是等价的：

class Bar {
	constructor(x) {
		this.x = x
	}
	getX() {
		return this.x
	}
}

function Bar(x) {
	this.x = x
}

Bar.prototype.getX = function getX() {
	return this.x;
}

prototype也是JavaScript对象，实例通过prototype共享属性和方法。

const foo = new Bar(true)

通过new实例化得到对象foo，foo拥有自己的Shape，Shape上有属性x的信息。foo的prototype是Bar.prototype，Bar.prototype拥也有自己的Shape，Shape上有属性getX的信息。Bar.prototype也是JavaScript对象，其prototype是Object.prototype。Object.prototype是原型链的根，所以其prototype是null。

创建另外一个实例qux，foo和qux拥有共同的Shape，并且都有到Bar.prototype的引用。

const x = foo.getX()

调用foo.getX()可以看做是两步操作。第一步获取getX；第二步以实例foo作为this调用getX()。

const $getX = foo.getX
const x = $getX.call(foo)

我们主要关注第一步的查找过程。

引擎从foo实例开始，首先在foo实例的Shape上判断没有属性getX，然后沿原型链向上查找，来到Bar.prototype，在Bar.prototype的Shape上查找到属性getX的信息，其值的offset是0，最终获取到了getX。

从一个例子开始，看看prototype属性访问的时间复杂度和优化手段。

class Bar {
	constructor(x) { this.x = x; }
	getX() { return this.x; }
}

const foo = new Bar(true);
const x = foo.getX();
//        ^^^^^^^^^^

前面ICs部分，为了快速获取属性引擎需要做一次判断：判断IC记录的Shape和参数的Shape是否为同一个。现在来看下访问prototype上的属性需要做几次判断：

1. 实例foo的Shape没有改变并且没有getX属性。
2. foo的prototype依然是Bar.prototype。
3. Bar.prototype的Shape没有改变并且有getX属性。

由于JS的灵活性，很容使用Object.setPrototypeOf()等方式改变object的prototype，所第2步的判断是必要的。

那么一般获取prototype上的属性要经过1+2N次判断。N是属性所在prototype的深度。

优化手段一：将实例的prototype引用存储在实例的Shape，而不是实例本身。

这样只需要判断实例的Shape没有改变，那么也即可以保证实例的prototype没有改变，判断次数由1+2N降低为1+N。

优化手段二：Validity cells

虽然通过优化手段一降低了判断次数，但是时间复杂度还是线性的O(n)。为了使时间复杂度降低为常数，引擎引入了Validity cells。

• 每个prototype的Shape都有一个ValidityCell与其关联。
• 每当与ValidityCell关联的prototype或其之上的prototype改变，那么ValidityCell失效。

这样提升prototype属性访问速度的Inline Cache就保存4个字段。

1. Shape: 实例的Shape。
2. Offset: 属性值的位置索引。
3. prototype: 包含属性值的prototype。
4. ValidityCell: 与实例Shape指向的prototype关联的ValidityCell。

Inline Cache构建起来后，下次访问只需要判断IC保存的Shape无变化、ValidityCell有效，就可以直接在prototype的Offset位置读取属性值。

通常来说我的业务代码继承层级不会太深，不过有一个继承层次较深的常用场景是DOM。

const anchor = document.createElement('a');
const title = anchor.getAttribute('title')

getAttribute()在Element.prototype上。

编码原则

通过以上内容，在编码时要注意以下几点：

1. 对于拥有相同结构的对象，尽量保证属性添加的顺序也一致。
2. 不要随意改动原型链，这会使当前的IC失效。
3. 尽量避免使用delete, delete会改变实例Shape或其原型链，从而使当前的IC失效。