Python, Catastrophic Regular Expressions and the GIL (2013)
benfrederickson.com
Python, Catastrophic Regular Expressions and the GIL (2013)
1–10 of 39 posts
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#2The article starts with the famous quote by Jamie Zawinski:
Some people, when confronted with a problem, think ‘I know, I’ll use regular
expressions.’ Now they have two problems.
The article is short and to the point.
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#3I've been in this situation many times.
> However, the regular expression module is a C module that doesn’t release the GIL before running.
I would love to know why.
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#4I've been in this situation many times. > However, the regular expression module is a C module that doesn’t release the GIL before running. I would love to know why.
Mostly a guess, but:
- Releasing/acquiring the GIL isn't cheap. So you'd need to know in advance whether it's worth it or not.
- You need the GIL acquired to instantiate the resulting "match data", captures, etc.Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#5The article starts with the famous quote by Jamie Zawinski: Some people, when confronted with a problem, think ‘I know, I’ll use regular expressions.’ Now they have two problems. It then goes on to discuss the perils of regular expressions, when they encounter unanticipated data and run into catastrophic backtracking because of greedy expressions. The article is short and to the point.
More on that quote: https://blog.codinghorror.com/regular-expressions-now-you-ha...
>... there's a bit more to the story than that, as evidenced by Jeffrey Friedl's exhaustive research on the Zawinski quote. Zawinski himself commented on it. Analyzing the full text of Jamie's posts in the original 1997 thread, we find the following:
>Perl's nature encourages the use of regular expressions almost to the exclusion of all other techniques; they are far and away the most "obvious" (at least, to people who don't know any better) way to get from point A to point B.
>The first quote is too glib to be taken seriously. But this, I completely agree with. Here's the point Jamie was trying to make: not that regular expressions are evil, per se, but that overuse of regular expressions is evil.
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#6For another real-world example, see "Details of the Cloudflare outage on July 2, 2019" [1]
Python `re` module now supports possessive quantifiers and atomic grouping (I wrote a blog post here [2]). So, for example, `(a+|\w+)*+:` instead of `(a+|\w+)*:` will avoid such catastrophic behavior.
[1] https://blog.cloudflare.com/details-of-the-cloudflare-outage...
[2] https://learnbyexample.github.io/python-regex-possessive-qua...
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#7I've been in this situation many times. > However, the regular expression module is a C module that doesn’t release the GIL before running. I would love to know why.
Mostly a guess, but: - Releasing/acquiring the GIL isn't cheap. So you'd need to know in advance whether it's worth it or not. - You need the GIL acquired to instantiate the resulting "match data", captures, etc.
Stuff like re.sub frequently calls into Python code as well, so it would seem to be rather hairy to get rid of the GIL for this. It could of course add the usual workarounds of cooperative multitasking, like yielding (releasing the GIL) from time to time, just like the main interpreter loop does (sys.setswitchinterval)
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#8I sometimes think regular expressions being greedy is a bad default.
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#9For another real-world example, see "Details of the Cloudflare outage on July 2, 2019" [1] Python `re` module now supports possessive quantifiers and atomic grouping (I wrote a blog post here [2]). So, for example, `(a+|\w+)*+:` instead of `(a+|\w+)*:` will avoid such catastrophic behavior. [1] https://blog.cloudflare.com/details-of-the-cloudflare-outage... [2] https://learnbyexample.github.io/python-regex-possessive…
While atomic grouping can prevent this from happening again once you've already found the problem, the real solution is just making sure there is a timeout on your web process. That way even if you hit catastrophic backtracking, your servers aren't going to be unavailable unless someone is purposely reDOSing them.
Re: Python, Catastrophic Regular Expressions and the GIL (2013)
#10Why Perl version of regexps returns near-instantly for same regexp ?
I tested few other on regex101.com and none of them ran longer than a millisecond or two