Hacker News Reader

In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.

View on HN

> Obviously if I were accepting regular expressions from random people, I'd use RE2.

And if you're using Perl, it's not hard to do so[1]. Pluggable regex engines FTW. :)

1: https://metacpan.org/pod/re::engine::RE2

re2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.

How does the DFA engine match anything without looking at the whole input?

I think s/he meant to say O(nm) vs O(m), n being the number of branches in the regex and m being the length of the input.

Reply on news.ycombinator.com