[string] Add a fast path to String.p.replace

[string] Add a fast path to String.p.replace

This adds a fast path to skip runtime calls to GetSubstitution when
the replacer string does not contain a '$' char.

Extended background:

String.prototype.replace is (roughly) structured as follows:

* Check if {searchValue} has a @@replace Symbol, and delegate to that if
  so. We currently implement efficient fast paths when {searchValue} is
  a String or a fast RegExp.
* A specialized fast path for single-char {searchValue}, "long" subject
  string, and String {replaceValue} that do not contain '$' chars (yes,
  this fast path is very specialized).
* Check for the location of the first match using StringIndexOf, and
  exit early if no match is found.
* Finally build the return value, which is 'prefix + replacement +
  suffix', where replacement is either the result of calling {replaceValue}
  (if it is callable), or GetSubstitution(ToString({replaceValue}))
  otherwise.

There's several spots that could be improved.

StringIndexOf currently calls into C++ runtime for all but the simple
1-byte, 1-char {searchValue} case. We need to finally add support for
remaining cases.

The runtime call to GetSubstitution can be skipped if the replacer
string does not contain any '$' syntax. This CL handles that case.

BUG=

Review-Url: https://codereview.chromium.org/2813843002
Cr-Commit-Position: refs/heads/master@{#44606}
Committed: https://chromium.googlesource.com/v8/v8/+/f4ba786de8c182db79c293697b81184df41c6344

[jgruber, 2017-04-11 09:52:37]

The CQ bit was checked by jgruber@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-11 09:52:46]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-11 10:28:28]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-11 10:28:29]

Dry run: This issue passed the CQ dry run.

[jgruber, 2017-04-11 10:49:23]

jgruber@chromium.org changed reviewers:
+ bmeurer@chromium.org, ishell@chromium.org

[jgruber, 2017-04-11 12:16:31]

The CQ bit was checked by jgruber@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-11 12:16:40]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[jgruber, 2017-04-11 12:24:37]

Patchset 2 is a bit smarter: 
* avoids scanning replace_string twice by telling String::GetSubstitution where
to continue scanning.
* calls the Runtime_StringReplaceOneCharWithString 'fast path' only if
subject_string is a ConsString.

Microbenchmarks show 1.7x speedup, speedometer doesn't seem to care at all (at
least not on the overall time).

[jgruber, 2017-04-11 12:25:31]

Description was changed from

==========
[string] Add a fast path to String.p.replace

This adds a fast path to skip runtime calls to GetSubstitution when
the replacer string does not contain a '$' char.

Extended background:

String.prototype.replace is (roughly) structured as follows:

* Check if {searchValue} has a @@replace Symbol, and delegate to that if
  so. We currently implement efficient fast paths when {searchValue} is
  a String or a fast RegExp.
* A specialized fast path for single-char {searchValue}, "long" subject
  string, and String {replaceValue} that do not contain '$' chars (yes,
  this fast path is very specialized).
* Check for the location of the first match using StringIndexOf, and
  exit early if no match is found.
* Finally build the return value, which is 'prefix + replacement +
  suffix', where replacement is either the result of calling {replaceValue}
  (if it is callable), or GetSubstitution(ToString({replaceValue}))
  otherwise.

There's several spots that could be improved.

We should probably reevaluate whether the specialized fast path for
single-char {searchValue} still makes sense (my gut feeling is it
doesn't).

StringIndexOf currently calls into C++ runtime for all but the simple
1-byte, 1-char {searchValue} case. We need to finally add support for
remaining cases.

The runtime call to GetSubstitution can be skipped if the replacer
string does not contain any '$' syntax. This CL handles that case.

BUG=
==========

to

==========
[string] Add a fast path to String.p.replace

This adds a fast path to skip runtime calls to GetSubstitution when
the replacer string does not contain a '$' char.

Extended background:

String.prototype.replace is (roughly) structured as follows:

* Check if {searchValue} has a @@replace Symbol, and delegate to that if
  so. We currently implement efficient fast paths when {searchValue} is
  a String or a fast RegExp.
* A specialized fast path for single-char {searchValue}, "long" subject
  string, and String {replaceValue} that do not contain '$' chars (yes,
  this fast path is very specialized).
* Check for the location of the first match using StringIndexOf, and
  exit early if no match is found.
* Finally build the return value, which is 'prefix + replacement +
  suffix', where replacement is either the result of calling {replaceValue}
  (if it is callable), or GetSubstitution(ToString({replaceValue}))
  otherwise.

There's several spots that could be improved.

StringIndexOf currently calls into C++ runtime for all but the simple
1-byte, 1-char {searchValue} case. We need to finally add support for
remaining cases.

The runtime call to GetSubstitution can be skipped if the replacer
string does not contain any '$' syntax. This CL handles that case.

BUG=
==========

[commit-bot: I haz the power, 2017-04-11 12:57:35]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-11 12:57:36]

