7 ms·

New Pip resolver takes a long time to complete

66 points by josmek 6y ago

mst 6y ago
I built a resolver like this for perl/CPAN at once point. Then realised it would have this problem a few days before I'd planned to release, and didn't ship it. I am feeling very lucky right now.
rdlfo 6y ago
Perhaps something like mamba [1] could speed up the resolver. That is if the resolver is actually achieving anything at all. [1] https://github.com/mamba-org/mamba https://github.com/mamba-org/mamba
- eganjs 6y ago
  My understanding is mamba, like conda, just call pip. So it likely wouldn't make a difference. The pip section in a env file is just a list of arguments passed through to the pip install command. Prior to pip 20.3 we had to add `--use-feature=2020-resolver` to get an install that resolved for our teams that used mamba.
  - Iwan-Zotow 6y ago
    No, conda is not calling pip
    - eganjs 6y ago
      You're wrong, it does. Conda installs conda packages and conda uses pip to install pip packages. However a pip package can be converted to a conda package, and then in that case the dependency will be installed by conda and not pip.
      - martin_renou 6y ago
        You're wrong, it does not. You can install a pip package in a conda env. But this is actually not recommended. When using `mamba install` or `conda install`, pip is not involved at all.
        uranusjr 6y ago
        You’re correct, Conda does not call pip when it installs packages. But pip does have a subtle involvement here: Many Python packages available to Conda are packaged based on installations made by pip, and (IMO lazily and incorrectly) inherits a lot of pip characteristics. This makes the packages “appear” to be installed by pip, and sometimes induce interpolation inconsistencies.
  - martin_renou 6y ago
    Mamba and conda do not call pip. You can install a pip package inside a conda environment. But when running `mamba install` or `conda install`, pip is not involved at all.
    - rdlfo 6y ago
      I got a bit confused by the statements in the thread. If the issue is downloading wheels to check dependencies, mamba should be a better alternative, as not only it is downloading packages in parallel but it uses a different dependency solver.
riedel 6y ago
Maybe by fixing the solver they can finally prove P=NP ;)
- oehtXRwMkIs 6y ago
  I think that will be proven before python fixes their package management.
  - noitpmeder 6y ago
    At least they are trying to fix it, vs other languages where there are literally no paths forward. IMO python has one of the more mature packaging ecosystems out there at this point. It is so incredibly easy.
    - FloatArtifact 6y ago
      Distribution still is a pain unless you're going through pip.
      - pydry 6y ago
        who doesn't use pip?
    - nawgz 6y ago
      >IMO Python has one of the more mature packaging ecosystems out there Ouch, what languages are you using where this is true? For example, JS / NPM / Yarn are absolutely blowing pip out of the water. I guess I can imagine Java or C++ users having your perspective though
      - uranusjr 6y ago
        Every language community has its own priorities, and the package manager grows different traits to meet community needs. Those traits would come at a price, and different comunnities (and their package managers) would make different tradeoffs due to their different priorities. Python has a very involved history dealing with platform-native stuff, and provide a lot of convinience aroud specifying, providing, and obtaining those native stuff. But the complexity would leak into platform-agnostic packages, and gives an impression that packaging is worse when “all you want” is some .py scripts. JavaScript provides a much better interface for packaging and installation, but the expense is that native modules are much more difficult to package, and tend to fail spectacularly on installation when something does not work out. Many more things are like this from each side. There are a lot of smart people working on these things in each ecosystem, and when you think some package manager is far surperior over others in every way, you are more than often simply wrong. Or saying it the other way (and paraphrasing a commenter from another thread), the only package manager you think is good is from the ecosystem you are not deeply familiar with.
sjburt 6y ago
They need to store the version requirements metadata outside the packages. Having to download the entire wheel just to see whether it is compatible is ridiculous. This could all be computed by downloading an index file, then performing the resolution. They made a half-assed attempt when pypa/pip added the "data-requires-python" tag, but that covers python interpreter version only, it needed to have been done for all dependencies. What's especially irksome is that Debian and RPM both solved this 20+ years ago and python has refused to learn any lessons.
- woodruffw 6y ago
  This is the subject of discussion in this Warehouse (the PyPI backend) issue[1]. The TL;DR is that it probably requires a PEP. FD: I've been working on adjacent features in PyPI. [1]: https://github.com/pypa/warehouse/issues/8254 https://github.com/pypa/warehouse/issues/8254
- deleted 6y ago
  [deleted]
- cozzyd 6y ago
  yeah, why not just use libsolv or something?
