New resolver: Build automated testing to check for acceptable performance

Question

New resolver: Build automated testing to check for acceptable performance

Opened this issue 4 years ago · 51 comments

Our new dependency resolver may make pip a bit slower than it used to be.

Therefore I believe we need to pull together some extremely rough speed tests and decide what level of speed is acceptable, then build some automated testing to check whether we are meeting those marks.

I just ran a few local tests (on a not-particularly-souped-up laptop) to do a side-by-side comparison:

$ time pip install --upgrade pip
Requirement already up-to-date: pip in [path]/python3.7/site-packages (20.2)

real	0m0.867s
user	0m0.680s
sys	0m0.076s

$ time pip install --upgrade pip --use-feature=2020-resolver
Requirement already satisfied: pip in [path]/python3.7/site-packages (20.2)

real	0m1.243s
user	0m0.897s
sys	0m0.060s

Or, in 2 different virtualenvs:

$ time pip install --upgrade chardet
Requirement already up-to-date: chardet in [path].virtualenvs/form990/lib/python3.7/site-packages (3.0.4)

real	0m0.616s
user	0m0.412s
sys	0m0.053s

$ time pip install --upgrade chardet --use-feature=2020-resolver
Requirement already satisfied: chardet in [path].virtualenvs/ical3/lib/python3.7/site-packages (3.0.4)

real	0m1.137s
user	0m0.404s
sys	0m0.053s

These numbers will add up with more complicated processes, dealing with lots of packages at a time.

Related to #6536 and #988.

Edit by @brainwane: As of November 2020 we have defined some speed goals and the new resolver has acceptable performance, so I've switched this issue to be about building automated testing to ensure that we continue to meet our goals in the future.

Edit by @uranusjr: Some explanation for people landing here. The new resolver is generally slower because it checks the dependency between packages more rigorously, and tries to find alternative solutions when dependency specifications do not meet. The legacy resolver, on the other hand, just picks the one specification it likes best without verifying, which of course is faster but also irresponsible.

Feel free to post examples here if the new resolver runs slowly for your project. We are very interested in reviewing all of them to identify possible improvements. When doing so, however, please make sure to also include the pip install output, not just your requirements.txt. The output is important for us to identify what pip is spending time for, and suggest workarounds if possible.

Answer 1 · 2020-07-30T21:46:20.000Z

For SkyPortal, we use pip to verify that all required Python packages are present. This takes about 2 seconds on the old pip, and 20 with the resolver enabled.

Will it be possible to revert to the old behavior in the future (i.e., switch off the resolver?).

pip install -r requirements.txt  1.16s user 0.20s system 54% cpu 2.492 total
pip install -r requirements.txt --use-feature=2020-resolver  16.67s user 0.26s system 84% cpu 20.057 total

Perhaps it would be possible to do a quick "first check" to see if all packages just happen to satisfy requirements, and if they don't to only then enable the resolver?

Our requirements.txt:

supervisor>=4
numpy>=1.12.1
scipy>=0.16.0
pandas>=0.17.0
dask>=0.15.0
joblib>=0.11
seaborn>=0.10.0
bokeh==0.12.9
pytest-randomly>=2.1.1
factory-boy==2.11.1
astropy>=4.0
aplpy>=1.1.1
reproject>=0.7
avro-python3==1.8.2
fastavro==0.21.7
tqdm>=4.23.2
matplotlib>=3
astroquery>=0.4
sqlalchemy-utils
apispec>=3.2.0
marshmallow>=3.4.0
marshmallow-sqlalchemy>=0.21.0
marshmallow-enum>=1.5.1
Pillow>=6
sncosmo>=2.1.0
tdtax>=0.1.1
healpix-alchemy>=0.1.2
jsonschema
jsonpath_ng>=1.5.1
pytest-rerunfailures>=9.0
astroplan>=0.6

Answer 2 · 2020-07-30T22:49:16.000Z

I believe both resolvers already do a scan to check whether packages are already satisfied. The problem is the new resolver is slower to determine what are needed to satisfy the dependencies, since the checks are much more involved than the naive legacy logic.

In your particular use case, if you always list all requirements (instead of relying on pip to discover transient dependencies), you can use the --no-deps option to skip the dependency discovery part entirely, which would make the operation lightning fast in both implementations. (OK, that’s an exaggeration, nothing in pip is lightning fast. But it’ll be a lot faster.)

Answer 3 · 2020-08-01T13:08:58.000Z

I reported a similar performance issue in #8675.

Answer 4 · 2020-08-18T10:19:09.000Z

i have simplifed the test case a bit and measure only the pip running time. download times are not included as prefer binary is used. requirements:

Django==3.0.9
django-auth-ldap
django-cors-headers
django-debug-toolbar
django-extensions
django-uwsgi
django-haystack==3.0b2
hyperkitty==1.3.3
mailman
mailman-hyperkitty
postorius
psycopg2-binary==2.8.5
supervisor
uWSGI==2.0.19.1
whoosh

Please find the 2 log files in this gist: https://gist.github.com/minusf/bd0edfeaf5975980917f2d0792677b52

old: sh -x tvenv.sh 2>&1  19.82s user 6.60s system 92% cpu 28.517 total

new: sh -x tvenv.sh 2>&1  59.04s user 7.78s system 95% cpu 1:10.22 total

Answer 5 · 2020-08-18T15:50:27.000Z

@uranusjr I don't see the --no-deps option listed in the help, even when enabling the new resolver. Is this expected?

Answer 6 · 2020-08-18T16:27:12.000Z

@stefanv It's the 4th option in pip install --help's "Install Options" section in basically any reasonably new pip (say >= 20.0).

$ pip install --help

Usage:
[snipped for brevity]
Description:
[snipped for brevity]
Install Options:
  --no-clean                  Don't clean up build directories.
  -r, --requirement <file>    Install from the given requirements file. This option can be used multiple times.
  -c, --constraint <file>     Constrain versions using the given constraints file. This option can be used multiple times.
  --no-deps                   Don't install package dependencies.
[snipped for brevity]

Answer 7 · 2020-08-18T21:04:34.000Z

Thanks @pradyunsg! But I see now that this would cause problems too, since it would require us to list all dependencies in our requirements.txt file.

Answer 8 · 2020-08-25T15:23:33.000Z

