3 ms·
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 t
by pcwalton 12y 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.
- humanarity 12y agoJIT 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?