cargo -Z minimal-versions update is slow

[d-e-s-o]

Problem

cargo -Z minimal-versions update is super slow on some repositories. Take https://github.com/d-e-s-o/cargo-http-registry, for example, where it takes 9 minutes to downgrade dependencies on my system:

$ time cargo -Z minimal-versions update
________________________________________________________
Executed in  543.37 secs    fish           external
   usr time  542.32 secs    0.00 micros  542.32 secs
   sys time    0.10 secs  890.00 micros    0.10 secs

(cargo 1.71.1-nightly, rustc 1.71.1-nightly (eb26296b5 2023-08-03))

I understand it's a somewhat hard problem, but perhaps there is some speedup possible?

I also seem to have identified a regression about two months ago. The above repository uses the command in CI, and in this CI run the command takes a mere 24s to complete (using rust version 1.72.0-nightly (114fb86ca 2023-06-15)). In the next one this time went up to a whooping 10 minutes (!!) (using rust version 1.72.0-nightly (36fb58e43 2023-06-26)). Now it's possible that GitHub Actions also changed something on their side (meaning I cannot guarantee that the environment is exactly the same; there were no large changes to the repository's dependencies from what I can tell, though), but I'd be surprised if that had such an impact.

Steps

1. git clone https://github.com/d-e-s-o/cargo-http-registry.git
2. cd cargo-http-registry
3. cargo -Z minimal-versions update

Possible Solution(s)

No response

Notes

No response

Version

cargo 1.71.1-nightly
release: 1.71.1-nightly
host: x86_64-unknown-linux-gnu
libgit2: 1.6.4 (sys:0.17.1 vendored)
libcurl: 8.1.2 (sys:0.4.61+curl-8.0.1 system ssl:OpenSSL/3.0.9)
os: Gentoo Linux 2.13 [64-bit]

[Eh2406]

Thank you for reporting the bug. I consider any resolution over a few seconds as a bug. I am sorry for the poor performance. Unfortunately, I have not made time to look into these kinds of problems in a long time.

I can't think of any changes to the resolver that might have caused this regression. But if you would like to bisect nightly versions that would be helpful. Alternatively, because dependency resolution is NP-hard this could be caused by a change in the input. For example a new version of a crate in your dependency graph.

[ehuss]

The critical change was a new release of tokio which added a dependency. Here is a reproduction:

1. Clone https://github.com/rust-lang/crates.io-index-archive
2. Check out c7ecf2c1ed8e9fbd0a2ed0d76fc623eed693200e
3. Set up a project with:

# .cargo/config.toml

[source.crates-io]
replace-with = "old-crates"

[source.old-crates]
registry = 'file:///path/to/crates.io-index-archive'

[net]
git-fetch-with-cli = true

# Cargo.toml

[package]
name = "foo"
version = "0.0.0"

[dependencies]
git2 = {version = "0.17"}
tokio = {version = "1.0", default-features = false, features = ["rt"]}
warp = {version = "0.3", default-features = false}

[dev-dependencies]
tempfile = {version = "3.1"}
tokio = {version = "1.0", default-features = false, features = ["macros", "rt"]}
_serde_urlencoded_unused = {package = "serde_urlencoded", version = "0.7.1"}

4. cargo update -Z minimal-versions
5. Notice that the previous commit, 7c09fc05c87085bf41f1a3650e10f200ad222f93 runs much faster (73s versus 3s on my system).

---

@d-e-s-o, I would recommend not using -Z minimal-versions. It is likely that it is going to be removed without being stabilized. I recommend using -Z direct-minimal-versions instead.

[d-e-s-o]

Thanks for investigating this slowdown and for the recommendation, @ehuss! I will play around with -Z direct-minimal-versions and see if it works for my use case. Feel free to close this issue unless you want to keep it around as a generic "performance could be better" issue for minimal versions dependency resolution.