We also tried to enable the new resolver (and actually fixed a number of dependency conflicts by using it, so that's good!)

But the performance is abysmal in the usual developer case where after switching git branches I'll just run pip install -r requirements.txt so ensure everything is at the expected version.

Compare the runtime of the new resolver:

$ /usr/bin/time pip install --use-feature=2020-resolver -r requirements.txt
77.60user 0.75system 3:38.77elapsed 35%CPU (0avgtext+0avgdata 249740maxresident)k
19160inputs+18912outputs (0major+87724minor)pagefaults 0swaps

with the runtime of the old resolver:

$ /usr/bin/time pip install -r requirements.txt
1.75user 0.12system 0:01.87elapsed 100%CPU (0avgtext+0avgdata 41828maxresident)k
40inputs+8outputs (0major+25404minor)pagefaults 0swaps

Granted, this is for 211 installed packages. Many of those are internal and rely on other internal and PyPI packages, so the dependency graph is far from trivial. But a slowdown by a factor of ~100 appears a bit too much.

Interestingly, the new resolver takes 1-2 seconds to check each already installed package and even checks many packages multiple times:

$ cat pip-output.txt | sort | uniq -c | sort -n | tail -n 20
      4 Requirement already satisfied: cython==0.23.4 in ./.../site-packages (from -r etc/requirements/common.txt (line 14)) (0.23.4)
      4 Requirement already satisfied: dynapp==2.7.3 in ./.../site-packages (from -r etc/requirements/common.txt (line 16)) (2.7.3)
      4 Requirement already satisfied: requests==2.21.0+scale1 in ./.../site-packages (from -r etc/requirements/common.txt (line 48)) (2.21.0+scale1)
      4 Requirement already satisfied: scale.toolbelt==0.1.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 69)) (0.1.0)
      5 Requirement already satisfied: enum34 in ./.../site-packages (from cryptography==1.3.4+scale1->-r etc/requirements/common.txt (line 13)) (1.1.6)
      5 Requirement already satisfied: lxml==3.8.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 25)) (3.8.0)
      5 Requirement already satisfied: python-dateutil==2.7.5 in ./.../site-packages (from -r etc/requirements/loco2-common.txt (line 5)) (2.7.5)
      5 Requirement already satisfied: pytz in ./.../site-packages (from spyne==2.9.3+scale5->-r etc/requirements/common.txt (line 94)) (2018.7)
      5 Requirement already satisfied: scale.util.pubsub==1.3.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 78)) (1.3.0)
      6 Requirement already satisfied: cryptography==1.3.4+scale1 in ./.../site-packages (from -r etc/requirements/common.txt (line 13)) (1.3.4+scale1)
      6 Requirement already satisfied: scale.program-manager==1.1.4 in ./.../site-packages (from -r etc/requirements/common.txt (line 64)) (1.1.4)
      6 Requirement already satisfied: scale.util.event==2.0.2 in ./.../site-packages (from -r etc/requirements/common.txt (line 70)) (2.0.2)
      6 Requirement already satisfied: scale.util.progress-monitor==1.3.2 in ./.../site-packages (from -r etc/requirements/common.txt (line 77)) (1.3.2)
      7 Requirement already satisfied: scale.util.threadutil==1.2.1 in ./.../site-packages (from -r etc/requirements/common.txt (line 80)) (1.2.1)
      7 Requirement already satisfied: setuptools>=11.3 in ./.../site-packages (from cryptography==1.3.4+scale1->-r etc/requirements/common.txt (line 13)) (44.1.1)
      8 Requirement already satisfied: pytest==3.7.4 in ./.../site-packages (from -r etc/requirements/common-test.txt (line 18)) (3.7.4)
      8 Requirement already satisfied: scale.util.exception==1.2.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 71)) (1.2.0)
      9 Requirement already satisfied: scale.util.osutils==1.2.3 in ./.../site-packages (from -r etc/requirements/common.txt (line 76)) (1.2.3)
     10 Requirement already satisfied: scale.util.i18n==2.0.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 74)) (2.0.0)
     15 Requirement already satisfied: six==1.12.0 in ./.../site-packages (from -r etc/requirements/common.txt (line 93)) (1.12.0)

Answer 9 · 2020-09-15T08:40:48.000Z

I benchmarked on a medium-sized Django project and found the slowdown was from 1.6 seconds to 41 seconds (again when all packages are already installed locally at the correct versions):

$ wc -l requirements.txt
     171 requirements.txt
$ time python -m pip install --no-deps -r requirements.txt
Requirement already satisfied: ...
python -m pip install --no-deps -r requirements.txt  0.65s user 0.10s system 92% cpu 0.809 total
$ time python -m pip install -r requirements.txt
Requirement already satisfied: ...
python -m pip install -r requirements.txt  1.52s user 0.12s system 99% cpu 1.646 total
$ time python -m pip install --use-feature=2020-resolver -r requirements.txt
Requirement already satisfied: ...
python -m pip install --use-feature=2020-resolver -r   37.05s user 0.69s system 91% cpu 41.121 total

I profiled the project with py-spy:

$ sudo py-spy record --threads --idle --rate 1000 --format speedscope --output pip-install.speedscope /path/to/project/venv/bin/pip install -- --use-feature=2020-resolver -r requirements.txt

This resulted in a speedscope file - see attached. It can be used at https://www.speedscope.app/ to investigate the profile.

pip-install-redacted.speedscope.zip

Most of the time - 93,547 out of 99,225 frames - was unsurprisingly under Resolver.resolve():

Tracing it down I noticed there are a lot of invocations of parse_links. From this I surmised that the new resolver is hitting parsing HTML a lot.

Indeed when I turned off my internet connection and tried again, using --no-deps or the old resolver, pip install can succeed entirely with the local set of information. But the new resolver makes requests that fail almost immediately - trying to get the PyPI page for a requirement after already printing that it has been satisfied:

$ time python -m pip install --use-feature=2020-resolver -r requirements.txt
Requirement already satisfied: aiohttp==3.6.2 in ./venv/lib/python3.8/site-packages (from -r requirements.txt (line 7)) (3.6.2)
WARNING: Retrying (Retry(total=4, connect=None, read=None, redirect=None, status=None)) after connection broken by 'NewConnectionError('<pip._vendor.urllib3.connection.HTTPSConnection object at 0x104ccd940>: Failed to establish a new connection: [Errno 8] nodename nor servname provided, or not known')': /simple/aiohttp/
WARNING: Retrying (Retry(total=3, connect=None, read=None, redirect=None, status=None)) after connection broken by 'NewConnectionError('<pip._vendor.urllib3.connection.HTTPSConnection object at 0x104ccd820>: Failed to establish a new connection: [Errno 8] nodename nor servname provided, or not known')': /simple/aiohttp/
WARNING: Retrying (Retry(total=2, connect=None, read=None, redirect=None, status=None)) after connection broken by 'NewConnectionError('<pip._vendor.urllib3.connection.HTTPSConnection object at 0x104ccda00>: Failed to establish a new connection: [Errno 8] nodename nor servname provided, or not known')': /simple/aiohttp/
WARNING: Retrying (Retry(total=1, connect=None, read=None, redirect=None, status=None)) after connection broken by 'NewConnectionError('<pip._vendor.urllib3.connection.HTTPSConnection object at 0x104ccd580>: Failed to establish a new connection: [Errno 8] nodename nor servname provided, or not known')': /simple/aiohttp/
WARNING: Retrying (Retry(total=0, connect=None, read=None, redirect=None, status=None)) after connection broken by 'NewConnectionError('<pip._vendor.urllib3.connection.HTTPSConnection object at 0x104ccd6a0>: Failed to establish a new connection: [Errno 8] nodename nor servname provided, or not known')': /simple/aiohttp/
Requirement already satisfied: aioredis==1.3.1 in ./venv/lib/python3.8/site-packages (from -r requirements.txt (line 8)) (1.3.1)

These requests don't seem necessary as the resolution continues just fine (although I didn't wait until the end)... I hope this can help.

Answer 10 · 2020-09-15T09:14:38.000Z

I was just told about --use-feature=fast-deps to use range requests for dependencies. I tried combining it with the new resolver but it didn't make it any faster:

$ time python -m pip install --use-feature=2020-resolver --use-feature=fast-deps -r requirements.txt
WARNING: pip is using lazily downloaded wheels using HTTP range requests to obtain dependency information. This experimental feature is enabled through --use-feature=fast-deps and it is not ready for production.
Requirement already satisfied: ...
python -m pip install --use-feature=2020-resolver --use-feature=fast-deps -r   37.98s user 0.83s system 90% cpu 42.658 total

Answer 11 · 2020-09-22T16:37:37.000Z

Pip version: 20.2.3
Python version: 3.8.1
Number of requirements: 269
Computer: MacBook Pro with Core i9
Internet: ~170 Mbps home internet in San Francisco

With a fully frozen requirements.txt (all packages specified, all with ==), that installs 269 requirements, in a virtual environment where all the requirements are already satisfied:

Classic resolver:

$ time pip install -r requirements.txt

real	0m1.635s
user	0m1.483s
sys	0m0.144s

2020-resolver:

$ time pip --use-feature=2020-resolver install -r requirements.txt

real	4m5.993s
user	1m56.048s
sys	0m3.692s

2020-resolver with --no-deps:

$ time pip --use-feature=2020-resolver install --no-deps -r requirements.txt

real	1m33.484s
user	0m42.211s
sys	0m1.923s

That is 2 seconds for the classic resolver, 246 seconds for 2020-resolver (123x slower), 94 seconds for 2020-resolver with --no-deps (47x slower). Poetry does the same in about 8 seconds (I realize Poetry is different because it keeps a fully resolved local lock file).

