Optimize _GrowableArray._join and _StringBase._interpolate.

Optimize _GrowableArray._join and _StringBase._interpolate.

R=fschneider@google.com

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

[Lasse Reichstein Nielsen, 2014-09-11 06:16:28]

lrn@google.com changed reviewers:
+ fschneider@google.com

[Florian Schneider, 2014-09-11 13:27:36]

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

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:691: String operator +(String other) {
I'm not convinced about this optimization: Maybe the native operator+ defined in
StringBase should be optimized instead by "copying" it down to all sub-classes
of StringBase and optimized for the argument type by the compiler.

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:692: if (ClassID.getID(other) !=
ClassID.cidExternalOneByteString) {
Why cidExternalOneByteString? Shouldn't it be cidOneByteString?

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:708: for (int i = 0; i < secondLength; i++) {
I'd rename secondLength to otherLength. s/firstLength/thisLength, too.

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:709: _setAt(result, firstLength + i,
this.codeUnitAt(i));
s/this/other/

[Lasse Reichstein Nielsen, 2014-09-11 14:15:06]

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

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:691: String operator +(String other) {
If you can do compiler magic to do better, by all means do :)

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:692: if (ClassID.getID(other) !=
ClassID.cidExternalOneByteString) {
Ack. I had both at some time, and apparently deleted the wrong one.
That also explains why the errors below wasn't caught in tests - no external
strings in the tests.

This also improves performance, now that the code actually runs.

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:708: for (int i = 0; i < secondLength; i++) {
On 2014/09/11 13:27:36, Florian Schneider wrote:
> I'd rename secondLength to otherLength. s/firstLength/thisLength, too.

Done.

https://codereview.chromium.org/551823002/diff/100001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:709: _setAt(result, firstLength + i,
this.codeUnitAt(i));
On 2014/09/11 13:27:36, Florian Schneider wrote:
> s/this/other/

Done.

[Lasse Reichstein Nielsen, 2014-09-11 14:24:23]

I tried a small micro-benchmark to see the difference.
It is extreme for one-element interpolations, noticeable for two-element
interpolations, and negligible for three-element interpolations.

Results before (bigger is better):

One-element interpolation ASCII: 3179.0 /ms
One-element interpolation non-ASCII: 1575.0 /ms
One-element interpolation Object ASCII: 3194.5 /ms
One-element interpolation Object non-ASCII: 1578.0 /ms
Two-element interpolation ASCII: 2699.0 /ms
Two-element interpolation non-ASCII: 1428.0 /ms
Two-element interpolation Object ASCII: 2702.0 /ms
Two-element interpolation Object non-ASCII: 1414.5 /ms
Three-element interpolation ASCII: 2063.0 /ms
Three-element interpolation non-ASCII: 1198.5 /ms
Three-element interpolation Object ASCII: 2047.5 /ms
Three-element interpolation Object non-ASCII: 1224.5 /ms

Results after:

One-element interpolation ASCII: 32870.0 /ms
One-element interpolation non-ASCII: 30453.5 /ms
One-element interpolation Object ASCII: 32248.5 /ms
One-element interpolation Object non-ASCII: 30975.0 /ms
Two-element interpolation ASCII: 3202.5 /ms
Two-element interpolation non-ASCII: 2059.5 /ms
Two-element interpolation Object ASCII: 3273.5 /ms
Two-element interpolation Object non-ASCII: 2059.5 /ms
Three-element interpolation ASCII: 2163.0 /ms
Three-element interpolation non-ASCII: 1300.5 /ms
Three-element interpolation Object ASCII: 2307.0 /ms
Three-element interpolation Object non-ASCII: 1300.0 /ms



Benchmark included below for the curious:
--------

bench1(name, s1, s2, s3) {
  int c = 0;
  int e = 0;
  const N = 1000;
  var r = 0;
  final sw = new Stopwatch()..start();
  do {
    for (int i = 0; i < N; i++) {
      r = "$s1".length + "$s2".length + "$s3".length;
    }
    c += N;
    e = sw.elapsedMilliseconds;
  } while (e < 2000);
  sw.stop();
  print("One-element interpolation $name: ${c/e} /ms");
  return r;
}

bench2(name, s1, s2, s3) {
  int c = 0;
  int e = 0;
  const N = 1000;
  var r = 0;
  final sw = new Stopwatch()..start();
  do {
    for (int i = 0; i < N; i++) {
      r = "x$s1".length + "x$s2".length + "x$s3".length;
    }
    c += N;
    e = sw.elapsedMilliseconds;
  } while (e < 2000);
  sw.stop();
  print("Two-element interpolation $name: ${c/e} /ms");
  return r;
}

bench3(name, s1, s2, s3) {
  int c = 0;
  int e = 0;
  const N = 1000;
  var r = 0;
  final sw = new Stopwatch()..start();
  do {
    for (int i = 0; i < N; i++) {
      r = "$s1/$s1".length + "$s2/$s2".length + "$s3/$s3".length;
    }
    c += N;
    e = sw.elapsedMilliseconds;
  } while (e < 2000);
  sw.stop();
  print("Three-element interpolation $name: ${c/e} /ms");
  return r;
}

class O {
  final String string;
  O(this.string);
  String toString() => string;
}

main() {
  o(s) => new O(s);
  for (var bench in [bench1, bench2, bench3]) {
    bench("ASCII", "a", "abcdefgh", "z" * 200);
    bench("non-ASCII", "\u3008", "abcdefg\u3008", "\u3008" * 200);
    bench("Object ASCII", o("a"), o("abcdefgh"), o("z" * 200));
    bench("Object non-ASCII", o("\u3008"), o("abcdefg\u3008"), o("\u3008" *
200));
  }
}

[srdjan, 2014-09-11 16:33:00]

srdjan@google.com changed reviewers:
+ srdjan@google.com

[srdjan, 2014-09-11 16:33:01]

I am not convinced about the need for this CL. The disadvantage of this CL that
it adds considerably more code without obvious benefit in real world programs
(microbenchmarks do not count). Additionally, the problem of slow + operator in
the loop is properly solvable by converting the loop to use StringBuffer either
by the programmer or by the optimizing compiler.

P.S.: Whenever changing VM's libs, please remember to add a member of the VM
team to the list of reviewers.

[Lasse Reichstein Nielsen, 2014-09-11 18:28:23]

On 2014/09/11 16:33:01, srdjan wrote:
> I am not convinced about the need for this CL. The disadvantage of this CL
that
> it adds considerably more code without obvious benefit in real world programs
> (microbenchmarks do not count). 

Real world programs do use "$x" as the canonical way to turn x into a string.
Except that it's discouraged because "$x" is slow in the VM.
That use has an x10 speedup here, so that alone is definitely worth it.

Special casing two elements might not be as important.

Both could perhaps be handled better by recognizing the number of elements at
parsing time and generating specialized intermediate instructions instead of
allocating an array and going through _interpolate.

Reusing the argument array is just a memory saving.

> Additionally, the problem of slow + operator in
> the loop is properly solvable by converting the loop to use StringBuffer
either
> by the programmer or by the optimizing compiler.

Not sure which plus or loop you are referring to.
The plus operator optimization is just trying to special case Latin1 string +
Latin1 string to make it faster in general. 
It affects the outcome of the micro-benchmark only because the + operator is
used in the two-element interpolation special case.

> P.S.: Whenever changing VM's libs, please remember to add a member of the VM
> team to the list of reviewers.

I picked Florian Schneider for that reason. Should I also add a US-based
reviewer?

[srdjan, 2014-09-11 18:30:18]

On 2014/09/11 18:28:23, Lasse Reichstein Nielsen wrote:
> On 2014/09/11 16:33:01, srdjan wrote:
> > I am not convinced about the need for this CL. The disadvantage of this CL
> that
> > it adds considerably more code without obvious benefit in real world
programs
> > (microbenchmarks do not count). 
> 
> Real world programs do use "$x" as the canonical way to turn x into a string.
> Except that it's discouraged because "$x" is slow in the VM.
> That use has an x10 speedup here, so that alone is definitely worth it.
> 
> Special casing two elements might not be as important.
> 
> Both could perhaps be handled better by recognizing the number of elements at
> parsing time and generating specialized intermediate instructions instead of
> allocating an array and going through _interpolate.
> 
> Reusing the argument array is just a memory saving.
> 
> > Additionally, the problem of slow + operator in
> > the loop is properly solvable by converting the loop to use StringBuffer
> either
> > by the programmer or by the optimizing compiler.
> 
> Not sure which plus or loop you are referring to.
> The plus operator optimization is just trying to special case Latin1 string +
> Latin1 string to make it faster in general. 
> It affects the outcome of the micro-benchmark only because the + operator is
> used in the two-element interpolation special case.
> 
> > P.S.: Whenever changing VM's libs, please remember to add a member of the VM
> > team to the list of reviewers.
> 
> I picked Florian Schneider for that reason. Should I also add a US-based
> reviewer?

Sorry my mistake, the AAR VM team members are more than adequate.

[srdjan, 2014-09-11 18:43:18]

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:283: // return _StringBase._interpolate(this);
remove dead code

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:288: // Is non-zero if list contains a
non-onebyte string
Terminate comment with perioid

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:291: final element =
final String element?

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:313: throw new ArgumentError(object);
For this we should be using checked mode not explicit type checks.

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

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:539: throw new ArgumentError(first);
Use types for checked mode (final String firstString) instead of throwing
ArgumentError-s (also below)

[Lasse Reichstein Nielsen, 2014-09-11 19:04:00]

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:283: // return _StringBase._interpolate(this);
On 2014/09/11 18:43:17, srdjan wrote:
> remove dead code

Acknowledged.

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:288: // Is non-zero if list contains a
non-onebyte string
On 2014/09/11 18:43:17, srdjan wrote:
> Terminate comment with perioid

Acknowledged.

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:291: final element =
On 2014/09/11 18:43:16, srdjan wrote:
> final String element?

Acknowledged.

https://codereview.chromium.org/551823002/diff/120001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:313: throw new ArgumentError(object);
This is simulating the interpolation "$object". With that optimized, this
function is probably not worth it.

[Lasse Reichstein Nielsen, 2014-09-15 07:20:48]

Reduced complexity of interpolate.
PTAL

[Ivan Posva, 2014-09-16 14:57:31]

iposva@google.com changed reviewers:
+ iposva@google.com

[Ivan Posva, 2014-09-16 14:57:32]

Thanks,
-Ivan

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:277: while (nextElement is String) {
Please add comments where appropriate that this is not really a while loop over
i at the most outer level.

There are many internal continuations of the loop. As far as I can tell quickly
once you get here, you will not go back to the top of the loop. If that is the
case you should state that.

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:291: final String element = "$nextElement";
Shadowing element makes this inner loop even more confusing.

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:303: return _StringBase._concatRangeNative(list,
0, length);
Might want to pass codeUnitCount? We already know it here.

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

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:541: values[i] = s;
Again, non-properly looping loop. Please add comments as to what is going on and
ideally switch to a while statement.

[Lasse Reichstein Nielsen, 2014-09-18 09:30:37]

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
File runtime/lib/growable_array.dart (right):

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:277: while (nextElement is String) {
On 2014/09/16 14:57:32, Ivan Posva wrote:
> Please add comments where appropriate that this is not really a while loop
over
> i at the most outer level.
> 
> There are many internal continuations of the loop. As far as I can tell
quickly
> once you get here, you will not go back to the top of the loop. If that is the
> case you should state that.

Done.

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:291: final String element = "$nextElement";
Renamed to elementString.

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
runtime/lib/growable_array.dart:303: return _StringBase._concatRangeNative(list,
0, length);
We probably always have that information, or could have it, when using
_concatRangeNative, so adding an extra argument sounds like a good idea.

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

https://codereview.chromium.org/551823002/diff/160001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:541: values[i] = s;
Comments added.
I've tried rewriting as while statement.
I', not sure it's more readable, but that might be author blindness.

The alternative I would normally use is:
  oneByteLoop: {
    for (...) {
       if (is not onebyteString) break oneByteLoop;
    }
    return _OneByteString._concatAll(...)
  }
  // handle non-onebyte case.

I am usually requested to rewrite that to something without labels, hence this
nested loop structure.

(Language feature request: for (...) {...} else { return ... } !)

[Ivan Posva, 2014-09-19 17:20:52]

On 2014/09/18 09:30:37, Lasse Reichstein Nielsen wrote:
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
> File runtime/lib/growable_array.dart (right):
> 
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
> runtime/lib/growable_array.dart:277: while (nextElement is String) {
> On 2014/09/16 14:57:32, Ivan Posva wrote:
> > Please add comments where appropriate that this is not really a while loop
> over
> > i at the most outer level.
> > 
> > There are many internal continuations of the loop. As far as I can tell
> quickly
> > once you get here, you will not go back to the top of the loop. If that is
the
> > case you should state that.
> 
> Done.
> 
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
> runtime/lib/growable_array.dart:291: final String element = "$nextElement";
> Renamed to elementString.
> 
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/growable_ar...
> runtime/lib/growable_array.dart:303: return
_StringBase._concatRangeNative(list,
> 0, length);
> We probably always have that information, or could have it, when using
> _concatRangeNative, so adding an extra argument sounds like a good idea.
> 
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/string_patc...
> File runtime/lib/string_patch.dart (right):
> 
>
https://codereview.chromium.org/551823002/diff/160001/runtime/lib/string_patc...
> runtime/lib/string_patch.dart:541: values[i] = s;
> Comments added.
> I've tried rewriting as while statement.
> I', not sure it's more readable, but that might be author blindness.
> 
> The alternative I would normally use is:
>   oneByteLoop: {
>     for (...) {
>        if (is not onebyteString) break oneByteLoop;
>     }
>     return _OneByteString._concatAll(...)
>   }
>   // handle non-onebyte case.
> 
> I am usually requested to rewrite that to something without labels, hence this
> nested loop structure.
> 
> (Language feature request: for (...) {...} else { return ... } !)

Lasse, did you upload your latest changes?

Thanks,
-Ivan

[Lasse Reichstein Nielsen, 2014-09-19 18:48:29]

Ack no, I didn't, sorry about that. Should be there now.

[Lasse Reichstein Nielsen, 2014-09-25 10:53:29]

PTAL

[Florian Schneider, 2014-09-25 11:14:45]

LGTM.

Please make sure that all cases in _join, _interpolate and operator+
(non-OneByteString, non-String elements, etc) are covered by our tests.

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

https://codereview.chromium.org/551823002/diff/180001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:683: }
I would really like this to be specialized for external one- and both kinds of
two-byte strings as well. On the other hand we may not want to duplicate this
whole method 4 times.

How is performance if you factor the code below here out into a common helper,
and add operator+ to all concrete String classes?

[Lasse Reichstein Nielsen, 2014-09-30 08:28:27]

Committed patchset #11 (id:200001) manually as 40800 (presubmit successful).

[Lasse Reichstein Nielsen, 2014-09-30 09:17:45]

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

https://codereview.chromium.org/551823002/diff/180001/runtime/lib/string_patc...
runtime/lib/string_patch.dart:683: }
I think I'll revert this operator for now and do some more tests.
It's no longer used in interpolate, so it really is a separate change.