Avoid extra duplication of substrings during string.replaceAll.

Avoid extra duplication of substrings during string.replaceAll.

R=asiva@google.com, zerny@google.com

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

[Lasse Reichstein Nielsen, 2015-01-19 11:34:59]

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

[Lasse Reichstein Nielsen, 2015-01-19 11:35:00]

A 25-30% improvement on string replaceAll{,Mapped}.
Visible in the RegExp benchmark.

[zerny-google, 2015-01-20 13:43:11]

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

[zerny-google, 2015-01-20 13:43:11]

lgtm but let's have the other reviewers take a look too.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc
File runtime/lib/string.cc (right):

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:110: ASSERT(string.IsTwoByteString()
||string.IsExternalTwoByteString());
Nit: space after ||

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:492: throw new ArgumentError("${pattern} is not a
Pattern");
Is it OK that we no longer have an explicit ArgumentError here and below?

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:507: matches.add(-(startIndex | preMatchLength <<
_lengthShift));
Nit: add parens around <<

Also, does compacting the matches array like this have any measurable payoff?

[Florian Schneider, 2015-01-20 16:39:34]

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc
File runtime/lib/string.cc (right):

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:116: result |= TwoByteString::CharAt(string, i);
This should be ExternalTwoByteString::CharAt in the case of an
ExternalTwoByteString. Maybe move this dispatch to outside the loop.

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:547: return _joinReplaceAllResult(this, matches,
length,
Would it make sense to implement the 'this' two-byte case also in Dart instead
of going to C++?

[siva, 2015-01-21 00:29:20]

I assuming avoiding duplication should result in better performance, is there a
benchmark test to measure and demonstrate this. If an existing benchmark shows
improvement document the % improvement in the comments for this CL.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc
File runtime/lib/string.cc (right):

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:130: const Array& matches =
Array::Handle(matches_growable.data());
Since 'isolate' is available to the native method use it when creating handles.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:159: object ^= matches.At(i);
Missing check for if (i < len) here?

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:238: return result.raw();
This function seems to be long, do you think it would make it more readable if
the two 'for' loops are extracted out into helper functions?

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:570: i++;
This is really dicey, 'i' is being incremented and there is no check if it is
still '< matches.length', if it is expected to be less then at least document
that and assert that it is less.

[siva, 2015-01-21 00:29:46]

*I assuming*I am assuming*

[Lasse Reichstein Nielsen, 2015-01-21 10:48:43]

Benchmarks show improvements on the scale (ia32, x64 is comparable):

SunSpiderGolemRegexpDna (Intel Core i5) 13%
SunSpiderGolemRegexpDna (Intel Core 2)  15%
RegExp (Intel Core i5)                  49%
RegExp (Intel Core 2)                   85%

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc
File runtime/lib/string.cc (right):

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:110: ASSERT(string.IsTwoByteString()
||string.IsExternalTwoByteString());
On 2015/01/20 13:43:11, zerny-google wrote:
> Nit: space after ||

Done.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:116: result |= TwoByteString::CharAt(string, i);
On 2015/01/20 16:39:33, Florian Schneider wrote:
> This should be ExternalTwoByteString::CharAt in the case of an
> ExternalTwoByteString. Maybe move this dispatch to outside the loop.

Done.
Is there a simple way to get the uint16_t* of the data? It seems it's all in
private methods (either through .raw() or using CharAddr).

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:130: const Array& matches =
Array::Handle(matches_growable.data());
Done in this code. The rest of the file could do it a lot more too.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:159: object ^= matches.At(i);
On 2015/01/21 00:29:20, siva wrote:
> Missing check for if (i < len) here?

Done.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string.cc#ne...
runtime/lib/string.cc:238: return result.raw();
I think I'll move the first loop into a helper method. The second loop is doing
the actual work, so I think it fits here.

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:492: throw new ArgumentError("${pattern} is not a
Pattern");
Almost. I'll add back a check for "null", but we shouldn't be checking that the
argument has the type that its type annotation requires - the analyzer is there
to warn if you use it incorrectly.

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

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:507: matches.add(-(startIndex | preMatchLength <<
_lengthShift));
Done.
I see ~5% improvement on a small/micro benchmark.
It should be simple to turn it off and see the difference.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:547: return _joinReplaceAllResult(this, matches,
length,
The one-byte case actually turns out to be slower in some cases, so I'll limit
it to small strings. I'll see if I can find out why.

There is no TwoByteString._allocate and _setCharAt functions, so we can't create
a TwoByteString in Dart code like we can for OneByteString.

https://codereview.chromium.org/858543002/diff/40001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:570: i++;
Adding assert.
This function should only be called from the one above, where we only build
valid matches lists.
If someone calls it with bad data, it's OK to just die at the array access
instead of doing the i < matches.length check first.

[Lasse Reichstein Nielsen, 2015-01-21 13:52:10]

Patch 5 may have lost ~1-2 percentage improvement on RegExp (preliminary
results, benchmarks still running), but I think it's worth it. The code is much
nicer.

[siva, 2015-01-22 00:08:17]

LGTM once comments are addressed.

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

https://codereview.chromium.org/858543002/diff/70001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:46: static const int _maxStartValue = (1 << (30 -
_lengthSize)) - 1;
what are '11' and '30' here? can they be given descriptive names.

https://codereview.chromium.org/858543002/diff/70001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:533: if (replacementIsOneByte && length < 500) {
document this magic constant as
static const int _xxxxxxValue = 500;
in this class.

[Lasse Reichstein Nielsen, 2015-01-22 08:25:38]

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

https://codereview.chromium.org/858543002/diff/70001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:46: static const int _maxStartValue = (1 << (30 -
_lengthSize)) - 1;
11 is semi-arbitrarily chosen as the size of the length in the encoding of a
slice, so _lengthSize is the descriptive name.
I'll rename it to _lengthBits to make it clear what the unit is.

The 30 is a safe limit of available bits in a negative smi.
I'll give it a name.

https://codereview.chromium.org/858543002/diff/70001/runtime/lib/string_patch...
runtime/lib/string_patch.dart:533: if (replacementIsOneByte && length < 500) {
Done:   
static const int _maxJoinReplaceOneByteStringLength = 500;

I guess it could be shorter, but not without loosing precision :)

[Lasse Reichstein Nielsen, 2015-01-22 08:28:00]

Committed patchset #6 (id:90001) manually as 43059 (presubmit successful).