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

Status: RESOLVED DUPLICATE of bug 502058

(Core :: JavaScript Engine, defect)

Description

[Bryan]

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.

Comment 1

[Bryan]

Attachment: html page that runs a test to reproduce the issue

Attached a page that runs the script described in steps to reproduce.

Comment 2

[Ria Klaassen (not reading all bugmail)]

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

Comment 3

[Ria Klaassen (not reading all bugmail)]

Trunk builds (Minefield): http://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/latest-mozilla-central/

Comment 4

[Bryan]

Thanks. Is this fix likely to go out in an upcoming point release, or will it be longer?

Comment 5

[Ria Klaassen (not reading all bugmail)]

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

Comment 6

[Bryan]

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

Comment 7

[David Mandelin [:dmandelin]]

Thanks for the analysis. FWIW, the other bug is marked 'wanted1.9.1.x'.