Do a binary search to find the best wheel lazily?

[wolfv]

Sometimes we end up downloading loads of wheels. I would need to find a test case but I think boto sometimes ends up doing that.

In this case we might be better off by doing a binary search for the best matching version by more intelligently finding the first fitting one.

[notatallshaw]

This should be a good, but very simple, set of requirements to test against:

"urllib3[socks]<3" "boto3<1.28.57"

And testing on rip now, it is much slower than I expected (currently resolves quite fast with pip)

[notatallshaw]

I'm sure you're aware but bear in mind, that you could have Package A versions 1, 2, 3, 4, ..., 99, 100, and only Package A versions 3 and 97 are compatible in your entire dependency graph.

[wolfv]

Do you have a (large) wheel cache with pip? Or did you notice any other "strategy" that pip uses to get a faster resolution speed?

[notatallshaw]

Do you have a (large) wheel cache with pip? Or did you notice any other "strategy" that pip uses to get a faster resolution speed?

No, the cache is unrelated, pip is visting a much smaller number of candidates before solving this requirement. Pip has implemented a few different optimizations that may be helping here, most recently extras are used to constrain the resolution path pypa/pip#12095, backjumping was implemented earlier in the year sarugaku/resolvelib#113, and prefering causes was implemented some time ago pip pypa/pip#10481, but it would take a deep investigation to understand what might be contributing the most.

But I also think that sometimes any given resolution algorithm can just be unlucky and take the wrong path, I created this example from when Pip was slow with these requirements: pypa/pip#12274

Additionally though it does seem rip is backtracking fairly slowly through old versions of boto3 and botocore, when I first ran it it looked like it had to compile a bunch of old sdists and was taking 2 seconds per step. Running it a second time I guess that dependency information is cached(?), it still seems to take about 1/3 of a second per step. But I am not familiar with debugging rust code so this is just observations from looking at the logs.