3 ms·
> 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
by ufo 6y ago
> 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?
- nethunters 6y agoNot 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 https://github.com/fancy-regex/fancy-regex
- boulos 6y agoIt 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/dc712da548c7fb433caed56af9a021d964952728/src/regexp/experimental/experimental-compiler.cc https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021... [2] https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021d964952728/src/regexp/experimental/experimental-interpreter.cc https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...
- SloopJon 6y agoThat 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-of-regex-engines/ 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-spidermonkey/ https://hacks.mozilla.org/2020/06/a-new-regexp-engine-in-spi... HN discussion: https://news.ycombinator.com/item?id=23487960 https://news.ycombinator.com/item?id=23487960
- ufo 6y agoThanks for the references. The academic paper about Hyperscan is very interesting: https://www.usenix.org/system/files/nsdi19-wang-xiang.pdf 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.