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

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
8 years ago
7 years ago

People

(Reporter: firefox, Assigned: dmandelin)

Tracking

({perf})

1.9.1 Branch
Points:
---

Firefox Tracking Flags

(status1.9.1 .9-fixed)

Details

(Whiteboard: wanted-3.5.1, URL)

Attachments

(3 attachments)

(Reporter)

Description

8 years ago
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.
(Reporter)

Comment 1

8 years ago
Created attachment 386589 [details]
Testcase
OS: Windows Vista → All
Hardware: x86 → All
Summary: TraceMonkey: Severe performance deterioration of String.match with complex regex → TM: Severe performance deterioration of String.match with complex regex
Version: unspecified → 1.9.1 Branch
(Assignee)

Comment 2

8 years ago
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.
Assignee: general → dmandelin
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Attachment #386612 - Flags: review?(gal)

Comment 3

8 years ago
Comment on attachment 386612 [details] [diff] [review]
Patch

Time to move this stuff out of the lir.
Attachment #386612 - Flags: review?(gal) → review+
(Assignee)

Updated

8 years ago
Flags: wanted1.9.1.x?
Whiteboard: wanted-3.5.1
(Assignee)

Comment 4

8 years ago
Pushed to TM as 24ea6a78f889.

Comment 5

8 years ago
http://hg.mozilla.org/mozilla-central/rev/24ea6a78f889
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
(Assignee)

Updated

8 years ago
Duplicate of this bug: 503538
If this is wanted on the 1.9.1 branch please request approval on the patch.
status1.9.1: --- → ?
Flags: wanted1.9.1.x?
(Assignee)

Comment 8

8 years ago
Created attachment 425345 [details] [diff] [review]
Patch rebased for 1.9.1 (context changed only)
Attachment #425345 - Flags: approval1.9.1.9?
(Assignee)

Updated

8 years ago
Blocks: 536334

Updated

8 years ago
Attachment #425345 - Flags: review+
Comment on attachment 425345 [details] [diff] [review]
Patch rebased for 1.9.1 (context changed only)

a=beltzner for 1.9.1
Attachment #425345 - Flags: approval1.9.1.9? → approval1.9.1.9+
(Assignee)

Comment 10

7 years ago
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/816f7af6da91
status1.9.1: ? → wanted

Updated

7 years ago
status1.9.1: wanted → .9-fixed
Keywords: perf
You need to log in before you can comment on or make changes to this bug.