502058 - TM: Severe performance deterioration of String.match with complex regex

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[firefox]

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]

Attachment: Testcase

Comment 2

[David Mandelin [:dmandelin]]

Attachment: 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]

Comment on attachment 386612 [details] [diff] [review]
Patch

Time to move this stuff out of the lir.

Comment 4

[David Mandelin [:dmandelin]]

Pushed to TM as 24ea6a78f889.

Comment 5

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/24ea6a78f889

Comment 7

[Daniel Veditz [:dveditz]]

If this is wanted on the 1.9.1 branch please request approval on the patch.

Comment 8

[David Mandelin [:dmandelin]]

Attachment: Patch rebased for 1.9.1 (context changed only)

Comment 9

[Mike Beltzner [:beltzner, not reading bugmail]]

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]]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/816f7af6da91