Status: New
Owner: ----
New issue 831 by polarjs: regexp performance seems to degrade exponentially
with length of failed expression
http://code.google.com/p/v8/issues/detail?id=831
Here is a test case that illustrates this issue:
=== BEGIN test =====
function init() {
var strValue = "[email protected]";
print( "started " + strValue );
var startTime = Date.now();
var emailRegEx = /^[A-Z0-9]+([A-Z0-9._%+-]*)+...@[a-z0-9.-]+\.[a-z]{2,4}$/i;
var s = strValue.search(emailRegEx) != -1;
var endTime = Date.now();
print( "ended "+s );
print( "time = " + (endTime - startTime));
}
init();
=== END test =====
I built d8 with bleeding edge rev 5279 (scons mode=debug d8). Here's the
result (time in ms):
$ ./d8_g ../../wk-trunk/regexp-issue.js
started [email protected]
ended true
time = 2
Replace the '@' strValue with a 'c' and we get:
$ ./d8_g ../../wk-trunk/regexp-issue.js
started mickey.mousecgmail.com
ended false
time = 244
Add one char ('1') after mouse, and we get:
$ ./d8_g ../../wk-trunk/regexp-issue.js
started mickey.mouse1cgmail.com
ended false
time = 483
Add one more char ('2'), and we get:
$ ./d8_g ../../wk-trunk/regexp-issue.js
started mickey.mouse12cgmail.com
ended false
time = 969
Note that the time seems to be doubling with each char added. The failed
match case also seems to take significantly more (about 2 orders of
magnitude) time than the success case. Is this reasonable?
The above test was conducted using up a relatively fast x86 machine. On
ARM, the difference in time can be significantly more pronounced.
In the above, I used a debug build. I also re-tested with a non-debug
build, and the timing results are still in the proximate values.
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
