Why are pre-allocated arrays slower than dynamically allocated arrays?

[Boris Cherny]

Befuddled javascript engineer here.

Test case here: http://jsperf.com/preallocated-vs-dynamic-arrays/

I'd expect a pre-allocated array to be faster than instantiating a new array every time and copying values over from the old one, if that's what's going on under the hood. Or is V8 using some sort of linked list internally? Can someone help explain what's going on with these test cases?

=Boris

[Jakob Kummerow]

There, fixed that for ya: http://jsperf.com/preallocated-vs-dynamic-arrays/3

Pre-allocated vs. dynamically grown is only part of the story. For preallocated arrays, 100,000 just so happens to be the threshold where V8 decides to give you a slow (a.k.a. "dictionary mode") array.

Also, growing arrays on demand doesn't allocate a new array every time an element is added. Instead, the backing store is grown in chunks (currently it's grown by roughly 50% each time it needs to be grown, but that's a heuristic that might change over time).

--
--
v8-users mailing list
v8-u...@googlegroups.com
http://groups.google.com/group/v8-users
---
You received this message because you are subscribed to the Google Groups "v8-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Boris Cherny]

Fascinating, thank you for the response!

Pre-allocated vs. dynamically grown is only part of the story. For preallocated arrays, 100,000 just so happens to be the threshold where V8 decides to give you a slow (a.k.a. "dictionary mode") array.

What data structures does V8 use under the hood to store arrays? Is 100k the only critical threshold? A link to the source would suffice if it's at all readable :)

Also, growing arrays on demand doesn't allocate a new array every time an element is added. Instead, the backing store is grown in chunks (currently it's grown by roughly 50% each time it needs to be grown, but that's a heuristic that might change over time).

By "grown" do you mean "a new larger array is instantiated which inherits members from the old array"?

Cheers

[Jakob Kummerow]

On Sun, Dec 15, 2013 at 7:16 PM, Boris Cherny <bch...@gmail.com> wrote:

Fascinating, thank you for the response!

Pre-allocated vs. dynamically grown is only part of the story. For preallocated arrays, 100,000 just so happens to be the threshold where V8 decides to give you a slow (a.k.a. "dictionary mode") array.

What data structures does V8 use under the hood to store arrays?

Arrays for dense elements, dictionaries for sparse elements.

 

Is 100k the only critical threshold?

I'm afraid I don't understand the question. V8 has plenty of heuristics for all sorts of behavior. I'm not sure what a "critical threshold" is.

 

A link to the source would suffice if it's at all readable :) 

I'd start at https://code.google.com/p/v8/source/browse/branches/bleeding_edge/src/objects.cc#12675 (JSObject::SetElementWithoutInterceptor), but array handling is fairly complex, so you'll have to read several thousand lines to understand all of it.

Also, growing arrays on demand doesn't allocate a new array every time an element is added. Instead, the backing store is grown in chunks (currently it's grown by roughly 50% each time it needs to be grown, but that's a heuristic that might change over time).

By "grown" do you mean "a new larger array is instantiated which inherits members from the old array"?

var array = new Array(1000);  // packed backing store with capacity 1000, array.length == 1000

for (var i = 0; i < 1000; ++i) array[i] = i;  // no allocation

array[1000] = 1000;  // array must be grown, new backing store is allocated with capacity ~1500, a.length = 1001. Elements are copied from old to new backing store, old backing store will be discarded by next GC.

for (var i = 1001; i < 1500; ++i) array[i] = i;  // no further allocation as we already have the backing store

array[1600] = 1600;  // new backing store allocated, capacity about 1600*1.5 = 2400

// Additional fun to be had:

array[0] = 1.5;  // the first double! New double backing store is allocated, all integer elements are converted and copied over.

array[1000000] = 1;  // array is no longer dense -> dictionary backing store is allocated, all elements are copied over.

[Boris Cherny]

var array = new Array(1000);  // packed backing store with capacity 1000, array.length == 1000

for (var i = 0; i < 1000; ++i) array[i] = i;  // no allocation

array[1000] = 1000;  // array must be grown, new backing store is allocated with capacity ~1500, a.length = 1001. Elements are copied from old to new backing store, old backing store will be discarded by next GC.

for (var i = 1001; i < 1500; ++i) array[i] = i;  // no further allocation as we already have the backing store

array[1600] = 1600;  // new backing store allocated, capacity about 1600*1.5 = 2400

// Additional fun to be had:

array[0] = 1.5;  // the first double! New double backing store is allocated, all integer elements are converted and copied over.

array[1000000] = 1;  // array is no longer dense -> dictionary backing store is allocated, all elements are copied over.

Very cool, thank you for the writeup!