Add optimized _OneByteString.toLowerCase.

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);
   }
 
   /* patch */ const factory String.fromEnvironment(String name,
@@ skipping 760 matching lines @@
     } else {
       for (int i = 0; i < delta; i++) {
         for (int j = 0; j < padLength; j++) {
           result._setAt(index++, padding.codeUnitAt(j));
         }
       }
     }
     return result;
   }
 
+  // Lower-case conversion table for Latin-1.
+  static const _LC_TABLE = const [
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,

[srdjan, 2014/03/25 20:05:37]

Why not Uin8List instead? Any performance difference?

[Anders Johnsen, 2014/03/25 20:10:46]

I tried, and saw a minor slowdown with a HTTP benchmark.

[Lasse Reichstein Nielsen, 2014/03/25 20:33:57]

It can't be const then, so it will be lazily initialized (and cost a little
extra to access, but reading it into a local once per method might be enough).

[srdjan, 2014/03/25 20:37:15]

A static final is quite efficient. Once the optimization kicks in, the variable
has been already initialized and the content is known and invariant .

[Anders Johnsen, 2014/03/25 20:38:26]

Putting it into a local final var made it even slower.

+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
+    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
+    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
+    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
+    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
+    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
+    0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
+    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
+    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
+    0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
+    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
+    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
+    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
+    0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
+    0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
+    0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
+    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
+    0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
+    0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
+    0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
+    0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
+    0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
+    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
+    0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
+    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xd7,
+    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xdf,
+    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
+    0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
+    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
+    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
+  ];
+
+  String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) {

[srdjan, 2014/03/25 20:05:37]

_toLowerCaseUpperCaseDetectedAt

[Lasse Reichstein Nielsen, 2014/03/25 20:10:12]

The "At" doesn't add anything when the parameter is named as it is.

[Anders Johnsen, 2014/03/25 20:10:46]

Done.

[Anders Johnsen, 2014/03/25 20:12:26]

No, but it makes the call-site more clear.

[srdjan, 2014/03/25 20:14:49]

It is all about reading the code at call site, where the argument names are not
visible. 

+    // String contains upper case characters. Create a new string.
+    final length = this.length;
+    final result = _allocate(length);
+    // First up to firstUpperIndex.
+    int i = 0;
+    for (; i < firstUpperCaseIndex; i++) {
+      result._setAt(i, this.codeUnitAt(i));
+    }

[Lasse Reichstein Nielsen, 2014/03/25 20:10:12]

I tried this split into "known non-uppercase" and "rest", and for me it was
slower than just having just one loop that translates everything. Probably
depends on the string, my strings weren't that long, so the first upper-case
string was early in the string.

I recommend trying without it. 
It gives just one loop with a completely standard for-loop from 0 to length.
That optimizes very well.

[Anders Johnsen, 2014/03/25 20:12:26]

Will try!

[srdjan, 2014/03/25 20:14:49]

We need to run the benchmarks on a typical set of inputs to gain meaningful
numbers. Are we doing that?

+    for (; i < length; i++) {
+      result._setAt(i, _LC_TABLE[this.codeUnitAt(i)]);
+    }
+    if (length == 1) {
+      return result[0];

[Lasse Reichstein Nielsen, 2014/03/25 20:10:12]

I don't think this is necessary. I haven't done it in other functions that
creates strings, like trim.

[Anders Johnsen, 2014/03/25 20:12:26]

But it it fetches the right 'symbol' object?

Srdjan, wdyk?

[srdjan, 2014/03/25 20:14:49]

I'd remove it.

[Anders Johnsen, 2014/03/25 20:26:06]

Done.

+    }
+    return result;
+  }
+
+  String toLowerCase() {
+    for (int i = 0; i < this.length; i++) {
+      final c = this.codeUnitAt(i);
+      // Ranges: 0x41-0x5a ('A' - 'Z'), 0xc0-0xd6, 0xd8-0xde.
+      if (c != _LC_TABLE[c]) {
+        return _toLowerCaseUpperCaseDetected(i);
+      }
+    }
+    return this;
+  }
+
   // Allocates a string of given length, expecting its content to be
   // set using _setAt.
   static _OneByteString _allocate(int length) native "OneByteString_allocate";
 
 
   static _OneByteString _allocateFromOneByteList(List<int> list)
       native "OneByteString_allocateFromOneByteList";
 
   // This is internal helper method. Code point value must be a valid
   // Latin1 value (0..0xFF), index must be valid.
@@ skipping 90 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);
 }