slow regex?
Dave Mitchell
bleed):
$_ = <<'EOF';
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
EOF
print "matched\n" if /.*?A.*?B+\s+X/s;
While I can see that it may need to backtrack 70x70 times, this still
seems quite slow. (This is a stripped-down version of a regex I wrote
for production code that basically ground to a halt).
Is this is bug, or do I have unrealistic expectations?
Dave.
--
In England there is a special word which means the last sunshine
of the summer. That word is "spring".
Andy Lester
> This regex takes 2.5 secs on my machine to fail to match (5.8.4 and
> bleed):
>
> $_ = <<'EOF';
> AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
> BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
> EOF
>
> print "matched\n" if /.*?A.*?B+\s+X/s;
There's no need for that .*? at the beginning. It's always going to
match (although I"m not sure what that ? is gonna do after a *).
Drop the leading .* and you're happy.
--
Andy Lester => an...@petdance.com => www.petdance.com => AIM:petdance
Yitzchak Scott-Thoennes
> This regex takes 2.5 secs on my machine to fail to match (5.8.4 and
> bleed):
>
> $_ = <<'EOF';
> AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
> BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
> EOF
>
> print "matched\n" if /.*?A.*?B+\s+X/s;
>
> While I can see that it may need to backtrack 70x70 times, this still
> seems quite slow. (This is a stripped-down version of a regex I wrote
> for production code that basically ground to a halt).
>
> Is this is bug, or do I have unrealistic expectations?
>
> Dave.
Any regex with a series of * or + can be bad news (especially if it
is going to end up failing). Use (?> ) to surround parts you know
won't need to backtrack. See perlre.
h...@crypt.org
:This regex takes 2.5 secs on my machine to fail to match (5.8.4 and
:bleed):
:
: $_ = <<'EOF';
: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
: BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
: EOF
:
: print "matched\n" if /.*?A.*?B+\s+X/s;
:
:While I can see that it may need to backtrack 70x70 times, this still
:seems quite slow. (This is a stripped-down version of a regex I wrote
:for production code that basically ground to a halt).
:
:Is this is bug, or do I have unrealistic expectations?
Testing C<< join '', 'A' x $n, ' ', 'B' x $n, ' ' >> against that
regexp, and grepping the resulting -Dr output for 'Setting an EVAL scope',
the number of scopes set as a function of $len is:
(n^4 + 4n^3 + 5n^2 + 10n) / 4
.. which gives 6,351,800 for n=70.
That's not quite as bad as an exponential search, but still pretty poor:
it is avoidable only by optimisation though, because there really are
4 degrees of freedom that vary according to n. That is, 3 of the
quantifiers /.*?/, /.*/, /B+/, and the starting point (since the match
is unanchored).
Since the components are all deterministic, in the sense that there are
no references to captures and no evals, it might be possible to invent
an optimisation scheme that works backwards: the first time we try to
match the /X/ at end of string and fail, we can tell the previous node
'no point matching to here', and that information can accumulate and
propagate backwards through the pattern up until the point we tell the
start node 'no point matching anywhere', at which point it can give up.
However, it would be quite difficult to store that information: you'd
need to be able to store a bit per length($string) per node in the
pattern (even if you might usually be able to collapse the information
to more compact ranges), and that could get real expensive when matching
a long string against a moderately complex pattern.
I think though that this is essentially what the superexponential cache
tries to do, and not so long ago we disabled that for a wide class of
cases because it was giving wrong results in a small subset of cases.
If we could revisit that to either fix the wrong results, or better
characterise the situations it can't guarantee handling correctly, we
might well be able to reduce the cost of such patterns to around O(n^2).
Hugo
Dave Mitchell
> Dave Mitchell <da...@iabyn.com> wrote:
> :This regex takes 2.5 secs on my machine to fail to match (5.8.4 and
> :bleed):
> :
> : $_ = <<'EOF';
> : AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
> : BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
> : EOF
> :
> : print "matched\n" if /.*?A.*?B+\s+X/s;
> :
> :While I can see that it may need to backtrack 70x70 times, this still
> :seems quite slow. (This is a stripped-down version of a regex I wrote
> :for production code that basically ground to a halt).
> :
> :Is this is bug, or do I have unrealistic expectations?
>
> Testing C<< join '', 'A' x $n, ' ', 'B' x $n, ' ' >> against that
> regexp, and grepping the resulting -Dr output for 'Setting an EVAL scope',
> the number of scopes set as a function of $len is:
> (n^4 + 4n^3 + 5n^2 + 10n) / 4
> .. which gives 6,351,800 for n=70.
Ah yes, I hadn't really thought it through - I can see now why its O(n^4)
not O(n^2).
Thanks.
PS folks - I wouldn't *really* start a regex with .*? - this was only a
by-product of stripping down the real regex. Honest!
--
To collect all the latest movies, simply place an unprotected ftp server
on the Internet, and wait for the disk to fill....