Regexes appear to be significantly slower than re2 in some cases

[brson]

My understanding is that we believe them to be competitive, but two benchmarks I've seen were not really in the ballpark. The easiest one to test is the shootout's regexdna, which you can see from the upstream shootout is drastically slower than the re2-based C++ implementation.

cc @BurntSushi

[BurntSushi]

Indeed! RE2's C++ implementation is extremely sophisticated. It has a DFA for very quickly finding matches and the location of an overall match. A full NFA simulation is used when you need submatches (and this is made more performant, I think, by running a DFA first to limit the range of text searched by the NFA). This includes doing wonderfully crazy things like reversing the regex itself. Also, I believe RE2/C++ uses parallelism over DFA states, but I'm not entirely sure how that works.

The Rust implementation uses a full NFA simulation. Full stop.

The regex! macro basically encodes that full NFA simulation, but without heap allocation for keeping track of captures (since it knows the total number of captures at compile time). There are other optimizations, but I suspect the elimination of most heap allocation is a big one.

With that said, the main NFA simulation (not the native code specialization) should be roughly on par with Go's regexp package. (I say this because Go's regexp package only has a full NFA simulation and lacks a DFA.) However, Go's regexp package does have a special "one pass" NFA optimization that makes certain regexes faster. There are probably other optimizations in Go's implementation that I'm missing or have forgotten about.

RE2 for Go and C++ were written by the same person (Russ Cox). The sophistication of Rust's regex crate is much more closely aligned with Go's regexp package than it is C++'s RE2 library.

So yes, Rust's regexes are going to be slower than RE2/C++'s regexes until its implementation becomes more sophisticated.

(I've always tried to be very careful to say "RE2/Go" or "RE2/C++", but I'm sure that got lost in the kerfuffle. RE2 is more readily identified with the C++ library, and I don't think I've ever expected my implementation to be on par with it. RE2/Go? Yeah. On par, or close to it. When you add native regexes to the mix, Rust will outperform Go's implementation I think.)

[brson]

Thanks for the explanation, @BurntSushi.

[pcwalton]

IIRC those regexes are pretty simple. Maybe we can add some hacks to make them (and only them) fast?

[brson]

@BurntSushi do you have a sense of the scope of a project to add the advanced optimizations from RE2/C++? For example, could a student do it in a month?

[BurntSushi]

@brson I think it's possible. Another idea might be to start them with the "one pass" NFA optimization. Russ Cox briefly describes it here: http://swtch.com/~rsc/regexp/regexp3.html (Do a CTRL-F for one-pass). That could get them warmed up with the existing implementation before they start on the DFA stuff. But that's just an idea. (The one-pass optimization has two steps: analysis of the regex to determine whether it is a one-pass regex or not and then the actual optimization in the NFA simulation.)

Also, in general, Russ's regexp articles are required reading: http://swtch.com/~rsc/regexp/ --- Rust's regex implementation is based on them.

[steveklabnik]

I meant to move this to the regex crate :(

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/regex#24