Rust's regex-dna benchmark results

http://benchmarksgame.alioth.debian.org/u64/performance.php?test=regexdna

by brson • 11 years ago

9 6 11 years ago

benchmarksgame.alioth.debian.org

brson• 11 years ago

This uses a pure-Rust regex engine[1] by Andrew Gallant.

[1] https://github.com/rust-lang/regex

cmrx64• 11 years ago

Impressive! What was done to pull ahead?

masklinn• 11 years ago

https://github.com/rust-lang/regex/pull/91 I'm guessing, probably more specifically https://github.com/rust-lang/regex/issues/21

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.,

[0] https://github.com/rust-lang/regex/issues/95

burntsushi• 11 years ago

Main ingredients:

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. :-)

towelguy• 11 years ago

Wait, the second fastest is the Javascript one?

eddyb• 11 years ago

I'm not surprised, v8 has a RegExp JIT (irregexp IIRC) which used to be 20x faster than SpiderMonkey's RegExp for simple patterns.

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.

Rust's regex-dna benchmark results

Related Stories