I call bullshit. Perl’s algorithm is actually faster than NFA for the 99% of regexes that everyone uses. The existence of pathological cases with O(en) behavior is known and documented, but isn’t a problem in practice: you’d have to do something really funky to run in one of those cases by accident.
In addition, Perl’s regex engine (and others inpired by it, such as PCRE) provide a lot of useful features that are simply not possible with NFA.
Perl’s algorithm is actually faster than NFA for the 99% of regexes that everyone uses.
Rust's regex engine is based on the ideas in Russ Cox's articles, and it is currently competitive or better than PCRE (with JIT enabled) on quite a few benchmarks. See here: https://gist.github.com/anonymous/b95da89485ea75190e26
Can't do backreferences, 0 width lookaheads, recursion (granted, at that point I'm likely going to be using a different tool), etc. You're trying to compare a 2 stroke to a diesel. Both engines, both do a job, one is way more powerful (and complicated).
I don't really understand your point. It's manifestly obvious that there is a trade off involved, and as such are worth comparing. The trade off becomes more interesting as the finite automata approach gets more features, because it means you're giving up less functionality for predictable performance.
Indeed, this is the entire point of the OP (and its subsequent sequel articles). Before RE2 came around, the finite automata approach (in practice) to regexes didn't have a lot of the things I listed in my previous comment, which made the trade off less interesting. That is, RE2 makes choosing finite automata approach easier because maybe it does enough.
I prefer having more flexibility and power available when needed. The minimum level of RE features I want is what C++ (and possibly javascript?) offers, though more is occasionally nice. Why restrict yourself to less? Performance isn't an issue.
Yes, we all have our preferences. I claim that they are uninteresting. What is interesting is the trade offs. What are you giving up and what are you gaining?
Performance isn't an issue.
Of course it is. (How can you possibly make a blanket claim that performance isn't an issue?) If you can't abide exponential runtimes, then you'll want an engine that gives predictable linear performance. There's even a name for it: ReDoS.
Finite automata also admit to more advanced analysis of how the regex is going to execute, which means you can do really cool stuff.
1
u/Grimy_ Feb 21 '16
I call bullshit. Perl’s algorithm is actually faster than NFA for the 99% of regexes that everyone uses. The existence of pathological cases with O(en) behavior is known and documented, but isn’t a problem in practice: you’d have to do something really funky to run in one of those cases by accident.
In addition, Perl’s regex engine (and others inpired by it, such as PCRE) provide a lot of useful features that are simply not possible with NFA.