Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Python, Catastrophic Regular Expressions and the GIL (2013)

benfrederickson.com

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#21

Post by asah »

formerly_proven wrote: post #7
byroot wrote: post #4

Earlier quoted context omitted.

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)

assuming it's legal to do so, GIL release seems like a reasonable flag to add to possibly-expensive functions like re.()

... or even better, have re. track its own performance and release the GIL if it forecasts that it statistically-might use a lot more computation... a trivial strawman algorithm: if len(input) > MAX then release GIL first.

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#22

Post by photochemsyn »

The simple example is fixable by anchoring the inner greedy expression, i.e.

regex = re.compile(r'(^a+)+b')

Perhaps the more general problem was that "The regular expression that was causing the issue here was rather long and convoluted".

A good rule seems to be never have long and convoluted regexs, instead have a pipeline of simple-to-understand regexes that can be independently debugged (I don't know if this could cause performance slowdowns however).

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#23

Post by kh1 »

asicsp wrote: post #6

For 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…

The gif showing the backtracking is cool. I wonder if there's similar tool for python.

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#25

Post by cmacleod4 »

Need I point out that one can avoid both the issues highlighted here by just using Tcl?

Regexps in Tcl use a non-backtracking implementation which handles such cases with minimal slowdown, e.g. the example shown with 16 and 32-character inputs:

    (dep) 7 % timerate {regexp (a+)+b aaaaaaaaaaaaaaaa}
    0.353737 µs/# 2826961 # 2826961 #/sec 1000.000 net-ms
    (dep) 8 % timerate {regexp (a+)+b aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
    0.412612 µs/# 2423587 # 2423587 #/sec 1000.000 net-ms
One discussion of this can be found at https://comp.lang.tcl.narkive.com/XPVME8zS/tcl-regexp-perfor... .

Tcl's threading implementation has no GIL, which not only avoids the type of lock-up described here, but also allows performance to scale to use all cores of your machine, see: https://www.hammerdb.com/blog/uncategorized/why-tcl-is-700-f... .

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#26

Post by klyrs »

photochemsyn wrote: post #22

The simple example is fixable by anchoring the inner greedy expression, i.e. regex = re.compile(r'(^a+)+b') Perhaps the more general problem was that " The regular expression that was causing the issue here was rather long and convoluted ". A good rule seems to be never have long and convoluted regexs, instead have a pipeline of simple-to-understand regexes that can be independently debugged (I don't know if this cou…

Why would you leave the second + intact, when the ^ prevents it from matching 2 or more times? And what if you want to match the substring in "Faaaaabulous"?

Did you see the even simpler fix in TFA that doesn't break mid-string matches?

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#28

Post by photochemsyn »

klyrs wrote: post #26
photochemsyn wrote: post #22

The simple example is fixable by anchoring the inner greedy expression, i.e. regex = re.compile(r'(^a+)+b') Perhaps the more general problem was that " The regular expression that was causing the issue here was rather long and convoluted ". A good rule seems to be never have long and convoluted regexs, instead have a pipeline of simple-to-understand regexes that can be independently debugged (I don't know if this cou…

Why would you leave the second + intact, when the ^ prevents it from matching 2 or more times? And what if you want to match the substring in "Faaaaabulous"? Did you see the even simpler fix in TFA that doesn't break mid-string matches?

Ah right I do now.

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#29

Post by BerislavLopac »

The real problem is using multithreading in CPython for any set of tasks that has a nonzero chance to block one of the tasks due to a CPU-bound issue. The rule of thumb here - and I learned that the hard way - is to use async/await for anything I/O bound, and multiprocessing for anything CPU-bound.

Re: Python, Catastrophic Regular Expressions and the GIL (2013)

#30

Post by brenns10 »

It really feels like they buried the lede here, as almost all discussions about catastrophic backtracking seem to do. Here's the second-to-last paragraph:

> Alternatively you could switch to a regular expression engine that doesn’t exhibit this kind of behaviour. RE2 is an excellent library that uses a finite automata approach to avoid this type of catastrophic backtracking. Using this library on the same 32 character input reduces the running time from 12 minutes to basically instant. The downside being that RE2 doesn’t support all the functionality of the builtin re package.

Perl Compatible Regular Expressions (the flavor used by most engines, including Python's) _require_ this exponential worst-case behavior (using an implementation called backtracking). But the theory behind regex does not require this, and if you eliminate just a couple (infrequently used) features of PCRE, you can have a regex engine that runs in linear time (with respect to the size of the input string). See [2], this is by the authors of RE2. The features which are incompatible with this sort of implementation are:

1. Lookahead assertions. 2. Backreferences to matched groups.

If you don't know what these are, or you rarely ever use them, then you really have no business using this kind of regex engine. (And if you are using them, then I'd argue you're shoving a bit too much logic into a regex, but that's beside the point). Nonetheless, every popular programming language (except Go[1]) has included an exponential backtracking regex implementation in their standard library, and exposed the entire industry to this stupidity, all for a few backreferences and lookahead assertions.

What's especially crazy is this: it's easy for a regex engine to detect the use of these constructs, because it has to parse the regex anyway! So it's feasible for the engine to optimistically try to use an efficient implementation, and only fall back to using a backtracking implementation when you're actually using these features. This is what the Python re2 module[3] does, it uses RE2 by default and supports falling back to the backtracking implementation if necessary.

Instead, we're stuck reading the same postmortem every few years describing how "catastrophic backtracking" ruined another company/person's day, when the problem has been solved for decades, and language/library creators have just failed to include that solution.

[1]: Rob Pike invented, or at least popularized, the algorithm used by RE2. He was also involved in the creation of Go, as was Russ Cox[2]. [2]: https://swtch.com/~rsc/regexp/ [3]: https://pypi.org/project/re2/

Post reply on HN