Last Comment Bug 502058 - TM: Severe performance deterioration of String.match with complex regex
: TM: Severe performance deterioration of String.match with complex regex
Status: RESOLVED FIXED
wanted-3.5.1
: perf
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: 1.9.1 Branch
: All All
: -- normal (vote)
: ---
Assigned To: David Mandelin [:dmandelin]
:
Mentors:
http://www.schierla.de/tmp/testcase/t...
: 503538 (view as bug list)
Depends on:
Blocks: 536334
  Show dependency treegraph
 
Reported: 2009-07-02 13:33 PDT by firefox
Modified: 2010-03-30 11:18 PDT (History)
9 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
.9-fixed


Attachments
Testcase (2.56 KB, text/html)
2009-07-02 13:34 PDT, firefox
no flags Details
Patch (4.71 KB, patch)
2009-07-02 15:29 PDT, David Mandelin [:dmandelin]
gal: review+
Details | Diff | Review
Patch rebased for 1.9.1 (context changed only) (4.59 KB, patch)
2010-02-04 16:25 PST, David Mandelin [:dmandelin]
gal: review+
mbeltzner: approval1.9.1.9+
Details | Diff | Review

Description firefox 2009-07-02 13:33:36 PDT
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; de-DE; rv:1.9.1) Gecko/20090624 Firefox/3.5 (.NET CLR 3.5.30729)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; de-DE; rv:1.9.1) Gecko/20090624 Firefox/3.5 (.NET CLR 3.5.30729)

Executing String.match with a (certain) complex regex on long strings 
takes much (factor 1000) longer with TraceMonkey enabled.

Reproducible: Always

Steps to Reproduce:
1. Open the test case (cf. URL or attachment)
2. Click the "Test" button
3. Toggle TraceMonkey (javascript.options.jit.content)
4. Click the "Test" button again
Actual Results:  
The run with TraceMonkey takes a lot longer than the one without
(6800ms with TraceMonkey vs. 7ms without Tracemonkey)

Expected Results:  
Both runs should take about equally long.
Comment 1 firefox 2009-07-02 13:34:41 PDT
Created attachment 386589 [details]
Testcase
Comment 2 David Mandelin [:dmandelin] 2009-07-02 15:29:08 PDT
Created attachment 386612 [details] [diff] [review]
Patch

The problem is related to this code in RegExpNativeCompiler::compile:

        /* 
         * If the regexp is too long nanojit will assert when we
         * try to insert the guard record.
         */
        if (re_length > 1024)
            return JS_FALSE;

The regexp in this test case is longer that 1024, so we exit here. But the fragment doesn't get blacklisted, so we keep trying to compile it again and again. Each compilation is only about 100,000 cycles, but we run so many of them (repeating the match operation globally on a string of increasing length) that they add up.

I tried adding "fragment->blacklist()" to the code above, but that doesn't work. Because of the way the regexp identity is stored in a fragment, it ends up not getting stored in this case, so we don't find the blacklisted fragment ever, and keep trying to compile over and over.

Instead, I decided to use a free flag bit in JSRegExp to record the fact that we can't compile the regexp and shouldn't try again. This also allows us to bail out of the native compilation path faster than before.
Comment 3 Andreas Gal :gal 2009-07-02 15:35:30 PDT
Comment on attachment 386612 [details] [diff] [review]
Patch

Time to move this stuff out of the lir.
Comment 4 David Mandelin [:dmandelin] 2009-07-06 13:22:09 PDT
Pushed to TM as 24ea6a78f889.
Comment 6 David Mandelin [:dmandelin] 2009-07-10 11:54:54 PDT
*** Bug 503538 has been marked as a duplicate of this bug. ***
Comment 7 Daniel Veditz [:dveditz] 2009-08-20 19:44:36 PDT
If this is wanted on the 1.9.1 branch please request approval on the patch.
Comment 8 David Mandelin [:dmandelin] 2010-02-04 16:25:48 PST
Created attachment 425345 [details] [diff] [review]
Patch rebased for 1.9.1 (context changed only)
Comment 9 Mike Beltzner [:beltzner, not reading bugmail] 2010-02-22 10:41:20 PST
Comment on attachment 425345 [details] [diff] [review]
Patch rebased for 1.9.1 (context changed only)

a=beltzner for 1.9.1
Comment 10 David Mandelin [:dmandelin] 2010-02-22 10:45:27 PST
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/816f7af6da91

Note You need to log in before you can comment on or make changes to this bug.