Comparing speed of non-matching regexp

Question

The following Python code is incredibly slow:

import re
re.match( '([a]+)+c', 'a' * 30 + 'b' )

and it gets worse if you replace 30 with a larger constant.

I suspect that the parsing ambiguity due to the consecutive + is the culprit, but I'm not very expert in regexp parsing and matching. Is this a bug of the Python regexp engine, or any reasonable implementation will do the same?

I'm not a Perl expert, but the following returns quite fast

perl -e '$s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; print "ok\n" if $s =~ m/([a]+)+c/;'

and increasing the number of 'a' does not alter substantially the execution speed.

Answer 1

I assume that Perl is clever enough to collapse the two +s into one, while Python is not. Now let's imagine what the engine does, if this is not optimized away. And remember that capturing is generally expensive. Note also, that both +s are greedy, so the engine will try to use as many repetitions as possible in one backtracking step. Each bullet point represents one backtracking step:

• The engine uses as many [a] as possible, and consumes all thirty as. Then it can not go any further, so it leaves the first repetition and captures 30 as. Now the next repetition is on and it tries to consume some more with another ([a]+) but that doesn't work of course. And then the c fails to match b.
• Backtrack! Throw away the last a consumed by the inner repetition. After this we leave the inner repetition again, so the engine will capture 29 as. Then the other + kicks in, the inner repetition is tried out again (consuming the 30th a). Then we leave the inner repetition once again, which also leaves the capturing group, so the first capture is thrown away and the engine captures the last a. c fails to match b.
• Backtrack! Throw away another a inside. We capture 28 as. The second (outer repetition) of the capturing group consumes the last 2 as which are captured. c fails to match b.
• Backtrack! Now we can backtrack in the second other repetition and throw away the second of two as. The one that is left will be captured. Then we enter the capturing group for the third time and capture the last a. c fails to match b.
• Backtrack! Down to 27 as in the first repetition.

Here is a simple visualization. Each line represents one backtracking step, and each set of parentheses shows one consumption of the inner repetition. The curly brackets represent those that are newly captured for that step of backtracking, while normal parentheses are not revisited in this particular backtracking step. And I leave out the b/c because it will never be matched:

{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaa}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaa}{aaaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aaa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa){a}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a)(a){a}{a}

And. so. on.

Note that in the end the engine will also try all combinations for subsets of a (backtracking just through the first 29 as then through the first 28 as) just to discover, that c does also not match a.

The explanation of regex engine internals is based on information scattered around regular-expressions.info.

To solve this. Simply remove one of the +s. Either r'a+c' or if you do want to capture the amount of as use r'(a+)s'.

Finally, to answer your question. I would not consider this a bug in Python's regex engine, but only (if anything) a lack in optimization logic. This problem is not generally solvable, so it is not too unreasonably for an engine to assume, that you have to take care of catastrophic backtracking yourself. If Perl is clever enough to recognize sufficiently simple cases of it, so much the better.

Answer 2

Rewrite your regular expression to eliminate the "catastrophic backtracking", by removing the nested quantifiers (see this question):

re.match( '([a]+)+c', 'a' * 30 + 'b' )
# becomes
re.match( 'a+c', 'a' * 30 + 'b' )