在V8中使用数组（性能问题） [英] Working with arrays in V8 (performance issue)

问题描述

我尝试了下一个代码（它在Google Chrome和nodejs中显示类似的结果）：

$ p $ var c = new Array（200000 ）; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：27839.499ms
undefined

我也运行了下一个测试： p>

  var t = []; console.time（ WTF）; for（var i = 0; i <400000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）; 
 wtf：449.948ms 
 undefined 
 var t = []; console.time（ WTF）; for（var i = 0; i <400000; ++ i）{t.push（undefined）;} console.timeEnd（'wtf'）; 
 wtf：406.710ms 
 undefined 
  

但是在Firefox中，第一个变体：

 >>> var t = new Array（200000）; console.time（ WTF）; ... {t.push（Math.random（））;} console.timeEnd（'wtf'）; 
 wtf：602ms 
  

在V8中会发生什么？

$

pre> var t = new Array（99999）; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：220.936ms
undefined
var t = new Array（100000）; t [99999] = 1; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：1731.641ms
undefined
var t = new Array（100001）; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：1703.336ms
undefined
var t = new Array（180000）; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：1725.107ms
undefined
var t = new Array（181000）; console.time（ WTF）; for（var i = 0; i <200000; ++ i）{t.push（Math.random（））;} console.timeEnd（'wtf'）;
wtf：27587.669ms
undefined


解决方案

如果预分配，不要使用 .push ，因为您将创建一个由散列表支持的稀疏数组。 您可以预先分配最多99999个元素的稀疏数组由一个C数组支持，之后它是一个哈希表。

第二个数组是从0开始以连续的方式添加元素的，所以它将由一个真正的C数组，而不是一个哈希表。

如此大概：

0到Length-1，没有孔，那么它可以用一个快速C数组表示。如果你的数组中有
的空洞，那么它将用一个非常慢的散列表来表示。例外是，如果你预先分配一个数组
的大小< 100000，那么你可以在数组中有空洞，仍然得到一个C数组的支持：

pre $ var $ a = new Array（N ）;

//如果N < 100000，这不会使数组哈希表：
a [50000] =稀疏;

var b = [] //或新数组（N），N> = 100000
// B将由散列表
b [50000] =疏;
//b.push(\"Sparse），与上面的大致相同，如果你使用新的Array与N> 0

I tried next code (it shows similar results in Google Chrome and nodejs):

var t = new Array(200000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27839.499ms
undefined

I also runned next tests:

var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 449.948ms
undefined
var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(undefined);} console.timeEnd('wtf');
wtf: 406.710ms
undefined

But in Firefox all looks fine with the first variant:

>>> var t = new Array(200000); console.time('wtf'); ...{t.push(Math.random());} console.timeEnd('wtf');
wtf: 602ms

What happens in V8?

UPD * magically decreasing performance *

var t = new Array(99999); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 220.936ms
undefined
var t = new Array(100000); t[99999] = 1; console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1731.641ms
undefined
var t = new Array(100001); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1703.336ms
undefined
var t = new Array(180000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1725.107ms
undefined
var t = new Array(181000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27587.669ms
undefined

解决方案

If you preallocate, do not use .push because you will create a sparse array backed by a hashtable. You can preallocate sparse arrays up to 99999 elements which will be backed by a C array, after that it's a hashtable.

With the second array you are adding elements in a contiguous way starting from 0, so it will be backed by a real C array, not a hash table.

So roughly:

If your array indices go nicely from 0 to Length-1, with no holes, then it can be represented by a fast C array. If you have holes in your array, then it will be represented by a much slower hash table. The exception is that if you preallocate an array of size < 100000, then you can have holes in the array and still get backed by a C array:

var a = new Array(N); 

//If N < 100000, this will not make the array a hashtable:
a[50000] = "sparse";

var b = [] //Or new Array(N), with N >= 100000
//B will be backed by hash table
b[50000] = "Sparse";
//b.push("Sparse"), roughly same as above if you used new Array with N > 0

这篇关于在V8中使用数组（性能问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！