-Zminimal-versions hangs (takes >2 hours) to resolve dep graph

[matthiaskrgr]

I have a Cargo.toml with around 1000 dependencies from one of the devs. When I run cargo update -Zminimal-versions on the crate, Resolving dependency graph... was not done after more than 2 hours.

cargo 1.46.0-nightly (4f74d9b2a 2020-07-08)

Cargo.toml.txt

[Eh2406]

A real world example of exponential blow up! We have not had a non synthetic example in a long time. This is very exciting. This should be interesting to dig into.

Unfortunately I have been having a deficit of enthusiasm lately. I don't know if I remember what it feels like to be interested in a thing. So I don't want to claim that "I will jump right in". If someone wants to provide the enthusiasm and is willing to stare into the abyss, I will help as I can. Upto and including Zoom pair programing, please let me know.

If I were to get started, I'd try to continue to minimes the example. Is there a case that has 10 deps and takes >2 min. I might try:

• Tern on trace longing, and see what it is working on when it gets "stuck". Try removing deps that are not that.
• Wright a script that builds tomls that are subsets and runs cargo on them. If it goes fast try a different subset, if it goes for more then 2 min use it as the new superset.
• Wright a something that turns the index into a very long long test case, Then use a variation on this minimizer to make it smaller.

[Eh2406]

Running on my computer it takes 20ish minutes without loging or 50ish mins with loging. The speed up may be do to changes to the index, or computer hardware. By scraping the log I was able to sort the dependencies by when cargo's resolver first looks at each dependency. The time in seconds when it is first loaded is recorded in the comments.
Cargo.toml

I have done this analysis many times now. Then realized that I messed something up or got so excited by using this data to minimize the input that I lost this starting point. So this is not a conclusion, it is more a commit I can come back to. The next step is to look at the long pauses. For example solana-metrics was started at 616 sec in and it took until 3399 sec in before it got to working on the next dep. All the remaining deps took less than one sec after that. So I hypothesize that solana-metrics is critically involved and the 20 after it are not relevant.

[Eh2406]

I was able to reproduce with just

self_update = "*" # 433
solana-metrics = "*" # 616

Oddly the full 1000 dep takes ~20 min and this 2 dep version takes over 50 min for me.
(I'd appreciate if others can confirm this behavior.)

My next step would be to look at the direct deps of those two and try to see if it can be reproduced one layer down. Or, something. 🤷

[matthiaskrgr]

I can at least confirm that the 2-dep example also takes way too much time to resolve :P