Improve string library performance. String concat and indexOf.

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 66 matching lines @@
   String operator +(String other) native "String_concat";
 
   String toString() {
     return this;
   }
 
   bool operator ==(Object other) {
     if (identical(this, other)) {
       return true;
     }
-    if ((other is !String) ||
+    // TODO(5413632): Compare hash codes when both are present.

[Ivan Posva, 2013/10/28 23:35:09]

I don't think comparing hash codes is effective, as I don't think you get them
frequently enough. So we might want to just remove this TODO.

[srdjan, 2013/10/29 17:02:29]

Done.

+    if ((other is! String) ||
         (this.length != other.length)) {
-      // TODO(5413632): Compare hash codes when both are present.
       return false;
     }
-    final len = this.length;
+    final int len = this.length;

[Ivan Posva, 2013/10/28 23:35:09]

?

[srdjan, 2013/10/29 17:02:29]

Removed type.

     for (int i = 0; i < len; i++) {
       if (this.codeUnitAt(i) != other.codeUnitAt(i)) {
         return false;
       }
     }
     return true;
   }
 
 
   int compareTo(String other) {
@@ skipping 314 matching lines @@
         isOneByteString = false;
         if (s is! String) {
           throw new ArgumentError(s);
         }
       }
       stringList[i] = s;
     }
     if (isOneByteString) {
       return _OneByteString._concatAll(stringList, totalLength);
     }
-    return _concatAllNative(stringList, 0, stringList.length);
+    return _concatRangeNative(stringList, 0, stringList.length);
   }
 
   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 64 matching lines @@
   }
 
   List<int> get codeUnits => new _CodeUnits(this);
 
   Runes get runes => new Runes(this);
 
   String toUpperCase() native "String_toUpperCase";
 
   String toLowerCase() native "String_toLowerCase";
 
+  // Concatenate ['start', 'end'[ elements of 'strings'. 'strings' must contain
+  // String elements. Optimized for OneByteStrings.
+  static String _concatRange(List<String> strings, int start, int end) {
+    if ((end - start) == 1) {
+      return strings[start];
+    }
+    final int numValues = strings.length;
+    if (start == 0 && (end == numValues)) {

[Ivan Posva, 2013/10/28 23:35:09]

(start == 0)

[srdjan, 2013/10/29 17:02:29]

Done.

+      int totalLength = 0;
+      for (int i = 0; i < numValues; i++) {
+        String s = strings[i];
+        if (s._cid != _OneByteString._classId) {
+          return _concatRangeNative(strings, start, end);
+        }
+        totalLength += s.length;
+      }
+      return _OneByteString._concatAll(strings, totalLength);
+    }
+    return _concatRangeNative(strings, start, end);
+  }
+
   // Call this method if not all list elements are known to be OneByteString(s).
   // 'strings' must be an _List or _GrowableList.
-  static String _concatAllNative(List<String> strings, int start, int end)
-      native "Strings_concatAll";
+  static String _concatRangeNative(List<String> strings, int start, int end)
+      native "String_concatRange";
 }
 
 
 class _OneByteString extends _StringBase implements String {
   static final int _classId = "A"._cid;
 
   factory _OneByteString._uninstantiable() {
     throw new UnsupportedError(
         "_OneByteString can only be allocated by the VM");
   }
@@ skipping 15 matching lines @@
       native "OneByteString_splitWithCharCode";
 
   List<String> split(Pattern pattern) {
     if ((pattern._cid == _OneByteString._classId) && (pattern.length == 1)) {
       return _splitWithCharCode(pattern.codeUnitAt(0));
     }
     return super.split(pattern);
   }
 
   // All element of 'strings' must be OneByteStrings.
-  static _concatAll(_List<String> strings, int totalLength) {
+  static _concatAll(List<String> strings, int totalLength) {
     // TODO(srdjan): Improve code below and raise or eliminate the limit.
     if (totalLength > 128) {
       // Native is quicker.
-      return _StringBase._concatAllNative(strings, 0, strings.length);
+      return _StringBase._concatRangeNative(strings, 0, strings.length);
     }
     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;
   }
 
+  int indexOf(Pattern pattern, [int start = 0]) {
+    final int len = this.length;

[Ivan Posva, 2013/10/28 23:35:09]

Not sure whether we should be using this. or not. Also no types inside methods.

[srdjan, 2013/10/29 17:02:29]

The name' length' is too generic, therefore I feel it makes in this case for a
more readable code. Let me know if you disagree.

+    // Specialize for single character pattern.
+    if ((pattern._cid == _OneByteString._classId) &&

[Ivan Posva, 2013/10/28 23:35:09]

What about an ExternalOneByteString?

[srdjan, 2013/10/29 17:02:29]

Added: TODO. The inner loop should stay monomorphic. Will need to add a test.

+        (pattern.length == 1) &&
+        (start >= 0) && (start < len)) {
+      final int patternCu0 = pattern.codeUnitAt(0);

[Ivan Posva, 2013/10/28 23:35:09]

Another quick test you could do: If the pattern is outside of the one byte
string range then you will not find it.

[srdjan, 2013/10/29 17:02:29]

Good idea, once I allow two byte strings.

+      for (int i = start; i < len; i++) {
+        if (this.codeUnitAt(i) == patternCu0) {
+          return i;
+        }
+      }
+      return -1;
+    }
+    return super.indexOf(pattern, start);
+  }
+
   // Allocates a string of given length, expecting its content to be
   // set using _setAt.
   static _OneByteString _allocate(int length) native "OneByteString_allocate";
 
   // This is internal helper method. Code point value must be a valid
   // Latin1 value (0..0xFF), index must be valid.
   void _setAt(int index, int codePoint) native "OneByteString_setAt";
 }
 
 
@@ skipping 80 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);
 }