Optimize concatenation of lists of onebyte strings by implementing it in Dart.

runtime/lib/string_patch.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.
 
 patch class String {
   /* patch */ factory String.fromCharCodes(Iterable<int> charCodes) {
     return _StringBase.createFromCharCodes(charCodes);
   }
 }
 
@@ skipping 318 matching lines @@
     buffer.write(onNonMatch(this.substring(startIndex)));
     return buffer.toString();
   }
 
 
   /**
    * Convert all objects in [values] to strings and concat them
    * into a result string.
    */
   static String _interpolate(List values) {
-    int numValues = values.length;
+    final int numValues = values.length;
     _ObjectArray stringList = new List(numValues);
+    bool isOneByteString = true;
+    int totalLength = 0;
     for (int i = 0; i < numValues; i++) {
-      stringList[i] = values[i].toString();
+      var s = values[i].toString();
+      if (s is! _OneByteString) {
+        isOneByteString = false;
+      }
+      totalLength += s.length;

[siva, 2013/05/06 23:08:49]

The totalLength addition could be done under an else right, as it is not needed
for the non OneByteString case.
if (s is! _OneByteString) {
  ..
} else {
  totalLength += ...
}

[srdjan, 2013/05/08 21:17:21]

Done.

+      stringList[i] = s;
     }
-    return _concatAll(stringList);
+    if (isOneByteString) {
+      return _OneByteString._concatAll(stringList, totalLength);
+    }
+    return _concatAllNative(stringList);
   }
 
   Iterable<Match> allMatches(String str) {
     List<Match> result = new List<Match>();
     int length = str.length;
     int patternLength = this.length;
     int startIndex = 0;
     while (true) {
       int position = str.indexOf(this, startIndex);
       if (position == -1) {
@@ skipping 72 matching lines @@
       if (string is! String) {
         throw new ArgumentError(Error.safeToString(string));
       }
       stringsList.add(string);
     }
     return concatAll(stringsList);
   }
 
   static String concatAll(Iterable<String> strings) {
     _ObjectArray stringsArray;
+    final len = strings.length;
     if (strings is _ObjectArray) {
       stringsArray = strings;
-      for (int i = 0; i < strings.length; i++) {
+      for (int i = 0; i < len; i++) {
         if (strings[i] is! String) throw new ArgumentError(strings[i]);
       }
     } else {
-      int len = strings.length;
       stringsArray = new _ObjectArray(len);
       int i = 0;
-      for (String string in strings) {
+      for (int i = 0; i < len; i++) {
+        var string = strings[i];
         if (string is! String) throw new ArgumentError(string);
         stringsArray[i++] = string;
       }
     }
     return _concatAll(stringsArray);

[siva, 2013/05/06 23:08:49]

Why not have a isOneByteString flag which is set in the loop above and directly
dispatch to 
_OneByteString._concatAll(....) or
_concatAllNative(...)
like how you do in _interpolate above.

   }
 
-  static String _concatAll(_ObjectArray<String> strings)
+  static String _concatAll(_ObjectArray<String> strings) {
+    int totalLength = 0;
+    final stringsLength = strings.length;
+    for (int i = 0; i < stringsLength; i++) {
+      var e = strings[i];
+      if (e is! _OneByteString) {
+        return _concatAllNative(strings);
+      }
+      totalLength += e.length;

[siva, 2013/05/06 23:08:49]

Ditto comment about totalLength under an else.

[srdjan, 2013/05/08 21:17:21]

Here it is different since we stop looping the first time we recognize that it
is not a oneByteString.

+    }
+    return _OneByteString._concatAll(strings, totalLength);
+  }
+
+  // Call this method if not all list elements are OneByteString-s.
+  static String _concatAllNative(_ObjectArray<String> strings)
       native "Strings_concatAll";
 }
 
 
 class _OneByteString extends _StringBase implements String {
   factory _OneByteString._uninstantiable() {
     throw new UnsupportedError(
         "_OneByteString can only be allocated by the VM");
   }
 
@@ skipping 14 matching lines @@
   List<String> _splitWithCharCode(int charCode)
       native "OneByteString_splitWithCharCode";
 
   List<String> split(Pattern pattern) {
     if ((pattern is _OneByteString) && (pattern.length == 1)) {
       return _splitWithCharCode(pattern.codeUnitAt(0));
     }
     return super.split(pattern);
   }
 
+  // All element of 'strings' must be OneByteStrings.
+  static _concatAll(_ObjectArray<String> strings, int totalLength) {
+    var res = _OneByteString._allocate(totalLength);
+    final stringsLength = strings.length;
+    int rIx = 0;
+    for (int i = 0; i < stringsLength; i++) {
+      _OneByteString e = strings[i];
+      final eLength = e.length;
+      for (int s = 0; s < eLength; s++) {
+        res._setAt(rIx++, e.codeUnitAt(s));
+      }
+    }
+    return res;
+  }
+
   // Allocates a string of given length, expecting its content to be
   // set using _setAt.
   static _OneByteString _allocate(int length) native "OneByteString_allocate";
 
   // Code point value must be a valid Latin1 (0..0xFF). Index must be valid.
   void _setAt(int index, int codePoint) native "OneByteString_setAt";
 }
 
 
 class _TwoByteString extends _StringBase implements String {
@@ skipping 116 matching lines @@
 class _CodeUnits extends Object with ListMixin<int>,
                                      UnmodifiableListMixin<int> {
   /** The string that this is the code units of. */
   String _string;
 
   _CodeUnits(this._string);
 
   int get length => _string.length;
   int operator[](int i) => _string.codeUnitAt(i);
 }