阅读 176

V8 中数组的性能相关问题

“编写快速软件”的秘密就是:先写出可调优的软件,然后调优它以求获得足够的速度。

马丁·福勒(Martin Fowler). 重构:改善既有代码的设计(第2版)

如马丁大爷所说,可扩展和可读是我们写代码的时候第一需要关心的东西,一般情况下性能的考虑优先级应该低一点。这篇短文是偶尔看到一个V8团队工程师的演讲总结而成。通过探讨数组的性能问题一方面可以了解一下JavaScript数组在引擎层面的存在方式;另一方面在一些对性能敏感的case,通过一些写法来避免数组中的低效操作。庆幸的是包括V8在内的大多数JS引擎都对ES6+ for...of 以及Array的原型链方法做了特别优化,所以只要按照“正常、现代”方式操作数组,通常问题不大。

类型

我们知道在ES6及之前JavaScript中大概有numberstring… 7种类型。以number类型为例,该类型代表了在JavaScript中出现的一切可能的数字(当然还是有长度限制的。值得一提的是当前BigInt类型已处于stag-4,其可以代表更大范围的整数)。一些别的编程语言(如C++Java等)是区分整型和浮点型的。我们知道V8自身是C++写得,所以在引擎世界中数字的类型是什么呢,我们举个例子来看。

const arr = [1]; // [1]  Smi Element
arr.push[3.14]; // [1, 3.14] Double Element
arr.push[{}]; // [1, 3.14, {}] Regular Element
arr.length = 5; // [1, 3.14, {}, hole, hole] Holey Regular Element
复制代码
  1. 我们声明一个数组,初始化一个元素1。这个时候在JS世界,我们认为arr就是一个数组,无他。但是在引擎的世界,会认为这个一个Smi类型元素组成的数组。(Smi据说是Small的意思,类似为short)。在操作这个数组时,引擎会根据Smi的特性对数组做一些优化
  2. JS不区分整型和浮点型,所以我们可以往这个数组里推入一个新的浮点值3.14。对于JS世界,类型上并不会改变什么。引擎世界就不能认为这个数组时Smi类型元素组成的,因为这里包含了浮点数。所以这里会把类型泛化,认为arrDouble类型的元素组成的数组。在操作数组时引擎会根据Double类型的特性做一些优化。优化空间当然没有Smi类型大。
  3. JS为弱类型动态语言。数组中不必强制要求统一类型,所以我们可以推入一个对象。鉴于当前这个数组中没什么类型都有,引擎世界这是就没办法认为这个数组中一定为某种类型了,所以就认为arr是一个由Regular类型元素组成的数组。显然Regular类型相当于没有类型,操作数组时,引擎预先知道的信息更少,也就更加难以进行优化。
  4. JS数组可以直接通过修改length属性来动态扩容。当新赋值的值小于当前length值时,超出当前length定义的位置元素将被删除。反之,如果新复制的length值大于当前值时,就会在当前未定义的位置添加Hole。因此上边代码的最后一句就会在arr后面添加两个Hole。在引擎世界中,这个数组类型转化为Holey Regular类型元素组成的。Holey顾名思义就是带有空洞的意思,而与之相反的不带空洞的数组就被称为Packet,姑且认为是紧致的意思。Packet数组在查找元素时,在当前数组上没找到就会停止返回undefined,查找效率比较高;Holey数组在查找时,如果没有找到会继续查找原型链(通常顺序是arrIns -> Array.prototype -> Object.prototype),直到最后一道原型链检查过没有找到才会返回undefined,因此查找效率比较低。
  5. 任何一种类型的数组都可以转化为对应类型的Holey数组。

综上所述,我们可以将数组的类型分为如下图所示的六种类型,这六种类型会产生动态转化,转换关系如图箭头所示,不可逆。箭头指向的类型通常引擎对数组操作的优化更少一点,而对箭头背对的类型则会更多一点。所以为了提高数组操作效率我们可以遵循如下两个原则:

  • 尽可能避免Holey Array,因为它会降低我们的查找效率
  • 尽可能避免动态类型转化,因为它会让引擎能做的优化工作更少
  • 尽可能避免使用类数组对象,因为引擎不会对它做数组特有的优化

实际操作

避免空洞数组

  • 避免使用new Array(LEN)
  • 避免访问超出上限的位置,如arr[LEN]
  • 避免使用.length属性为数组扩容,使用push

避免动态类型转化

  • 一个数组尽量存储统一类型的元素
  • 避免使用+0,-0。后者会导致数组从SMI转为DOUBLE

避免使用类数组对象

最典型的类数组对象就是所有函数的局部作用域中的arguments对象了,如果要大量操作这个对象,先将其转为数组。不过幸运的是通过ES6的操作符,我们可以直接将函数调用的实参存在一个正儿八经的数组里,所以我们基本上可以告别arguments了。

如何初始化一个数组

const arr = new Array(LEN)
复制代码

好处:如果预知数组的长度的话,这种方式能预先分配好内存,避免在数组增长过程中动态分配内存

坏处:会产生空洞数组,操作效率比较低

const arr = []; arr.push(ele);
复制代码

好处和坏处刚好跟上一种方式相反,这种方式,创建效率比较低,因为需要在增加元素的过程中,动态申请内容;但是操作效率比较高,因为这种数组没有空洞。

const arr = [ele1, ele2 ...]
复制代码

最好使用数组字面量来初始化数组,避免上述的问题。当然这需要我们预先知道数组的长度和初始值,另外如果数组很大的话,这种方式是不现实的。

后记

作为JavaScript开发者,其实大部分时间不需要关系性能问题,所有JavaScript引擎也有致力于让我们可以不用考虑太多性能,只需要遵循试下最流行的写法就可以在引擎中运行的很快。所以我不指望这篇文章会为你、我写出来更高性能的JavaScript带来多大贡献,仅为满足好奇心而已。