New Resolver: Be less eager about hitting the network

[pradyunsg]

pip's new resolver is hitting the network even when the currently installed version does satisfy the version requested. Further, it's also includes 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.

Originally posted by @pradyunsg in #8664 (comment)

[uranusjr]

it's also includes 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.

I thought the networking implementation already handles caching on this? I recall reviewing a PR to add lru_cache on the index page parsing function.

[pradyunsg]

Output from running w/ -r /tmp/foo.txt with pinned packages being already installed.

/tmp/foo.txt is from #8664 (comment).

Even though the page parsing code has lru_cache, what's happening is we're reaching out over the network even though we've seen the page, due to the way we're handling max_age on the pages in the download cache stuff.

[pfmoore]

I'm not sure it's "just" network hits. The new resolver checks multiple times for the same requirement:

>pip install -r .\repro.txt --use-feature=2020-resolver | wc -l
370
>pip install -r .\repro.txt | wc -l
164

An example:

>pip install -r .\repro.txt | grep automat
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from -r .\repro.txt (line 16)) (20.2.0)
>pip install -r .\repro.txt --use-feature=2020-resolver | grep automat
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from -r .\repro.txt (line 16)) (20.2.0)
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from -r .\repro.txt (line 16)) (20.2.0)
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from -r .\repro.txt (line 16)) (20.2.0)

Also, putting a memory cache on _get_html_response in collector.py (which should in theory remove the bulk of repeated network request costs) made very little difference to the runtime.

[pradyunsg]

The new resolver checks multiple times for the same requirement:

That's expected, since it'll reach the requirement from multiple edges of the graph.

putting a memory cache on _get_html_response in collector.py (which should in theory remove the bulk of repeated network request costs) made very little difference to the runtime.

OH, huh.

[pradyunsg]

filtered-resolver-log.txt

Adding a debugging reporter to resolvelib (one that does a logger.debug("Reporter.{function_name}({arguments})", {arguments})) results in the above file.

pip install --log /tmp/log.txt -r /tmp/requirements.txt --use-feature=2020-resolver
grep -E "Getting page|Reporter" /tmp/log.txt > /tmp/filtered-resolver-log.txt

Notably, the file is empty when used without the 2020-resolver -- we're not hitting the network at all with the old resolver code. :)

[pfmoore]

Consider the following:

>pip install automat==20.2.0
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (20.2.0)
Requirement already satisfied: attrs>=19.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (20.2.0)
Requirement already satisfied: six in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (1.15.0)

Old resolver checks automat and its 2 dependencies.

>pip install automat==20.2.0 --use-feature=2020-resolver
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (20.2.0)
Requirement already satisfied: six in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (1.15.0)
Requirement already satisfied: attrs>=19.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (20.2.0)

So does new resolver.

>pip install automat==20.2.0 six==1.15.0
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (20.2.0)
Requirement already satisfied: six==1.15.0 in d:\work\projects\pip\.venv\lib\site-packages (1.15.0)
Requirement already satisfied: attrs>=19.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (20.2.0)

Old resolver doesn't re-check six, because it "did it earlier". (Oversimplification, but basically accurate)

>pip install automat==20.2.0 six==1.15.0 --use-feature=2020-resolver
Requirement already satisfied: automat==20.2.0 in d:\work\projects\pip\.venv\lib\site-packages (20.2.0)
Requirement already satisfied: six==1.15.0 in d:\work\projects\pip\.venv\lib\site-packages (1.15.0)
Requirement already satisfied: six==1.15.0 in d:\work\projects\pip\.venv\lib\site-packages (1.15.0)
Requirement already satisfied: attrs>=19.2.0 in d:\work\projects\pip\.venv\lib\site-packages (from automat==20.2.0) (20.2.0)

The new resolver does re-check.

Now multiply that by 161 requirements in the actual example. That's why the old resolver has 160-odd lines and the new has twice as many.

On my machine, the old resolver (160-odd checks) takes around 1-2 seconds. The new resolver with --no-deps takes 15 seconds and also does around 160 checks. That seems to be the cost of the extra complexity (plus the fact that we haven't tuned the new resolver much, yet). Without --no-deps the new resolver outputs twice as many lines, equating to twice as many checks, and takes around 30 seconds.

So I see two main components to the slowdown:

1. Extra complexity and possible wasted time in the new resolver. That doesn't seem linear in the number of requirements. I need to do some more analysis to estimate how it grows, but it's about a 50% increase on one requirement, up to 15x on 160.
2. Additional time because the new resolver checks everything (as it should) whereas the old resolver ignored a lot of requirements.

For (1), it's not surprising that the performance gets worse non-linearly. Dependency resolution algorithms are essentially exponential in performance, so big dependency graphs will be pretty nasty. That's fairly fundamental. The best we can likely do here is to work hard to improve the base performance so that the exponential factor doesn't hurt us quite so soon. But we're going to remain exponential.

For (2), that's fundamentally the cost of correctness. We can't avoid it because the old resolver was "getting away with" simply dropping requirements. Unfortunately (!), it was often safe to do so, so the old resolver seemed to be fast and accurate in many cases (whereas it was actually just fast and lucky!)

Notably, the file is empty when used without the 2020-resolver

OK, it looks like a significant component of (1) is the network hit. That means we probably can significantly improve that base performance by removing the network cost.

[pradyunsg]

Yup to everything you've said. :)

[uranusjr]

what's happening is we're reaching out over the network even though we've seen the page, due to the way we're handling max_age on the pages in the download cache stuff.

Huh. Is there a way to configure requests so we cache responses during one pip command run, but drop the cache once the command ends? Similar to how the browser can set the cache header to “end of session” (iow each pip command run is a session, and cache clears when session ends). This is probably a good thing to do even out of the context of this performance problem—it would be very confusing if a new version becomes available right in the middle of a dependency resolution run.

[pfmoore]

That's what I was hoping that putting a LRU cache on _get_html_response would do but I messed it up somehow. +1 on having everything fetched at most once per run.

[pradyunsg]

I think we prefer the already-installed version, when it satisfies a requirement except when upgrading. Looks like the entire "don't hit the network when the already installed version works" discussion was discussed in #8023.

[uranusjr]

Slapping _lru_cache on PackageFinder.find_all_candidates instead gets me

real  0m47.327s
user  0m35.412s
sys	  0m1.267s

Current performace for comparison:

real  1m25.259s
user  0m59.505s
sys	  0m1.542s

Not nearly as good as the legacy resolver (which is 2s), but probably a good start?

[pradyunsg]

I think skipping the network requests would be give us a much bigger chunk of performance improvement -- but obviously both is best. :P

[pfmoore]

Agreed. But the logic of caching find_all_candidates in my view is that it asserts very clearly that the set of candidates for a project is fixed (for the duration of a pip run) and we can rely on that. So adding a cache makes a statement about semantics.

Not calling find_all_candidates if we don't need to is a different semantic assertion. One we should also do, but logically separate.

[uranusjr]

Also the not calling find_all_candidates part is much more difficult to implement (as discussed in #8023).

[pradyunsg]

Gonna go ahead and close this now, given that #8912 is merged and #8023 covers basically the rest of this issue.