New growth strategy for growable arrays

The current growth strategy for growable arrays allocates a backing array of size 2 at (empty) creation and doubles the size whenever the capacity is insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are promoted to old-space or survive an old-space gc when running dart2js and Fasta. For these applications, the vast majority of arrays stay empty. More than half of the total object size of promoted backing arrays is backing for empty growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters and length), and object sizes are rounded up to an even number of words, we waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created with a shared, zero-sized array as backing, avoiding the allocation of a backing array if no elements are added. When the array needs to grow, it starts out at 3 and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays specially. In particular, the Array::MakeArray function needs to allocate a new, empty array if its result is to be returned to Dart code.

Benchmarks suggest that the change improves memory usage by a few percent overall and does not significantly affect run time.

BUG=
R=erikcorry@google.com

Committed: https://github.com/dart-lang/sdk/commit/cec963f028198ec5871840491ba78b096ad0b819

[Aske Simon Christensen, 2017-06-20 14:07:26]

Description was changed from

==========
New growth strategy for growable arrays

BUG=
==========

to

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

BUG=
==========

[Aske Simon Christensen, 2017-06-20 14:12:57]

Description was changed from

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

BUG=
==========

to

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

BUG=
==========

[Aske Simon Christensen, 2017-06-20 14:34:51]

Description was changed from

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

BUG=
==========

to

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty. More than half
of the total object size of promoted backing arrays is backing for empty
growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

BUG=
==========

[Aske Simon Christensen, 2017-06-20 14:34:51]

askesc@google.com changed reviewers:
+ erikcorry@google.com, lrn@google.com

[Aske Simon Christensen, 2017-06-20 14:38:50]

Description was changed from

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty. More than half
of the total object size of promoted backing arrays is backing for empty
growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

BUG=
==========

to

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty. More than half
of the total object size of promoted backing arrays is backing for empty
growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

Benchmarks suggest that the change improves memory usage by a few percent
overall and does not significantly affect run time.

BUG=
==========

[Lasse Reichstein Nielsen, 2017-06-21 07:36:22]

SGTM, but I'm not a VM engineer :)

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:91: var data = _new_data(length);
_new_data is not Dart naming. Use _newData instead.

