Resolver spends too much time calculating "weights" to parents #10557
Labels
C: dependency resolution
About choosing which dependencies to install
Comments
Rizhiy
added
S: needs triage
|
When I installed the offending package manually with the correct version, I got an error that it's version is incompatible with another specified package. After resolving the conflict, the installation succeeds properly. So I guess the problem is that there is a conflict in Also, pip starts checking versions for packages which are not even part of the conflict which is bad. |
|
I think I got the rough behaviour:
I will try to make a reproducible example later. |
DiddiLeija
added
C: dependency resolution
|
There's no way to reproduce without your requirements.txt. |
|
We have (probably) the same problem when installing Plone with pip. To reproduce (using an alpha version here) do the following. With an older The first pip command needs to install a lot of packages, so it will take a while. The last command as you can see takes maybe two or three seconds. Now retry with the standard resolver. Remember that the package is already installed, all dependencies were pinned in the constraints, I can start python and Yes, that is four minutes, instead of a few seconds. I had a look with See also a thread on community.plone.org. One problem we found there, were cyclic dependencies, but we solved them all in the constraints used in my example above. |
|
For good measure, I thought I would make pip more verbose, but there does not seem to be anything interesting: I checked the directories a couple of times during the process, but there was nothing in them. |
|
Closing since OP did not provide a reproduction, and the available reproduction has been fixed in #10239. |
uranusjr
added
resolution: duplicate
|
@uranusjr Except it clearly hasn't, as indicated by example in @mauritsvanrees response? Here is the example: Tested today with P.S. Surely, closing the issue after 2 days just because I couldn't provide an example is ridiculous. |
|
Likely I linked to an incorrect PR then. The bottom line is I couldn't reproduce on main. |
|
I have checked that all the installed packages are specified in |
Just checked on main (21.3.dev0), still having problem: |
|
Also, if you run the installation command with |
|
If that's where the resolver hangs, your issue is not about constraints, since when the resolver reaches that point, it should have already finished version resolution, including constraints. |
uranusjr
added
state: needs reproducer
uranusjr
changed the title
|
Using #10481 and running: The relevant log messages are: And that seems to tell me that the resolution is pretty quick with the fixes in #10481. |
|
Note that this involved downloads as well. Running again with
|
|
From the report, resolution time isn't the actual issue though, it's after the resolution where we sort packages for installation. |
|
Indeed. Here's the graph we're trying to do that with: |
|
I think I have made a reproducible example: https://github.com/Rizhiy/pip-conflicts While making it, I realised that the problem is, most likely, that pip conflict resolution is just very slow/stupid and not that it is incorrect. |
As someone who had that gut feeling many months ago and have been trying to come up with better approaches ever since I can tell you it's not an easy problem to solve. Finding a solution on a dependency graph is basically a brute force problem if you don't make any assumptions about said dependency graph. Hopefully though #10481 will fix the time it takes your requirements to resolve. Otherwise I have some more ideas on how to improve resolution time further. |
|
It's not the dependency resolution that is slow here -- I've demonstrated that above. As @uranusjr noted, the problem in this case is the logic that's computing the "order to install packages" ( |
I see, I thought OP had changed their mind on what the issue was, thanks for the correction. |
|
@pradyunsg Did you look at the example I provided? The behaviour seems different from the @mauritsvanrees case. Even if resolver is not at fault here, there seems to be erroneous logging since I'm getting messages like: P.S. I checked behaviour using #10481 and the problem is still there. |
|
No, I haven't played with your example repository yet. There's two separate things in this issue, as far as I'm concerned:
Based on a quick look, it looks like your example repository demonstrates the first issue, where the resolver is going to try too hard to get a solution; especially if one doesn't exist. That's already got a bunch of other issues to track it -- #9517 is one that is handy right now.
For this example, #10481 solves the stupid backtracking issue; although the computation of what order to install packages in still takes a long time; likely due to the dense nature of the dependency graph.
I'm guessing this is a typo? |
|
Yes, I meant #10481, fixed original. |
|
I added a bit of debugging code in the I tried this with So for 80 packages, the Then try So the As suspected, it does not scale very well. :-) Maybe iterating over |
|
Yup yup. This was written for correctness, rather than speed, so that looks about right to me. It's basically exploring all paths on the graph, and remembering the length of the longest one. It makes sense to me that this would be horrendous for a dense graph like that. :) |
|
This much simpler version of In my case, Hypothetically, if ten packages depend on So:
|
|
I guess I'm missing something here. Why does installation order matter at all? Unless a package has |
|
A lot of packages out there depend on installation ordering to work correctly, e.g. some namespace packages overwrite files already installed by another package, and produce incorrect end results if we swap the order. |
|
Somehow I have a feeling that while it might be a lot in absolute terms, it is a very small as a percentage of all packages. |
|
In the meantime, another question: why is |
|
First of all, the dependency graph is not guaranteed to be acyclic 🙂 The resolver indeed constructed a graph, so feel free to contribute an implementation that reduces node visits if you have algorithmics insights on this . |
|
The discussion in #8127 is relevant, in case someone wants to tackle this. There's existing tests for this method's logic here: If this were guarenteed to be an DAG, then we wouldn't be having this conversation. :)
Yea, we're not measuring in-degree vs out-degree here. This implementation will fail all the tests for what From #8127:
|
|
Okay, I have a solution that works for me, and passes the |
|
Done: #10574 |
pradyunsg
pushed a commit
that referenced
this issue
Nov 20, 2021
Fixes #10557 where the resolver spends too much time calculating the weights. Also, do not let `get_installation_order` calculate these weights at all when there is nothing left to install. Co-authored-by: Tzu-ping Chung <[email protected]>
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
Description
When running something like
pip install -c requirements.txt <package_name>sometimes pip starts checking unnecessary versions.I know that version checking is unnecessary because
requirements.txtcontains all the packages with exact versions.Everything works as expected with legacy resolver.
Expected behaviour
Since all of the versions are already specified, just get them.
pip version
21.2.4
Python version
3.8.8
OS
Ubuntu
How to Reproduce
Unfortunately, I can't provide a reproducible example since it only happens with a package on internal pip index.
The offending package does have the version specified in requirements.txt and a different version is installed when the command is run.
Output
It says something like:
But I already have
kiwisolver==1.3.1in myrequirements.txt.Code of Conduct
The text was updated successfully, but these errors were encountered: