A few clarifications:
On Sat, Feb 20, 2016 at 8:18 PM, Louis Santillan <[email protected]> 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]> 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.
