[regexp] Add fast-path for global, callable replace

[regexp] Add fast-path for global, callable replace

This adds a fast-path for calls to RegExp.prototype[@@replace] for cases in
which the given regexp is unmodified and global, and the given replace argument
is callable.

The fast-path implementation itself is almost identical to the original JS
implementation except that it currently does not reuse result_array.

SunSpider/unpack-code relies heavily on this codepath.

BUG=v8:5339
Committed: https://crrev.com/a8e30c0e689a68a8d5d457be28eec1fb5b7a3702
Cr-Commit-Position: refs/heads/master@{#40504}

[jgruber, 2016-10-19 12:05:02]

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

[commit-bot: I haz the power, 2016-10-19 12:05:11]

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

[jgruber, 2016-10-19 12:47:43]

jgruber@chromium.org changed reviewers:
+ yangguo@chromium.org

[commit-bot: I haz the power, 2016-10-19 13:15:58]

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

[commit-bot: I haz the power, 2016-10-19 13:15:59]

Dry run: Try jobs failed on following builders:
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)

[jgruber, 2016-10-19 13:23:10]

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

[commit-bot: I haz the power, 2016-10-19 13:23:19]

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, 2016-10-19 13:33:26]

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

[commit-bot: I haz the power, 2016-10-19 13:33:27]

Dry run: Try jobs failed on following builders:
  v8_linux64_gyp_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_gyp_rel_ng/build...)

[jgruber, 2016-10-19 15:17:29]

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

[commit-bot: I haz the power, 2016-10-19 15:17:39]

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, 2016-10-19 15:57:21]

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

[commit-bot: I haz the power, 2016-10-19 15:57:22]

Dry run: This issue passed the CQ dry run.

[jgruber, 2016-10-19 16:39:13]

Some comments mainly for myself, but I'd also appreciate input. Much of this
would be better off in a follow-up commit.

https://chromiumcodereview.appspot.com/2433923003/diff/40001/src/runtime/runt...
File src/runtime/runtime-regexp.cc (right):

https://chromiumcodereview.appspot.com/2433923003/diff/40001/src/runtime/runt...
src/runtime/runtime-regexp.cc:1004: // The cache FixedArray is a COW-array and
we need to return a copy.
It might not make sense anymore for the result cache to store COW arrays, now
that our implementation operates directly on fixed arrays (which ignores any COW
logic).

In principle, we could also move away from JSArray wrappers, but in this case
the StringBuilderConcat runtime function still expects a JSArray. Maybe operate
on FixedArrays here and wrap it in a JSArray shortly before the call to SBC?

https://chromiumcodereview.appspot.com/2433923003/diff/40001/src/runtime/runt...
src/runtime/runtime-regexp.cc:1279: DCHECK(!global);  // Handled as fast path.
The entire functional_replace branch should be removed since it is dispatched
directly from the TF impl. We should also use the same map-based fast-path
checks from C++ as in TF.

For replace, we could even dispatch all 'fast' paths (in the sense of unmodified
JSRegExp instances) from TF and only keep the slow path in
Runtime_RegExpReplace.

https://chromiumcodereview.appspot.com/2433923003/diff/40001/src/runtime/runt...
src/runtime/runtime-regexp.cc:1299: CONVERT_ARG_HANDLE_CHECKED(JSArray,
result_array, 3);
Reusing the result array does not seem to make any runtime difference for
ss/unpack-code. We could probably remove the result_array arg entirely and just
create it as needed in SearchRegExpMultiple.

[Yang, 2016-10-20 09:53:14]

lgtm

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
File src/runtime/runtime-regexp.cc (right):

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
src/runtime/runtime-regexp.cc:1004: // The cache FixedArray is a COW-array and
we need to return a copy.
On 2016/10/19 16:39:13, jgruber wrote:
> It might not make sense anymore for the result cache to store COW arrays, now
> that our implementation operates directly on fixed arrays (which ignores any
COW
> logic).
> 
> In principle, we could also move away from JSArray wrappers, but in this case
> the StringBuilderConcat runtime function still expects a JSArray. Maybe
operate
> on FixedArrays here and wrap it in a JSArray shortly before the call to SBC?


I'd simply introduce a version of SBC that only takes FixedArrays.

Maybe we can avoid modifying the FixedArray altogether, so that we don't need to
make a copy for caching. Iirc we modify the FixedArray because we call the
function and replace elements by the return values. That whole FixedArray is
then passed to SBC.

Maybe we could have RegExpMultiple return a FixedArray for the regexp results,
which is cacheable. Return values of calling the functions is collected in a
second FixedArray, and SBC can then merge both to the final result. Does that
make sense?

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
src/runtime/runtime-regexp.cc:1299: CONVERT_ARG_HANDLE_CHECKED(JSArray,
result_array, 3);
On 2016/10/19 16:39:13, jgruber wrote:
> Reusing the result array does not seem to make any runtime difference for
> ss/unpack-code. We could probably remove the result_array arg entirely and
just
> create it as needed in SearchRegExpMultiple.

I wonder whether we need a JSArray for this at all. Can't we just return a
FixedArray directly?

[jgruber, 2016-10-20 10:57:33]

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

[commit-bot: I haz the power, 2016-10-20 10:57:40]

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

[jgruber, 2016-10-20 10:58:30]

