Optimize one-byte string's toUpperCase.

runtime/lib/string_patch.dart

Index: runtime/lib/string_patch.dart
diff --git a/runtime/lib/string_patch.dart b/runtime/lib/string_patch.dart
index 5d72fdc1450ee7210abdf1d11cd6cb13bc922710..0e2ef929bcaec1c7dc3b33a8c79af775f201ecd7 100644
--- a/runtime/lib/string_patch.dart
+++ b/runtime/lib/string_patch.dart
@@ -835,6 +835,48 @@ class _OneByteString extends _StringBase implements String {
     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);
@@ -852,6 +894,29 @@ class _OneByteString extends _StringBase implements String {
     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";