Repository: pypa/pip
Pull request #12453 (2023-12-28 15:46:12)

Cache is_satisfied_by
This is a performance improvement for a presumably common use case, namely the installation of a project with locked dependencies using `pip install -c requirements.txt -e .`, in an environment where most dependencies are already installed.

More precisely the case I'm testing is a ~500 lines `requirements.txt`, and running the above command in an environment where all dependencies are already installed. This is typically done by developers when pulling a new version of the project, to ensure their environment is up-to-date.

When running this under py-spy, it appears that `PipProvider.is_satisfied_by` largely dominates the 50 seconds running `resolve()` (out of a total 55 sec execution time).

![image](https://github.com/pypa/pip/assets/692075/534fcc51-3133-4213-9083-7c69a1fecec9)

Some tracing showed that `is_satisfied_by` is repeatedly called for the same requirement and candidate.

So I experimented with some caching. 

The result of this PR is a 40 seconds saving on the 50 sec `resolve()`. The total execution time went down to 15 sec from 55.

![image](https://github.com/pypa/pip/assets/692075/eb032eed-a604-4321-a05f-4fd5efe1c1b4)

I'm opening as draft as there are some possible improvements, but it's ready for comments on the general approach already.

sbidoul: The root cause of the perf issue is likely related to https://github.com/sarugaku/resolvelib/issues/147
pfmoore: +1 on the general approach. Making `InstallRequirement` hashable and comparable in its own right can be a follow-up PR if it's complex (and it looks like it could be complex).

There's a risk of incorrect results caused by two requirements which compare as equal but actually aren't (for example two URL requirements with the same target but different auth data) but I'm assuming that risk is small enough to be acceptable.
pradyunsg: What's the `contains` that dominates `is_satisfied_by`? 
sbidoul: > What's the `contains` that dominates `is_satisfied_by`?

It's from `packaging.specifiers`.
notatallshaw: > The root cause of the perf issue is likely related to [sarugaku/resolvelib#147](https://github.com/sarugaku/resolvelib/issues/147)

Yes, resolvelibs algorithm checks each step if each requirement has been satisfied: https://github.com/sarugaku/resolvelib/blob/1.0.1/src/resolvelib/resolvers.py#L217, called here https://github.com/sarugaku/resolvelib/blob/1.0.1/src/resolvelib/resolvers.py#L409 and here https://github.com/sarugaku/resolvelib/blob/1.0.1/src/resolvelib/resolvers.py#L443.

So for 500 requirements each step will check if each of the 500 requirements have already been resolved, which for yet unpinned requirements involves checking each requirements requirements leading to at least `O(n^2)` behavior. Ideally there would be an algorthmic fix for this, but I've not yet found one.

Also I beleive this PR potentially fixes this users issue https://github.com/pypa/pip/issues/12314 (though reproducing the users results has been challenging).
notatallshaw: By the way for this use case:

> common use case, namely the installation of a project with locked dependencies using pip install -c requirements.txt -e .

I do have a seperate idea that could fix it algorithmically: https://github.com/sarugaku/resolvelib/issues/146. But I've not done any work towards a PR yet, so I can't compare.
notatallshaw: Is there a reason this is still in draft mode? It would be great to see this land this year.
sbidoul: @notatallshaw thanks for the ping. I think this was ready, but it needs double checking for correctness. So I marked it ready for review. I'll add the news entry soon.
notatallshaw: Testing performance today on Python 3.12 with all packages cached (ran the command twice to populate cache) `pip install --dry-run apache-airflow[all]` took ~5 mins 50 seconds on main and ~3 mins 10 seconds on this branch.

This is a huge performance improvement for real world large dependency trees.

Patch:
diff --git a/news/12453.feature.rst b/news/12453.feature.rst
new file mode 100644
index 000000000..704cd012a
--- /dev/null
+++ b/news/12453.feature.rst
@@ -0,0 +1,1 @@
+Improve performance of resolution of large dependency trees, with more caching.
diff --git a/src/pip/_internal/resolution/resolvelib/candidates.py b/src/pip/_internal/resolution/resolvelib/candidates.py
index 49a1f660c..140aaafcb 100644
--- a/src/pip/_internal/resolution/resolvelib/candidates.py
+++ b/src/pip/_internal/resolution/resolvelib/candidates.py
@@ -352,13 +352,13 @@ class AlreadyInstalledCandidate(Candidate):
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}({self.dist!r})"
 
-    def __hash__(self) -> int:
-        return hash((self.__class__, self.name, self.version))
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, AlreadyInstalledCandidate):
+            return NotImplemented
+        return self.name == other.name and self.version == other.version
 
-    def __eq__(self, other: Any) -> bool:
-        if isinstance(other, self.__class__):
-            return self.name == other.name and self.version == other.version
-        return False
+    def __hash__(self) -> int:
+        return hash((self.name, self.version))
 
     @property
     def project_name(self) -> NormalizedName:
diff --git a/src/pip/_internal/resolution/resolvelib/factory.py b/src/pip/_internal/resolution/resolvelib/factory.py
index 781c54fd8..e36df15d4 100644
--- a/src/pip/_internal/resolution/resolvelib/factory.py
+++ b/src/pip/_internal/resolution/resolvelib/factory.py
@@ -3,6 +3,7 @@ import functools
 import logging
 from typing import (
     TYPE_CHECKING,
+    Callable,
     Dict,
     FrozenSet,
     Iterable,
@@ -391,6 +392,7 @@ class Factory:
         incompatibilities: Mapping[str, Iterator[Candidate]],
         constraint: Constraint,
         prefers_installed: bool,
+        is_satisfied_by: Callable[[Requirement, Candidate], bool],
     ) -> Iterable[Candidate]:
         # Collect basic lookup information from the requirements.
         explicit_candidates: Set[Candidate] = set()
@@ -456,7 +458,7 @@ class Factory:
             for c in explicit_candidates
             if id(c) not in incompat_ids
             and constraint.is_satisfied_by(c)
-            and all(req.is_satisfied_by(c) for req in requirements[identifier])
+            and all(is_satisfied_by(req, c) for req in requirements[identifier])
         )
 
     def _make_requirements_from_install_req(
diff --git a/src/pip/_internal/resolution/resolvelib/provider.py b/src/pip/_internal/resolution/resolvelib/provider.py
index 315fb9c89..fb0dd85f1 100644
--- a/src/pip/_internal/resolution/resolvelib/provider.py
+++ b/src/pip/_internal/resolution/resolvelib/provider.py
@@ -1,5 +1,6 @@
 import collections
 import math
+from functools import lru_cache
 from typing import (
     TYPE_CHECKING,
     Dict,
@@ -234,8 +235,10 @@ class PipProvider(_ProviderBase):
             constraint=constraint,
             prefers_installed=(not _eligible_for_upgrade(identifier)),
             incompatibilities=incompatibilities,
+            is_satisfied_by=self.is_satisfied_by,
         )
 
+    @lru_cache(maxsize=None)
     def is_satisfied_by(self, requirement: Requirement, candidate: Candidate) -> bool:
         return requirement.is_satisfied_by(candidate)
 
diff --git a/src/pip/_internal/resolution/resolvelib/requirements.py b/src/pip/_internal/resolution/resolvelib/requirements.py
index 4af4a9f25..f980a356f 100644
--- a/src/pip/_internal/resolution/resolvelib/requirements.py
+++ b/src/pip/_internal/resolution/resolvelib/requirements.py
@@ -1,3 +1,5 @@
+from typing import Any
+
 from pip._vendor.packaging.specifiers import SpecifierSet
 from pip._vendor.packaging.utils import NormalizedName, canonicalize_name
 
@@ -17,6 +19,14 @@ class ExplicitRequirement(Requirement):
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}({self.candidate!r})"
 