- jrochkind1 6y ago
  rubygems went through several iterations of API to try to deal with this, including yes, starting with a dependency-info-only API. I wish different language/platform communities were better at learning from each other (and this does go in all directions). In the field of software these days, we don't do much learning from prior art. It's just too hard to keep up with it all. Heck, I recall this happening with rubygems -- the introductio of the dependencies API to efficiently get the minimum data needing for resolving dependencies before downloading actual packages, and then several iterations on it -- and I can't find any actual documentary evidence of it to share right now. I don't know how anyone WOULD use it as prior art; the source code for a fairly complex project in a language you aren't familiar with isn't going to work, even if you knew to go look for it, which why would you.
- 6y ago
dang 6y ago
Recent and related: https://news.ycombinator.com/item?id=25253236 https://news.ycombinator.com/item?id=25253236
cbaines 6y ago
I used to think package managers and dependency resolvers were inseperable, I even did a little bit of work on the APT resolver. Since using GNU Guix though, I'm so glad it doesn't have a dependency resolver as part of building or installing packages! It's so much better for it, no slow or unpredictable resolving, you know what it's going to do. I think this is one reason why I've never used pip for managing Python software, I've only ever used Debian, and then Guix.
- yjftsjthsd-h 6y ago
  Wait, how does guix avoid a dependency resolver? It still has dependencies for packages... are they just hardcoding exact dependencies (including versions) and relying on the "can install multiple versions of a package" property to make that work? That seems inefficient, though I guess maybe they need that for the "this hash means this exact binary" outcome?
  - cbaines 6y ago
    Guix has packages, and packages have inputs (like dependencies), and you're right in that normally package definitions specify the exact dependencies it the code (they're hardcoded). Guix package definitions are truely code though, so if you want to generate packages on the fly by using a dependency resolver, you can totally write some code to make that happen. With respect to inefficiency, what do you mean? It's quite time efficient when building and installing to not have to attempt to resolve dependencies.
    - jrochkind1 6y ago
      If they are specifying exact hard-coded dependency versions... if a X -> Y -> A, and B -> A, and M -> N -> A... and a security patch is released for A, then X, Y, B, M and N all need new releases to specify new exact dependencies, in order to use the new A'? It's disastrous for security patches, only highly inconvenient for things like performance improvement releases. But this is why we have dependency resolving, right? What am I missing?
