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_ELEMENTSPACKED_DOUBLE_ELEMENTS 两种类型的检查,这会造成一些性能消耗;

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

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

参考:

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

回复

我来回复
  • 暂无回复内容