[Core] Optimize List

sdk/lib/collection/list.dart

 // Copyright (c) 2013, 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.
 
 part of dart.collection;
 
 /** A reusable set used to identify cyclic lists during toString() calls. */
 Set _toStringVisiting = new HashSet.identity();
 
 /**
@@ skipping 62 matching lines @@
     return this[length - 1];
   }
 
   E get single {
     if (length == 0) throw new StateError("No elements");
     if (length > 1) throw new StateError("Too many elements");
     return this[0];
   }
 
   bool contains(Object element) {
-    int length = this.length;
-    for (int i = 0; i < length; i++) {
+    for (int i = 0; i < this.length; i++) {
       if (this[i] == element) return true;

[Lasse Reichstein Nielsen, 2014/02/03 13:27:44]

If the '==' operator on the elements modify the list, we want a concurrent
modification error here.

Ofcourse it shouldn't, but when it does, it's most likely a programming error,
and we want to catch it soon.

I am considering whether just changing the loop limit to list.length will enable
better optimizations, but I don't want to avoid the error here.

[vicb, 2014/02/03 13:38:30]

I haven't thought about operator overloading here... Good catch.

However this would mean than both the element is container and it modify the
list, should be pretty unusual.

But still I agree the check should remain.

What about an 'assert' so that prod code is not affected. If it's ok what about
changing for assert for all the ConcurrentModificationError ? 

[Lasse Reichstein Nielsen, 2014/02/04 12:32:00]

Pretty unusual, hopefully.

While we could probably wrap some modification checks in asserts, we couldn't do
it for all of them. In some cases, a concurrent modification might mean that we
can't continue iterating (e.g., a linked list where the links are no longer
valid).

I think I'll prefer to keep the checks in production mode too.
But if we are doing them on fixed-length lists, we should fix that.

[vicb, 2014/02/04 13:00:31]

Crashing because of the check or because of any other induced errors in not
really different in prod ? I'll revert anyway
Don't get what you mean by this last sentence ?

-      if (length != this.length) {
-        throw new ConcurrentModificationError(this);
-      }
     }
     return false;
   }
 
   bool every(bool test(E element)) {
     int length = this.length;
     for (int i = 0; i < length; i++) {
       if (!test(this[i])) return false;
       if (length != this.length) {
         throw new ConcurrentModificationError(this);
@@ skipping 54 matching lines @@
       }
       if (length != this.length) {
         throw new ConcurrentModificationError(this);
       }
     }
     if (matchFound) return match;
     throw new StateError("No matching element");
   }
 
   String join([String separator = ""]) {
-    int length = this.length;
-    if (!separator.isEmpty) {
-      if (length == 0) return "";
-      String first = "${this[0]}";
-      if (length != this.length) {
-        throw new ConcurrentModificationError(this);
-      }
-      StringBuffer buffer = new StringBuffer(first);
-      for (int i = 1; i < length; i++) {
-        buffer.write(separator);
-        buffer.write(this[i]);
-        if (length != this.length) {
-          throw new ConcurrentModificationError(this);
-        }
-      }
-      return buffer.toString();
+    if (this.length == 0) return "";
+    StringBuffer buffer = new StringBuffer();
+    if (separator.isEmpty) {
+      buffer.writeAll(this);
     } else {
-      StringBuffer buffer = new StringBuffer();
-      for (int i = 0; i < length; i++) {
-        buffer.write(this[i]);
-        if (length != this.length) {
-          throw new ConcurrentModificationError(this);
-        }
-      }
-      return buffer.toString();
+      buffer.writeAll(this, separator);
     }
+    return buffer.toString();

[Lasse Reichstein Nielsen, 2014/02/03 13:27:44]

This change looks ok, if performance is as good (or better!) as before.

My quick checks tracks it as pretty much performance neutral (checking join of
10000 long fixed-length List and Uint32List of the numbers 0..999 as string and
as number).

[vicb, 2014/02/03 13:38:30]

I haven't seen much of a change in perf - it should be *marginally* faster as
the length check as been removed and the code is doing pretty much the same
(inside writeAll)

[Lasse Reichstein Nielsen, 2014/02/04 12:32:00]

I see marginally slower (very, very marginally), probably because it goes
through an iterator instead of directly indexing into the list.
I think it's still ok, though.

   }
 
   Iterable<E> where(bool test(E element)) => new WhereIterable<E>(this, test);
 
   Iterable map(f(E element)) => new MappedListIterable(this, f);
 
   Iterable expand(Iterable f(E element)) =>
       new ExpandIterable<E, dynamic>(this, f);
 
   E reduce(E combine(E previousValue, E element)) {
@@ skipping 336 matching lines @@
       result.write('[');
       result.writeAll(this, ', ');
       result.write(']');
      } finally {
        _toStringVisiting.remove(this);
      }
 
     return result.toString();
   }
 }