looperhacks 6y ago
Did I get it right, the problem is basically that the dependency info is turing complete and decided "at installtime", thus the dependency graph cannot be computed without installing many versions of all dependencies? (I do not use python, so I don't know much about how pip works) Are there other languages that have dependencies decided at installtime?
- vmchale 6y ago
  > dependency info is turing complete It's NP-complete in general I think, definitely the case in Haskell-land. I think OCaml sets an explicit timeout for dependency resolution? > the dependency graph cannot be computed without installing many versions of all dependencies? Does PyPi not have an index or something? (with statically known package bounds?)
- cipherboy 6y ago
  Most distros have install time dependency resolution, such as yum/dnf using libsolv. Repos are a collection of packages alongside metadata tables containing package versions and their dependencies. The tables get cached locally and are used to resolve dependencies prior to downloading any actual RPMs.
- JackC 6y ago
  Right, for packages distributed as source (vs. having prebuild "binary wheels") the dependencies are specified in python code. Example from one comment on the bug: setup( install_requires=[random.choice(["urllib3", "requests"])] ) This example wouldn't make any sense, but you could imagine installing different dependencies for x86 CPUs or something via a runtime check, and there are lots of packages that use this for checking python versions even though there's now a static way to do that. So that leads to this situation, from another comment: "And as an example, [the botocore package, which has releases nearly daily] depends on python-dateutil>=2.1,<3.0.0. So if [your dependency constraints are] to install python-dateutil 3.0.0 and botocore, pip will have to backtrack through every release of botocore before it can be sure that there isn't one that works with dateutil 3.0.0. ... And worse still, if an ancient version of botocore does have an unconstrained dependency on python-dateutil, we could end up installing it with dateutil 3.0.0, and have a system that, while technically consistent, doesn't actually work." Sounds like there's a long term plan that could fix this situation. Binary wheels already have the needed metadata in a way that could be exposed by PyPI via a fast "fetch dependency constraints for all versions" API, but isn't yet. And for source dists there's a very new plan ( https://www.python.org/dev/peps/pep-0643/ https://www.python.org/dev/peps/pep-0643/ ) to let them indicate that they don't modify install_requires at runtime, so their deps could also be exposed via API, but the ecosystem will have to catch up with that. I dunno what pip does in the meantime, though! (I'm a python dev but haven't followed this beyond skimming the bug, so I hope I'm getting this right.)
qz2 6y ago
It'll still be faster than NuGet. I had to wait 12 minutes (!) to install a package the other day while it resolved dependencies on a single package.

66 points by josmek 6y ago

mst 6y ago

I built a resolver like this for perl/CPAN at once point. Then realised it would have this problem a few days before I'd planned to release, and didn't ship it. I am feeling very lucky right now.

rdlfo 6y ago

Perhaps something like mamba [1] could speed up the resolver. That is if the resolver is actually achieving anything at all. [1] https://github.com/mamba-org/mamba https://github.com/mamba-org/mamba

eganjs 6y ago
My understanding is mamba, like conda, just call pip. So it likely wouldn't make a difference. The pip section in a env file is just a list of arguments passed through to the pip install command. Prior to pip 20.3 we had to add `--use-feature=2020-resolver` to get an install that resolved for our teams that used mamba.
- Iwan-Zotow 6y ago
  No, conda is not calling pip
  - eganjs 6y ago
    You're wrong, it does. Conda installs conda packages and conda uses pip to install pip packages. However a pip package can be converted to a conda package, and then in that case the dependency will be installed by conda and not pip.
    - martin_renou 6y ago
      You're wrong, it does not. You can install a pip package in a conda env. But this is actually not recommended. When using `mamba install` or `conda install`, pip is not involved at all.
      - uranusjr 6y ago
        You’re correct, Conda does not call pip when it installs packages. But pip does have a subtle involvement here: Many Python packages available to Conda are packaged based on installations made by pip, and (IMO lazily and incorrectly) inherits a lot of pip characteristics. This makes the packages “appear” to be installed by pip, and sometimes induce interpolation inconsistencies.
- martin_renou 6y ago
  Mamba and conda do not call pip. You can install a pip package inside a conda environment. But when running `mamba install` or `conda install`, pip is not involved at all.
  - rdlfo 6y ago
    I got a bit confused by the statements in the thread. If the issue is downloading wheels to check dependencies, mamba should be a better alternative, as not only it is downloading packages in parallel but it uses a different dependency solver.

riedel 6y ago

Maybe by fixing the solver they can finally prove P=NP ;)

oehtXRwMkIs 6y ago
I think that will be proven before python fixes their package management.
- noitpmeder 6y ago
  At least they are trying to fix it, vs other languages where there are literally no paths forward. IMO python has one of the more mature packaging ecosystems out there at this point. It is so incredibly easy.
  - FloatArtifact 6y ago
    Distribution still is a pain unless you're going through pip.
    - pydry 6y ago
      who doesn't use pip?
  - nawgz 6y ago
    >IMO Python has one of the more mature packaging ecosystems out there Ouch, what languages are you using where this is true? For example, JS / NPM / Yarn are absolutely blowing pip out of the water. I guess I can imagine Java or C++ users having your perspective though
    - uranusjr 6y ago
      Every language community has its own priorities, and the package manager grows different traits to meet community needs. Those traits would come at a price, and different comunnities (and their package managers) would make different tradeoffs due to their different priorities. Python has a very involved history dealing with platform-native stuff, and provide a lot of convinience aroud specifying, providing, and obtaining those native stuff. But the complexity would leak into platform-agnostic packages, and gives an impression that packaging is worse when “all you want” is some .py scripts. JavaScript provides a much better interface for packaging and installation, but the expense is that native modules are much more difficult to package, and tend to fail spectacularly on installation when something does not work out. Many more things are like this from each side. There are a lot of smart people working on these things in each ecosystem, and when you think some package manager is far surperior over others in every way, you are more than often simply wrong. Or saying it the other way (and paraphrasing a commenter from another thread), the only package manager you think is good is from the ecosystem you are not deeply familiar with.

sjburt 6y ago

They need to store the version requirements metadata outside the packages. Having to download the entire wheel just to see whether it is compatible is ridiculous. This could all be computed by downloading an index file, then performing the resolution. They made a half-assed attempt when pypa/pip added the "data-requires-python" tag, but that covers python interpreter version only, it needed to have been done for all dependencies. What's especially irksome is that Debian and RPM both solved this 20+ years ago and python has refused to learn any lessons.

woodruffw 6y ago
This is the subject of discussion in this Warehouse (the PyPI backend) issue[1]. The TL;DR is that it probably requires a PEP. FD: I've been working on adjacent features in PyPI. [1]: https://github.com/pypa/warehouse/issues/8254 https://github.com/pypa/warehouse/issues/8254
deleted 6y ago
[deleted]
cozzyd 6y ago
yeah, why not just use libsolv or something?
jrochkind1 6y ago
rubygems went through several iterations of API to try to deal with this, including yes, starting with a dependency-info-only API. I wish different language/platform communities were better at learning from each other (and this does go in all directions). In the field of software these days, we don't do much learning from prior art. It's just too hard to keep up with it all. Heck, I recall this happening with rubygems -- the introductio of the dependencies API to efficiently get the minimum data needing for resolving dependencies before downloading actual packages, and then several iterations on it -- and I can't find any actual documentary evidence of it to share right now. I don't know how anyone WOULD use it as prior art; the source code for a fairly complex project in a language you aren't familiar with isn't going to work, even if you knew to go look for it, which why would you.
6y ago

dang 6y ago

Recent and related: https://news.ycombinator.com/item?id=25253236 https://news.ycombinator.com/item?id=25253236

cbaines 6y ago

I used to think package managers and dependency resolvers were inseperable, I even did a little bit of work on the APT resolver. Since using GNU Guix though, I'm so glad it doesn't have a dependency resolver as part of building or installing packages! It's so much better for it, no slow or unpredictable resolving, you know what it's going to do. I think this is one reason why I've never used pip for managing Python software, I've only ever used Debian, and then Guix.

yjftsjthsd-h 6y ago
Wait, how does guix avoid a dependency resolver? It still has dependencies for packages... are they just hardcoding exact dependencies (including versions) and relying on the "can install multiple versions of a package" property to make that work? That seems inefficient, though I guess maybe they need that for the "this hash means this exact binary" outcome?
- cbaines 6y ago
  Guix has packages, and packages have inputs (like dependencies), and you're right in that normally package definitions specify the exact dependencies it the code (they're hardcoded). Guix package definitions are truely code though, so if you want to generate packages on the fly by using a dependency resolver, you can totally write some code to make that happen. With respect to inefficiency, what do you mean? It's quite time efficient when building and installing to not have to attempt to resolve dependencies.
  - jrochkind1 6y ago
    If they are specifying exact hard-coded dependency versions... if a X -> Y -> A, and B -> A, and M -> N -> A... and a security patch is released for A, then X, Y, B, M and N all need new releases to specify new exact dependencies, in order to use the new A'? It's disastrous for security patches, only highly inconvenient for things like performance improvement releases. But this is why we have dependency resolving, right? What am I missing?

