Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

v8特殊数组上push的性能BUG

  当数组上存在特殊元素时总是会有许多问题,之前的文章中就指出过一两个。但这回是数组中最常用的push方法存在的性能BUG,那影响就比较严重了。但由于受影响的只有push而已,解决这个问题只要针对push即可。比如不用内置的push方法,自己实现添加元素。
  当我们在数组上定义一个非常规属性元素(非常规属性指具有不可枚举、不可写、不可配置,这三个性质其中之一的属性)时,数组不仅会进入字典模式,在此之后每次执行push方法在内部都需会遍历整个数组。也就是说,只要数组中存在或曾经存在非常规属性元素,数组的push方法时间复杂度就由原来的O(1)变为O(na),这里的n指数组内元素的个数。
<input type="button" value="初始化1E7个元素" id="x1" />
<input type="button" value="定义0位置的元素为不可枚举" id="x2" />
<input type="button" value="添加一个元素" id="x3" />
<script>
onload=function(a){
  x1.onclick=function(i){
    console.time(this.value);
    for(a=[],i=0;i<1E7;i++)a.push(i);
    console.timeEnd(this.value);
    x2.disabled=false;
  },x2.onclick=function(){
    console.time(this.value);
    Object.defineProperty(a,0,{enumerable:false});
    console.timeEnd(this.value);
    x3.disabled=false;
  },x3.onclick=function(){
    console.time(this.value);
    a.push(null); //注意这里只执行一次push哟
    console.timeEnd(this.value);
  },x2.disabled=x3.disabled=true;
};
</script>
  
  经过前面的两个步骤之后,push执行一次的耗时居然需要400ms+,这是难以想象的。而且,就如果我上面描述的,只要非常规属性元素曾经存在就会带来这个问题,即使那个元素已经被删除或设置成常规元素。
<input type="button" value="test" id="test" />
<script>
test.onclick=function(){
  var i,a=[];
  Object.defineProperty(a,0,{
    writable:true,
    enumerable:true,
    configurable:true
  }); //这里的三个参数任意一个改成false就要杯具
  console.time(this.value);
  for(i=0;i<1E4;i++)a.push(i);
  console.timeEnd(this.value);
};
</script>
  上面这个测试机会是瞬间完成的,因为这里的defineProperty定义的是常规属性元素。但如果 <input type="button" value="test" id="test" />
<script>
test.onclick=function(){
  var i,a=[];
  Object.defineProperty(a,0,{configurable:true});
  Object.defineProperty(a,0,{enumerable:true});
  Object.defineProperty(a,0,{writable:true});
  console.time(this.value);
  for(i=0;i<1E4;i++)a.push(i);
  console.timeEnd(this.value);
};
</script>
  这么写就要杯具,因为defineProperty的配置参数默认是false。也就是说第一次执行defineProperty的时候这个数组就存在enumerable:falsewritable:false,虽然后面两个代码把这两个值设置为了true,但对于数组来说非常规属性元素已曾经存在了。
  要解决这个问题,最直接的方法是不用自带的push方法。比如把上面的a.push(i);改成a[a.length]=i;就可以解决。当然,除此之外还有其它方法,只要让字典模式的数组恢复成快速模式即可。具体方法就不在这篇细说了,以后的文章中再做解释。

  测试于:Chrome 31.0.1650.57 m
网名:
54.144.24.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^