Thanks for the review!

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
File src/runtime/runtime-regexp.cc (right):

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
src/runtime/runtime-regexp.cc:1004: // The cache FixedArray is a COW-array and
we need to return a copy.
On 2016/10/20 09:53:14, Yang wrote:
> On 2016/10/19 16:39:13, jgruber wrote:
> > It might not make sense anymore for the result cache to store COW arrays,
now
> > that our implementation operates directly on fixed arrays (which ignores any
> COW
> > logic).
> > 
> > In principle, we could also move away from JSArray wrappers, but in this
case
> > the StringBuilderConcat runtime function still expects a JSArray. Maybe
> operate
> > on FixedArrays here and wrap it in a JSArray shortly before the call to SBC?
> 
> 
> I'd simply introduce a version of SBC that only takes FixedArrays.
> 
> Maybe we can avoid modifying the FixedArray altogether, so that we don't need
to
> make a copy for caching. Iirc we modify the FixedArray because we call the
> function and replace elements by the return values. That whole FixedArray is
> then passed to SBC.
> 
> Maybe we could have RegExpMultiple return a FixedArray for the regexp results,
> which is cacheable. Return values of calling the functions is collected in a
> second FixedArray, and SBC can then merge both to the final result. Does that
> make sense?

That would work, I'm just not sure what we would gain.

We still need to create an array of the same size (initialized with holes so
O(n)), and then do one write per function result. The same amount of work as
now, but added complexity because of a new SBC that can handle merging.

What about we:
* Move RegExpExecMultiple to take and return FixedArrays.
* Remove the result_array arg and alloc in REExecMultiple as needed.
* Always return copies of the cached FixedArrays.
* Wrap the FixedArray in a JSArray just before the call to SBC. If we need to
optimize, we still have the option of adding a new SBC that takes FixedArrays.

https://codereview.chromium.org/2433923003/diff/40001/src/runtime/runtime-reg...
src/runtime/runtime-regexp.cc:1299: CONVERT_ARG_HANDLE_CHECKED(JSArray,
result_array, 3);
On 2016/10/20 09:53:14, Yang wrote:
> On 2016/10/19 16:39:13, jgruber wrote:
> > Reusing the result array does not seem to make any runtime difference for
> > ss/unpack-code. We could probably remove the result_array arg entirely and
> just
> > create it as needed in SearchRegExpMultiple.
> 
> I wonder whether we need a JSArray for this at all. Can't we just return a
> FixedArray directly?

Sure. I kept the JSArray return type for now because of the interaction with
StringBuilderConcat. This is something worth looking at in a follow-up though.

[jgruber, 2016-10-20 11:03:02]

The CQ bit was unchecked by jgruber@chromium.org

[jgruber, 2016-10-20 11:03:08]

The CQ bit was checked by jgruber@chromium.org

[jgruber, 2016-10-20 11:03:09]

The patchset sent to the CQ was uploaded after l-g-t-m from yangguo@chromium.org
Link to the patchset: https://codereview.chromium.org/2433923003/#ps60001
(title: "Remove callable path from RegExpReplace")

[commit-bot: I haz the power, 2016-10-20 11:03:19]

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, 2016-10-20 11:12:58]

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

[commit-bot: I haz the power, 2016-10-20 11:12:59]

Try jobs failed on following builders:
  v8_presubmit on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/26942)

[jgruber, 2016-10-20 11:36:23]

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

[jgruber, 2016-10-20 11:36:23]

+ bmeurer for compiler/

[Benedikt Meurer, 2016-10-20 14:59:50]

lgtm

[jgruber, 2016-10-21 08:14:41]

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

[commit-bot: I haz the power, 2016-10-21 08:14:51]

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, 2016-10-21 08:41:31]

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

[commit-bot: I haz the power, 2016-10-21 08:41:32]

Dry run: Try jobs failed on following builders:
  v8_linux64_asan_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_asan_rel_ng/buil...)

[jgruber, 2016-10-21 08:50:31]

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

[commit-bot: I haz the power, 2016-10-21 08:50:43]

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

[jgruber, 2016-10-21 08:54:23]

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

[commit-bot: I haz the power, 2016-10-21 08:54:34]

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, 2016-10-21 09:29:41]

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

[commit-bot: I haz the power, 2016-10-21 09:29:42]

Dry run: This issue passed the CQ dry run.

[jgruber, 2016-10-21 12:07:56]

The CQ bit was checked by jgruber@chromium.org

[jgruber, 2016-10-21 12:07:56]

The patchset sent to the CQ was uploaded after l-g-t-m from
bmeurer@chromium.org, yangguo@chromium.org
Link to the patchset: https://codereview.chromium.org/2433923003/#ps120001
(title: "Rebase")

[commit-bot: I haz the power, 2016-10-21 12:08:03]

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, 2016-10-21 12:12:00]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2016-11-17 22:09:49]

Description was changed from

==========
[regexp] Add fast-path for global, callable replace

This adds a fast-path for calls to RegExp.prototype[@@replace] for cases in
which the given regexp is unmodified and global, and the given replace argument
is callable.

The fast-path implementation itself is almost identical to the original JS
implementation except that it currently does not reuse result_array.

SunSpider/unpack-code relies heavily on this codepath.

BUG=v8:5339
==========

to

==========
[regexp] Add fast-path for global, callable replace

This adds a fast-path for calls to RegExp.prototype[@@replace] for cases in
which the given regexp is unmodified and global, and the given replace argument
is callable.

The fast-path implementation itself is almost identical to the original JS
implementation except that it currently does not reuse result_array.

SunSpider/unpack-code relies heavily on this codepath.

BUG=v8:5339

Committed: https://crrev.com/a8e30c0e689a68a8d5d457be28eec1fb5b7a3702
Cr-Commit-Position: refs/heads/master@{#40504}
==========

[commit-bot: I haz the power, 2016-11-17 22:09:50]

Patchset 7 (id:??) landed as
https://crrev.com/a8e30c0e689a68a8d5d457be28eec1fb5b7a3702
Cr-Commit-Position: refs/heads/master@{#40504}