(I know the VM code hasn't always followed Dart conventions, especially before
the style guide even existed, but let's not make it worse :)

The name isn't very telling either (see below).

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:222: static _List _new_data(int capacity) {
The name isn't very telling. It's a noun phrase, which sounds more like a
parameterized property than a method called for its side-effects.
Consider createDataList or createBackingList instead.

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:232: int _growth_capacity(int old_capacity) {
-> _growthCapacity

The name isn't very descriptive. I can't read the name and tell you what it
does. Not that I have a much better idea, though.
Maybe:
  int _nextLargerCapacity(int oldCapacity)

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:233: return (old_capacity == 0) ? 3 :
old_capacity * 2 + 1;
As branchless expression:
  (old_capacity | 1) * 2 + 1
since you know that capacities are always zero or odd. :)

Consider using "=> e;" function instead of "{ return e; }".

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:237: var new_data = _new_data(new_capacity);
While you are here, consider new_data -> newData.

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22085: // The backing array may be a shared instance, or
may not have correct
This function isn't talking about "backing arrays" otherwise, so it's unclear
what it means here. I assume this function handles all allocation of
fixed-length lists (_List instances), not just backing arrays of growable
arrays.

[erikcorry, 2017-06-21 07:58:31]

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22085: // The backing array may be a shared instance, or
may not have correct
On 2017/06/21 07:36:21, Lasse Reichstein Nielsen wrote:
> This function isn't talking about "backing arrays" otherwise, so it's unclear
> what it means here. I assume this function handles all allocation of
> fixed-length lists (_List instances), not just backing arrays of growable
> arrays.

The naming of this method is terrible.  It's not used for all allocation of
fixed-length lists.  What this tricky method does is to take a growable list
(list object with fixed length backing list) and returns a non-growable list. 
Usually it does this by extracting and trimming the backing and returning that.

[erikcorry, 2017-06-21 09:06:01]

What Lasse said and LGTM

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array.cc
File runtime/lib/growable_array.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.cc:94: return Array::MakeArray(array, true);
Boolean literal arguments are not readable later, so we don't allow them like
this.  The normal way is to write:

return Array::MakeArray(array, /*unique=*/true);

personally I prefer:

return Array::MakeArray(array, /* unique= */ true);

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:143: void add(T value) {
First part of this deleted comment is still true and probably useful.

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:228: // in terms of object size
since this is free because of alignment requirements of the GC.

(Don't forget full stops at the end of comments.)

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22069: RawArray* Array::MakeArray(const
GrowableObjectArray& growable_array,
Perhaps call this MakeNongrowableArray?

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22171: intptr_t new_capacity = (Capacity() == 0) ? 3 :
Capacity() * 2 + 1;
Lasse's trick for branchless calculations works here too.

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.h
File runtime/vm/object.h (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.h#newcode...
runtime/vm/object.h:7771: value.IsCanonical()));
Perhaps insert a comment to the effect that the backing array is always untyped.

[Lasse Reichstein Nielsen, 2017-06-21 09:14:15]

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22069: RawArray* Array::MakeArray(const
GrowableObjectArray& growable_array,
Or MakeArrayNongrowable, which doesn't sound as if "Make" means "Create" (which
it does when followed by a noun phrase).

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22085: // The backing array may be a shared instance, or
may not have correct
ACK, my bad. I actually recognized that at the call point and promptly forgot it
again when I got here.

[Aske Simon Christensen, 2017-06-21 12:19:33]

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:222: static _List _new_data(int capacity) {
On 2017/06/21 07:36:21, Lasse Reichstein Nielsen wrote:
> The name isn't very telling. It's a noun phrase, which sounds more like a
> parameterized property than a method called for its side-effects.
> Consider createDataList or createBackingList instead.

Chose "allocateData", since that is what it does.

https://codereview.chromium.org/2949803002/diff/1/runtime/lib/growable_array....
runtime/lib/growable_array.dart:233: return (old_capacity == 0) ? 3 :
old_capacity * 2 + 1;
On 2017/06/21 07:36:21, Lasse Reichstein Nielsen wrote:
> As branchless expression:
>   (old_capacity | 1) * 2 + 1

Which can be simplified to (old_capacity * 2) | 3

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/2949803002/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:22069: RawArray* Array::MakeArray(const
GrowableObjectArray& growable_array,
On 2017/06/21 09:14:15, Lasse Reichstein Nielsen wrote:
> Or MakeArrayNongrowable, which doesn't sound as if "Make" means "Create"
(which
> it does when followed by a noun phrase).

Array::MakeFixedLength corresponds to the Dart-side makeListFixedLength which is
a wrapper for it.

[Aske Simon Christensen, 2017-06-22 08:52:14]

Description was changed from

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty. More than half
of the total object size of promoted backing arrays is backing for empty
growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

Benchmarks suggest that the change improves memory usage by a few percent
overall and does not significantly affect run time.

BUG=
==========

to

==========
The current growth strategy for growable arrays allocates a backing array of
size 2 at (empty) creation and doubles the size whenever the capacity is
insufficient while adding elements.

I collected statistics for the sizes and capacities of growable arrays which are
promoted to old-space or survive an old-space gc when running dart2js and Fasta.
For these applications, the vast majority of arrays stay empty. More than half
of the total object size of promoted backing arrays is backing for empty
growable arrays.

Furthermore, since the overhead for an array is 3 words (header, type parameters
and length), and object sizes are rounded up to an even number of words, we
waste one word for all even-sized arrays.

This CL changes the growth strategy so that empty growable arrays are created
with a shared, zero-sized array as backing, avoiding the allocation of a backing
array if no elements are added. When the array needs to grow, it starts out at 3
and grows to double size plus one each time: 7, 15, 31, ...

A few places in the VM code need to handle these shared, zero-sized arrays
specially. In particular, the Array::MakeArray function needs to allocate a new,
empty array if its result is to be returned to Dart code.

Benchmarks suggest that the change improves memory usage by a few percent
overall and does not significantly affect run time.

BUG=
R=erikcorry@google.com

Committed:
https://github.com/dart-lang/sdk/commit/cec963f028198ec5871840491ba78b096ad0b819
==========

[Aske Simon Christensen, 2017-06-22 08:52:16]

Committed patchset #2 (id:20001) manually as
cec963f028198ec5871840491ba78b096ad0b819 (presubmit successful).