876976 - Speed up array creation for global regexp matches

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Sean Stangl [:sstangl]]

Attachment: WIP patch

Array creation currently calls defineElement() immediately after each match. Instead, we could accumulate the elements and use the very fast NewDenseCopiedArray() constructor. The attached patch does so.

Note that this work is only now possible because of the recent refactoring work done by Matt Stults in Bug 841615.

I haven't measured on the jQuery benchmark attached in Bug 876846 (browser will take a long time to build), but in a local microbenchmark, the patch shows promising results.

Note that I first tried to accumulate StringRanges so that js_NewDependentString() could be called in a separate tight loop, but doing so wound up significantly slower than just calling js_NewDependentString() in the body of the match loop.

The patch is pretty much good to go, but I'd like to see the results on the jQuery test before putting it up for review.

Comment 1

[Sean Stangl [:sstangl]]

Attachment: WIP patch [not a vim temp file]

Comment 2

[Sean Stangl [:sstangl]]

Attachment: Match microbenchmark

Microbenchmark used for testing. The scores on x64 are:

SM (unpatched): 5.4s
SM (patched): 1.8s
V8 (release): 2.2s

Comment 3

[Sean Stangl [:sstangl]]

Oops! I made the wrong thing fast. The jQuery benchmark actually builds matches using .exec(), not .match(), which uses a similar but disjoint code path, so this isn't any use in beating v8 on that particular benchmark.

On the plus side, .match() is fast now.

Comment 4

[Sean Stangl [:sstangl]]

Attachment: Speed up global regexp match

Comment 5

[Boris Zbarsky [:bzbarsky]]

> return NULL;

Should be "return false;" to get this to compile on clang over here.  ;)

Comment 6

[Hannes Verschore [:h4writer]]

Comment on attachment 755121 [details] [diff] [review]
Speed up global regexp match

Review of attachment 755121 [details] [diff] [review]:
-----------------------------------------------------------------

Nice (both patches ;))

::: js/src/jsstr.cpp
@@ +1702,3 @@
>      size_t i = 0;
>      ScopedMatchPairs matches(&cx->tempLifoAlloc());
> +    RegExpRunStatus status = re.execute(cx, input->chars(), charsLen, &i, matches);

I assume you wanted to use "chars" instead of "input->chars()" here?

@@ +1745,5 @@
> +
> +        /* Extract the matched substring, root it, and remember it for later. */
> +        JSLinearString *str = js_NewDependentString(cx, input, match.start, match.length());
> +        if (!str)
> +            return NULL;

return false;

@@ +1747,5 @@
> +        JSLinearString *str = js_NewDependentString(cx, input, match.start, match.length());
> +        if (!str)
> +            return NULL;
> +        if (!elements.append(StringValue(str)))
> +            return NULL;

return false;

Comment 7

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/c9fe4e4bd7ca

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/c9fe4e4bd7ca