Status: New
Owner: ----
New issue 1259 by [email protected]: RegExp matching is too slow in
case of iterative matching of alternatives
http://code.google.com/p/v8/issues/detail?id=1259
If you try to match a pattern which contains alternations enclosed by an
iterative group then the time of the matching takes much more time on a long
input than that is expected. The "timeout" is occured when the pattern
matching fails (otherwise the matching is ended at the first iteration).
E.g.:
'xxxxxxxxxxxxxxxxxxxxxxxxxxx'.match(/(x|x)*a/);
If you increase the length of the input the time of the matching is
exponentially increasing.
When the number of alternatives is increased (e.g. /(x|x|x)*a/) or the
subpattern contains iterative terms (e.g. /(x*|x)*a/) then the pattern
matching is much more slower.
I think the problem is in the backtracking logic of the generated code.
Probably the
current logic does a lots of unnecessary redundant check on alternatives in
every iteration and the failure of matching could be recognized earlier.
E.g.:
The algorythm does backtrack 10 times to the first alternative in case
of 'xx'.match(/(.|.)*a/).
The problem is same in the mozilla test suite: ecma_3/RegExp/regress-307456
(see test/mozilla/mozilla.status).
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
