why does adding regex-automata to Cargo.toml increase Regex::new compilation times?

[vvmikheev]

Hello.
I have met some weird problems with the latest 1.10.5 regex release.

After the upgrade I have encountered some serious performance problems with regular expressions compilation.
After hours of debugging I have noticed kinda unexpected behavior - adding regex-automata crate to Cargo.toml file somehow affects the regex performance (makes it several times worse).

MRE:

use std::time::Instant;
use regex::Regex;

fn main() {
    let now = Instant::now();
    for _ in 0..10000 {
        Regex::new("some.regex").unwrap();
    }
    println!("took {}ms", now.elapsed().as_millis());
}

Cargo.toml file:

[package]
name = "testy"
version = "0.1.0"
edition = "2021"

[dependencies]
regex = "1.10.5"
regex-automata = "0.4.7" # <-- remove this guy to see the difference! 

I understand that regex-automata is in the dependencies of regex. Moreover - the only thing that is changed in Cargo.lock file is the list of dependencies of the testy crate. But on my computer this program takes like 3 second without explicit regex-automata and 18 seconds with it.

[BurntSushi]

It happens because regex and regex-automata do not have the same set of default features. regex-automata, in particular, has dfa-build and dfa-search enabled by default. But for regex, those features only get enabled when perf-dfa-full is enabled, and that's specifically not enabled by default for precisely the reason you've run into.

The perf-dfa-full feature causes regex to try and use a fully determinized DFA in some cases. It has pretty harsh limits on when it attempts this to avoid making regex compile times even worse, but even building a small DFA is expensive. However, it can open up new optimization opportunities, which is why it's a thing. But in general, the trade off isn't really worth it. In addition to make regex compile times slower, it also makes Rust compile times take much longer and bloats the binaries quite a bit. (Because bringing in DFA support requires a fair bit of code.)

[vvmikheev]

Thank you for your answer.

However this side-effect seems a little bit unpredictable and improper. E.g. regex-automata might be in the dependencies of some other crate one is trying to use. And just importing this crate to the dependencies list will drastically increase compilation time of regexps one previously had no problem with.

Moreover it is not the case for regex 1.9.5 - this version is not affected by regex-automata in dependencies at all.

[BurntSushi]

However this side-effect seems a little bit unpredictable and improper. E.g. regex-automata might be in the dependencies of some other crate one is trying to use. And just importing this crate to the dependencies list will drastically increase compilation time of regexps one previously had no problem with.

I mean, that's feature unification. And regex-automata is specifically marketed as an expert-level crate in the second sentence of its docs. Which is just me trying to say, "here be dragons, you might shoot yourself in the foot if you aren't careful."

It's not like you can't avoid this. If you bring regex-automata in, you can control which features are enabled. If someone else brings it in and enables more than what you want, then that's just how the cookie crumbles. And that applies for all of regex features. Like what if you didn't want perf-onepass (which is enabled by default) but someone else enabled it in your dependency graph? That will cause a hit to compile times in some cases. Same thing with prefilters and lots of other things.

Don't get me wrong, crate features are a subtle and difficult-to-deal-with aspect of the Rust ecosystem. But this is just one instance of it, and I don't see any real alternative other than changing the default features of regex-automata. And I'm not going to do that because it would cut out a very sizeable and important part of that crate's API surface by default. That isn't a good experience either.

Moreover it is not the case for regex 1.9.5 - this version is not affected by regex-automata in dependencies at all.

This isn't right. It is impacted. But regex 1.9 depends on regex-automata 0.3. So if you have regex-automata 0.4 in your dependencies, then you're bringing in two different copies of regex-automata and the feature selection for regex-automata 0.4 doesn't impact the feature selection for regex-automata 0.3 used by regex 1.9.

[BurntSushi]

Here's another example where crate features can bite you: #982

[vvmikheev]

Okay, thank you so much for your response!
regex-automata is mentioned in the dependencies of some crate that is in the dependencies of the other crate I am using.
Guess there is nothing I can actually do about it (

[BurntSushi]

Of course you can. Treat it like you would any other bug. Go file an issue with that project.