js性能优化之monomorphism

1,330 阅读4分钟

之前看了wizard大神关于js极致优化的演讲,优化主要包括3个方向

  1. monomorphism
  2. bit operator
  3. bloom filter

下来自己也搜了一些关于monomorphism的文章,这里做一个总结。

monomorphism是啥

直译过来是单一形态,什么意思呢? 大概就是说咱虽然是动态类型的语言吧,但是最好也别太飘了,对象的类型能稳定就稳定,别老是做删属性,增属性这种操作。引用v8大神Vyacheslav Egorov的话来说就是:

nicest dynamic behavior is static-like

怎么翻译我也不知道,总之就是代码写的越像静态的越好(感觉在变相给ts点赞)。

对象是怎存的

要弄清楚原因,咱得先弄明白咱得对象都是怎么存的。

在一些静态类型语言里面,比如java,因为类的每个属性的类型已经定了,所以每个类型要占的内存大小也可以确定,所以在compile的时候,每个属性的offset等信息都是可以确定的。这样一来,访问一个属性就会非常快。

而在js这种动态类型的语言里面,compile的时候显然没法知道每个属性在内存里的offset到底是多少。 那js里面是怎么找到属性的内存地址的呢?

hidden class

js的vm,比如v8,会给每一个我们创建的对象,都生成一个对应的hidden class。 这个hidden class上会存属性的一些metadata以及在内存里的offset。

那么问题来了?这些值直接存object上不就好了么?干嘛还再搞一个hidden class的概念出来?

原因是为了节省内存,hidden class是可以共享的。 比如下面这例子:

    let a = {x: 2, y: 3}
    let b = {x: 3, y: 4}

对象a和b的property以及类型完全一致,我们完全可以使用一个hidden class来描述这两个对象。 如此一来,管你成千上万个对象,只要你的属性一样,一个hidden class就搞定了。

如果对象b动态的增加了一个属z,会是什么情况?

显然,我们没法直接取修改之前的hidden class, 因为对象a并没有也增加这么一个属性. 取而代之的操作是会生成一个新的hidden class,描述新的属性c的metadata和offset。 并且新生成的hidden class会指向之前的hidden class,这个结构的学名叫Transition Chain。当我们访问一个对象属性的时候,会先从最新的hidden class找起。

如果b这个对象继续增加新的属性,transition chain上的hidden class也会越来越多。那么就会有一个问题,加如我新加了100个属性,那为了找到最开始的属性值,我得遍历100个hidden class才能拿到最终的offset。 这个性能显然不好。

inline cache

为了解决这个问题,v8采用了inline cache

inline cache背后的概念很简单:当我对对象和属性类型的预测是对的,那中间的计算就省略了,直接从缓存里取offset值就完事了。

ok,inline cache很牛逼,但它都在哪些地方用呢?

js里的每个函数都会被封装在一个闭包里面,闭包里面除了函数之外, 就是一堆对hidden class的inline cache。

比如这个例子:

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

getX({x: 1})
getX({x: 2})

函数getX在第一遍被调用后,会用{x:1}的hidden class作为cache entry做好缓存。第二遍调用的时候,因为hidden class一样,所以就直接从缓存里拿offset了。

需要注意的一点是,inline cache的cache entry并不是只有一个,可以有多个,cache entry的数量直接决定了读取的性能。 根据cache entry数量不同,inline cache分为了3种状态:

  1. monomorphic: 就一个cache entry,这样速率是最快的。
  2. polymorphic:1 < cache entry <= 4。 这个状态下,会在entry里挨个匹配,匹配的速率就取决于咱们机器跑conditional branch的速率了。
  3. megamorphic: cache entry > 4。 这个状态就麻烦了,因为hidden class的type太多了,所以会被存到一个global的哈希表里面。在有冲突的情况下,直接覆盖。(这里其实我理解了很久,之前一直觉得哈希表读取的时间也是常量,是非常快的。但果然还是太年轻了啊,哈希表把key映射到内存的哈希函数其实是非常耗性能的,这里有一篇v8优化这个过程的文章)。 当然了,megamorphic的性能还是会比去跑transition chain好上不少的。

那三种状态究竟速度差多少呢? 可以看下这个测试:

megamorphic状态下的对象读操作大概要比monomorphic慢86%左右,性能差别可以说是非常显著了。

参考文献

A sneak peek into super optimized code in JS frameworks by Maxim Koretskyi | JSConf EU 2019

What's up with monomorphism? Explaining JavaScript VMs in JavaScript - Inline Caches

Optimizing hash tables: hiding the hash code