Closed Bug 503538 Opened 14 years ago Closed 14 years ago

Regular expressions with more than 511 elements OR'd (|) together have extremely poor performance

Categories

(Core :: JavaScript Engine, defect)

1.9.1 Branch
x86_64
Windows Vista
defect
Not set
major

Tracking

()

RESOLVED DUPLICATE of bug 502058

People

(Reporter: bryanrsmith, Unassigned)

Details

Attachments

(1 file)

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US) AppleWebKit/530.5 (KHTML, like Gecko) Chrome/2.0.172.33 Safari/530.5
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1) Gecko/20090624 Firefox/3.5 (.NET CLR 3.5.30729)

Creating a regular expression with 511 elements OR'd together (for example, 'a|b|c|d|...') executes quickly. Adding a single '|a' on to the end of the regex, so that it has 512 elements, causes the regex to run several orders of magnitude slower. Rerunning the 512-element regex will cause it to take progressively longer to execute until the browser is restarted.

Reproducible: Always

Steps to Reproduce:
1. Run the following script, which creates a regular expression with 511 elements OR'd together, and executes it 10,000 times:
// Begin regex test
var reTest = new RegExp('a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a');

var start = (new Date()).getTime();
for(var i = 0; i < 10000; i++)
{
	reTest.exec("test");
}

var end = (new Date()).getTime();
alert('Ran in ' + (end - start) + ' ms.');

// End regex test
2. Note that it takes approximately 50ms in FF3.5, 550ms in IE8, 3ms in chrome.

3. Modify reTest and add 1 more '|a' on to the end. reTest now has 512 elements OR'd together.

4. Rerun the test. Note that it now takes approximately 1000ms in FF3.5. IE8 and chrome show no noticeable change in performance.

5. Reload the page to immediately re-run the script. Note that the second time FF3.5 takes approximately 2000ms. It will get about 1000ms slower every time you run the script until you restart the browser.
Actual Results:  
Performance of the complex (>511 element) regular expression degraded significantly.

Expected Results:  
The regular expression should continue performing quickly. It's execution time should not vary significantly between runs or require a browser restart.

Verified in FF3.5 on Mac OSX as well. This issue was not present in versions of Firefox prior to 3.5.
Attached a page that runs the script described in steps to reproduce.
Tested on Windows Vista, I see the problem indeed with Firefox 3.5, but it seems fixed on latest trunk. 

Firefox 3.5: ~1500 ms
Firefox 3.6: ~270 ms
Firefox 3.0: ~320 ms
Assignee: nobody → general
Component: General → JavaScript Engine
Product: Firefox → Core
QA Contact: general → general
Version: unspecified → 1.9.1 Branch
Thanks. Is this fix likely to go out in an upcoming point release, or will it be longer?
Is possible because it is a recent patch; some bug in this range (21 hidden changesets) has fixed this: http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=e6dc95bd3eb5&tochange=a5b215383e58
Here it is. Looks like the issue was caused by the regex pattern string length being greater than 1024 characters. 

https://bugzilla.mozilla.org/show_bug.cgi?id=502058
Thanks for the analysis. FWIW, the other bug is marked 'wanted1.9.1.x'.
Status: UNCONFIRMED → RESOLVED
Closed: 14 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.