Title: re engine exhaustively explores more than necessary
Type: performance Stage:
Components: Regular Expressions Versions: Python 3.3, Python 2.7
Status: closed Resolution: duplicate
Dependencies: Superseder: the re module can perform poorly: O(2**n) versus O(n**2)
View: 1662581
Assigned To: Nosy List: mrabarnett, nikomatsakis, terry.reedy
Priority: normal Keywords:

Created on 2011-02-24 12:57 by nikomatsakis, last changed 2011-02-25 20:42 by terry.reedy. This issue is now closed.

Messages (3)
msg129262 - (view) Author: Niko Matsakis (nikomatsakis) Date: 2011-02-24 12:57
Executing code like this:

>>> r = re.compile(r'(\w+)*=.*')
>>> r.match("abcdefghijklmnopqrstuvwxyz")

takes a long time (around 12 seconds, on my machine).  Presumably this is because it is enumerating all the various ways to divvy up the alphabet for (\w+), even though there is no "=" sign to be found.  In contrast, in perl a regular expression like that seems to run instantly.

This could be optimized by recognizing that no "=" sign was found, and thus it does not matter how the first part of the regular expression matches, so there is no need to try additional possibilities.  To some extent, of course, the answer is just "don't write regular expressions like that."  This example is reduced down from a real regexp where the potential inefficiency was less obvious.  Nonetheless the general optimization of recognizing when further re-enumeration is not necessary makes sense more generally.

In any case, I am submitting the bug report merely to raise the issue as a possible future optimization, not to suggest that it must be addressed immediately (or even at all).
msg129297 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2011-02-24 18:10
It's a known issue (see issue #1662581, for example).

There's a new implementation at PyPI which doesn't have this problem:
msg129424 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-02-25 20:42
13 secs on my 7 year old windows machine.
Date User Action Args
2011-02-25 20:42:44terry.reedysetstatus: open -> closed

superseder: the re module can perform poorly: O(2**n) versus O(n**2)
versions: + Python 2.7, Python 3.3, - Python 2.6, Python 3.1
nosy: + terry.reedy

messages: + msg129424
resolution: duplicate
2011-02-24 18:10:51mrabarnettsetnosy: + mrabarnett
messages: + msg129297
2011-02-24 12:57:46nikomatsakiscreate