Shrink 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);
     }
@@ skipping 95 matching lines @@
 
   factory _GrowableList.from(Iterable<T> other) {
     List<T> result = new _GrowableList<T>();
     result.addAll(other);
     return result;
   }
 
   factory _GrowableList.withData(_List data)
     native "GrowableList_allocate";
 
+  int get _capacity native "GrowableList_getCapacity";
+
   int get length native "GrowableList_getLength";
 
-  int get _capacity native "GrowableList_getCapacity";
-
   void set length(int new_length) {
     if (new_length > _capacity) {

[Ivan Posva, 2016/02/16 23:54:54]

Judging from Srdjan's comment we should not intermix new_length and new_capacity
interchangably here.

How about:
void set length(int new_length) {
  var new_capacity = (new_length == 0) ? _kDefaultCapacity : new_length;
  if (new_capacity > capacity) {
    ...
  }

and changing the parameter name in _grow and _shrink to be clearer (e.g.
new_capacity).

[Cutch, 2016/02/17 21:12:54]

Done.

       _grow(new_length);
+      _setLength(new_length);
+      return;
+    }
+    // We are shrinking. Pick the method which has fewer writes.
+    // In the shrink-to-fit path, we write 2 * |new_length| words
+    // (null fill + copy).

[Ivan Posva, 2016/02/16 23:54:54]

How about "(null init + copy)" and "(null overwrite)"?

[Cutch, 2016/02/17 21:12:54]

Done.

+    // In the non-shrink-to-fit path, we write |length - new_length| words
+    // (null fill).
+    final bool shouldShrinkToFit = (2 * new_length) < (length - new_length);

[Ivan Posva, 2016/02/16 23:54:54]

Which would mean here (new_capacity + new_length) < (length - new_length).

[Cutch, 2016/02/17 21:12:54]

Done.

+    if (shouldShrinkToFit) {
+      _shrink(new_length);
     } else {
       for (int i = new_length; i < length; i++) {
         this[i] = null;
       }
     }
     _setLength(new_length);
   }
 
   void _setLength(int new_length) native "GrowableList_setLength";
 
@@ skipping 85 matching lines @@
   }
 
   void _grow(int new_length) {
     var new_data = new _List(new_length);
     for (int i = 0; i < length; i++) {
       new_data[i] = this[i];
     }
     _setData(new_data);
   }
 
+  void _shrink(int new_length) {

[srdjan, 2016/02/16 23:45:29]

if (new_length == _capacity) return

[Ivan Posva, 2016/02/16 23:54:54]

I don't think this would work here as the code above assumes that the data array
will be initialized with nulls automatically. The new call does this implicitly.

[Cutch, 2016/02/17 21:12:54]

Acknowledged.

[Cutch, 2016/02/17 21:12:54]

Acknowledged.

+    var new_data = new _List(new_length == 0 ? _kDefaultCapacity : new_length);
+    for (int i = 0; i < new_length; i++) {
+      new_data[i] = this[i];
+    }
+    _setData(new_data);
+  }
+
   // 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 97 matching lines @@
       result._setLength(length);
       return result;
     }
     return growable ? <T>[] : new List<T>(0);
   }
 
   Set<T> toSet() {
     return new Set<T>.from(this);
   }
 }