Rust's regex-dna benchmark results
benchmarksgame.alioth.debian.org
benchmarksgame.alioth.debian.org
Back when I was playing with parsers in JS, the fastest approach to anything string-related was through RegExp, even trivial tasks like "first character is X".
The caveat, of course, was that you would only get that performance under v8.
Nowadays it should be more balanced, but I have no idea how v8 compares to SM anymore.
1. Cache matching engine state. (This is kind of a no-brainer. Previously, new matching state was heap allocated for every execution of the automaton. Fixing this didn't make it go fast, but it made it so it wasn't embarrassing slow.)
2. Do more analysis on regexes to find literal prefixes. Note the plural: if multiple literal prefixes are found, then they are compiled down to an Aho-Corasick DFA.
3. AC gets us most of the way there, but the extra squeeze is to pre-compute all failure transitions and stuff the DFA into a transition matrix. Each byte in the input now corresponds to a single state transition. (Because of the memory overhead, this is only done for small numbers of small prefixes. But this turns out to covers lots of real world use cases---it's not just for the benchmark.)
There were some other optimizations that have less impact, such as a bounded backtracking engine, use of `memchr` and an inline representation of `Option<char>` (this last one is suspect).
Still lots more to do though. :-)
The bench changes are very impressive (beware though, new benches have been added as smaller ones had gotten too fast to be of much interest)
It seems regex! (the one provided in the library, not the one used by TFA's benchmark) has suffered from some performance regressions[0] though many of its usage would benefit from using the dynamic Regex::new instead.,