Hacker News Reader

Comment by ufo | Hacker News Reader

> For now it remains experimental because Irregexp is orders of magnitude faster than the new engine on most common patterns

I'm sure that an important reason for this is that thousands of man-hours have been invested optimizing Irregexp. However, is that the only explanation?

In my experience, while an NFA-based engine has better asymptotic complexity, a backtracking-based engine can be hard to beat for patterns that don't do much backtracking. In a textbook NFA automaton, the time spent maintaining a set of parallel states may be "wasted" if it turns out that the first state in the list is already going to succeed anyway.

Regex experts of Hacker News, do you know if there are any engines and/or algorithms that try to get the best of both worlds? Fast execution for patterns that don't need much backtracking, but avoiding exponential run time in the worst case?

View on HN

It looks like the current implementation [1] just always compiles to Bytecode which is then interpreted [2]. The usual one is more like PCRE JIT in that it defaults to using a macro assembler to generate machine code and execute it.

So I wouldn't draw too much from the current performance difference, it's primarily "simple interpreter vs machine code". IIUC, the plan from that blog post is to default to the backtracking mode (depth first) for a small-ish number of backtracks at which point you switch strategies to get that best of both worlds-ish behavior.

[1] https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...

[2] https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...

That caught my eye too. I looked for benchmarks of re2, but couldn't find anything more recent than this:

https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...

burntsushi criticized it at the time as being unfair to DFA engines.

Incidentally, I also discovered that Firefox now uses Chrome's Irregexp engine:

https://hacks.mozilla.org/2020/06/a-new-regexp-engine-in-spi...

HN discussion:

https://news.ycombinator.com/item?id=23487960

Thanks for the references. The academic paper about Hyperscan is very interesting: https://www.usenix.org/system/files/nsdi19-wang-xiang.pdf

My impression is that they break the regex into components and use choose different algorithms for each component:

1. String search (for fixed strings)

2. DFA (if the number of states is small enough)

3. NFA (if the numer of states is too large)

But one important detail is that Hyperscan doesn't do capture groups and IIRC, capture groups are hard to do using a DFA representation. So going back to my original question, I now wonder if there are other ways to run an NFA (for regexes with capture groups) other than the traditional method of updating all the states in parallel, one character at a time.

Not an expert but fancy regex is a Rust library that uses a hybrid approach to detect whether a sub expression contains backtracking and delegates to the appropriate engine.

https://github.com/fancy-regex/fancy-regex

Reply on news.ycombinator.com