Great observation, but re2 does have tradeoffs to gain that performance. Backreferences, for example: https://github.com/google/re2/issues/101
Absolutely. But for most common uses of backreferences, this is largely mitigated by having a post-regex step that compares capturing groups for equality, which induces overhead also linear in the length of the string. Of course this falls short of true backreference support, but for tasks where we do not expect potential matches to overlap, it gets the job done.
Sure. I just object to the "drop-in replacement" notion. Bad idea or not, many people have existing code dependant on backreferences.
Re:Speed improvements in Python 3.7
by Blackthorn on Tuesday February 13, 2018 @08:44PM
(#16372728)
Backreferences are one of the items that makes regexes non-linear, which defeats the point of being able to trust arbitrary regexes to have good performance.
https://pypi.python.org/pypi/re2/
https://github.com/google/re2/wiki/WhyRE2
> RE2 was designed and implemented with an explicit goal of being able to handle regular expressions from untrusted users without risk. One of its primary guarantees is that the match time is linear in the length of the input string. It was also written with production concerns in mind: the parser, the compiler and the execution engines limit their memory usage by working within a configurable budget – failing gracefully when exhausted – and they avoid stack overflow by eschewing recursion.
Really interesting articles in the second link detailing how this works!