CODEWITHSUNDEEP
javascriptarraysperformancev8
bugs
bugs

Reputation: 15313

How does V8 optimise the creation of very large arrays?

Recently, I had to work on optimising a task that involved the creation of really large arrays (~ 10⁸ elements).

I tested a few different methods, and, according to jsperf, the following option seemed to be the fastest.

var max = 10000000;
var arr = new Array(max);
for (let i = 0; i < max; i++) {
  arr[i] = true;
}

Which was ~ 85% faster than

var max = 10000000;
var arr = [];
for (let i = 0; i < max; i++) {
  arr.push(true);
}

And indeed, the first snippet was much faster in my actual app as well.

However, my understanding was that the V8 engine was able to perform optimised operations on array with PACKED_SMI_ELEMENTS elements kind, as opposed to arrays of HOLEY_ELEMENTS.

So my question is the following:

why is the first snippet faster than the second one?

Related questions I've been through:

Upvotes: 7

Views: 1413

Answers (1)

jmrk
jmrk

Reputation: 40521

V8 developer here. The first snippet is faster because new Array(max) informs V8 how big you want the array to be, so it can allocate an array of the right size immediately; whereas in the second snippet with []/.push(), the array starts at zero capacity and has to be grown several times, which includes copying its existing elements to a new backing store.

https://www.youtube.com/watch?v=m9cTaYI95Zc is a good presentation but probably should have made it clearer how small the performance difference between packed and holey elements is, and how little you should worry about it.

In short: whenever you know how big you need an array to be, it makes sense to use new Array(n) to preallocate it to that size. When you don't know in advance how large it's going to be in the end, then start with an empty array (using [] or new Array() or new Array(0), doesn't matter) and grow it as needed (using a.push(...) or a[a.length] = ..., doesn't matter).

Side note: your "for loop with new Array() and push" benchmark creates an array that's twice as big as you want.

Upvotes: 13

Related Questions