Thanks a lot Jokob for the clarifications. How fast is Object.keys() on a dense array?
On Sunday, February 21, 2016 at 5:12:47 PM UTC-5, Jakob Kummerow wrote: > > A few clarifications: > > On Sat, Feb 20, 2016 at 8:18 PM, Louis Santillan <[email protected] > <javascript:>> wrote: > >> In JS, the size of the Array is not directly related to the index keys >> of the Array. In this respect, JS is memory conservative. So, you >> can always pre-allocate an array of 50 entries and until you add a >> 51st entry, the runtime shouldn't have to grow the Array which will >> then (often) make it sparse. > > > To be precise, the JS spec doesn't say anything about preallocation > behavior. Implementations can do whatever they think is clever. Also, I > don't see how adding a 51st element to a dense 50-element array would make > it sparse (in either the mathematical or the memory-layout sense of the > word). > > >> In v8, however, you can trigger sparse >> behavior (or hashed behavior) by using poor (sub-optimal) indexing as >> well. >> >> ``` >> // Memory dense, sub-optimal access array >> var i, a = new Array( 50 ); >> for( i = 0; i < 50; i++ ) >> { >> a[ i * 50 ] = ( i + 1 ) * 50; >> } >> ``` >> >> v8 initially expects that `a` will have indexes [0...49]. It's smart >> enough to realize that it doesn't need to allocate more memory but >> array accesses are forever slower once your second index becomes 50 in >> the above code. >> > > For recent V8 versions, this is not correct. With the code above, the > array still has "fast elements" (i.e. a contiguous, non-dictionary backing > store) in the end. > The general concept is true, however: at some point there's a sparseness > threshold where V8 will use a dictionary for the elements. > > >> Also, as you saw, you can hint to runtime your intentions for the >> Array but touching `.length`. This helps when you need to grow the >> array but hurts if you truncate it. v8 reverts to sparse behavior in >> the truncation case. >> > > Incorrect. Truncating an array does not trigger to-dictionary conversion > of its elements backing store. > > >> On Sat, Feb 20, 2016 at 7:11 AM, Michael Zhou >> <[email protected] <javascript:>> wrote: >> > From this perf https://jsperf.com/preallocating-array/27, using >> > pre-allocated Array(size) seems the fastest. >> > > Yes, those results make sense. > > > On Saturday, February 20, 2016 at 8:57:20 AM UTC-5, Dean McNamee wrote: >> >> >> >> https://youtu.be/UJPdhx5zTaw?t=17m43s >> >> >> >> Not sure if that advice still stands as it's a few years old, but my >> >> experience has been, in the general case, it is unfortunately faster >> >> to allocate an empty array and use push() than to preallocate an array >> >> of the desired size and populate it. I have notes above a utility >> >> function I wrote that said I measured a 2x improvement in using push >> >> over Array(size), but I can't tell you now for what sort of size >> >> values that was. >> > > Preallocation behavior of Array(N) has changed over time. I believe the > dictionary threshold used to be N=100,000, whereas more recent V8 versions > assume that programmers know what they're doing and preallocate even for > much larger values of N. > > >> >> >> >> As always, just try it and measure. >> > > Strong +1! > And don't obsess about it -- even if you see a 2x difference in a > microbenchmark, real uses cases might have very different performance > characteristics. > Keep in mind that there are no "good" and "bad" representations -- what > works better depends on the use case. > > >> I've also found using some of the >> >> native methods helps in the process to understand why the performance >> >> difference is there. >> >> >> >> You can probably use something like the native %HasFastProperties() to >> >> check (this means running with --allow_natives_syntax). >> > > In V8, properties != elements. You're looking for > %HasDictionaryElements(). > > >> >> >> >> There is also %_HasFastPackedElements() in Hydrogen, but I didn't look >> >> to see what the difference is. >> > > Don't use that one, it's subtle and doesn't do what you think it does. > > >> >> >> >> On Sat, Feb 20, 2016 at 1:05 PM, Michael Zhou >> >> <[email protected]> wrote: >> >> > If I have >> >> > >> >> > var arr = new Array(50); // Should be dense, I guess? >> >> > arr[20] = 0; >> >> > arr[40] = 1; >> >> > arr[20] = undefined; >> >> > var keys = Object.keys(arr); >> >> > >> >> > Will this access pattern make v8 think arr is a sparse array and >> change >> >> > to >> >> > using a hash table? >> > > No, Object.keys() does not convert array elements to dictionary mode. > > >> >> > >> >> > Also, is copying from old back store to new back store unavoidable >> when >> >> > I >> >> > grow the array by doing >> >> > for (var i = 50; i < 100; i++) { >> >> > arr[i] = 0; >> >> > } >> > > Yes, when a backing store is grown, the old backing store's contents must > be copied into the new one. (V8 used to have an optimization that tried to > avoid this in a very specific corner case, but in general, objects in > memory can't be grown in-place.) > > >> >> > >> >> > ? Thanks. >> > > -- -- 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/d/optout.
