Faster non-regexp global string.replace.

Faster non-regexp global string.replace.
BUG=v8:1662
Committed: http://code.google.com/p/v8/source/detail?r=9180

[Yang, 2011-09-07 13:33:40]

Previous implementation of string.replace would call the chain
RegExpImpl::Exec->RegExpImpl::AtomExec->SearchString including all the type
checks, conversions, determining search strategy, etc. for every single match,
which makes this rather slow.

This would speed up the most used cases for string.replace, for example when a
string is replaced with URL encoded characters. For a specially designed test
case the performance improvement almost reaches 70%.

Please take a look.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2773
src/runtime.cc:2773: char pattern,
Moved up from further below.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2795
src/runtime.cc:2795: Vector<const SubjectChar> subject,
Moved up from further below.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2820
src/runtime.cc:2820: {
Refactored code from Runtime_StringSplit.

[Lasse Reichstein, 2011-09-07 13:50:52]

LGTM.

Another possible optimization is to not find all the indices first, but do it
inline. It saves the intermediate data structure. In that case you don't know
the length of the resulting string, but it's often sufficient to allocate a
string at the end of newspace, and extend or crop it as needed.

At least in the case where the replacement's length is the same as the pattern's
length, you do know the exact length of the result before finding matches, but
specializing for just that case might be a little too specific.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2874
src/runtime.cc:2874: Handle<String> replacement = Handle<String>::null()) {
Don't use an optional argument, just pass the null-handle in the few cases where
we replace with the empty string.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2881
src/runtime.cc:2881:
String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex));
Assert that the regexp is atomic.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2906
src/runtime.cc:2906: String::WriteToFlat(*subject,
Would it be worth it to check that that subject_pos is actually less than
indices.at(i)? I.e, there is something to write.

http://codereview.chromium.org/7782028/diff/1/src/runtime.cc#newcode2911
src/runtime.cc:2911: // Replace match.
Move comment down one line.