I really like what the 2020-resolver does. I'd be happy to take the performance penalty in CI, in a new virtual env, to ensure correctness. But for local development, where users may be expected to run tox to update multiple existing virtual envs and run tests against multiple versions of Python, adding 4 minutes per virtual env isn't very nice.

I don't want --no-deps, I want something more like --no-deps-for-already-satisfied-requirements. It can be hard with pip to have a fully frozen requirements.txt when supporting multiple versions of Python, because some packages have "fancy" setup.py files that calculate requirements in Python instead of using environment markers. So for new requirements (not already satisfied in the virtual env) I want deps to be installed. But for existing packages there is no need to calculate deps because the package and its deps are already installed.

Answer 12 · 2020-09-22T18:57:17.000Z

@antoncohen Can I just check I understand your example here? You have a requirements.txt that contains a list of every package that gets installed, with an exact equality constraint forcing precisely one version for every one. Every package is already installed, so there's nothing for pip to do? That seems like on the one hand, it's a completely artificial case, so not representative of real-world situations, but on the other hand, something that the new resolver should certainly be able to handle better than what you're seeing.

Assuming I haven't misunderstood, there's something odd going on here. If we have a requirement foo==1.0.0 that should generate only a single candidate, because packages are unique by name and version. Once we see that requirement, the resolver should have a solution set with just that one version in it, and there's no choices to be made. All of the requirements in requirements.txt are in the root set, so they should be applied first - so even though the finder may return multiple candidates, we'll drop them straight away.

If my reasoning above is correct, then we should never even see candidates that don't get installed.

As everything is pre-installed, we should pick the installed version over a new install, and we can get metadata by a simple filesystem lookup. So there's no need to go to PyPI (or any other index) at all.

It's possible there's a genuine bug here, and the resolver is not constraining the candidates based on the root set early enough. To prove that, we'd likely need to instrument a run of the problem case and see exactly what order the code is doing things. That would mean getting a reproducible example, though.

If your test case is genuinely made up of fully pinned requirements (foo==1.0) and no local directories, URL/VCS links, etc, then it should be reproducible, or at least it should be possible to create an artificial version of it. To help me try to create a reproducer for this, could you post somewhere the actual requirements file you used, and the full dependency list of every package in that list? (You can get the dependency data from the installed metadata using something like grep Requires-Dist (dir $env:VIRTUAL_ENV\Lib\site-packages\*.dist-info\METADATA) - that's Powershell syntax, Unix shouldn't be that dissimilar).

If I've misunderstood how your example is set up, my analysis above is wrong. In that case don't bother with the detail data. But I would be glad to know what I didn't understand about your test case 🙂

Answer 13 · 2020-09-22T19:32:18.000Z

You have a requirements.txt that contains a list of every package that gets installed, with an exact equality constraint forcing precisely one version for every one. Every package is already installed, so there's nothing for pip to do? That seems like on the one hand, it's a completely artificial case, so not representative of real-world situations, but on the other hand, something that the new resolver should certainly be able to handle better than what you're seeing.

I know you weren't asking, but this is the case I tested. I don't think it's 'completely artificial' - I quite often run the command when switching branches or pulling latest changes on a project just in case dependencies changed.

Answer 14 · 2020-09-22T20:08:57.000Z

I know you weren't asking, but this is the case I tested. I don't think it's 'completely artificial' - I quite often run the command when switching branches or pulling latest changes on a project just in case dependencies changed.

But the example has everything, including dependencies, pinned. So "just in case dependencies changed" doesn't apply. It's a situation where we know absolutely, up front, that pip won't install anything. Or are you expecting to get pip install fail with a "cannot resolve" error as a way of reporting that the dependencies changed?

Unless I'm misunderstanding 🙂

Anyway, the main point here is that we really need a reproducible test case. At the moment, we don't have one, so I'm mostly just trying to get enough information to construct one (that can be run with all local files, so we can avoid network/cache effects).

Answer 15 · 2020-09-22T20:23:50.000Z

So "just in case dependencies changed" doesn't apply.

He ist taking about the dependencies listed in the requirements.txt of his project. Changing branches will change the contents of requirements.txt, so to work on the new branch one has to update the virtual environment to work in.

I do that about 20 times a day. And sometimes I forget to run it with the result that our application does not come up. For this reason some colleagues like to add a hook to git to run pip install -r requirements.txt after each checkout.

Answer 16 · 2020-09-22T20:32:50.000Z

But again, the example I was responding to said "in a virtual environment where all the requirements are already satisfied". So again this is a different situation.

I don't want to dismiss your use cases. They are just harder to analyze, because if pip might find it needs to install things, that introduces extra work the resolver has to do. The significant advantage of @antoncohen's case is that it doesn't have those complexities, making it easier to analyze. The disadvantage is that it is (or at least seems to be) more unrealistic than the sorts of case you're talking about.

Answer 17 · 2020-09-22T20:57:22.000Z

If we have a requirement foo==1.0.0 that should generate only a single candidate, because packages are unique by name and version.

This isn't exactly True right? I haven't dug into the new code at all yet, but presumably you can have an sdist and multiple wheels that all have the same version and different dependencies? Also in PEP 440, ==1.0.0 can match multiple versions, if local versions are being used (banned on PyPI).

Answer 18 · 2020-09-22T21:22:11.000Z

@dstufft Yes, it's not entirely accurate. I'm assuming no local versions are involved. And the finder will give back a list of compatible files for the given version, but we should pick just one to hand to the resolver, based on things like --prefer-binary etc. The resolver should only see one file, though, it doesn't allow for different "candidate" objects for the same name/version.

Apologies, I'm doing this from memory at the moment, it's a few weeks since I've gone into the code in depth. My main interest at the moment is pinning down the reported behaviour well enough to replicate it locally. Once I've got that, I'd intend to fire a test case at an instrumented version of the code, and really dig into precisely what's happening.

To get the sort of slowdowns being reported suggests that the resolver is backtracking badly, or otherwise doing a lot of unnecessary work. If the situation is as described, that may be a bug - because the described situation is so constrained that there's nothing to backtrack to. So either we have a bug or the description is failing to make clear where the source of additional options is coming from. Hopefully someone can come up with enough detail that we can establish which is the case here.

Answer 19 · 2020-09-22T23:45:30.000Z

@pfmoore, thanks for the response!

If your test case is genuinely made up of fully pinned requirements (foo==1.0) and no local directories, URL/VCS links

In my initial test 6 of the 200+ requirements were directory tarballs, I consider them frozen because they are referenced by hash and don't change. I removed them so truly 100% of requirements.txt is fully pinned like foo==1.0. The result is the same:

$ time pip --use-feature=2020-resolver install -r requirements-no-tar.txt

...
Requirement already satisfied: google-auth==1.21.2 in /path/to/lib/python3.8/site-packages (from -r requirements-no-tar.txt (line 84)) (1.21.2)
Requirement already satisfied: pytz==2017.2 in /path/to/lib/python3.8/site-packages (from -r requirements-no-tar.txt (line 211)) (2017.2)
Requirement already satisfied: protobuf==3.13.0 in /path/to/lib/python3.8/site-packages (from -r requirements-no-tar.txt (line 169)) (3.13.0)
...

real	4m10.779s
user	1m54.720s
sys	0m3.405s

The output is all "Requirement already satisfied", and every line of "Requirement already satisfied" takes about a second.

You have a requirements.txt that contains a list of every package that gets installed, with an exact equality constraint forcing precisely one version for every one. Every package is already installed, so there's nothing for pip to do? That seems like on the one hand, it's a completely artificial case, so not representative of real-world situationsions

Everyone has different use cases. But in my experience, dealing with applications that get deployed to production, this is the 99% use case. Every production application that uses requirements.txt will usually have a fully pinned and resolved requirements.txt. Usually that requirements.txt is generated from looser constraints with something like pip-compile, poetry export, or pipenv lock -r.

In local development there is almost always an existing virtual environment with dependencies installed. pip install is used to update the dependencies. Most of the time there will be no updates, some of the time there will be a few updates. Installing all packages would be rare. But you don't know what packages need installing until pip install checks.

