JS 引擎中的 Inline Cache 技术内幕，你知道多少？

文章来源：infoq腾讯云中间件

JavaScript 以简单易用而著称，NodeJS 的出现使 JavaScript 的影响进一步扩大。JavaScript 是动态类型的语言，动态类型为应用开发者带来了便利，但也为 JavaScript 运行时的性能带来了负担，例如类型的不断变化可能会导致基于类型的某些优化失效。为了解决 JavaScript 由于动态类型导致的运行性能受损问题，各大 JavaScript 引擎几乎都采用了 IC（Inline Cache）技术：即通过缓存上一次对象的类型信息来加速当前对象属性的读写访问。本文从引例入手，以 V8 JavaScript 引擎（主要由于 V8 既是 Chrome 浏览器的 JS 引擎，也是 node 的 JS 引擎）为基础，深入分析 Inline Cache 机制的基本原理。

引例

function Point(x,y) {
this.x = x;
this.y = y;
}
var p = new Point(0, 1);
var q = new Point(2,3);
var r = new Point(4,5);

为了避免 API 调用不稳定因素的影响，通过修改 V8 源码，在内部插入时间戳的方式。在 3.2G 8 核机器上，分别测试三次调用 new Point(x,y)时执行 this.x=x 这个语句耗时，结果如下表所示。

执行代码	this.x=x耗时统计
var p = new Point(0,1);	4.11ns
var q = new Point(2,3);	6.63ns
var r = new Point(4,5);	0.65ns

从表中的结果可以看出，事实并非想象中的从第二次执行开始，速度就会变快，相反，第二次比第一次还要慢，到第三次的时候速度才会变快。本文后面会通过分析 V8 IC 机制来解释为什么第二次速度最慢，第三次执行速度又变快的原因。

问题分析

1. 对象的隐藏类(Hidden Class)

由于 JavaScript 对象没有类型信息，几乎所有 JS 引擎都采用隐藏类（Hidden Class/Shape/Map 等）来描述对象的布局信息，用以在虚拟机内部区分不同对象的类型，从而完成一些基于类型的优化。

V8 对 JavaScript 对象都使用 HeapObject 来描述和存储，每一种 JavaScript 对象都是 HeapObject 的子类，而每个 HeapObject 都用 Map 来描述对象的布局。对象的 Map 描述了对象的类型，即成员数目、成员名称、成员在内存中的位置信息等。

上述源码中对象 p、q、r 都是由同一个构造函数 Point 生成，因此他们具有同样的内存布局，可以采用同一个 Map 来描述。

2. 隐藏类变迁（Map Transition）

因为 JavaScript 是高度动态的程序设计语言，对象的成员可以被随意动态地添加、删除甚至修改类型。因此，对象的隐藏类在程序的运行过程中可能会发生变化，V8 内部把这种变化叫隐藏类变迁（Map Transition）。

以上文代码为例，当 Point function 被声明时，V8 就会给 Point 创建隐藏类 map0，由于暂时还没有属性，因此 map0 为空。当执行 this.x=x 时，V8 会创建第二个 Hidden Class map1，map1 是基于 map0，并且描述了属性 x 在内存中的位置，此时 this 对象的 Hidden Class 会通过 Map Transition 变为 map1。当执行 this.y=y 时，会重复前面的操作，一个新的 Hidden Class map2 会被创建，此时 this 对象的 Hidden Class 被更新为 map2。this 对象的 Map 从 map0 变为 map1，再变成 map2 的过程就叫做 Map Transition。图一描述了 Point 类对象创建过程中 Map Transition 的过程。

Map Transition示意图

3. 类型反馈向量（type feedback vector）

前面已经提到 IC 机制的原理是：对于某代码语句比如 this.x=x，比较上次执行到该语句时缓存的 Map 和对象当前的 Map 是否相同，如果相同则执行对应的 IC-Hit 代码，反之执行 IC-Miss 代码。那么 V8 是如何组织被缓存的 Map 和 IC-Hit 代码？以上文代码为例，V8 会在 Point 函数对象上添加一个名为 type_feedback_vector 的数组成员，对于该函数中的每处可能产生 IC 的代码，Point 对象中的 type_feedback_vector 会缓存上一次执行至该语句时对象的 Map 和对应的 IC-Hit 代码（在 V8 内部称为 IC-Hit Handler）。上文中的 Point 函数中有两处可能产生 IC 的语句，this.x=x 和 this.y=y。假设某次执行至 this.x=x 时，对象 this 的 Map 是 map0，执行至 this.y=y 时 this 的 Map 是 map1，那么 Point 对象的 type_feedback_vector 数据内容如下所示：

