写文章

JavaScript的稀疏数组和密集数组

吐槽君 分类：javascript

文章首发：github.com/qiudongwei/…

测试一段代码

运行环境：Chrome JavaScript | V8 8.9.255.20

let array1 = [1];
let array2 = [1];
// array2[2]=2; // 超出数组长度

console.time('array1');  
for (let i = 0; i < 10000000; i++) {  
    array1.push(i); 
}  
console.timeEnd('array1'); 


console.time('array2');  
for (let j = 0; j < 10000000; j++) {  
    array2.push(j); 
}  
console.timeEnd('array2');

① 测试几次发现，array1和array2耗时相近，几乎是一样的；
② 取消第三行的注释再运行，测试发现，array1的耗时明显要小于array2；

或者直接在这测试：jsben

这是为什么呢？V8内部是如何处理数组操作的？

数组中的元素类型

在JavaScript层面，开发者可以给数组的元素设置任意基础数据类型，eg：arr = [1, 1.2, 'hello', {}, []]，然而，在V8层面，它理解的元素类型却只有三种：

  • SMI_ELEMENTS：又称Smi，小整数（Small integers）
  • DOUBLE_ELEMENTS：双精度浮点数，浮点数和不能表示为 Smi 的整数
  • ELEMENTS：常规元素，不能表示为 Smi 或双精度的值

举个例子，暂时忽略PACKED_这个前缀：

const arr = [1, 2, 3]; // 元素类型: PACKED_SMI_ELEMENTS
arr.push(1.54);         // 元素类型变为: PACKED_DOUBLE_ELEMENTS
arr.push('c');            // 元素类型变为: PACKED_ELEMENTS

由上例子可知，V8为每个数组分配一种元素类型 SMI_ELEMENTS | DOUBLE_ELEMENTS | ELEMENTS，并且元素类型的转换只能从特定的（eg：SMI_ELEMENTS ）到更一般的（eg：ELEMENTS）。

再看一个例子：

const arr = [1, 2, ,4]; // 元素类型HOLEY_SMI_ELEMENTS
arr.push(5);               // 元素类型变为: HOLEY_DOUBLE_ELEMENTS
arr.push('a');             // 元素类型变为: HOLEY_ELEMENTS

这个例子里面，arr出现了个洞（没有被完满填充）我们称其为稀疏数组，用一个HOLEY去标识其类型； PACKED则表示这是个密集数组。
稀疏数组是不可逆的，一旦标记为有空，它就是永远有洞，即便它被填充了！稀疏数组不可转变为密集数组，反之却可以。如下图表明了各元素类型之间的转换关系：
image

而数组的稀疏与否，有可能（数据量足够大的时候）会影响数组操作的性能。

数组的性能问题

  1. 对于稀疏数组，V8需要对其原型链进行额外的检查和昂贵的查找；
  2. 一般来说，更具体的元素种类可以进行更细粒度的优化。元素类型越一般，对该对象的操作就会越慢；
  3. V3依赖其内嵌缓存（inline cache）机制可以更有效地去对具体类型的（密集）数组作数组操作的优化；

避免创建稀疏数组

  1. 避免new Array创建数组
// bad
const arr = new array(5);

// good
const arr = [0, 0, 0, 0, 0];

// better
const arr = Array.from({length: 5}
  1. 避免越界访问数组
const arr = [1, 2, 3];

// bad
log(arr[3]);
  1. 避免给length赋值
const arr = [1, 2, 3];

// bad
arr.length = 5;

数组多态

如果您的代码需要处理包含多种不同元素类型的数组，则可能会比单个元素类型数组要慢，因为你的代码要对不同类型的数组元素进行多态操作。看这个例子：

const each = (array, callback) => {
  for (let index = 0; index < array.length; ++index) {
    const item = array[index];
    callback(item);
  }
};

// 第一次调用
each(['a', 'b', 'c'], doSomething);

// 第二次调用
each([1.1, 2.2, 3.3], doSomething);

// 第三次调用
each([1, 2, 3], doSomething);

在第一次调用中，数组类型是 PACKED_ELEMENTS，V8使用 inline cache（内嵌缓存）记住 each 函数是被一个特定元素类型调用的，在下一次调用时，V8会先检查数组类型是否是 PACKED_ELEMENTS，如果是，则复用上次生成的代码，否则会做更多的事情，如重新生成相应的代码；

第二次调用的时候，数组类型是 PACKED_DOUBLE_ELEMENTS，V8检查到出现了与缓存中不一样的数组类型，此时，V8将 each 函数中的数组标记为多态，接下来的每一次 each 调用都需要进行 PACKED_ELEMENTS 和 PACKED_DOUBLE_ELEMENTS 两种类型的检查，这会造成一些性能消耗；

第三次调用结束的时候，V8缓存中出现了3种不同类型的 each 缓存，V8为了能够复用生成的代码，接下来的每一次 each 调用，都会做相应的类型检查。

然而，内置方法（eg：Array.prototype.forEach）可以更有效地处理这种多态性，因此在性能敏感的情况下应用优先考虑使用它。

参考：

V8 中的元素种类及性能优化

回复

我来回复

  • 暂无回复内容