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.

[lambdaq]

the metadata in PyPI is inside the wheel files and it's expensive to download a wheel file only to retrieve metadata

I am new to this but has anyone tried to parse wheels without full download?

1. assume wheels are in ZIP format
2. there's metadata at the end of ZIP file.
3. use Http Range requests to get the metadata inside the wheel

This could save lots of network time?

Also I noticed the pip library has a total size of 13MB. If ppl find this acceptable, this should also be enough to cache every deps metadata from pypi locally 🤣

[wolfv]

Yes, that's how we do it! :)