数组下标	IC对应的源码	缓存的Map和对应的IC-Hit Handler
0	this.x=x	<map0, ic-hit handler>
1	this.y=y	<map1, ic-hit handler>

简单来说，type_feedback_vector 缓存了 Map 和与之对应的 IC-Hit handler，这样 IC 相关的逻辑简化为只需要通过访问 type_eedback_vector 就可以判断是否 IC Hit 并执行对应的 IC-Hit Handler。

4. IC 状态机

为了描述 V8 中 IC 状态的变化情况，本节将以状态机的形式描述 V8 中最常见 IC 种类的状态变化情况。V8 中最常用的 IC 分为五个状态，如图二所示。初始为 uninitialized 状态，当发生一次 IC-Miss 时会变为 pre-monomorphic 态，再次 IC-Miss 会进入 monomorphic 态，如果继续 IC-Miss，则会进入 polymorphic 状态。进入 polymorphic 之后如果继续 IC-Miss 3 次，则会进入 megamorphic 态，并最终稳定在 megamophic 态。

IC状态机

引例中代码会涉及到 IC 状态机的前三种状态。

以 Point 函数走红 this.x=x 语句为例，第一次执行时，由于 Point.type_feedback_vetor 为空，因此此时会发生 IC-Miss，并将该处 IC 状态从 uninitialized 设置为 pre-monomorphic，IC-Miss Handler 会分析出此时 this 对象的 Map 中不包含属性 x，因此会添加成员 x，接着会发生 Map Transition，即前文提到的 this 对象的隐藏类从 map0 变为 map1。由于考虑到大部分函数可能只会被调用一次，因此 V8 的策略是发生第一次 IC-Miss 时，并不会缓存此时的 map，也不会产生 IC-Hit handler；

第二次调用构造函数执行 this.x=x 时，由于 Point.type_feedback_vector 仍然为空，因此会发生第二次 IC-Miss，并将 IC 状态修改为 monomorphic，此次 IC-Miss Hanlder 除了发生 Map Transition 之外，还会编译生成 IC-Hit Handler，并将 map0 和 IC Hit Handler 缓存到 Point.type_feedback_vector 中。由于此次 IC-Miss Handler 需要编译 IC-Hit Handler 的操作比较耗时，因此第二次执行 this.x=x 是最慢的；

第三次调用构造函数中 this.x=x 时，发现 Point.type_feedback_vector 不为空，且此时缓存的 map0 与此时 this 对象的 Map 也是一致的，因此会直接调用 IC-Hit Handler 来添加成员 x 并进行 Map transition。由于此次无需对 map0 进行分析，也无需编译 IC-Hit Handler，因此此时执行效率比前两次都高。

至此，本节已经解释清楚为什么 V8 执行构造函数时，第二遍最慢而第三遍最快的原因。

5. Polymorphic 和 Megamorphic

function f(o) {
  return o.x;
}
f({x:1}) //pre-monomorphic
f({x:2}) //monomorphic
f({x:3, y:1}) // polymorphic degree 2
f({x:4, z:1}) // polymorphic degree 3
f({x:5, a:1}) // polymorphic degree 4
f({x:6, b:1}) // megamorphic

上述代码描述了图二状态机中 polymorphic 态和 megamophic 态的两种情形。上面 3 中提到 type_feedback_vector 会缓存 Map 和 IC-Hit Handler，但是如果 IC 状态太多比如到达 megamorphic 态，此时 Map 和 IC-Hit Handler 便不会再缓存在 Point 对象的 feedback_vector 中，而是存储在固定大小的全局 hashtable 中，如果 IC 态多于 hashtable 的大小，则会对之前的缓存进行覆盖。通过上述分析，可以总结得出不同 IC 态的性能：

如果每次都能在monomorphic态IC-Hit，代码的运行速度是最快的；
在polymorphic态IC-Hit时，需要对缓存进行线性查找；
Megamorphic是性能最低的IC-Hit，因为需要每次对hashtable进行查找，但是megamorphic ic hit性能仍然优于IC-Miss；
IC-Miss性能是最差的；

综合前文所述，仅从 Inline cache 的角度来分析，如果 JavaScript 开发者在应用开发时能让 IC 态保持在 monomorphic 或者 polymorphic，代码的性能是最好的。特别是对于一些比较注重应用冷启动性能的场景，减少启动过程中的 IC-Miss 会使启动时间大幅缩短。