Closed Bug 841615 Opened 11 years ago Closed 11 years ago

Use MatchOnly mode for str.match()

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla24

People

(Reporter: sstangl, Unassigned)

References

Details

(Whiteboard: [good first bug][mentor=sstangl][lang=c++])

Attachments

(3 files, 8 obsolete files)

Contrived Benchmark Template
438 bytes, application/octet-stream
Details
global match test based off of blogspot session
189.87 KB, application/octet-stream
Details
Upated with corrections.
12.55 KB, patch
sstangl
: review+
Details | Diff | Splinter Review 
The function str_match(), implementing the .match() property of string objects, should be converted to use the new MatchOnly regular expression mode from Bug 808245, with lazy updating of the RegExpStatics. This change is motivated by Bug 792797 (affects loading time of certain blogspot.com domains).

str_match() is implemented in terms of a helper function DoMatch(). When a global regular expression is given as the .match() argument, DoMatch() is supposed to continuously run the regular expression until it ceases to match, then accumulate the results into an array. However, in the current implementation, if the global array contains N parentheses (capturing subexpressions), DoMatch() will generate a temporary match results array of size N+1, copy this array into the RegExpStatics, then discard the last N elements and append only the first to the results array. This is a large waste of effort, especially if there is a tremendous number of parentheses as is the case with blogspot.

Instead, we should use MatchOnly mode via .executeMatchOnly(), which will ignore subexpressions and only capture the first match. The RegExpStatics will then be lazily updated at the end of execution with the inputs to the last successful match. For cleanliness, it would be preferable to implement str_match() without referring to DoMatch() -- then only str_replace() depends on it, and we can rename it, simplify it, and possibly later, remove it.

This should be a fairly simple, mostly mechanical change with large performance impact given the right inputs.
Hi! I'd be willing to take this. I'm looking at the executeMatchOnly() usages in str_search() and str_replace_regexp_remove() right now, so I'll work on a patch and get back.
Assignee: general → prp.1111
Sorry about the delay, could just start working on the patch. I tried to replicate what's been done in str_search, with updateLazily() taking the match index as one of its parameters, but the testMatchStringObject test fails with this error:

Error: Assertion failed: got (void 0), expected null
Exit code: 3

Here's the paste:

http://pastebin.mozilla.org/2175222