Dry run: This issue passed the CQ dry run.

[Igor Sheludko, 2017-04-12 09:51:10]

lgtm

[jgruber, 2017-04-12 10:39:17]

The CQ bit was checked by jgruber@chromium.org

[commit-bot: I haz the power, 2017-04-12 10:39:24]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-12 10:40:57]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1491993557800500,
"parent_rev": "a5f91b3a95e1424a6621b6aefe2e77736c7ba3ff", "commit_rev":
"f4ba786de8c182db79c293697b81184df41c6344"}

[commit-bot: I haz the power, 2017-04-12 10:41:03]

Description was changed from

==========
[string] Add a fast path to String.p.replace

This adds a fast path to skip runtime calls to GetSubstitution when
the replacer string does not contain a '$' char.

Extended background:

String.prototype.replace is (roughly) structured as follows:

* Check if {searchValue} has a @@replace Symbol, and delegate to that if
  so. We currently implement efficient fast paths when {searchValue} is
  a String or a fast RegExp.
* A specialized fast path for single-char {searchValue}, "long" subject
  string, and String {replaceValue} that do not contain '$' chars (yes,
  this fast path is very specialized).
* Check for the location of the first match using StringIndexOf, and
  exit early if no match is found.
* Finally build the return value, which is 'prefix + replacement +
  suffix', where replacement is either the result of calling {replaceValue}
  (if it is callable), or GetSubstitution(ToString({replaceValue}))
  otherwise.

There's several spots that could be improved.

StringIndexOf currently calls into C++ runtime for all but the simple
1-byte, 1-char {searchValue} case. We need to finally add support for
remaining cases.

The runtime call to GetSubstitution can be skipped if the replacer
string does not contain any '$' syntax. This CL handles that case.

BUG=
==========

to

==========
[string] Add a fast path to String.p.replace

This adds a fast path to skip runtime calls to GetSubstitution when
the replacer string does not contain a '$' char.

Extended background:

String.prototype.replace is (roughly) structured as follows:

* Check if {searchValue} has a @@replace Symbol, and delegate to that if
  so. We currently implement efficient fast paths when {searchValue} is
  a String or a fast RegExp.
* A specialized fast path for single-char {searchValue}, "long" subject
  string, and String {replaceValue} that do not contain '$' chars (yes,
  this fast path is very specialized).
* Check for the location of the first match using StringIndexOf, and
  exit early if no match is found.
* Finally build the return value, which is 'prefix + replacement +
  suffix', where replacement is either the result of calling {replaceValue}
  (if it is callable), or GetSubstitution(ToString({replaceValue}))
  otherwise.

There's several spots that could be improved.

StringIndexOf currently calls into C++ runtime for all but the simple
1-byte, 1-char {searchValue} case. We need to finally add support for
remaining cases.

The runtime call to GetSubstitution can be skipped if the replacer
string does not contain any '$' syntax. This CL handles that case.

BUG=

Review-Url: https://codereview.chromium.org/2813843002
Cr-Commit-Position: refs/heads/master@{#44606}
Committed:
https://chromium.googlesource.com/v8/v8/+/f4ba786de8c182db79c293697b81184df41...
==========

[commit-bot: I haz the power, 2017-04-12 10:41:04]

Committed patchset #2 (id:20001) as
https://chromium.googlesource.com/v8/v8/+/f4ba786de8c182db79c293697b81184df41...