New growth strategy for growable arrays

runtime/lib/growable_array.dart

Index: runtime/lib/growable_array.dart
diff --git a/runtime/lib/growable_array.dart b/runtime/lib/growable_array.dart
index b004b062b4406b2f38c4ab47da9ee4cbf6f8fc42..7ae3724fab720b45336da95d950c8eab4a527d95 100644
--- a/runtime/lib/growable_array.dart
+++ b/runtime/lib/growable_array.dart
@@ -87,10 +87,8 @@ class _GrowableList<T> extends ListBase<T> {
     return result;
   }
 
-  static const int _kDefaultCapacity = 2;
-
   factory _GrowableList(int length) {
-    var data = new _List((length == 0) ? _kDefaultCapacity : length);
+    var data = _new_data(length);

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

_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).

     var result = new _GrowableList<T>.withData(data);
     if (length > 0) {
       result._setLength(length);
@@ -99,7 +97,7 @@ class _GrowableList<T> extends ListBase<T> {
   }
 
   factory _GrowableList.withCapacity(int capacity) {
-    var data = new _List((capacity == 0) ? _kDefaultCapacity : capacity);
+    var data = _new_data(capacity);
     return new _GrowableList<T>.withData(data);
   }
 
@@ -112,16 +110,6 @@ class _GrowableList<T> extends ListBase<T> {
   void set length(int new_length) {
     int old_capacity = _capacity;
     int new_capacity = new_length;
-    if (new_length == 0) {
-      // Ensure that we use _kDefaultCapacity only when the old_capacity
-      // is greater than _kDefaultCapacity otherwise we end up growing the
-      // the array.
-      if (old_capacity < _kDefaultCapacity) {
-        new_capacity = old_capacity;
-      } else {
-        new_capacity = _kDefaultCapacity;
-      }
-    }
     if (new_capacity > old_capacity) {
       _grow(new_capacity);
       _setLength(new_length);
@@ -152,14 +140,10 @@ class _GrowableList<T> extends ListBase<T> {
 
   void operator []=(int index, T value) native "GrowableList_setIndexed";
 
-  // The length of this growable array. It is always less than or equal to the
-  // length of the object array, which itself is always greater than 0, so that
-  // grow() does not have to check for a zero length object array before
-  // doubling its size.
   void add(T value) {

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

First part of this deleted comment is still true and probably useful.

     var len = length;
     if (len == _capacity) {
-      _grow(len * 2);
+      _grow(_growth_capacity(len));
     }
     _setLength(len + 1);
     this[len] = value;
@@ -178,7 +162,7 @@ class _GrowableList<T> extends ListBase<T> {
       var newLen = len + iterLen;
       if (newLen > cap) {
         do {
-          cap *= 2;
+          cap = _growth_capacity(cap);
         } while (newLen > cap);
         _grow(cap);
       }
@@ -204,7 +188,7 @@ class _GrowableList<T> extends ListBase<T> {
         if (this.length != newLen) throw new ConcurrentModificationError(this);
         len = newLen;
       }
-      _grow(_capacity * 2);
+      _grow(_growth_capacity(_capacity));
     } while (true);
   }
 
@@ -232,8 +216,25 @@ class _GrowableList<T> extends ListBase<T> {
     ;
   }
 
+  // Shared array used as backing for new empty growable arrays
+  static final _List _emptyList = new _List(0);
+
+  static _List _new_data(int capacity) {

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

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.

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

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

+    if (capacity == 0) {
+      // Use shared empty list as backing
+      return _emptyList;
+    }
+    // Round up size to the next odd number, since this is free
+    // in terms of object size

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

since this is free because of alignment requirements of the GC.

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

+    return new _List(capacity | 1);
+  }
+
+  int _growth_capacity(int old_capacity) {

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

-> _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)

+    return (old_capacity == 0) ? 3 : old_capacity * 2 + 1;

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

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; }".

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

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

+  }
+
   void _grow(int new_capacity) {
-    var new_data = new _List(new_capacity);
+    var new_data = _new_data(new_capacity);

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

While you are here, consider new_data -> newData.

     for (int i = 0; i < length; i++) {
       new_data[i] = this[i];
     }
@@ -241,7 +242,7 @@ class _GrowableList<T> extends ListBase<T> {
   }
 
   void _shrink(int new_capacity, int new_length) {
-    var new_data = new _List(new_capacity);
+    var new_data = _new_data(new_capacity);
     for (int i = 0; i < new_length; i++) {
       new_data[i] = this[i];
     }