+    def __hash__(self) -> int:
+        return hash(self.candidate)
+
+    def __eq__(self, other: Any) -> bool:
+        if not isinstance(other, ExplicitRequirement):
+            return False
+        return self.candidate == other.candidate
+
     @property
     def project_name(self) -> NormalizedName:
         # No need to canonicalize - the candidate did this
@@ -49,6 +59,14 @@ class SpecifierRequirement(Requirement):
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}({str(self._ireq.req)!r})"
 
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, SpecifierRequirement):
+            return NotImplemented
+        return str(self._ireq) == str(other._ireq)
+
+    def __hash__(self) -> int:
+        return hash(str(self._ireq))
+
     @property
     def project_name(self) -> NormalizedName:
         assert self._ireq.req, "Specifier-backed ireq is always PEP 508"
@@ -98,12 +116,21 @@ class SpecifierWithoutExtrasRequirement(SpecifierRequirement):
         self._ireq = install_req_drop_extras(ireq)
         self._extras = frozenset(canonicalize_name(e) for e in self._ireq.extras)
 
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, SpecifierWithoutExtrasRequirement):
+            return NotImplemented
+        return str(self._ireq) == str(other._ireq)
+
+    def __hash__(self) -> int:
+        return hash(str(self._ireq))
+
 
 class RequiresPythonRequirement(Requirement):
     """A requirement representing Requires-Python metadata."""
 
     def __init__(self, specifier: SpecifierSet, match: Candidate) -> None:
         self.specifier = specifier