In CI often times there will be fresh installs. But when people try to optimize CI build times they might end up caching virtual envs or layering images.

To help me try to create a reproducer for this, could you post somewhere the actual requirements file you used, and the full dependency list of every package in that list?

I can't provide the exact requirements.txt because it includes private packages. But I can construct one. I searched Google for [django open source projects], found taiga-back, grabbed their requirements.txt, added a bunch of random large packages, and used Poetry to export a locked requirements.txt.

One important note, my testing that takes 4 minutes has some packages that come from a private PyPI repo. I noticed that even if no packages come from the private PyPI, having --extra-index-url makes the pip install take 2x longer. So I searched Google for [pypi simple] and found a public mirror (Alibaba Cloud) to use for testing with a second PyPI.

This gist contains the requirements.txt and the grep Requires-Dist *.dist-info/METADATA output:

https://gist.github.com/antoncohen/ace9499dc881fc472873c4c0da97663c

Here are the timings I got:

No extra-index-url:

$ time pip --use-feature=2020-resolver install -r random-django-requirements.txt

real	0m34.021s
user	0m28.477s
sys	0m0.503s

With extra-index-url:

$ time pip --use-feature=2020-resolver install --extra-index-url https://mirrors.aliyun.com/pypi/simple -r random-django-requirements.txt

real	1m9.045s
user	0m56.234s
sys	0m0.870s

Classic resolver:

$ time pip install --extra-index-url https://mirrors.aliyun.com/pypi/simple -r random-django-requirements.txt

real	0m0.992s
user	0m0.856s
sys	0m0.125s

Our actual requirements.txt is twice as large, and our private PyPI is probably slower than Alibaba Cloud. But hopefully this example where it takes over a minute will be helpful.

Answer 20 · 2020-09-23T06:23:27.000Z

The output is all "Requirement already satisfied", and every line of "Requirement already satisfied" takes about a second.

Same here for our internal project.

I noticed that even if no packages come from the private PyPI, having --extra-index-url makes the pip install take 2x longer.

That's good to know because we use an internal devpi install to take some load from pypi.org and to provide our internal packages. pip of course checks both indexes as it seems - not sure if it is possible to disable pypi lookups?!

I can't provide the exact requirements.txt because it includes private packages. But I can construct one.

Same here. Maybe I could provide it but not the packages...

But I constructed a sufficiently large requirements file by taking an older project, dropping private packages and adding some from pypi. For reproducability I created a Dockerfile to run this independent of the local setup.

You can find Dockerfile and requirements.txt here: https://gist.github.com/tlandschoff-scale/83a95661e40bf4b51c32c0f990e15a37

Run time here:

Step 8/9 : RUN echo "This is the old resolver:" && time pip install -r requirements.txt
 ---> Running in ac4b41b4498b
This is the old resolver:
...
2.17user 0.16system 0:02.44elapsed 95%CPU (0avgtext+0avgdata 43108maxresident)k
456inputs+344outputs (1major+16502minor)pagefaults 0swaps

compared with the new resolver:

Step 9/9 : RUN echo "This is the new resolver:" && time pip install --use-feature=2020-resolver -r requirements.txt
 ---> Running in 2bd39d69ad0b
This is the new resolver:
40.78user 0.41system 0:49.47elapsed 83%CPU (0avgtext+0avgdata 77680maxresident)k
0inputs+16768outputs (0major+31328minor)pagefaults 0swaps

Out of curiosity I added the extra index from Alibaba and did an extra run:

Step 10/10 : RUN echo "This is the new resolver, extra index:" && time pip install --extra-index-url https://mirrors.aliyun.com/pypi/simple --use-feature=2020-resolver -r requirements.txt
 ---> Running in b1536adc0e11
This is the new resolver, extra index:
Looking in indexes: https://pypi.org/simple, https://mirrors.aliyun.com/pypi/simple
...
82.18user 0.69system 4:02.02elapsed 34%CPU (0avgtext+0avgdata 102144maxresident)k
32inputs+33488outputs (0major+41613minor)pagefaults 0swaps
Removing intermediate container b1536adc0e11

Answer 21 · 2020-09-23T06:48:20.000Z

Thanks @antoncohen for taking the time to provide a reproducer and for the explanation of your use case. Please understand, I'm not dismissing your situation at all, my only thought was that it may be sufficiently specialised that if we get into a trade-off where we have to make something else slower to speed this up, we will need to consider the question of what is the common case we should optimise (and that's always very hard to determine, as we get very conflicting reports of what counts as the "common case" from people with radically different workflows).

I'll do some investigation of your reproducer over the next few days and see what I can find.

Answer 22 · 2020-09-23T11:14:45.000Z

requirements.txt
Here's my reproduction. Attached is the requirements.txt file - everything is pinned with == thanks to pip-compile.

Setup, on Python 3.8.5:

python -m venv venv
source venv/bin/activate
python -m pip install -U pip wheel
python -m pip install -r requirements.txt

Again testing, with old resolver:

$ time python -m pip install -r requirements.txt
Requirement already satisfied: aiohttp==3.6.2 in ./venv/lib/python3.8/site-packages (from -r requirements.txt (line 7)) (3.6.2)
...
Requirement already satisfied: pip>=10.0.0 in ./venv/lib/python3.8/site-packages (from pip-lock==2.1.1->-r requirements.txt (line 101)) (20.2.3)
python -m pip install -r requirements.txt  1.59s user 0.18s system 91% cpu 1.935 total

With new resolver:

$ time python -m pip install --use-feature=2020-resolver -r requirements.txt
Requirement already satisfied: aiohttp==3.6.2 in ./venv/lib/python3.8/site-packages (from -r requirements.txt (line 7)) (3.6.2)
...
Requirement already satisfied: hyperlink==20.0.1 in ./venv/lib/python3.8/site-packages (from -r requirements.txt (line 66)) (20.0.1)
python -m pip install --use-feature=2020-resolver -r requirements.txt  39.06s user 0.95s system 90% cpu 44.422 total

Answer 23 · 2020-09-23T16:01:09.000Z

