[Python-Dev] re performance

[MRAB]

On 2017-01-26 21:13, Sven R. Kunze wrote:
> Hi folks,
>
> I recently refreshed regular expressions theoretical basics *indulging
> in reminiscences* So, I read https://swtch.com/~rsc/regexp/regexp1.html
>
> However, reaching the chart in the lower third of the article, I saw
> Python 2.4 measured against a naive Thompson matching implementation.
> And I was surprised about how bad it performed compared to an
> unoptimized version of an older than dirt algorithm.
>
> So, I decided to give it a try with Python2.7 and Python3.5. Eh, voilà,
> 100% cpu and no results so far. Nothing has changed at all since 2007.
>
>   >>> import re
>   >>> re.match(r'a?'*30 + r'a'*30, 'a'*30)
> .... (still waiting)
>
> Quoting from the article: " Some might argue that this test is unfair to
> the backtracking implementations, since it focuses on an uncommon corner
> case. This argument misses the point: given a choice between an
> implementation with a predictable, consistent, fast running time on all
> inputs or one that usually runs quickly but can take years of CPU time
> (or more) on some inputs, the decision should be easy."
>
> Victor, as the head of Python performance department, and Matthew, as
> the maintainer of the new regex module, what is your stance on this
> particular issue?
>
>   From my perspective, I can say, that regular expressions might worth
> optimizing especially for web applications (url matching usually uses
> regexes) but also for other applications where I've seen many tight
> loops using regexes as well. So, I am probing interest on this topic here.
It's possible to add some checks to reduce the problem, as I've done in 
the regex module, but I'm not sure how easy it would be to retrofit it 
into the existing re code. (It wasn't pleasant in the regex module, so...).