Optimize List.toList/.sublist and List.from on lists.

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> implements List<T> {
 
   void insert(int index, T element) {
     if ((index < 0) || (index > length)) {
       throw new RangeError.range(index, 0, length);
     }
@@ skipping 84 matching lines @@
   }
 
   void fillRange(int start, int end, [T fillValue]) {
     IterableMixinWorkaround.fillRangeList(this, start, end, fillValue);
   }
 
   List<T> sublist(int start, [int end]) {
     Lists.indicesCheck(this, start, end);
     if (end == null) end = this.length;
     int length = end - start;
-    if (start == end) return <T>[];
-    List list = new _GrowableList<T>.withCapacity(length);
-    list.length = length;
-    Lists.copy(this, start, list, 0, length);
-    return list;
+    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 result = new _GrowableList<T>.withData(data);
     if (length > 0) {
       result._setLength(length);
     }
@@ skipping 44 matching lines @@
   void add(T value) {
     var len = length;
     if (len == _capacity) {
       _grow(len * 2);
     }
     _setLength(len + 1);
     this[len] = value;
   }
 
   void addAll(Iterable<T> iterable) {
-    for (T elem in iterable) {
-      add(elem);
+    var len = length;
+    if (iterable is EfficientLength) {
+      var cap = _capacity;
+      // Pregrow if we know iterable.length.
+      var iterLen = iterable.length;
+      var newLen = len + iterLen;
+      if (newLen > cap) {
+        do {
+          cap *= 2;
+        } while (newLen > cap);
+        _grow(cap);
+      }
     }
+    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);
+    } while (true);
   }
 
   T removeLast() {
     var len = length - 1;
     var elem = this[len];
     this[len] = null;
     _setLength(len);
     return elem;
   }
 
@@ skipping 15 matching lines @@
 
   int indexOf(Object element, [int start = 0]) {
     return IterableMixinWorkaround.indexOfList(this, element, start);
   }
 
   int lastIndexOf(Object element, [int start = null]) {
     return IterableMixinWorkaround.lastIndexOfList(this, element, start);
   }
 
   void _grow(int new_length) {
+//    if (new_length < _kDefaultCapacity) new_length = _kDefaultCapacity;

[Florian Schneider, 2014/08/26 13:17:06]

Remove commented code?

[Lasse Reichstein Nielsen, 2014/08/26 13:46:53]

Or uncomment it, as was the intention.
I just commented it out to check the performance.

Probably safer to remove it now, and do some more performance checks before
adding it again.

     var new_data = new _List(new_length);
     for (int i = 0; i < length; i++) {
       new_data[i] = this[i];
     }
     _setData(new_data);
   }
 
   // Iterable interface.
 
   bool contains(Object element) {
@@ skipping 107 matching lines @@
     IterableMixinWorkaround.shuffleList(this, random);
   }
 
   String toString() => ListBase.listToString(this);
 
   Iterator<T> get iterator {
     return new ListIterator<T>(this);
   }
 
   List<T> toList({ bool growable: true }) {
-    return new List<T>.from(this, growable: growable);
+    var length = this.length;
+    if (length > 0) {
+      List list = growable ? new _List(length) : new _List<T>(length);
+      for (int i = 0; i < length; i++) {
+        list[i] = this[i];
+      }
+      if (!growable) return list;
+      var result = new _GrowableList<T>.withData(list);
+      result._setLength(length);
+      return result;
+    }
+    return growable ? <T>[] : new List<T>(0);
   }
 
   Set<T> toSet() {
     return new Set<T>.from(this);
   }
 
   Map<int, T> asMap() {
     return new IterableMixinWorkaround<T>().asMapList(this);
   }
 }