Regular Expression Matching Can Be Simple and Fast (2007) | Hacker News Reader

Regular Expression Matching Can Be Simple and Fast (2007)

swtch.com

31 pointshumanarity16 comments

…if your regexes are, you know, regular. Which Perl-style regular expressions most definitely are not. So it's not a matter of just implementing the regexes you know faster, but limiting them to a subset of features first.

This is a perfectly valid thing to do, but it is changing the power of regexes significantly. I feel the article makes this fact easy to overlook—I certainly did until I took a class on automata.

But yes, presumably Perl could use an NFA-based algorithm if given a regex that is actually regular. One of my professors attributed the fact that it doesn't to old patent issues, but I have not been able to find a good source for that. It's also possible that it's just a case of worse is better: backtracking is fast enough 99% of the time, and if performance really matters, perhaps you shouldn't be using regexes anyhow.

Automatically downgrade to a more general implementation if those features are used. Add a flag to assert that a regex is actually regular and should use the fast implementation.

I don't know about Perl proper, but PCRE does have an automaton option (which the docs call a DFA but, if I remember correctly, is actually an NFA).

In practice, the vast majority of production regexen don't require backreferences or generalized assertions, so automata are an attractive option. This is particularly true for security applications (e.g. firewalls/NIDS) and public-facing services like Google Code Search. I wouldn't be surprised if people were attacking Snort boxes via PCRE, for example.

You can add some irregularity to the NFA construction. It's no longer "regular" but you can decorate it with some things like lookbacks, remembering multiple matches and more, and still get the benefit of the NFA. I remember adding a few such features a couple years ago.

To be honest, I've never been much of a fan of this article, because it neglects the fastest way to implement regexes in practice: use a fast JIT to emit code that performs recursive backtracking. The Thompson NFA is a better algorithm for pathological regexes that people don't frequently write (e.g. "(a?)﹡a﹡)"), but the constant factors are much worse for common cases.

The Thompson NFA has its place as a fallback to avoid exponential blowup on pathological regexes, but if I were implementing a performance-critical regex engine, I would start with a JIT for the recursive backtracking approach, because in practice constant factors dominate over algorithmic worst-time bounds, and only add the Thompson NFA later.

JIT sounds interesting. Do you have a good ref?

I don't feel the constant factors are large on Thompson. It's essentially linear to construct IIRC, and matching next char is then proportional to the number of current States which are valid. Which is bounded by the vertexes in the NFA which will mostly be less than DFA.

I don't see how you can get more efficient than that, because you're just keeping track of all the matching states which would seem to be the minimum required. I'm really keen to learn an even better way.

The proposal is a workable heuristic ( use the practically working algorithm rather than the one with a theoretical low bound which is costly in practice ), and people do well to heed it in many places, however I don't believe it applies here because Thompson is great in practice.

You sound like you know a lot about this, what am I missing?

And Ken Thompson's original 1968 paper,

http://www.fing.edu.uy/inco/cursos/intropln/material/p419-th...

Any good web-based regex tools that you use daily?

My personal favorite is RegExr:

http://www.regexr.com/

https://www.debuggex.com/

I haven't exactly searched far and wide, but this one is pretty good.

my go to one is http://refiddle.com/

I've used http://rubular.com/ but I won't say I've done any extensive research.

I'm a fan of http://regex101.com/

And when was the last time anyone used grouping in a regex!

As mentioned in the article, grouping can be done with Thompson-style algorithms. Backreferencing groups can not.* See the Plan9 regex library.

*Probably. Depends if P=NP or not.

I use groups, (look forward, and lookbehind) all the time, now that I have been comfortable with them, they are great in that I can write simpler regexps, or use fewer patterns. And I use perl for one liners, which is as far as I can go comfortably with perl. Thing is, I use regexps most for one-liners, and with perl, and grouping, it is simpler for me, than using sed for instance, where I then would have to think, (and test), substantially more, or filter the output through yet anoter sed expression. So grouping works for me. :) It is of course slower, but so far, the most critical time for me, has been the speed with which I can make a solution that works.

Reply on news.ycombinator.com