Optimize one-byte string's toUpperCase.

Optimize one-byte string's toUpperCase.

R=ajohnsen@google.com, srdjan@google.com

Committed: https://code.google.com/p/dart/source/detail?r=34812

[Lasse Reichstein Nielsen, 2014-03-26 20:54:00]

I need to run some benchmarks :)

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

DBQ

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:844: // Conversion to lower case performed by
subtracting 0x20.
What is the performance impact of changing the table to Uint8List, final? It
would save quite a bit of memory for both tables.

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

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:842: // The german scharfes s (\xdf) is converted
into two character (SS),
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"

[Lasse Reichstein Nielsen, 2014-03-27 10:20:14]

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:844: // Conversion to lower case performed by
subtracting 0x20.
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]

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:844: // Conversion to lower case performed by
subtracting 0x20.
On 2014/03/27 10:20:15, Lasse Reichstein Nielsen wrote:
> 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.

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

[srdjan, 2014-03-27 16:42:19]

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:844: // Conversion to lower case performed by
subtracting 0x20.
On 2014/03/27 10:20:15, Lasse Reichstein Nielsen wrote:
> 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.

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]

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dart
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/1/runtime/lib/string_patch.dar...
runtime/lib/string_patch.dart:844: // Conversion to lower case performed by
subtracting 0x20.
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.

[Bob Nystrom, 2014-03-28 15:57:38]

Drive-by!

https://codereview.chromium.org/213293002/diff/20001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/20001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:823: // The characters 0xb5 (µ) and 0xff (ÿ) have
uper case variants
"uper" -> "upper".

[Lasse Reichstein Nielsen, 2014-04-07 08:14:17]

PTAL

https://codereview.chromium.org/213293002/diff/20001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/20001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:823: // The characters 0xb5 (µ) and 0xff (ÿ) have
uper case variants
Done, thanks.

[Anders Johnsen, 2014-04-07 09:07:25]

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:866: if (c == _UC_TABLE.codeUnitAt(c)) continue;
This will not work with 0xff. Consider using 0x00 as marker, and check if the
current char is 0x00.

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:868: for (int j = i; j < this.length; j++) {
Would it be better to have one loop? The fast version (another one byte string)
now has two full iterations.

[Lasse Reichstein Nielsen, 2014-04-07 11:36:27]

PTAL

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:866: if (c == _UC_TABLE.codeUnitAt(c)) continue;
Well spotted.

https://codereview.chromium.org/213293002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:868: for (int j = i; j < this.length; j++) {
We have several cases, in order of increasing complexity:
- all upper case. First loop handles everything.
- some latin-1 with upper-case also latin-1. This has two iterations and one
allocation.
- some latin-1 with non-latin-1 upper case. This has one iteration and a
super-call.

With your change, we will do the allocation before the super-call, but only have
1.5 iteration.
We should try it, but I'm not sure it's a save overall.

[Anders Johnsen, 2014-04-07 11:43:43]

LGTM, with comments.

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:867: // Check rest of string for characters that
require complex handling.
complex -> non-latin1

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:869: final c = this.codeUnitAt(j);
Would this give a shadow warning with the editor?

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:870: if (_UC_TABLE.codeUnitAt(c) == 0x00 && c !=
0x00) {
Please add a comment here as well.

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:874: // Lower-case characters found, but no
problematic ones.
problematic one -> all within the latin1 range

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
File tests/corelib/string_case_test.dart (right):

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
tests/corelib/string_case_test.dart:34: Expect.equals("\u03Bc",
"\xb5".toUpperCase().toLowerCase());  /// 02: continued
Long line.

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
tests/corelib/string_case_test.dart:35: // Zero.
Do you have a test that would have spotted the 0xff issue? For lower-case, we
have a one-byte-string vs two-byte-string test for all characters. Can we do
that here as well?

[Lasse Reichstein Nielsen, 2014-04-07 12:12:13]

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:867: // Check rest of string for characters that
require complex handling.
On 2014/04/07 11:43:43, Anders Johnsen wrote:
> complex -> non-latin1

I thought about that, but "\xdf".toUpperCase() == "SS" is pure Latin-1, so it
would be incorrect.

Reworded.

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:869: final c = this.codeUnitAt(j);
No idea. It can at most be a hint, since the spec does not mandate a warning.
I don't think it is a problem.

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:870: if (_UC_TABLE.codeUnitAt(c) == 0x00 && c !=
0x00) {
On 2014/04/07 11:43:43, Anders Johnsen wrote:
> Please add a comment here as well.

Done.

https://codereview.chromium.org/213293002/diff/60001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:874: // Lower-case characters found, but no
problematic ones.
On 2014/04/07 11:43:43, Anders Johnsen wrote:
> problematic one -> all within the latin1 range

Reworded.

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
File tests/corelib/string_case_test.dart (right):

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
tests/corelib/string_case_test.dart:34: Expect.equals("\u03Bc",
"\xb5".toUpperCase().toLowerCase());  /// 02: continued
On 2014/04/07 11:43:43, Anders Johnsen wrote:
> Long line.

Done.

https://codereview.chromium.org/213293002/diff/60001/tests/corelib/string_cas...
tests/corelib/string_case_test.dart:35: // Zero.
It should be detected by the "\xff".toUpperCase() case alone.
That's why I added the "\x00" test. 

I'll add a few more tests, just for good measure.

[srdjan, 2014-04-07 15:41:39]

lgtm

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:873: if (_UC_TABLE.codeUnitAt(c) == 0x00 && c !=
0x00) {
Please add more parentheses.

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:874: // We use the 0x00 value for characters other
than NUL that don't
s/NUL/NULL/

[Lasse Reichstein Nielsen, 2014-04-07 16:03:55]

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
File runtime/lib/string_patch.dart (right):

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:873: if (_UC_TABLE.codeUnitAt(c) == 0x00 && c !=
0x00) {
Will do.

https://codereview.chromium.org/213293002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:874: // We use the 0x00 value for characters other
than NUL that don't
"null character" would be better then, the "nul" is just the common
abbreviation.

[Lasse Reichstein Nielsen, 2014-04-08 07:19:48]

Committed patchset #7 manually as r34812 (presubmit successful).