Where's it going wrong?
(In reply to Pranav Ravichandran [:pranavrc] from comment #2)
> Where's it going wrong?

It's calling args.rval().set(rval), but |rval| is never assigned a value.

The patch is more complicated than just calling executeMatchOnly(), because DoMatch() has some complicated behavior requiring looping for global matches and array generation. To start out writing this patch, it would be a good idea to duplicate DoMatch() into a new function, then attempt to reduce paths unused by str_match().
Could someone tell me how to verify the fix if there is one since it is a performance issue and the original code works? Thx
Can you confirm that you're still working on this bug?
Flags: needinfo?(prp.1111)
Ouch, sorry. I'll
Assignee: prp.1111 → general
Flags: needinfo?(prp.1111)
I'd like to take a shot of this if it's available.
Typo in my previous post: "of" --> "at".

I've attached an ugly patch that seems to pass the tests suggested on the New to SpiderMonkey page.  I still need to go back over the patch and make sure that the change conforms to the style guide.  Before I get to that level, I'd like to make sure this is on the right track and get feedback about how I've moved things around/names/etc.

I'm excited to contribute and am happy to make any desired changes.  Thanks for your time.
Attachment #749156 - Flags: feedback+
Should I add a sunspider performance test to verify the improvement?  Is there anything else I can do for the patch?

Thanks in advance,
Matt
Attachment #749156 - Attachment is obsolete: true
Attachment #749635 - Flags: feedback?(sstangl)
Below are some contrived benchmarks I generated to ensure the bug is behaving as intended.  I've attached the JavaScript template I used to generate these results.  The three variables I'm measuring are:
(P) the base Pattern: {a, abcde, abcdefghij}.
(N) Number of (P) used to build the test string: {10, 100, 1000, 10000}.
(M) the number of parenthetical Matching groups in the regex.
Tests are labeled: <B><N>x<P>.
Ex: Foo10x2 translates to "FooFooFooFooFooFooFooFooFooFoo".match(/(Foo)(Foo)/g)

a10x1:                -                   0.4ms +/- 38.2%    0.4ms +/- 38.2%
a100x10:              -                   0.3ms +/- 38.3%    0.2ms +/- 38.2%
a1000x10:             -                   2.3ms +/- 38.1%    1.9ms +/- 38.2%
a1000x100:            -                   1.1ms +/- 38.1%    0.8ms +/- 38.1%
a10000x10:            -                  14.2ms +/- 38.1%    9.7ms +/- 38.1%
a10000x100:           2.24x as fast       4.2ms +/- 38.1%    1.9ms +/- 38.1%
a10000x1000:          1.79x as fast       6.3ms +/- 38.1%    3.5ms +/- 38.1%

abcdef10x1:           -                   0.3ms +/- 38.2%    0.2ms +/- 38.3%
abcdef100x10:         -                   0.3ms +/- 38.1%    0.2ms +/- 38.1%
abcdef1000x10:        -                   1.7ms +/- 38.1%    1.3ms +/- 38.1%
abcdef1000x100:       -                   1.2ms +/- 38.1%    0.9ms +/- 38.1%
abcdef10000x10:       -                  12.6ms +/- 38.1%    8.4ms +/- 38.1%
abcdef10000x100:      1.79x as fast       5.1ms +/- 38.1%    2.8ms +/- 38.1%

abcdefghij10x1:       -                   0.3ms +/- 38.1%    0.3ms +/- 38.1%
abcdefghij100x10:     -                   0.3ms +/- 38.2%    0.3ms +/- 38.2%
abcdefghij1000x10:    -                   1.8ms +/- 38.1%    1.4ms +/- 38.1%
abcdefghij1000x100:   -                   1.4ms +/- 38.1%    1.1ms +/- 38.1%
abcdefghij10000x10:   -                  13.6ms +/- 38.2%    9.4ms +/- 38.1%
abcdefghij10000x100:  -                   6.1ms +/- 38.1%    3.9ms +/- 38.1%
abcdefghij10000x1000: -                  16.2ms +/- 38.1%   15.3ms +/- 38.1%

If I can find enough real-world examples of global, multi-capture-group regexes, I'll use them to get a more realistic idea of the impact of this patch.
Updating the patch comment and git format of this patch based on instructions here: https://developer.mozilla.org/en-US/docs/Mercurial_FAQ#How_can_I_generate_a_patch_for_somebody_else_to_check-in_for_me.3F

There should be no code changes with this update.
Attachment #749635 - Attachment is obsolete: true
Attachment #749635 - Flags: feedback?(sstangl)
Attachment #750276 - Flags: feedback?(sstangl)
Comment on attachment 750276 [details] [diff] [review]
Including patch comment + git formatting

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

This looks great! Thank you for taking the bug, and for the performance results -- they look really good! It would also be interesting to see what the effect is on a bunch of different blogspot.com sites, since that was where the DoMatch() performance was initially identified as a problem. Blogspot may have changed in the meantime, of course.

The patch is good, but with some small changes it can wind up fixing even more related pre-existing performance issues than originally identified. I pointed the issues out in the comments.

::: js/src/jsstr.cpp
@@ +1692,5 @@
>      RegExpShared &regExp() { return *re_; }
>  };
>  
> +typedef bool (*DoMatchForReplaceCallback)(JSContext *cx, RegExpStatics *res,
> +										  size_t count, void *data);