looperhacks 6y ago

Did I get it right, the problem is basically that the dependency info is turing complete and decided "at installtime", thus the dependency graph cannot be computed without installing many versions of all dependencies? (I do not use python, so I don't know much about how pip works) Are there other languages that have dependencies decided at installtime?

vmchale 6y ago
> dependency info is turing complete It's NP-complete in general I think, definitely the case in Haskell-land. I think OCaml sets an explicit timeout for dependency resolution? > the dependency graph cannot be computed without installing many versions of all dependencies? Does PyPi not have an index or something? (with statically known package bounds?)
cipherboy 6y ago
Most distros have install time dependency resolution, such as yum/dnf using libsolv. Repos are a collection of packages alongside metadata tables containing package versions and their dependencies. The tables get cached locally and are used to resolve dependencies prior to downloading any actual RPMs.
JackC 6y ago
Right, for packages distributed as source (vs. having prebuild "binary wheels") the dependencies are specified in python code. Example from one comment on the bug: setup( install_requires=[random.choice(["urllib3", "requests"])] ) This example wouldn't make any sense, but you could imagine installing different dependencies for x86 CPUs or something via a runtime check, and there are lots of packages that use this for checking python versions even though there's now a static way to do that. So that leads to this situation, from another comment: "And as an example, [the botocore package, which has releases nearly daily] depends on python-dateutil>=2.1,<3.0.0. So if [your dependency constraints are] to install python-dateutil 3.0.0 and botocore, pip will have to backtrack through every release of botocore before it can be sure that there isn't one that works with dateutil 3.0.0. ... And worse still, if an ancient version of botocore does have an unconstrained dependency on python-dateutil, we could end up installing it with dateutil 3.0.0, and have a system that, while technically consistent, doesn't actually work." Sounds like there's a long term plan that could fix this situation. Binary wheels already have the needed metadata in a way that could be exposed by PyPI via a fast "fetch dependency constraints for all versions" API, but isn't yet. And for source dists there's a very new plan ( https://www.python.org/dev/peps/pep-0643/ https://www.python.org/dev/peps/pep-0643/ ) to let them indicate that they don't modify install_requires at runtime, so their deps could also be exposed via API, but the ecosystem will have to catch up with that. I dunno what pip does in the meantime, though! (I'm a python dev but haven't followed this beyond skimming the bug, so I hope I'm getting this right.)

qz2 6y ago

It'll still be faster than NuGet. I had to wait 12 minutes (!) to install a package the other day while it resolved dependencies on a single package.