New growth strategy for growable arrays

runtime/lib/growable_array.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 class _GrowableList<T> extends ListBase<T> {
   void insert(int index, T element) {
     if ((index < 0) || (index > length)) {
       throw new RangeError.range(index, 0, length);
     }
     if (index == this.length) {
@@ skipping 69 matching lines @@
     if (length == 0) return <T>[];
     List list = new _List(length);
     for (int i = 0; i < length; i++) {
       list[i] = this[start + i];
     }
     var result = new _GrowableList<T>.withData(list);
     result._setLength(length);
     return result;
   }
 
-  static const int _kDefaultCapacity = 2;
-
   factory _GrowableList(int length) {
-    var data = new _List((length == 0) ? _kDefaultCapacity : length);
+    var data = _allocateData(length);
     var result = new _GrowableList<T>.withData(data);
     if (length > 0) {
       result._setLength(length);
     }
     return result;
   }
 
   factory _GrowableList.withCapacity(int capacity) {
-    var data = new _List((capacity == 0) ? _kDefaultCapacity : capacity);
+    var data = _allocateData(capacity);
     return new _GrowableList<T>.withData(data);
   }
 
   factory _GrowableList.withData(_List data) native "GrowableList_allocate";
 
   int get _capacity native "GrowableList_getCapacity";
 
   int get length native "GrowableList_getLength";
 
   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);
       return;
     }
     // We are shrinking. Pick the method which has fewer writes.
     // In the shrink-to-fit path, we write |new_capacity + new_length| words
     // (null init + copy).
     // In the non-shrink-to-fit path, we write |length - new_length| words
     // (null overwrite).
@@ skipping 10 matching lines @@
   }
 
   void _setLength(int new_length) native "GrowableList_setLength";
 
   void _setData(_List array) native "GrowableList_setData";
 
   T operator [](int index) native "GrowableList_getIndexed";
 
   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) {
     var len = length;
     if (len == _capacity) {
-      _grow(len * 2);
+      _grow(_nextCapacity(len));
     }
     _setLength(len + 1);
     this[len] = value;
   }
 
   void addAll(Iterable<T> iterable) {
     var len = length;
     final cid = ClassID.getID(iterable);
     final isVMList = (cid == ClassID.cidArray) ||
         (cid == ClassID.cidGrowableObjectArray) ||
         (cid == ClassID.cidImmutableArray);
     if (isVMList || (iterable is EfficientLengthIterable)) {
       var cap = _capacity;
       // Pregrow if we know iterable.length.
       var iterLen = iterable.length;
       var newLen = len + iterLen;
       if (newLen > cap) {
         do {
-          cap *= 2;
+          cap = _nextCapacity(cap);
         } while (newLen > cap);
         _grow(cap);
       }
       if (isVMList) {
         if (identical(iterable, this)) {
           throw new ConcurrentModificationError(this);
         }
         this._setLength(newLen);
         for (int i = 0; i < iterLen; i++) {
           this[len++] = iterable[i];
         }
         return;
       }
     }
     Iterator it = iterable.iterator;
     if (!it.moveNext()) return;
     do {
       while (len < _capacity) {
         int newLen = len + 1;
         this._setLength(newLen);
         this[len] = it.current;
         if (!it.moveNext()) return;
         if (this.length != newLen) throw new ConcurrentModificationError(this);
         len = newLen;
       }
-      _grow(_capacity * 2);
+      _grow(_nextCapacity(_capacity));
     } while (true);
   }
 
   T removeLast() {
     var len = length - 1;
     var elem = this[len];
     this.length = len;
     return elem;
   }
 
   T get first {
     if (length > 0) return this[0];
     throw IterableElementError.noElement();
   }
 
   T get last {
     if (length > 0) return this[length - 1];
     throw IterableElementError.noElement();
   }
 
   T get single {
     if (length == 1) return this[0];
     if (length == 0) throw IterableElementError.noElement();
     throw IterableElementError.tooMany();
     ;
   }
 
+  // Shared array used as backing for new empty growable arrays.
+  static final _List _emptyList = new _List(0);
+
+  static _List _allocateData(int capacity) {
+    if (capacity == 0) {
+      // Use shared empty list as backing.
+      return _emptyList;
+    }
+    // Round up size to the next odd number, since this is free
+    // because of alignment requirements of the GC.
+    return new _List(capacity | 1);
+  }
+
+  // Grow from 0 to 3, and then double + 1.
+  int _nextCapacity(int old_capacity) => (old_capacity * 2) | 3;
+
   void _grow(int new_capacity) {
-    var new_data = new _List(new_capacity);
+    var newData = _allocateData(new_capacity);
     for (int i = 0; i < length; i++) {
-      new_data[i] = this[i];
+      newData[i] = this[i];
     }
-    _setData(new_data);
+    _setData(newData);
   }
 
   void _shrink(int new_capacity, int new_length) {
-    var new_data = new _List(new_capacity);
+    var newData = _allocateData(new_capacity);
     for (int i = 0; i < new_length; i++) {
-      new_data[i] = this[i];
+      newData[i] = this[i];
     }
-    _setData(new_data);
+    _setData(newData);
   }
 
   // Iterable interface.
 
   void forEach(f(T element)) {
     int initialLength = length;
     for (int i = 0; i < length; i++) {
       f(this[i]);
       if (length != initialLength) throw new ConcurrentModificationError(this);
     }
@@ skipping 99 matching lines @@
       result._setLength(length);
       return result;
     }
     return growable ? <T>[] : new List<T>(0);
   }
 
   Set<T> toSet() {
     return new Set<T>.from(this);
   }
 }