On Sun, Dec 15, 2013 at 7:16 PM, Boris Cherny <[email protected]> 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. > > Cheers > > On Sunday, December 15, 2013 3:49:31 AM UTC-8, Jakob Kummerow wrote: > >> 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). >> >> >> On Sun, Dec 15, 2013 at 7:31 AM, Boris Cherny <[email protected]> wrote: >> >>> 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 >>> >> -- -- v8-users mailing list [email protected] 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
