Optimize one-byte string's toUpperCase.

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 */ factory String.fromCharCode(int charCode) {
@@ skipping 817 matching lines @@
     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,
   ];
 
+  // Upper-case conversion table for Latin-1.
+  // lower-case ranges: 0x61-0x7a ('a' - 'z'), 0xe0-0xff.
+  // The characters 0xb5 (µ) and 0xff (ÿ) have uper case variants
+  // that are not Latin-1. These are marked as -1 in the table.
+  // The german scharfes s (\xdf) is converted into two character (SS),

[sra1, 2014/03/26 21:29:17]

The VM has a bug then, since it translates \xdf to itself.

dart2js translates ß -upper-> SS -lower-> ss since that is what the JavaScript
toUpperCase does.

Go has a rune-level ToUpper.

Interestingly there is an upper-case ß
http://en.wikipedia.org/wiki/Capital_%E1%BA%9E
which is "mandatory in official documentation when writing geographical names in
all-caps"

+  // and is also marked with -1.
+  // Conversion to lower case performed by subtracting 0x20.

[srdjan, 2014/03/26 21:18:14]

What is the performance impact of changing the table to Uint8List, final? It
would save quite a bit of memory for both tables.

[Lasse Reichstein Nielsen, 2014/03/27 10:20:15]

For toLowerCase, it's a roughly 13% reduction in performance, by my simple test.
Goes from ~4900 ops/ms to ~4300 ops/ms.

That's by changing the _LC_TABLE declaration to:
  static final _LC_TABLE = () {
    var result = new Uint8List(256);
    for (int i = 0; i < 256; i++) {
      var c = i;
      if (i >= 0x41 && (i <= 0x5a || (i >= 0xc0 && (i <= 0xde && i != 0xd7)))) {
        c |= 0x20;
      }
      result[i] = c;
    }
    return result;
  }();

It doesn't matter whether I cache the _LC_TABLE in a local variable or not.

Another option is to have _UC_TABLE be a const (one-byte) String, and use
.codeUnitAt for lookup. 
That actually only reduces throughput on my test by ~5% and 10% on Anders' test.
It does have all the advantages of being const and using less memory, and if we
optimize 'codeUnitAt' on const strings, it could get even faster.

We can use the same trick for upper-case table, we can use 0xff as marker
instead of -1.

[Anders Johnsen, 2014/03/27 10:38:10]

I like the String idea. It has the potential of being just as fast.

[srdjan, 2014/03/27 16:42:20]

I am surprised that the performance goes down, maybe some optimization is
missing. Anyway, I would rather initialize it using
Uint8List.fromList(const[0x00, 0x01, ...]).

[Lasse Reichstein Nielsen, 2014/03/27 18:09:13]

I assumed that would require the same space for the const table, unless the VM
can GC that table after initializing.
It's still just initialization that happens on the first run, so how it's done
shouldn't affect my benchmark at all.

+  static const _UC_TABLE = const [
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    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, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
+    0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
+    0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
+    0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
+    0x60, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
+    0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
+    0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
+    0x58, 0x59, 0x5a, 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,   -1, 0xb6, 0xb7,
+    0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
+    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
+    0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
+    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
+    0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde,   -1,
+    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
+    0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
+    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xf7,
+    0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde,   -1,
+  ];
+
   String toLowerCase() {
     for (int i = 0; i < this.length; i++) {
       final c = this.codeUnitAt(i);
       if (c == _LC_TABLE[c]) continue;
       // Upper-case character found.
       final result = _allocate(this.length);
       for (int j = 0; j < i; j++) {
         result._setAt(j, this.codeUnitAt(j));
       }
       for (int j = i; j < this.length; j++) {
         result._setAt(j, _LC_TABLE[this.codeUnitAt(j)]);
       }
       return result;
     }
     return this;
   }
 
+  String toUpperCase() {
+    for (int i = 0; i < this.length; i++) {
+      final c = this.codeUnitAt(i);
+      if (c == _UC_TABLE[c]) continue;
+      // Check rest of string for characters that require complex handling.
+      for (int j = i; j < this.length; j++) {
+        if (_UC_TABLE[this.codeUnitAt(i)] < 0) {
+          return super.toUpperCase();
+        }
+      }
+      // Lower-case characters found, but no problematic ones.
+      final result = _allocate(this.length);
+      for (int j = 0; j < i; j++) {
+        result._setAt(j, this.codeUnitAt(j));
+      }
+      for (int j = i; j < this.length; j++) {
+        result._setAt(j, _UC_TABLE[this.codeUnitAt(j)]);
+      }
+      return result;
+    }
+    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);
 }