4 ms·

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/comp

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-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 ago
Thanks 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.