+        self._specifier_string = str(specifier)  # for faster __eq__
         self._candidate = match
 
     def __str__(self) -> str:
@@ -112,6 +139,17 @@ class RequiresPythonRequirement(Requirement):
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}({str(self.specifier)!r})"
 
+    def __hash__(self) -> int:
+        return hash((self._specifier_string, self._candidate))
+
+    def __eq__(self, other: Any) -> bool:
+        if not isinstance(other, RequiresPythonRequirement):
+            return False
+        return (
+            self._specifier_string == other._specifier_string
+            and self._candidate == other._candidate
+        )
+
     @property
     def project_name(self) -> NormalizedName:
         return self._candidate.project_name
@@ -148,6 +186,14 @@ class UnsatisfiableRequirement(Requirement):
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}({str(self._name)!r})"
 
+    def __eq__(self, other: object) -> bool:
+        if not isinstance(other, UnsatisfiableRequirement):
+            return NotImplemented
+        return self._name == other._name
+
+    def __hash__(self) -> int:
+        return hash(self._name)
+
     @property
     def project_name(self) -> NormalizedName:
         return self._name


Test patch:
diff --git a/tests/unit/resolution_resolvelib/test_requirement.py b/tests/unit/resolution_resolvelib/test_requirement.py
index b8cd13cb5..b7b0395b0 100644
--- a/tests/unit/resolution_resolvelib/test_requirement.py
+++ b/tests/unit/resolution_resolvelib/test_requirement.py
@@ -23,6 +23,14 @@ from tests.lib import TestData
 #   Editables
 
 
+def _is_satisfied_by(requirement: Requirement, candidate: Candidate) -> bool:
+    """A helper function to check if a requirement is satisfied by a candidate.
+
+    Used for mocking PipProvider.is_satified_by.
+    """
+    return requirement.is_satisfied_by(candidate)
+
+
 @pytest.fixture
 def test_cases(data: TestData) -> Iterator[List[Tuple[str, str, int]]]:
     def _data_file(name: str) -> Path:
@@ -80,6 +88,7 @@ def test_new_resolver_correct_number_of_matches(
             {},
             Constraint.empty(),
             prefers_installed=False,
+            is_satisfied_by=_is_satisfied_by,
         )
         assert sum(1 for _ in matches) == match_count
 
@@ -98,6 +107,7 @@ def test_new_resolver_candidates_match_requirement(
             {},
             Constraint.empty(),
             prefers_installed=False,
+            is_satisfied_by=_is_satisfied_by,
         )
         for c in candidates:
             assert isinstance(c, Candidate)