add Option<MarkerTree> to PubGrubPackage#3673
Merged
BurntSushi merged 6 commits intomainfrom May 20, 2024
Merged
Conversation
I'm planning to add another field here (markers), which puts a lot of stress on the positional approach. So let's just switch over to named fields.
It looks like the last vestiges of `Derivative` were removed in commit 7eaed07, but the then rendered superfluous `derive(Derivative)` wasn't removed.
It turns out that we use PubGrubPackage as the key in hashmaps in a fair few places. And when we iterate over hashmaps, the order is unspecified. This can in turn result in changes in output as a result of changes in the PubGrubPackage definition, purely as a function of its changing hash. This is confusing as there should be no semantic difference. Thus, this is a precursor to introducing some more determinism to places I found in the error reporting whose output depending on hashmap iteration order.
This makes use of the newly added `Ord` impl on `PubGrubPackage` to make the output of `format_terms` independent of hashmap iteration order. This was already collecting the terms into an intermediate `Vec`, so sorting probably isn't going to add any significant overhead here. (Plus, this is only running when formatting an error message after a solution could not be found, so an extra sort doesn't seem like a big deal here.) Note that some tests are updated in this commit as a result of this change. As far as I can tell, the semantic meaning of the output remains the same. But the order of the listed packages does not. Specific thing motivating this change is, in a subsequent, I added `Option<MarkerTree>` to `PubGrubPackage::Package`, and this caused similar changes in test output. So I backtracked and isolated this change from the addition of `Option<MarkerTree>`.
Since we're adding a `Option<MarkerTree>` to `PubGrubPackage`, and since we just make `PubGrubPackage` implement `Ord`, it follows that we want `MarkerTree` to also implement `Ord`.
This just adds the field to the type and always sets it to `None`. There are semantic changes in this commit. Closes #3359
charliermarsh
approved these changes
May 20, 2024
Member
charliermarsh
left a comment
There was a problem hiding this comment.
This all looks reasonable to me. Thanks for splitting it out.
konstin
added a commit
that referenced
this pull request
May 21, 2024
Pubgrub stores incompatibilities as (package name, version range) tuples, meaning it needs to clone the package name for each incompatibility, and each non-borrowed operation on incompatibilities. #3673 made me realize that `PubGrubPackage` has gotten large (expensive to copy), so like `Version` and other structs, i've added an `Arc` wrapper around it. ## Benchmarks It looks like this matters most for complex resolutions which, i assume because they carry larger `PubGrubPackageInner::Package` and `PubGrubPackageInner::Extra` types. ```bash hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/jupyter.in" "./uv-branch pip compile -q ./scripts/requirements/jupyter.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/airflow.in" "./uv-branch pip compile -q ./scripts/requirements/airflow.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/boto3.in" "./uv-branch pip compile -q ./scripts/requirements/boto3.in" ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 18.2 ms ± 1.6 ms [User: 14.4 ms, System: 26.0 ms] Range (min … max): 15.8 ms … 22.5 ms 181 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 17.8 ms ± 1.4 ms [User: 14.4 ms, System: 25.3 ms] Range (min … max): 15.4 ms … 23.1 ms 159 runs Summary ./uv-branch pip compile -q ./scripts/requirements/jupyter.in ran 1.02 ± 0.12 times faster than ./uv-main pip compile -q ./scripts/requirements/jupyter.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 153.7 ms ± 3.5 ms [User: 165.2 ms, System: 157.6 ms] Range (min … max): 150.4 ms … 163.0 ms 19 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 123.9 ms ± 4.6 ms [User: 152.4 ms, System: 133.8 ms] Range (min … max): 118.4 ms … 138.1 ms 24 runs Summary ./uv-branch pip compile -q ./scripts/requirements/airflow.in ran 1.24 ± 0.05 times faster than ./uv-main pip compile -q ./scripts/requirements/airflow.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 327.0 ms ± 3.8 ms [User: 344.5 ms, System: 71.6 ms] Range (min … max): 322.7 ms … 334.6 ms 10 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 311.2 ms ± 3.1 ms [User: 339.3 ms, System: 63.1 ms] Range (min … max): 307.8 ms … 317.0 ms 10 runs Summary ./uv-branch pip compile -q ./scripts/requirements/boto3.in ran 1.05 ± 0.02 times faster than ./uv-main pip compile -q ./scripts/requirements/boto3.in ```
konstin
added a commit
that referenced
this pull request
May 21, 2024
Pubgrub stores incompatibilities as (package name, version range) tuples, meaning it needs to clone the package name for each incompatibility, and each non-borrowed operation on incompatibilities. #3673 made me realize that `PubGrubPackage` has gotten large (expensive to copy), so like `Version` and other structs, i've added an `Arc` wrapper around it. It's a pity clippy forbids `.deref()`, it's less opaque than `&**` and has IDE support (clicking on `.deref()` jumps to the right impl). ## Benchmarks It looks like this matters most for complex resolutions which, i assume because they carry larger `PubGrubPackageInner::Package` and `PubGrubPackageInner::Extra` types. ```bash hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/jupyter.in" "./uv-branch pip compile -q ./scripts/requirements/jupyter.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/airflow.in" "./uv-branch pip compile -q ./scripts/requirements/airflow.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/boto3.in" "./uv-branch pip compile -q ./scripts/requirements/boto3.in" ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 18.2 ms ± 1.6 ms [User: 14.4 ms, System: 26.0 ms] Range (min … max): 15.8 ms … 22.5 ms 181 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 17.8 ms ± 1.4 ms [User: 14.4 ms, System: 25.3 ms] Range (min … max): 15.4 ms … 23.1 ms 159 runs Summary ./uv-branch pip compile -q ./scripts/requirements/jupyter.in ran 1.02 ± 0.12 times faster than ./uv-main pip compile -q ./scripts/requirements/jupyter.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 153.7 ms ± 3.5 ms [User: 165.2 ms, System: 157.6 ms] Range (min … max): 150.4 ms … 163.0 ms 19 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 123.9 ms ± 4.6 ms [User: 152.4 ms, System: 133.8 ms] Range (min … max): 118.4 ms … 138.1 ms 24 runs Summary ./uv-branch pip compile -q ./scripts/requirements/airflow.in ran 1.24 ± 0.05 times faster than ./uv-main pip compile -q ./scripts/requirements/airflow.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 327.0 ms ± 3.8 ms [User: 344.5 ms, System: 71.6 ms] Range (min … max): 322.7 ms … 334.6 ms 10 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 311.2 ms ± 3.1 ms [User: 339.3 ms, System: 63.1 ms] Range (min … max): 307.8 ms … 317.0 ms 10 runs Summary ./uv-branch pip compile -q ./scripts/requirements/boto3.in ran 1.05 ± 0.02 times faster than ./uv-main pip compile -q ./scripts/requirements/boto3.in ```
konstin
added a commit
that referenced
this pull request
May 21, 2024
Pubgrub stores incompatibilities as (package name, version range) tuples, meaning it needs to clone the package name for each incompatibility, and each non-borrowed operation on incompatibilities. #3673 made me realize that `PubGrubPackage` has gotten large (expensive to copy), so like `Version` and other structs, i've added an `Arc` wrapper around it. It's a pity clippy forbids `.deref()`, it's less opaque than `&**` and has IDE support (clicking on `.deref()` jumps to the right impl). ## Benchmarks It looks like this matters most for complex resolutions which, i assume because they carry larger `PubGrubPackageInner::Package` and `PubGrubPackageInner::Extra` types. ```bash hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/jupyter.in" "./uv-branch pip compile -q ./scripts/requirements/jupyter.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/airflow.in" "./uv-branch pip compile -q ./scripts/requirements/airflow.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/boto3.in" "./uv-branch pip compile -q ./scripts/requirements/boto3.in" ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 18.2 ms ± 1.6 ms [User: 14.4 ms, System: 26.0 ms] Range (min … max): 15.8 ms … 22.5 ms 181 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 17.8 ms ± 1.4 ms [User: 14.4 ms, System: 25.3 ms] Range (min … max): 15.4 ms … 23.1 ms 159 runs Summary ./uv-branch pip compile -q ./scripts/requirements/jupyter.in ran 1.02 ± 0.12 times faster than ./uv-main pip compile -q ./scripts/requirements/jupyter.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 153.7 ms ± 3.5 ms [User: 165.2 ms, System: 157.6 ms] Range (min … max): 150.4 ms … 163.0 ms 19 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 123.9 ms ± 4.6 ms [User: 152.4 ms, System: 133.8 ms] Range (min … max): 118.4 ms … 138.1 ms 24 runs Summary ./uv-branch pip compile -q ./scripts/requirements/airflow.in ran 1.24 ± 0.05 times faster than ./uv-main pip compile -q ./scripts/requirements/airflow.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 327.0 ms ± 3.8 ms [User: 344.5 ms, System: 71.6 ms] Range (min … max): 322.7 ms … 334.6 ms 10 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 311.2 ms ± 3.1 ms [User: 339.3 ms, System: 63.1 ms] Range (min … max): 307.8 ms … 317.0 ms 10 runs Summary ./uv-branch pip compile -q ./scripts/requirements/boto3.in ran 1.05 ± 0.02 times faster than ./uv-main pip compile -q ./scripts/requirements/boto3.in ```
konstin
added a commit
that referenced
this pull request
May 21, 2024
Pubgrub stores incompatibilities as (package name, version range) tuples, meaning it needs to clone the package name for each incompatibility, and each non-borrowed operation on incompatibilities. #3673 made me realize that `PubGrubPackage` has gotten large (expensive to copy), so like `Version` and other structs, i've added an `Arc` wrapper around it. It's a pity clippy forbids `.deref()`, it's less opaque than `&**` and has IDE support (clicking on `.deref()` jumps to the right impl). ## Benchmarks It looks like this matters most for complex resolutions which, i assume because they carry larger `PubGrubPackageInner::Package` and `PubGrubPackageInner::Extra` types. ```bash hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/jupyter.in" "./uv-branch pip compile -q ./scripts/requirements/jupyter.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/airflow.in" "./uv-branch pip compile -q ./scripts/requirements/airflow.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/boto3.in" "./uv-branch pip compile -q ./scripts/requirements/boto3.in" ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 18.2 ms ± 1.6 ms [User: 14.4 ms, System: 26.0 ms] Range (min … max): 15.8 ms … 22.5 ms 181 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 17.8 ms ± 1.4 ms [User: 14.4 ms, System: 25.3 ms] Range (min … max): 15.4 ms … 23.1 ms 159 runs Summary ./uv-branch pip compile -q ./scripts/requirements/jupyter.in ran 1.02 ± 0.12 times faster than ./uv-main pip compile -q ./scripts/requirements/jupyter.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 153.7 ms ± 3.5 ms [User: 165.2 ms, System: 157.6 ms] Range (min … max): 150.4 ms … 163.0 ms 19 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 123.9 ms ± 4.6 ms [User: 152.4 ms, System: 133.8 ms] Range (min … max): 118.4 ms … 138.1 ms 24 runs Summary ./uv-branch pip compile -q ./scripts/requirements/airflow.in ran 1.24 ± 0.05 times faster than ./uv-main pip compile -q ./scripts/requirements/airflow.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 327.0 ms ± 3.8 ms [User: 344.5 ms, System: 71.6 ms] Range (min … max): 322.7 ms … 334.6 ms 10 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 311.2 ms ± 3.1 ms [User: 339.3 ms, System: 63.1 ms] Range (min … max): 307.8 ms … 317.0 ms 10 runs Summary ./uv-branch pip compile -q ./scripts/requirements/boto3.in ran 1.05 ± 0.02 times faster than ./uv-main pip compile -q ./scripts/requirements/boto3.in ```
konstin
added a commit
that referenced
this pull request
May 21, 2024
Pubgrub stores incompatibilities as (package name, version range) tuples, meaning it needs to clone the package name for each incompatibility, and each non-borrowed operation on incompatibilities. #3673 made me realize that `PubGrubPackage` has gotten large (expensive to copy), so like `Version` and other structs, i've added an `Arc` wrapper around it. It's a pity clippy forbids `.deref()`, it's less opaque than `&**` and has IDE support (clicking on `.deref()` jumps to the right impl). ## Benchmarks It looks like this matters most for complex resolutions which, i assume because they carry larger `PubGrubPackageInner::Package` and `PubGrubPackageInner::Extra` types. ```bash hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/jupyter.in" "./uv-branch pip compile -q ./scripts/requirements/jupyter.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/airflow.in" "./uv-branch pip compile -q ./scripts/requirements/airflow.in" hyperfine --warmup 5 "./uv-main pip compile -q ./scripts/requirements/boto3.in" "./uv-branch pip compile -q ./scripts/requirements/boto3.in" ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 18.2 ms ± 1.6 ms [User: 14.4 ms, System: 26.0 ms] Range (min … max): 15.8 ms … 22.5 ms 181 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/jupyter.in Time (mean ± σ): 17.8 ms ± 1.4 ms [User: 14.4 ms, System: 25.3 ms] Range (min … max): 15.4 ms … 23.1 ms 159 runs Summary ./uv-branch pip compile -q ./scripts/requirements/jupyter.in ran 1.02 ± 0.12 times faster than ./uv-main pip compile -q ./scripts/requirements/jupyter.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 153.7 ms ± 3.5 ms [User: 165.2 ms, System: 157.6 ms] Range (min … max): 150.4 ms … 163.0 ms 19 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/airflow.in Time (mean ± σ): 123.9 ms ± 4.6 ms [User: 152.4 ms, System: 133.8 ms] Range (min … max): 118.4 ms … 138.1 ms 24 runs Summary ./uv-branch pip compile -q ./scripts/requirements/airflow.in ran 1.24 ± 0.05 times faster than ./uv-main pip compile -q ./scripts/requirements/airflow.in ``` ``` Benchmark 1: ./uv-main pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 327.0 ms ± 3.8 ms [User: 344.5 ms, System: 71.6 ms] Range (min … max): 322.7 ms … 334.6 ms 10 runs Benchmark 2: ./uv-branch pip compile -q ./scripts/requirements/boto3.in Time (mean ± σ): 311.2 ms ± 3.1 ms [User: 339.3 ms, System: 63.1 ms] Range (min … max): 307.8 ms … 317.0 ms 10 runs Summary ./uv-branch pip compile -q ./scripts/requirements/boto3.in ran 1.05 ± 0.02 times faster than ./uv-main pip compile -q ./scripts/requirements/boto3.in ``` <!-- Thank you for contributing to uv! To help us out with reviewing, please consider the following: - Does this pull request include a summary of the change? (See below.) - Does this pull request include a descriptive title? - Does this pull request include references to any relevant issues? -->
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
I'm plucking this off my WIP of resolver forking since it grew to
a fairly sizable change on its own. In this PR, all we do is add
Option<MarkerTree>toPubGrubPackage, but otherwise don't do anysemantic changes.
While conceptually simple, adding this tripped some test failures as a
result of the output depending on hashmap iteration order. So part of
this PR is devoted to removing that dependency and making the output
independent of hashmap iteration order.
I took the approach of making
PubGrubPackageimplementOrd. This inturn required implementing
Ordfor a number of other types. So thisfeels like a somewhat invasive change, although I did feel like all of
the
Ordimpls "made sense" for the types they were being added to.Reviewing this PR commit-by-commit should be much easier than looking
at the full diff.
Closes #3359