289669 - RegExp Object is extremely slow with String.replace

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Bug Tracker]

User-Agent:       Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0; .NET CLR 1.1.4322)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.8b2) Gecko/20050402 Firefox/1.0+

I do not know if it is the RegExp implementation or the String.replace method 
implementation but the URL given executes in 61 msec on IE, ~500 msec on 
Mozilla/Firefox. Given the current speed of the processors I think mozilla 
should break well down the 60 msec barrier. 500 msec is just plain unacceptable 
as you may also agree with.

Reproducible: Always

Steps to Reproduce:
1.run the code
2.
3.

Actual Results:  
It should be blazingly fast

Expected Results:  
Runs like an old i386DX on a 1.5ghz pentium 4.

For real life success, this needs to be sped up.

Comment 1

[Bug Tracker]

Correction on the given URL, IE runtime speed is between 16-31 msecs. Mozilla 
runtime is between 484-500 msecs.

ouch!
;)

Comment 2

[Bob Clary [:bc] (inactive)]

confirmed. we have O(N^2) behavior while IE has O(N)

Comment 3

[Bug Tracker]

O(N) ;), almost NP Complete aye?

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

The testcase seems to be down. Can someone attach it to this bug? Or is this
just a bug about String.replace being slow?

Comment 5

[Bob Clary [:bc] (inactive)]

Attachment: regexp.html (original)

Comment 6

[Bob Clary [:bc] (inactive)]

Attachment: regexp2.html (with pretty pictures! oooh!)

Comment 7

[Bob Clary [:bc] (inactive)]

Checking in regress-289669.js;
/cvsroot/mozilla/js/tests/ecma_3/RegExp/regress-289669.js,v  <--  regress-289669.js
initial revision: 1.1
done

Comment 8

[Bob Clary [:bc] (inactive)]

we are linear on the trunk now on all platforms but still much slower than IE (almost 30 times slower on limit 9000).

Comment 9

[Bob Clary [:bc] (inactive)]

still O(N^2) for windows shell from 20060405, but not browser. Maybe the windows realloc....

Comment 10

[Carlos Alén Silva]

Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.4) Gecko/20100503 Firefox/3.6.4

Using regexp.html I got 16-19 ms, much lower than the original 500 ms.

With Chrome 5, I got 6-9 ms.

Comment 11

[Ian Neal]

On both 1.9.2.5pre and 1.9.3a5pre I get 9-11 ms. Not tried Chrome 5 on linux.

Comment 12

[Jan de Mooij [:jandem]]

This is about as fast as Chrome now (4-6), probably fixed by YARR. Marking fixed.