Spending some more time to debug this... pip's new resolver is hitting the network even when the currently installed version does satisfy the version requested. Further, it's also hitting the same index page (i.e. https://pypi.org/simple/{project}) each time we see it during the graph exploration, which is obviously the wrong thing to do.

That's 100% a genuine bug, and I'll file a new issue for tracking that.

Answer 24 · 2020-09-24T20:01:58.000Z

I noticed that even if no packages come from the private PyPI, having --extra-index-url makes the pip install take 2x longer.

A little off-topic but that is expected since pip's code is currently mainly single-threaded.
Each time pip needs to get information from the indexes it will contact all indexes sequentially.
A note in the document explaining this might be useful.

(and if you're using a private devpi you should let it mirror PyPI with the nice guarantee that no public projects will shadow your private ones in case of name conflict).

Answer 25 · 2020-10-01T19:19:19.000Z

Thanks to @pfmoore and @uranusjr's amazingness, we have #8912 and #8932 which should significantly improve optimize how often we hit the network.

we need to pull together some extremely rough speed tests

I took wayyy too long to finish doing this, but... here are numbers for a few runs, comparing the legacy resolver vs the 2020 resolver in 20.2.3 vs after-#8932. All the requirements used for these tests are from reports we've seen from our users (yay feedback!) and are included below.

In the listing below, "cold" is a pip install -r ... run in a clean virtualenv. "warm" is a pip install -r ... run in an already populated virtualenv (basically the state after the "cold" run). All runs are after populating the cache with all the relevant files, to reduce the overhead of downloading the distribution files.

one.txt (legacy resolver, cold)        : 0m 28.09s
one.txt (new resolver, 20.2.3, cold)   : 1m  8.89s
one.txt (new resolver, #8932, cold)    : 1m 23.61s

one.txt (legacy resolver, warm)        : 0m  0.93s
one.txt (new resolver, 20.2.3, warm)   : 0m 52.86s
one.txt (new resolver, #8932, warm)    : 0m  1.23s

two.txt (legacy resolver, cold)        : 0m 56.02s
two.txt (new resolver, 20.2.3, cold)   : 1m 31.32s
two.txt (new resolver, #8932, cold)    : 2m  7.57s

two.txt (legacy resolver, warm)        : 0m  1.96s
two.txt (new resolver, 20.2.3, warm)   : 0m 57.29s
two.txt (new resolver, #8932, warm)    : 0m  2.99s

three.txt (legacy resolver, cold)      : 0m 18.94s
three.txt (new resolver, 20.2.3, cold) : 0m 29.00s
three.txt (new resolver, #8932, cold)  : 0m 28.29s

three.txt (legacy resolver, warm)      : 0m  0.61s
three.txt (new resolver, 20.2.3, warm) : 0m 13.63s
three.txt (new resolver, #8932, warm)  : 0m  0.81s

It's relatively straightforward to pull together more numbers here, but I think these paint a fairly reasonable "broad strokes" picture. Let me know if someone thinks we need more information here. :)

With #8932, things improve substantially for "warm" states, with a minor degradation in some situations for the "cold" case. Looking at the way the resolver is exploring the graph, I think we're doing OK. The part of this change that we had most feedback on -- the "warm" case -- should be fixed pretty soon. It's worth investigating why #8932 makes the "cold" cases slower though.

decide what level of speed is acceptable

Once #8932 is merged, I think we'll be at an acceptable point.

We are expecting some amount of degradation due to actually being strict, and looking at what the resolver is doing that seems to be the case here, so I think we're fine. FWIW, running with --no-deps isn't going to result in any speedups (since we're still verifying the choices made).

Beyond that, the only think that may be worth exploring is why #8932 right now isn't as fast as the 20.2.3 resolver in the cold case. I'll also point out that #8932 is open right now, so it's likely @uranusjr or I or @pfmoore would look into this before that merges. I don't think it's a big enough deviation to block the release but I'm all ears for differing opinions. :)

The input files, scripts and intermediate-output involved

Manually formatted text, w/ a text editor and a throw-away script:

> virtualenv /tmp/one.txt.venv --quiet --clear
  started   : 17:37:57.5497
  ended     : 17:37:58.0608
  time taken: 0m  0.51s
> /tmp/one.txt.venv/bin/pip install -r one.txt
  started   : 17:37:58.0608
  ended     : 17:38:26.1556
  time taken: 0m 28.09s
> /tmp/one.txt.venv/bin/pip install -r one.txt
  started   : 17:38:26.1556
  ended     : 17:38:27.0868
  time taken: 0m  0.93s

> virtualenv /tmp/one.txt.venv --quiet --clear
  started   : 17:38:27.0868
  ended     : 17:38:29.4514
  time taken: 0m  2.36s
> /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
  started   : 17:38:29.4514
  ended     : 17:39:38.3507
  time taken: 1m  8.89s
> /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
  started   : 17:39:38.3507
  ended     : 17:40:31.2113
  time taken: 0m 52.86s

> virtualenv /tmp/one.txt.venv --quiet --clear
  started   : 17:40:31.2113
  ended     : 17:40:33.6294
  time taken: 0m  2.41s
> /tmp/one.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
  started   : 17:40:33.6294
  ended     : 17:40:48.2973
  time taken: 0m 14.66s
> /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
  started   : 17:40:48.2973
  ended     : 17:42:11.9149
  time taken: 1m 23.61s
> /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
  started   : 17:42:11.9149
  ended     : 17:42:13.1487
  time taken: 0m  1.23s

> virtualenv /tmp/three.txt.venv --quiet --clear
  started   : 17:42:13.1487
  ended     : 17:42:14.5905
  time taken: 0m  1.44s
> /tmp/three.txt.venv/bin/pip install -r three.txt
  started   : 17:42:14.5905
  ended     : 17:42:33.5365
  time taken: 0m 18.94s
> /tmp/three.txt.venv/bin/pip install -r three.txt
  started   : 17:42:33.5365
  ended     : 17:42:34.1531
  time taken: 0m  0.61s

> virtualenv /tmp/three.txt.venv --quiet --clear
  started   : 17:42:34.1531
  ended     : 17:42:35.3589
  time taken: 0m  1.20s
> /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
  started   : 17:42:35.3589
  ended     : 17:43:04.3643
  time taken: 0m 29.00s
> /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
  started   : 17:43:04.3643
  ended     : 17:43:17.9963
  time taken: 0m 13.63s

> virtualenv /tmp/three.txt.venv --quiet --clear
  started   : 17:43:17.9963
  ended     : 17:43:19.5427
  time taken: 0m  1.54s
> /tmp/three.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
  started   : 17:43:19.5427
  ended     : 17:43:28.5639
  time taken: 0m  9.02s
> /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
  started   : 17:43:28.5639
  ended     : 17:43:56.8558
  time taken: 0m 28.29s
> /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
  started   : 17:43:56.8558
  ended     : 17:43:57.6750
  time taken: 0m  0.81s

> virtualenv /tmp/two.txt.venv --quiet --clear
  started   : 17:43:57.6750
  ended     : 17:44:02.2569
  time taken: 0m  4.58s
> /tmp/two.txt.venv/bin/pip install -r two.txt
  started   : 17:44:02.2569
  ended     : 17:44:58.2840
  time taken: 0m 56.02s
> /tmp/two.txt.venv/bin/pip install -r two.txt
  started   : 17:44:58.2840
  ended     : 17:45:00.2502
  time taken: 0m  1.96s

> virtualenv /tmp/two.txt.venv --quiet --clear
  started   : 17:45:00.2502
  ended     : 17:45:03.9982
  time taken: 0m  3.74s
> /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
  started   : 17:45:03.9982
  ended     : 17:46:35.3267
  time taken: 1m 31.32s
> /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
  started   : 17:46:35.3267
  ended     : 17:47:32.6175
  time taken: 0m 57.29s

> virtualenv /tmp/two.txt.venv --quiet --clear
  started   : 17:47:32.6175
  ended     : 17:47:36.0087
  time taken: 0m  3.39s
> /tmp/two.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
  started   : 17:47:36.0087
  ended     : 17:47:44.1832
  time taken: 0m  8.17s
> /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
  started   : 17:47:44.1832
  ended     : 17:49:51.7550
  time taken: 2m  7.57s
> /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
  started   : 17:49:51.7550
  ended     : 17:49:54.7549
  time taken: 0m  2.99s

$ bash ./run.sh
[...]
$ cat ./state.dump
(17:37:57.5497) > virtualenv /tmp/one.txt.venv --quiet --clear
(17:37:58.0608) > /tmp/one.txt.venv/bin/pip install -r one.txt
(17:38:26.1556) > /tmp/one.txt.venv/bin/pip install -r one.txt
(17:38:27.0868) > virtualenv /tmp/one.txt.venv --quiet --clear
(17:38:29.4514) > /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
(17:39:38.3507) > /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
(17:40:31.2113) > virtualenv /tmp/one.txt.venv --quiet --clear
(17:40:33.6294) > /tmp/one.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
(17:40:48.2973) > /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
(17:42:11.9149) > /tmp/one.txt.venv/bin/pip install -r one.txt --use-feature=2020-resolver
(17:42:13.1487) > virtualenv /tmp/three.txt.venv --quiet --clear
(17:42:14.5905) > /tmp/three.txt.venv/bin/pip install -r three.txt
(17:42:33.5365) > /tmp/three.txt.venv/bin/pip install -r three.txt
(17:42:34.1531) > virtualenv /tmp/three.txt.venv --quiet --clear
(17:42:35.3589) > /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
(17:43:04.3643) > /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
(17:43:17.9963) > virtualenv /tmp/three.txt.venv --quiet --clear
(17:43:19.5427) > /tmp/three.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
(17:43:28.5639) > /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
(17:43:56.8558) > /tmp/three.txt.venv/bin/pip install -r three.txt --use-feature=2020-resolver
(17:43:57.6750) > virtualenv /tmp/two.txt.venv --quiet --clear
(17:44:02.2569) > /tmp/two.txt.venv/bin/pip install -r two.txt
(17:44:58.2840) > /tmp/two.txt.venv/bin/pip install -r two.txt
(17:45:00.2502) > virtualenv /tmp/two.txt.venv --quiet --clear
(17:45:03.9982) > /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
(17:46:35.3267) > /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
(17:47:32.6175) > virtualenv /tmp/two.txt.venv --quiet --clear
(17:47:36.0087) > /tmp/two.txt.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
(17:47:44.1832) > /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
(17:49:51.7550) > /tmp/two.txt.venv/bin/pip install -r two.txt --use-feature=2020-resolver
(17:49:54.7549) > echo Done.

run.sh:

function run_pip() {
  run /tmp/$1.venv/bin/pip install -r $@
  run /tmp/$1.venv/bin/pip install -r $@
}

function run() {
  time=$(gdate "+%H:%M:%S.%4N")
  echo "($time) > $@" >> state.dump
  echo -ne "\033[34m($time) $ "
  echo -ne $@
  echo -e "\033[0m"
  $@
}

for file in $(ls *.txt)
do
  run virtualenv /tmp/$file.venv --quiet --clear
  run_pip $file

  run virtualenv /tmp/$file.venv --quiet --clear
  run_pip $file --use-feature=2020-resolver

  run virtualenv /tmp/$file.venv --quiet --clear
  run /tmp/$file.venv/bin/pip install https://github.com/uranusjr/pip/archive/new-resolver-lazy-sequence.zip
  run_pip $file --use-feature=2020-resolver
done

run echo "Done."

one.txt:

Django==3.0.9
django-auth-ldap
django-cors-headers
django-debug-toolbar
django-extensions
django-uwsgi
django-haystack==3.0b2
hyperkitty==1.3.3
mailman
mailman-hyperkitty
postorius
psycopg2-binary==2.8.5
supervisor
uWSGI==2.0.19.1
whoosh

two.txt:

#
# This file is autogenerated by pip-compile
# To update, run:
#
#    pip-compile
#
aiohttp==3.6.2            # via slackclient
aioredis==1.3.1           # via channels-redis
appdirs==1.4.4            # via black, virtualenv, zeep
appnope==0.1.0            # via ipython
apscheduler==3.6.3        # via -r requirements.in
asgiref==3.2.10           # via -r requirements.in, channels, channels-redis, daphne, django
async-timeout==3.0.1      # via aiohttp, aioredis
attrs==20.2.0             # via aiohttp, automat, curlylint, flake8-bugbear, jsonschema, service-identity, twisted, zeep
autobahn==20.7.1          # via daphne
automat==20.2.0           # via twisted
backcall==0.2.0           # via ipython
beautifulsoup4==4.9.1     # via webtest
black==20.8b1             # via -r requirements.in
boto3==1.15.3             # via -r requirements.in
botocore==1.18.3          # via boto3, s3transfer
cached-property==1.5.2    # via zeep
certifi==2020.6.20        # via requests, sentry-sdk
cffi==1.14.3              # via cryptography
cfgv==3.2.0               # via pre-commit
channels-redis==3.1.0     # via -r requirements.in
channels==2.4.0           # via -r requirements.in, channels-redis
chardet==3.0.4            # via aiohttp, requests
click==7.1.2              # via black, curlylint, pip-tools, safety
constantly==15.1.0        # via twisted
coverage==5.3             # via -r requirements.in
cryptography==3.1.1       # via autobahn, pyopenssl, service-identity
curlylint==0.12.0         # via -r requirements.in
daphne==2.5.0             # via -r requirements.in, channels
decorator==4.4.2          # via ipython
defusedxml==0.6.0         # via odfpy, zeep
diff-match-patch==20200713  # via django-import-export
distlib==0.3.1            # via virtualenv
dj-rest-auth==1.1.1       # via -r requirements.in
django-capture-on-commit-callbacks==1.2.0  # via -r requirements.in
django-debug-toolbar==3.1  # via -r requirements.in
django-extensions==3.0.9  # via -r requirements.in
django-import-export==2.3.0  # via -r requirements.in
django-ipware==3.0.1      # via -r requirements.in
django-money==1.1         # via -r requirements.in
django-oauth-toolkit==1.3.2  # via -r requirements.in
django-post-office==3.4.1  # via -r requirements.in
django-storages==1.10.1   # via -r requirements.in
django-webtest==1.9.7     # via -r requirements.in
django==3.0.10            # via -r requirements.in, channels, dj-rest-auth, django-capture-on-commit-callbacks, django-debug-toolbar, django-import-export, django-money, django-oauth-toolkit, django-post-office, django-storages, djangorestframework, jsonfield
djangorestframework==3.11.1  # via -r requirements.in, dj-rest-auth
dparse==0.5.1             # via safety
et-xmlfile==1.0.1         # via openpyxl
filelock==3.0.12          # via virtualenv
flake8-bugbear==20.1.4    # via -r requirements.in
flake8-comprehensions==3.2.3  # via -r requirements.in
flake8-tidy-imports==4.1.0  # via -r requirements.in
flake8==3.8.3             # via -r requirements.in, flake8-bugbear, flake8-comprehensions, flake8-tidy-imports
gql==2.0.0                # via -r requirements.in
graphql-core==2.3.2       # via gql
gunicorn==20.0.4          # via -r requirements.in
haversine==2.3.0          # via -r requirements.in
hiredis==1.1.0            # via aioredis
html5lib==1.1             # via -r requirements.in
huey==2.3.0               # via -r requirements.in
hyperlink==20.0.1         # via twisted
identify==1.5.4           # via pre-commit
idna==2.10                # via hyperlink, requests, twisted, yarl
incremental==17.5.0       # via twisted
ipython-genutils==0.2.0   # via traitlets
ipython==7.18.1           # via -r requirements.in
isodate==0.6.0            # via zeep
isort==5.5.3              # via -r requirements.in
jdcal==1.4.1              # via openpyxl
jedi==0.17.2              # via ipython
jmespath==0.10.0          # via boto3, botocore
jsonfield==3.1.0          # via django-post-office
jsonschema==3.2.0         # via ocpp
lxml==4.5.2               # via -r requirements.in, zeep
markuppy==1.14            # via tablib
mccabe==0.6.1             # via flake8
msgpack==1.0.0            # via channels-redis
multidict==4.7.6          # via aiohttp, yarl
mypy-extensions==0.4.3    # via black, mypy
mypy==0.782               # via -r requirements.in
nodeenv==1.5.0            # via pre-commit
numpy==1.18.5             # via -r requirements.in, pandas, scipy
oauthlib==3.1.0           # via django-oauth-toolkit, requests-oauthlib
ocpp==0.7.1               # via -r requirements.in
odfpy==1.4.1              # via tablib
openpyxl==3.0.5           # via tablib
packaging==20.4           # via dparse, safety
pandas==1.1.2             # via -r requirements.in
parameterized==0.7.4      # via -r requirements.in
parso==0.7.1              # via jedi
parsy==1.1.0              # via curlylint
pathspec==0.8.0           # via black, curlylint
pexpect==4.8.0            # via ipython
pickleshare==0.7.5        # via ipython
pillow==7.2.0             # via -r requirements.in
pip-lock==2.1.1           # via -r requirements.in
pip-tools==5.3.1          # via -r requirements.in
postcode.io==0.1.1        # via -r requirements.in
pre-commit==2.7.1         # via -r requirements.in
promise==2.3              # via gql, graphql-core
prompt-toolkit==3.0.7     # via ipython
psutil==5.7.2             # via -r requirements.in
psycopg2-binary==2.8.6    # via -r requirements.in
ptyprocess==0.6.0         # via pexpect
py-moneyed==0.8.0         # via django-money
pyasn1-modules==0.2.8     # via service-identity
pyasn1==0.4.8             # via pyasn1-modules, service-identity
pycodestyle==2.6.0        # via flake8
pycparser==2.20           # via cffi
pyflakes==2.2.0           # via flake8
pygments==2.7.1           # via ipython
pyhamcrest==2.0.2         # via twisted
pyopenssl==19.1.0         # via twisted
pyparsing==2.4.7          # via packaging
pyrsistent==0.17.3        # via jsonschema
python-dateutil==2.8.1    # via -r requirements.in, botocore, pandas, smartcar, time-machine
pytz==2020.1              # via apscheduler, django, pandas, tzlocal, zeep
pyyaml==5.3.1             # via dparse, pre-commit, tablib
redis==3.5.3              # via -r requirements.in
regex==2020.7.14          # via black
requests-mock==1.8.0      # via -r requirements.in
requests-oauthlib==1.3.0  # via -r requirements.in
requests-toolbelt==0.9.1  # via zeep
requests==2.24.0          # via -r requirements.in, django-oauth-toolkit, gql, postcode.io, requests-mock, requests-oauthlib, requests-toolbelt, safety, smartcar, zeep
rx==1.6.1                 # via graphql-core
s3transfer==0.3.3         # via boto3
safety==1.9.0             # via -r requirements.in
scipy==1.5.2              # via -r requirements.in
scraperapi-sdk==0.2.2     # via -r requirements.in
sentry-sdk==0.17.7        # via -r requirements.in
service-identity==18.1.0  # via twisted
setproctitle==1.1.10      # via -r requirements.in
simplejson==3.17.2        # via -r requirements.in
six==1.15.0               # via apscheduler, automat, cryptography, gql, graphql-core, html5lib, isodate, jsonschema, packaging, pip-tools, promise, pyopenssl, python-dateutil, requests-mock, virtualenv, webtest, zeep
slackclient==2.9.1        # via -r requirements.in
smartcar==4.3.2           # via -r requirements.in
soupsieve==2.0.1          # via beautifulsoup4
sqlparse==0.3.1           # via django, django-debug-toolbar
tablib[html,ods,xls,xlsx,yaml]==2.0.0  # via django-import-export
tabulate==0.8.7           # via -r requirements.in
tblib==1.7.0              # via -r requirements.in
time-machine==1.2.1       # via -r requirements.in
toml==0.10.1              # via black, curlylint, dparse, pre-commit
traitlets==5.0.4          # via ipython
twisted[tls]==20.3.0      # via daphne
txaio==20.4.1             # via autobahn
typed-ast==1.4.1          # via black, mypy
typing-extensions==3.7.4.3  # via black, mypy
tzlocal==2.1              # via apscheduler
urllib3==1.25.10          # via botocore, requests, sentry-sdk
virtualenv==20.0.31       # via pre-commit
waitress==1.4.4           # via webtest
wcwidth==0.2.5            # via prompt-toolkit
webencodings==0.5.1       # via html5lib
webob==1.8.6              # via webtest
webtest==2.0.35           # via django-webtest
whitenoise==5.2.0         # via -r requirements.in
xlrd==1.2.0               # via tablib
xlwt==1.3.0               # via tablib
yarl==1.5.1               # via aiohttp
zeep==3.4.0               # via -r requirements.in
zope.interface==5.1.0     # via twisted

three.txt:

click~=7.1
colorama~=0.4
enlighten~=1.6.1
networkx~=2.3
numpy>=1.17.0
numba>=0.50
orjson~=3.1
pandas~=1.0
pint~=0.13
pyarrow~=0.17
pydantic~=1.5
PyYAML~=5.1
sentry-sdk~=0.15
tabulate>=0.8.7
termcolor~=1.1

Answer 26 · 2020-10-01T20:52:20.000Z

Out of curiousity I tried the code from #8932 on our internal project. Here are the measurements:

pip 20.2.3, old resolver

1.98user 0.12system 0:02.10elapsed 99%CPU (0avgtext+0avgdata 42988maxresident)k
0inputs+8outputs (0major+25881minor)pagefaults 0swaps

pip 20.2.3, new resolver (`--use-feature=2020-resolver`)

83.87user 0.83system 3:52.55elapsed 36%CPU (0avgtext+0avgdata 253360maxresident)k
8936inputs+19304outputs (0major+91814minor)pagefaults 0swaps

#8932 commit `9b21352`, new resolver

3.62user 0.14system 0:03.79elapsed 99%CPU (0avgtext+0avgdata 116760maxresident)k
0inputs+8outputs (0major+44798minor)pagefaults 0swaps

For me the performance appears to be fine now. Thanks for the hard work! 👍

Answer 27 · 2020-10-02T08:40:14.000Z

I can also confirm the performance is way better now. I'm seeing 2.6 seconds for a warm install on 9b21352 , compared to 41.2 seconds on version 20.2.3. 🚀🏇🏎

Answer 28 · 2020-10-07T02:20:49.000Z

Very, very glad that the numbers @pradyunsg gathered indicate that, at worst, we have the new resolver, after the fix in #8932 , taking (at most) 3x as long as the legacy behavior.

Thank you to everyone who helped define this problem, gather data, figure out solutions, and implement them! I should say "helped and is helping" since this is not done yet.

I opened this thread with:

Therefore I believe we need to pull together some extremely rough speed tests and decide what level of speed is acceptable, then build some automated testing to check whether we are meeting those marks.

Is it feasible to set up automated testing to help us keep from getting too slow in the future? Ideally, that would warn us if we hit a certain duration threshold, and fail at a higher threshold?

Answer 29 · 2020-10-21T16:48:33.000Z

@stefanv @sbidoul @minusf @tlandschoff-scale @adamchainz @antoncohen The current release of pip, pip 20.2.4, includes the performance improvements from #8932 and #8912 plus a few other improvements, so please feel free to try it out and to spread the word.

Our current plan is to release pip 20.3, which will have the new resolver as the default, a week from now, around October 28 or 29.

Answer 30 · 2020-10-21T18:10:21.000Z

Thank you very much to the team for taking these concerns seriously and working hard to improve them; I am very happy with the execution speed I'm seeing in 2.2.4! 🚀

Answer 31 · 2020-10-21T18:20:20.000Z

Thank you! My install went from 240+ seconds (4+ minutes) with pip 20.2.3 to 7 seconds with pip 20.2.4 (both with --use-feature=2020-resolver). 👍

Answer 32 · 2020-10-22T07:25:00.000Z

I rechecked the performance with 20.2.4 and it is a stark contrast to pip 20.2.3. Runtime for my typical run is down from 4 minutes to 4 seconds. 👍

Answer 33 · 2020-10-25T12:10:05.000Z

I checked the performance again with pip 20.2.4 and I can confirm what others mentioned above. I posted the output of my reproducer: #8675 (comment). On some more realistic use cases I observe a factor 2 in execution time between the old and new resolver, which remains acceptable in practice. Kudos for this work!

On some python 2 tests I observe a stronger performance degration with the new resolver. At first glance it seems to repeatedly do index lookups for argparse and wsgiref. Not exactly sure what's happening there yet.

Answer 34 · 2020-10-25T12:37:23.000Z

One of the speedups is caching the installed on-disk metadata when the resolver looks for .dist-info directories. That was implemented with stdlib functools.lru_cache() (available only on Python 3). Without the cache, pip would call a get_distributions() function whenever it searches installed distributions, which involves some weird import logic that needs to exclude those two packages (due to pkg_resources quirks). That is probably what you’re seeing. In general we really didn’t spend much time backporting these speedups for old Python versions and took liberty to make things no-op if some of the tools are not available.

Answer 35 · 2020-10-25T12:54:59.000Z

@uranusjr I see thanks for the explanation. Do you think the same reasoning could explain a catastrophic degradation of pip wheel -r requirements.txt --no-deps --use-feature=2020-resolver on python 2, with all wheels in cache ? I'm examining a case right now that seems to take forever (> 3 hours) on python 2, while similar cases work fine on python 3.

Is it the plan to make the new resolver the default for python 2 too ?

Answer 36 · 2020-10-25T15:10:00.000Z

I’m not sure, TBH I don’t really personally use pip wheel much myself (and almost always with --no-deps when I do), and don’t really understand its internals to say what it’s doing differently to cause performance degradation not present in pip install.

Answer 37 · 2020-10-26T07:22:09.000Z

@uranusjr besides the python 2 issue, I see the new resolver has a visible performance impact on pip wheel under python 3 too, even when using --no-deps. I've not had time to dig into the issue enough to pinpoint it. If you are interested I can PM you a reproducer.

Answer 38 · 2020-10-26T14:49:09.000Z

That would be awesome. Are you on Zulip? It should be easiest to DM there since all of the people working on the resolver can be reached.

Answer 39 · 2020-10-26T16:38:44.000Z

I definitely want us to know more and look into the pip wheel performance issue.

Per our Python 2 support policy, pip 20.3 users who are using Python 2 and who have trouble with the new resolver can choose to switch to the old resolver behavior using the flag --use-deprecated=legacy-resolver. Then in pip 21.0 in January 2021 this question will be moot as pip will drop support for Python 2 altogether.

Answer 40 · 2020-10-27T11:19:24.000Z

@sbidoul, may I take a look at the reproducer for pip wheel's performance regression as well?

In addition, I'll be profiling pip's basic functionalities (comparing when legacy and new resolver used) in the next few days. It's for a course at university (scientific communication) so there'll be quite some time and human resource to take a deeper look—is there anything anyone here wants us to focus on, otherwise we'll just go for {install,download,wheel} of the combination of the most popular packages?

Answer 41 · 2020-10-28T09:09:47.000Z

@McSinyx I sent you the reproducer too.

Answer 42 · 2020-11-01T12:06:45.000Z

Update:

@xavfernandez identified a location where we were doing more operations than necessary. Changing that makes the "cold" cases in the example above even faster, since pip was doing an unnecessary re-evaluation. (see #9078 for details)
We've decided to not enable the new resolver by default on Python 2, in pip 20.3. It'll be the last release of pip that'll support Python 2 and we don't want to make potentially disruptive changes for Python 2 users. (see #9019 for the implementation, #9044 for the documentation)
pip 20.3 beta1 is out now! You can install by running pip install --upgrade --pre pip. It uses the new resolver by default. See #8936 (comment) for why it's a beta release, and our plans for making the main 20.3 release in mid-November.

Answer 43 · 2020-11-02T04:53:57.000Z

Based on the benchmarking and progress from the past several weeks I believe pip's performance with the new resolver is now fine to ship as default. Moving to "needs triage" so we can decide whether to close, or to refactor this issue into something more useful for the next phase.

Answer 44 · 2020-11-02T13:34:39.000Z

I believe pip's performance with the new resolver is now fine to ship as default.

My friends and I have just run benchmark and the result agrees with this 100%: as of 20.3.0b1, there's virtually no difference in performance between the two resolver. Here is our poster—it's far from perfect and we would love to have feedback on our work since it's the first time we do a scientific poster. Please feel more than free to use it to promote the new resolver roll-out process!

Answer 45 · 2020-11-12T06:40:25.000Z

The current release of pip, pip 20.2.4, includes the performance improvements from #8932 and #8912 plus a few other improvements, so please feel free to try it out and to spread the word.

I have posted an example where the new resolver in 20.2.4 is about 6 times as slow as the old one (55 vs 9 seconds) in #9126. This difference is down to less than 2 times (16 seconds) in the current dev version.

Answer 46 · 2020-11-12T08:40:15.000Z

My friends and I have just run benchmark and the result agrees with this 100%: as of 20.3.0b1, there's virtually no difference in performance between the two resolver.

I don't really agree with your summary.

First, your requirement sets are tiny (9 at most), so it's hard to draw conclusion on larger ones as effort may increase superlinearly.

Then, Figure 1. If you disable the download cache, you are including download times in your measurements, and this will dominate execution times.

Finally, Figure 2. I have found no way to use the old resolver in 20.3.0b1, so I think you are comparing apples with basically the same apples. It's no surprise to me you don't see a difference.

Answer 47 · 2020-11-12T11:28:07.000Z

First, your requirement sets are tiny (9 at most), so it's hard to draw conclusion on larger ones as effort may increase superlinearly.

Agreed, the use case I examined is different from your use case: one is what people does on their work stations (incremental installations) and one is recreating an environment. I don't think the poster is anyhow complete but it might give an end-user an idea of what to expect. I suppose for really long requirement sets GH-9082 might be one of the reason for the poorer performance.

If you disable the download cache, you are including download times in your measurements, and this will dominate execution times.

Yes, but apparently 20.2.4 did even more downloads that make it a lot slower in many cases: while in 20.3.0 it's almost the graph if the identity function, 20.2.4 is obviously above it:

(I'm sorry the the graph is not very straightforwardly annotated, it should be interpreted as new resolver performance in 20.2.4 and 20.3.0b1 compared to low resolver performance (which doesn't really change in the last many months.)

I have found no way to use the old resolver in 20.3.0b1

IIRC you can use --use-deprecated=legacy-resolver to force the legacy resolver and FYI the old resolver figures are from 20.2.4, regardless if compared to 20.2.4's or 20.3.0b1's new resolver.

Answer 48 · 2020-11-17T14:37:49.000Z

Just a note as it took me a while to find, you need to install pip version 20.3.0b1 to be able to use the --use-deprecated=legacy-resolver switch.

Answer 49 · 2020-11-30T18:27:46.000Z

Note: I was urged to comment here about our experience from twitter.

We (prefect) are a bit late on testing the new resolver (only getting around to it with the 20.3 release). We're finding that install times are now in the 20+ min range (I've actually never had one finish), previously this was at most a minute or two. The issue here seems to be in the large search space (prefect has loads of optional dependencies, for CI and some docker images we install all of them) coupled with backtracking.

I enabled verbose logs to try to figure out what the offending package(s) were but wasn't able to make much sense of them. I'm seeing a lot of retries for some dependencies with different versions of setuptools, as well as different versions of boto3. For our CI/docker builds we can add constraints to speed things up (as suggested here), but we're reluctant to increase constraints in our setup.py as we don't want to overconstrain downstream users. At the same time, we have plenty of novice users who are used to doing pip install prefect[all_extras] - telling them they need to add additional constraints to make this complete in a reasonable amount of time seems unpleasant. I'm not sure what the best path forward here is.

I've uploaded verbose logs from one run here (killed after several minutes of backtracking). If people want to try this themselves, you can run:

pip install "git+https://github.com/PrefectHQ/prefect.git#egg=prefect[all_extras]"

Any advice here would be helpful - for now we're pinning pip to 20.2.4, but we'd like to upgrade once we've figured out a solution to the above. Happy to provide more logs or try out suggestions as needed.

Thanks for all y'all do on pip and pypa!

Answer 50 · 2020-12-01T16:25:00.000Z

To keep things a bit easier to manage: we're going to have this issue (#8664) be about building automated testing to check for acceptable performance, and we've made #9187 the issue to "centralize incoming reports of situations that seemingly run for a long time" - including the question in #9187 (comment) :

Do we have a good sense of whether these cases where it takes a really long time to solve are typically cases where there is no answer and it's taking a long time to exhaustively search the space because our slow time per candidate means it takes hours.. or are these cases where there is a successful answer, but it just takes us awhile to get there?

Donald moved a relevant comment from here to there #9187 (comment) . Sorry for accidentally misdirecting you @jcrist!

Answer 51 · 2020-12-08T23:41:37.000Z

I just wanted to close the loop here from the SkyPortal side. When the new beta resolver was made available, it was unworkable for us. @brainwane reached out, filed this issue, and within a few months our problems were addressed.

A huge shoutout to the team for soliciting community feedback, taking it seriously, and doing such dedicated work to making pip better. I know that many (most?) of you are volunteers, and your efforts are so appreciated. 🙏

pip 20.2.3, old resolver

pip 20.2.3, new resolver (--use-feature=2020-resolver)

#8932 commit 9b21352, new resolver

pip 20.2.3, new resolver (`--use-feature=2020-resolver`)

#8932 commit `9b21352`, new resolver