Why TERRIBLE performance of regular expressions in re module ?

[Skip Montanaro]

    Russell> While debugging a CGI script, I came across the following
    Russell> strange behavior: a regular expression that seems to require
    Russell> exponential time to recognize a string.  For the first twenty
    Russell> some-odd characters, it performed fine.  I added another
    Russell> character, and the time became .. well, noticeable.  Another
    Russell> character, and recognition required 30+ seconds.  Another,
    Russell> 1:15.  Another, 2:2x.  Another, just under 5 minutes.  Another,
    Russell> 9 minutes, plus.

Can you post the pattern and the input string(s) you used?  You might want
to search the c.l.py archives for "backtracking".

Skip Montanaro | http://www.mojam.com/
skip at mojam.com | http://www.musi-cal.com/
847-971-7098   | Python: Programming the way Guido indented...