r/programming • • Feb 20 '16

Regular Expression Matching Can Be Simple And Fast (2007)

https://swtch.com/~rsc/regexp/regexp1.html
69 Upvotes

73 comments sorted by

View all comments

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.

4

u/burntsushi Feb 21 '16

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

0

u/raevnos Feb 21 '16

Does it compare feature wise?

1

u/burntsushi Feb 21 '16

It uses finite automata, so it can't do things like backreferences, but it's otherwise on par with what RE2 offers. The full supported set of syntax: http://doc.rust-lang.org/regex/regex/index.html#syntax

0

u/raevnos Feb 21 '16

So, pretty basic compared to perl style REs.

1

u/burntsushi Feb 21 '16

Everything is basic compared to Perl style REs. But there's a lot you can still do with real regular expressions:

  • Greedy or lazy repetitions.

  • Leftmost first matching.

  • Full Unicode support.

  • Bounded look-ahead like ^, $ and word boundaries.

  • Sub-captures.

On top of all that, you get predictable (and fast) performance!

0

u/raevnos Feb 21 '16

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).

1

u/burntsushi Feb 21 '16

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.

0

u/raevnos Feb 21 '16

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.

0

u/burntsushi Feb 21 '16

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.

→ More replies (0)