3 ms·
Since one of the mentioned improvements is performance of the builtin regular expression library... for anyone curious, there's a drop-in replacement, re2, that
by btown 9y ago
Since one of the mentioned improvements is performance of the builtin regular expression library... for anyone curious, there's a drop-in replacement, re2, that leverages a Google library to provide linear time guarantees for arbitrarily complex or user-provided regexes. (You lose lookahead assertions, but most use cases for them can just be handled in pre- or post-processing.) It's an incredibly handy tool that lets us confidently use complex regexes in production.
https://pypi.python.org/pypi/re2/ https://pypi.python.org/pypi/re2/
https://github.com/google/re2/wiki/WhyRE2 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!
- tyingq 9y agoGreat observation, but re2 does have tradeoffs to gain that performance. Backreferences, for example: https://github.com/google/re2/issues/101 https://github.com/google/re2/issues/101
- Blackthorn 9y agoBackreferences 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.
- btown 9y agoAbsolutely. 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.
- tyingq 9y agoSure. I just object to the "drop-in replacement" notion. Bad idea or not, many people have existing code dependant on backreferences.