SpiderMonkey coding style (https://wiki.mozilla.org/JavaScript:SpiderMonkey:Coding_Style) always uses spaces instead of tabs -- especially for alignment. It may be helpful to set the editor used to write the patch to always insert spaces instead of tabs. The modelines at the top of jsstr.cpp cause this behavior by default in vim and emacs, but other editors may require customization if they do not detect the foreign modelines.

@@ +1698,5 @@
>  /*
>   * BitOR-ing these flags allows the DoMatch caller to control when how the
>   * RegExp engine is called and when callbacks are fired.
>   */
>  enum MatchControlFlags {

Since DoMatch() is now broken up into DoSingleMatch(), DoMatch() [for global], and DoMatchForReplace() [maybe renamed DoReplace()?], do we need the MatchControlFlags anymore?

See the comment in DoSingleMatch() also.

@@ +1717,5 @@
> + * regexps.
> + */
> +static bool
> +BuildGlobalMatchArray(JSContext *cx, JSString *matchesInput,
> +		              const MatchPair &pair, size_t count, void *p)

Nit: Needs spaces instead of tabs.

@@ +1720,5 @@
> +BuildGlobalMatchArray(JSContext *cx, JSString *matchesInput,
> +		              const MatchPair &pair, size_t count, void *p)
> +{
> +    JS_ASSERT(count <= JSID_INT_MAX);  /* by max string length */
> +    JS_ASSERT(pair.limit >= pair.start);

This line can be expressed as "JS_ASSERT(pair.check())".

@@ +1730,5 @@
> +            return false;
> +    }
> +
> +    RootedObject obj(cx, arrayobj);
> +    RootedValue v(cx);

The creation of "Rooted" objects, which temporarily protect objects from garbage collection, is expensive: creation pushes to a global stack, and destruction pops from a global stack. This (pre-existing, augh!) code generates and destroys two Rooted* for each successful match, including empty matches.

It would be possible to pull these Rooted objects out of BuildGlobalMatchArray() and into DoMatch(), which would let us reassign the variables on each iteration of the loop without creating and destructing them. The downside is that we would create two Rooteds in the case of no match, but an O(1) slowdown is probably preferable to an O(n) slowdown.

@@ +1740,5 @@
> +}
> +
> +static bool
> +DoSingleMatch(JSContext *cx, RegExpStatics *res, Rooted<JSLinearString*> &linearStr,
> +		      RegExpShared &re, size_t charsLen, MatchControlFlags flags, MutableHandleValue rval)

Nit: Needs spaces instead of tabs.

@@ +1758,5 @@
> +
> +    res->updateFromMatchPairs(cx, linearStr, matches);
> +
> +    if (isTest) {
> +        rval.setBoolean(true);

|isTest| is true iff the caller is DoMatchForReplace(). But if |isTest| is true, then this is yet another situation in which the MatchPairs collected by re.execute() are calculated and then immediately discarded, since the output of the function is a boolean!

So we can do even better by having DoMatchForReplace() use re.executeMatchOnly(), with the RegExpStatics being updated lazily via res->updateLazily() instead of res->updateFromMatchPairs().

Then this code doesn't need to be shared between DoMatch() and DoMatchForReplace(), which lets us get rid of the MatchControlFlags and make the code more straightforward. Flags are evil.

@@ +1777,5 @@
> +
> +    size_t charsLen = linearStr->length();
> +    JSLinearString *linearPtr = linearStr.get();
> +
> +    if (re.global()) {

Breaking up the single-match case into a separate function is a good choice. If this condition is inverted to test |!re.global()|, then the next line can just be "return DoSingleMatch(...);", and we can remove a level of indentation from the rest of the following code (we have a style policy of "no else after return").

@@ +1794,5 @@
> +                break;
> +            }
> +            if (!BuildGlobalMatchArray(cx, linearPtr, match, count, data))
> +                return false;
> +            if (match.limit - match.start == 0) {

There's a helper method to give a name to this common test: |match.isEmpty()|.

@@ +1798,5 @@
> +            if (match.limit - match.start == 0) {
> +                ++i;
> +            }
> +        }
> +        res->updateLazily(cx, linearPtr, &re, i);

This line is very tricky. The problem is that the value of |i| (which stores the index of the last successful starting index) is incorrect -- if executeMatchOnly() returns RegExpRunStatus_Success_NotFound, it still updates |i|.

But the value of |i| that we want to pass to updateLazily() is the last value of |i| that resulted in a return value of RegExpRunStatus_Success.

It would be sufficient to store another variable, say |lastMatchedIndex|, update it right before BuildGlobalMatchArray(), and pass it to updateLazily() in place of |i|.

@@ +1809,5 @@
>  /* Factor out looping and matching logic. */
>  static bool
> +DoMatchForReplace(JSContext *cx, RegExpStatics *res, JSString *str,
> +		          RegExpShared &re, DoMatchForReplaceCallback callback,
> +		          void *data, MatchControlFlags flags, MutableHandleValue rval)

Nit: Needs spaces instead of tabs. Also, could we call this function "DoReplace()"?

@@ +1851,2 @@
>          bool callbackOnSingle = !!(flags & CALLBACK_ON_SINGLE_BIT);
> +        if (!rval.isNull() && callbackOnSingle && !callback(cx, res, 0, data))

Since there is only one callback used for DoMatchForReplace(), the callback function can be hardcoded, and the argument can be eliminated.
Attachment #750276 - Flags: feedback?(sstangl) → feedback+
Thanks for the feedback!  I've been working through it, and will update the patch tomorrow, hopefully with more useful benchmarks from Blogspot.

re: DoMatchForReplace --> DoReplace
There's already a DoReplace function used by ReplaceRegExp which is used by DoMatchForReplace.  I'm happy to rename both--whatever is clearest.  Name suggestions?
Also: I'd like to add a test for the bug you found.  Can you either tell me where it should go/what I should call it or direct me to where I can read about the right way to add a test?

Thanks again,
Matt
(In reply to Matt Stults from comment #13)
> There's already a DoReplace function used by ReplaceRegExp which is used by
> DoMatchForReplace.  I'm happy to rename both--whatever is clearest.  Name
> suggestions?

Oh, you're right. In that case, DoMatchForReplace() is a fine name.

(In reply to Matt Stults from comment #14)
> Also: I'd like to add a test for the bug you found.  Can you either tell me
> where it should go/what I should call it or direct me to where I can read
> about the right way to add a test?

Tests are added by just creating a new file in some subdirectory of js/src/jit-test/tests/, in this case probably in js/src/jit-test/tests/basic/. There are plenty of files to look at for an example, but the primary function for asserting a value is assertEq(x,y).
I just remembered that the change to executeMatchOnly() for replace() operations is not necessarily beneficial to performance: replacement operations can replace data with information collected into the RegExpStatics. If such a replace occurs, then we would run twice as many regular expression matches -- one more when the lazy RegExpStatics need to be resolved on each iteration.

It might be better to still separate the replace and match code into two separate functions so that we can remove the MatchControlFlags, but keep the replace code using execute(). In a follow-up bug, we can then investigate the impact of such a change on calls to replace() from real websites and maybe make the change then if the data look promising.
I believe I've made all of the requested changes.  Based on your suggestion for fixing the updateLazily bug, I imagine there is a simpler approach than what I came up with, but it's alluding me.

This was great feedback--please let me know if there are any other changes I can make, or if I missed anything.

Matt
Attachment #750276 - Attachment is obsolete: true
Attachment #751294 - Flags: feedback?(sstangl)
I've placed this test in:
/spidermonkey/js/src/jit-test/tests/basic/string-regexp-capture-groups.js
but it's not showing up in my patch.  Let me know if it should and I'll review the hg documentation to see if I can figure out what I'm doing wrong.

I would definitely like this test to go with my change if possible so that we catch similar failures automatically in the future.
Attached patch Code and test in the same patch (obsolete) — — Splinter Review 
Sorry for the spam, still getting used the hg.  This patch should include the code and the test with no other changes to either of the previous attachments.
Attachment #751294 - Attachment is obsolete: true
Attachment #751295 - Attachment is obsolete: true
Attachment #751294 - Flags: feedback?(sstangl)
Attachment #751296 - Flags: feedback?(sstangl)
I'm now looking into building benchmarks from Blogspot, and hope to post them either tonight or over the weekend.

In the meantime: Updated "contrived" benchmarks

a10x1:                  -                   0.5ms +/- 40.3%    0.5ms +/- 40.3% 
a100x10:                -                   0.4ms +/- 41.9%    0.3ms +/- 40.2% 
a1000x10:               -                   3.1ms +/- 39.3%    2.5ms +/- 39.8% 
a1000x100:              -                   1.5ms +/- 39.7%    1.1ms +/- 39.3% 
a10000x10:              -                  20.3ms +/- 39.8%   13.2ms +/- 39.2% 
a10000x100:             2.31x as fast       5.7ms +/- 39.8%    2.5ms +/- 39.8%
a10000x1000:            1.89x as fast       8.3ms +/- 39.1%    4.4ms +/- 39.3%

abcdef10x1:             -                   0.4ms +/- 39.9%    0.3ms +/- 40.5% 
abcdef100x10:           -                   0.4ms +/- 38.3%    0.3ms +/- 41.1% 
abcdef1000x10:          -                   2.1ms +/- 38.5%    1.8ms +/- 40.7% 
abcdef1000x100:         -                   1.6ms +/- 39.1%    1.4ms +/- 40.8% 
abcdef10000x10:         -                  16.8ms +/- 38.8%   11.8ms +/- 39.4% 
abcdef10000x100:        1.93x as fast       7.2ms +/- 40.5%    3.7ms +/- 39.1%
abcdef10000x1000:       -                  15.5ms +/- 38.7%   11.2ms +/- 38.6% 

abcdefghij10x1:         -                   0.4ms +/- 41.4%    0.3ms +/- 39.7% 
abcdefghij100x10:       -                   0.5ms +/- 42.6%    0.3ms +/- 40.3% 
abcdefghij1000x10:      -                   2.6ms +/- 41.4%    1.8ms +/- 39.9% 
abcdefghij1000x100:     -                   1.8ms +/- 39.4%    1.4ms +/- 39.4% 
abcdefghij10000x10:     -                  17.8ms +/- 38.8%   13.2ms +/- 40.1% 
abcdefghij10000x100:    -                   8.2ms +/- 39.4%    5.5ms +/- 40.1% 
abcdefghij10000x1000:   -                  21.1ms +/- 38.4%   18.9ms +/- 38.3%
Comment on attachment 751296 [details] [diff] [review]
Code and test in the same patch

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

This looks great. For the next version of the patch, feel free to toggle "review?" instead of "feedback?" and we can get it checked in.

::: js/src/jsstr.cpp
@@ +1714,5 @@
> +
> +typedef JSObject **MatchArgType;
> +
> +static bool
> +BuildGlobalMatchArray(JSContext *cx, RootedObject &obj, RootedValue &v, JSString *matchesInput,

Our rooting system is fairly complicated: when a Rooted object is passed to a function, it's passed via "Handles", e.g., "HandleObject obj" and "HandleValue v". In this case, since the values are being changed, we would take a "MutableHandleObject obj" and "MutableHandleValue v". Augh.

@@ +1723,5 @@
> +
> +    if(!obj) {
> +        /* Setup the return array if it hasn't been setup already.
> +         * This should only happen once in a match. */
> +        JSObject *&array = *static_cast<MatchArgType>(data);

Could we change "void *data" to "MatchArgType type" both here and for DoMatch()? This patch eliminated the abstraction around DoMatch(), so we don't have to hide values in (void *) anymore.

@@ +1765,5 @@
> +        if (status == RegExpRunStatus_Error)
> +            return false;
> +
> +        if (status == RegExpRunStatus_Success_NotFound) {
> +            rval.setNull();

The call to setNull() can be moved to the end of this function, which would let us remove the {} braces, since the conditional block would be a single line.

If you look at the callsite of DoMatch(), though, it would seem like rval isn't even needed for the global case...

@@ +1775,5 @@
> +        if (!BuildGlobalMatchArray(cx, obj, v, linearPtr, match, count, data))
> +            return false;
> +        if (match.isEmpty()) {
> +            ++i;
> +        }

Nit: no {} for |if| statements with single-line blocks.

@@ +1820,5 @@
> +        return false;
> +
> +    size_t charsLen = linearStr->length();
> +
> +    ScopedMatchPairs matches(&cx->tempLifoAlloc());

Creation of the ScopedMatchPairs should happen after the test for !re.global().

@@ +1824,5 @@
> +    ScopedMatchPairs matches(&cx->tempLifoAlloc());
> +
> +    if (!re.global())
> +        return DoSingleMatchForReplace(cx, res, linearStr, re, charsLen, rval) &&
> +               (rval.isNull() || ReplaceRegExp(cx, res, 0, data));

Sneaking things into a single return statement can it can make it annoying to step through in a debugger. Would it look terrible to write the logic out explicitly using if() statements?

@@ +1838,2 @@
>          if (status == RegExpRunStatus_Success_NotFound) {
>              rval.setNull();

Same comment for this rval as well.

@@ +2204,5 @@
>      rdata.sb.infallibleAppend(cp, repstr->length() - (cp - bp));
>  }
>  
>  static bool
> +ReplaceRegExp(JSContext *cx, RegExpStatics *res, size_t count, void *p)

Could we take a (ReplaceData &) instead of a (void *) now?
Also, it looks like |count| isn't necessary, since it's never used.
Attachment #751296 - Flags: feedback?(sstangl) → feedback+
Thanks for the quick feedback!  I'll try to get this patch finished and resubmitted tomorrow.

As far as compiling benchmarks from blogspot goes:
I instrumented DoMatch to print info about its call to the console (just using couts), which I verified using the JS shell.  However, when I build Firefox, nothing prints out to the console.  Does it seem likely that I've screwed up my firefox build somehow, or do I need to use a different approach for tracking calls to DoMatch?
Please disregard the above.  After some more digging, I've verified that my issue was user error.  Lots of false alarms tonight, but I'm learning.
I've broken doMatch and doMatchForReplace into global and "local" functions to simplify the structure and reduce unnecessary rooted object creation.  Is "local" the right word?  Hopefully this isn't too much of a bait-and-switch.

My rearranging has broken Mercurial's diff process, and it's incorrectly listing several functions as having been re-written: (BuildFlatMatchArray, str_match, str_search).  I'm going to post my profiling results and then return to try to figure out how to improve my diff.
Attachment #751296 - Attachment is obsolete: true
Attachment #751425 - Flags: review?(sstangl)
Contrived benchmarks remain positive.  However, profiling against the actual global str.match() calls from a Blogspot session showed little if any performance improvement.  

When run against a single session, the profile for my patch came out consistently worse by a tiny margin.  This was hard to judge because the test itself ran so quickly.  When I looped the session 30 times, the patch barely wins out.

When I only include matches that seemed relevant (multiple capture groups, etc) I see no noticeable difference profiling either the single session or when looping the session.

It seems like the next step is to use Cachegrind or similar to see what's taking time in these calls.  Let me know if you have suggestions for next steps, or if you feel further performance measurement is a separate bug.

a10x1:                  -                   0.4ms +/- 38.2%     0.4ms +/- 38.3%
a100x10:                -                   0.3ms +/- 38.2%     0.2ms +/- 38.2%
a1000x10:               -                   2.3ms +/- 38.1%     1.9ms +/- 38.2%
a1000x100:              -                   1.1ms +/- 38.4%     0.8ms +/- 38.1%
a10000x10:              -                  14.1ms +/- 38.1%     9.8ms +/- 38.1%
a10000x100:             2.22x as fast       4.2ms +/- 38.1%     1.9ms +/- 38.1%
a10000x1000:            1.76x as fast       6.2ms +/- 38.1%     3.5ms +/- 38.1%

abcdef10x1:             -                   0.3ms +/- 38.4%     0.2ms +/- 38.1%
abcdef100x10:           -                   0.3ms +/- 38.1%     0.2ms +/- 38.2%
abcdef1000x10:          -                   1.7ms +/- 38.1%     1.3ms +/- 38.1%
abcdef1000x100:         -                   1.2ms +/- 38.2%     1.0ms +/- 38.1%
abcdef10000x10:         -                  12.5ms +/- 38.1%     8.6ms +/- 38.1%
abcdef10000x100:        1.79x as fast       5.1ms +/- 38.1%     2.8ms +/- 38.1%
abcdef10000x1000:       -                  11.6ms +/- 38.1%     8.4ms +/- 38.1%

abcdefghij10x1:         -                   0.3ms +/- 38.2%     0.3ms +/- 38.2%
abcdefghij100x10:       -                   0.3ms +/- 38.2%     0.3ms +/- 38.1%
abcdefghij1000x10:      -                   1.8ms +/- 38.1%     1.3ms +/- 38.1%
abcdefghij1000x100:     -                   1.3ms +/- 38.1%     1.1ms +/- 38.1%
abcdefghij10000x10:     -                  13.4ms +/- 38.1%     9.2ms +/- 38.1%
abcdefghij10000x100:    -                   6.1ms +/- 38.1%     3.8ms +/- 38.1%
abcdefghij10000x1000:   -                  16.0ms +/- 38.1%    15.4ms +/- 38.1%
abcdefghij10000x1000:   -                  16.0ms +/- 38.1%    15.4ms +/- 38.1%

blogspotSingle:         ??                  4.8ms +/- 38.1%    4.9ms +/- 38.1%
blogspotLooped:         -                  55.4ms +/- 38.1%    54.9ms +/- 38.1%

blogspotRelevantSingle: ??                  2.5ms +/- 38.1%    2.5ms +/- 38.1%
blogspotRelevantLooped: -                  33.8ms +/- 38.1%    33.8ms +/- 38.1%
I've moved the matchForReplace functions away from the match functions to improve the diff.  It should be much easier to see what has actually changed now.
Attachment #751425 - Attachment is obsolete: true
Attachment #751425 - Flags: review?(sstangl)
Attachment #751431 - Flags: review?(sstangl)
Thanks for your feedback!

When I look at that URL, I only see the following global calls to match:

"https://apis.google.com/_/scs/apps-static/_/js/k=oz.gapi.en.9viu5Uur9oc.O/m=plusone/rt=j/sv=1/d=1/ed=1/am=IQ/rs=AItRSTPu0dCKg-4QKxr5R4RYn2JFNwwuLQ/cb=gapi.loaded_0".match(/\/\//g);
"https://apis.google.com/_/scs/apps-static/_/js/k=oz.gapi.en.9viu5Uur9oc.O/m=plusone/rt=j/sv=1/d=1/ed=1/am=IQ/rs=AItRSTPu0dCKg-4QKxr5R4RYn2JFNwwuLQ/cb=gapi.loaded_0".match(/\/cb=/g);
"https://apis.google.com/_/scs/apps-static/_/js/k=oz.gapi.en.9viu5Uur9oc.O/m=googleapis_client,iframes_styles_bubble_internal/rt=j/sv=1/d=1/ed=1/am=IQ/rs=AItRSTPu0dCKg-4QKxr5R4RYn2JFNwwuLQ/cb=gapi.loaded_0".match(/\/\//g);
"https://apis.google.com/_/scs/apps-static/_/js/k=oz.gapi.en.9viu5Uur9oc.O/m=googleapis_client,iframes_styles_bubble_internal/rt=j/sv=1/d=1/ed=1/am=IQ/rs=AItRSTPu0dCKg-4QKxr5R4RYn2JFNwwuLQ/cb=gapi.loaded_0".match(/\/cb=/g);
"https://apis.google.com/_/scs/apps-static/_/js/k=oz.plusone.en_US.mUkeRQ7VHQw.O/m=p1b,p1p/rt=j/sv=1/d=1/ed=1/am=XQD_Hw/rs=AItRSTOl13AhgSA_jyCRFApb2nz4BUNpAg/cb=gapi.loaded_1".match(/\/\//g);
"https://apis.google.com/_/scs/apps-static/_/js/k=oz.plusone.en_US.mUkeRQ7VHQw.O/m=p1b,p1p/rt=j/sv=1/d=1/ed=1/am=XQD_Hw/rs=AItRSTOl13AhgSA_jyCRFApb2nz4BUNpAg/cb=gapi.loaded_1".match(/\/cb=/g);

These are already captured in my blogspot.js benchmark.  Since they do not have multiple capture groups, they don't seem likely to experience a huge benefit from this patch (though maybe a small benefit from avoiding unnecessary rooted object construction).  Can you tell me if the above .match()'s are what you were expecting?  Maybe I am missing some calls for the profile?
You might find some useful details/perf profiles at this bug for blogspot perf:

https://bugzilla.mozilla.org/show_bug.cgi?id=792797
Comment on attachment 751431 [details] [diff] [review]
Improving diff format, fixing a couple of style issues.

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

This looks good, nice work! Aside from some small nitpicky stuff: it looks like we don't need |RootedObject obj| after all, and there is a bug with overeager RegExpStatics updating. With these issues fixed, the patch should be good to land.

::: js/src/jsstr.cpp
@@ +1712,5 @@
> +    res->updateFromMatchPairs(cx, linearStr, matches);
> +    return CreateRegExpMatchResult(cx, linearStr, matches, rval);
> +}
> +
> +typedef JSObject **MatchArgType;

Can we get rid of MatchArgType and just use (JSObject **) directly? (Actually, it turns out that we don't need either -- see comment about |RootedObject array| in str_match().)

@@ +1715,5 @@
> +
> +typedef JSObject **MatchArgType;
> +
> +static bool
> +BuildGlobalMatchArray(JSContext *cx, MutableHandleObject obj, MutableHandleValue v,

With the elimination of |obj| in favor of |array|, I find it somewhat less objectionable to construct |RootedValue v| in this function. It's your call, but the performance impact isn't terrible (probably unnoticeable), and it might look nicer constructing |v| in this function because it makes it clear that the code expects |v|'s rooting to end with this function, and that it is safe.

@@ +1722,5 @@
> +{
> +    JS_ASSERT(count <= JSID_INT_MAX);  /* by max string length */
> +    JS_ASSERT(pair.check());
> +
> +    if(!obj) {

Nit: |if (|.

@@ +1724,5 @@
> +    JS_ASSERT(pair.check());
> +
> +    if(!obj) {
> +        /* Setup the return array if it hasn't been setup already.
> +         * This should only happen once in a match. */

With the use of |RootedObject array| in place of |obj|, this comment may be removed, as it will be obvious.

@@ +1729,5 @@
> +        JSObject *&array = *data;
> +        if (!array)
> +            array = NewDenseEmptyArray(cx);
> +        obj.set(array);
> +        if(!obj)

Nit: |if (|.

@@ +1733,5 @@
> +        if(!obj)
> +            return false;
> +    }
> +
> +    JSString *str = js_NewDependentString(cx, matchesInput, pair.start, pair.limit - pair.start);

Nit: last argument can be |pair.length()|.

@@ +1741,5 @@
> +    return JSObject::defineElement(cx, obj, count, v);
> +}
> +
> +static bool
> +DoMatchGlobal(JSContext *cx, RegExpStatics *res, JSLinearString *linearPtr, RegExpShared &re, MatchArgType data)

Actually, could we just get rid of MatchArgType entirely and use (JSObject **)? It also looks like this line may exceed the 99-column limit and needs wrapping.

@@ +1770,2 @@
>      }
> +    res->updateLazily(cx, linearPtr, &re, prevMatch);

There is a bug here: updateLazily() will be called even if no matches were ever found.

@@ -1848,5 @@
>      if (!g.normalizeRegExp(cx, false, 1, args))
>          return false;
>  
> -    RootedObject array(cx);
> -    MatchArgType arg = array.address();

Oh, wow, I didn't even realize how wrong this (pre-existing) code is! This is extremely sneaky and horribly GC-unsafe: writing to a RootedObject while a GC slice is ongoing requires triggering prebarriers to add the new GC object to the graph, but this just clobbers the Rooted's memory in an unsafe way. Gross.

@@ +1828,3 @@
>          return false;
>  
> +    if(g.regExp().global()){

nit: |if (|

@@ +1828,4 @@
>          return false;
>  
> +    if(g.regExp().global()){
> +        RootedObject array(cx);

It looks like DoMatchGlobal() doesn't need either |RootedObject obj| or |MatchArgType data| -- it should just take a MutableHandleObject to this |array| -- since that's what |obj| is building anyway!

@@ +1835,4 @@
>          args.rval().setObjectOrNull(array);
> +    } else {
> +        RootedValue rval(cx);
> +        if(!DoMatchLocal(cx, res, linearStr, g.regExp(), &rval))

Nit: |if (|.
"Local" isn't quite the right word... which is probably "Non-Global", but that sounds terrible. "DoMatchOnce()"? It also would be fine to keep "Local".

@@ +1912,5 @@
>      StringBuffer       sb;             /* buffer built during DoMatch */
>  };
>  
>  static bool
> +ReplaceRegExp(JSContext *cx, RegExpStatics *res, ReplaceData &rVal);

ReplaceData is "rdata" elsewhere. Although sometimes it's just "data". The former is preferable.

@@ +1925,5 @@
> +    RegExpRunStatus status = re.execute(cx, linearStr->chars(), charsLen, &i, matches);
> +    if (status == RegExpRunStatus_Error)
> +        return false;
> +
> +    if (status != RegExpRunStatus_Success_NotFound) {

This would be better inverted: |if (status != RegExpRunStatus_Success_NotFound) \ return true;|

@@ +1951,5 @@
> +            break;
> +
> +        res->updateFromMatchPairs(cx, linearStr, matches);
> +
> +        if (!ReplaceRegExp(cx, res, data))

Just as a note, the plan for the future (in a separate bug) will be to pass the MatchPairs in place of the RegExpStatics, then only update the RegExpStatics upon return from this function. This is a large refactoring effort and gets very tricky in the |rdata.lambda| case in FindReplaceLength().

@@ +2551,5 @@
>          JS_ASSERT(!rdata.lambda && !rdata.elembase && !rdata.dollar);
>          return str_replace_regexp_remove(cx, args, rdata.str, re);
>      }
>  
> +    Rooted<JSLinearString*> linearStr(cx, rdata.str->ensureLinear(cx));

It would be better to check for !linearStr and return false here, rather than indent a number of following lines.

@@ +2552,5 @@
>          return str_replace_regexp_remove(cx, args, rdata.str, re);
>      }
>  
> +    Rooted<JSLinearString*> linearStr(cx, rdata.str->ensureLinear(cx));
> +    bool isSuccessfulMatch = false;

This name is misleading: if the return value of DoMatchForReplace*() is false, it does not mean that no match was found, but rather that an error occurred. No variable is necessary anyway: each branch of the |if (re.global())| can contain a check and |return false|.

@@ +2554,5 @@
>  
> +    Rooted<JSLinearString*> linearStr(cx, rdata.str->ensureLinear(cx));
> +    bool isSuccessfulMatch = false;
> +    if (linearStr) {
> +        if(re.global())

nit: |if (|.

@@ +2559,5 @@
> +            isSuccessfulMatch = DoMatchForReplaceGlobal(cx, res, linearStr, re, rdata);
> +        else
> +            isSuccessfulMatch = DoMatchForReplaceLocal(cx, res, linearStr, re, rdata);
> +    }
> +    if(!isSuccessfulMatch)

nit: |if (|.
Attachment #751431 - Flags: review?(sstangl)
This patch should address your feedback.  I decided to stick with "Local" (DoMatchLocal, etc), to emphasize the relationship to the Global methods since you mentioned that as an option.  I've also updated the test to catch the bug you found.  Let me know if I missed anything.
Attachment #751431 - Attachment is obsolete: true
Attachment #752008 - Flags: review?(sstangl)
Comment on attachment 752008 [details] [diff] [review]
Upated with corrections.

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

This is great. Thank you for cleaning up this regexp mess, and for seeing the patch through to the end!
Attachment #752008 - Flags: review?(sstangl) → review+
Keywords: checkin-needed
https://hg.mozilla.org/integration/mozilla-inbound/rev/0786d6b95b93
Flags: in-testsuite+
Keywords: checkin-needed
Target Milestone: --- → mozilla24
This checkin added two new rooting hazards:

Function 'jsstr.cpp:uint8 BuildGlobalMatchArray(JSContext*, JSString*, js::MatchPair*, uint64, class JS::MutableHandle<JSObject*>)' has unrooted 'matchesInput' of type 'JSString*' live across GC call 'JSObject* js::NewDenseEmptyArray(JSContext*, JSObject*, uint32)' at js/src/jsstr.cpp:1724

Function 'jsstr.cpp:uint8 DoMatchGlobal(JSContext*, js::RegExpStatics*, JSLinearString*, js::RegExpShared*, class JS::MutableHandle<JSObject*>)' has unrooted 'linearPtr' of type 'JSLinearString*' live across GC call 'jscntxt.h:uint8 JS_CHECK_OPERATION_LIMIT(JSContext*)' at js/src/jsstr.cpp:1746

I think just making the linearPtr and matchesInput arguments Handle<JSLinearString*> and Handle<JSString*> respectively should do the trick to fix those....
https://hg.mozilla.org/mozilla-central/rev/0786d6b95b93
Status: NEW → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Depends on: 874948
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: