Skip to content

Commit c8d39cb

Browse files
Avoid materializing complements during resolution (#20982)
More performance updates from nab, and the uv side of astral-sh/pubgrub#77. This forwards `difference` through uv's `Range` wrapper for both the encoded and canonical representations, and uses it in the batch prefetcher in place of intersecting with complements. The second commit temporarily pins the pubgrub crates to that branch so the change builds end to end, and is dropped once the crates release. On my machine I observed some small speed ups in conflict heavy scenarios: | resolve | wall time | |---|---| | `pip compile` boto3+awscli, `--python-version 3.6` | -3.5 to -3.9% | | `lock` boto3+awscli | -2.8 to -3.6% | | `pip compile` airflow[all], `--python-version 3.8` | no change | | small warm resolves | no change | --------- Co-authored-by: konstin <[email protected]>
1 parent 544157b commit c8d39cb

4 files changed

Lines changed: 26 additions & 10 deletions

File tree

‎Cargo.lock‎

Lines changed: 4 additions & 4 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎Cargo.toml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -186,7 +186,7 @@ percent-encoding = { version = "2.3.1" }
186186
petgraph = { version = "0.8.0" }
187187
proc-macro2 = { version = "1.0.86" }
188188
procfs = { version = "0.18.0", default-features = false, features = ["flate2"] }
189-
pubgrub = { version = "0.6.0", package = "astral-pubgrub" }
189+
pubgrub = { version = "0.6.1", package = "astral-pubgrub" }
190190
quote = { version = "1.0.37" }
191191
rand = { version = "0.9.4" }
192192
rayon = { version = "1.10.0" }
@@ -286,7 +286,7 @@ unicode-width = { version = "0.2.0" }
286286
unscanny = { version = "0.1.0" }
287287
url = { version = "2.5.2", features = ["serde"] }
288288
uuid = { version = "1.16.0" }
289-
version-ranges = { version = "0.2.1", package = "astral-version-ranges" }
289+
version-ranges = { version = "0.2.2", package = "astral-version-ranges" }
290290
walkdir = { version = "2.5.0" }
291291
webpki-root-certs = { version = "1" }
292292
which = { version = "8.0.0", features = ["regex"] }

‎crates/uv-resolver/src/pubgrub/range.rs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -176,6 +176,10 @@ impl Range<Version> {
176176
self.binary_op(other, Ranges::intersection)
177177
}
178178

179+
pub(crate) fn difference(&self, other: &Self) -> Self {
180+
self.binary_op(other, Ranges::difference)
181+
}
182+
179183
pub(crate) fn union(&self, other: &Self) -> Self {
180184
self.binary_op(other, Ranges::union)
181185
}
@@ -235,6 +239,10 @@ impl VersionSet for Range<Version> {
235239
Self::intersection(self, other)
236240
}
237241

242+
fn difference(&self, other: &Self) -> Self {
243+
Self::difference(self, other)
244+
}
245+
238246
fn contains(&self, version: &Self::V) -> bool {
239247
self.encoded_versions.contains(version)
240248
}
@@ -369,6 +377,15 @@ mod tests {
369377
for right in &ranges {
370378
assert_matches_recanonicalized(&left.intersection(right));
371379
assert_matches_recanonicalized(&left.union(right));
380+
assert_matches_recanonicalized(&left.difference(right));
381+
assert_eq!(
382+
left.difference(right),
383+
left.intersection(&right.complement())
384+
);
385+
assert_eq!(
386+
left.difference(right).encoded_versions(),
387+
left.intersection(&right.complement()).encoded_versions()
388+
);
372389
}
373390
}
374391
}

‎crates/uv-resolver/src/resolver/batch_prefetch.rs‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -231,9 +231,8 @@ impl BatchPrefetcherRunner {
231231
if let Some(candidate) =
232232
selector.select_no_preference(name, &compatible, version_map, env)
233233
{
234-
let compatible = compatible.intersection(
235-
&Range::singleton(candidate.version().clone()).complement(),
236-
);
234+
let compatible =
235+
compatible.difference(&Range::singleton(candidate.version().clone()));
237236
phase = BatchPrefetchStrategy::Compatible {
238237
compatible,
239238
previous: candidate.version().clone(),
@@ -259,7 +258,7 @@ impl BatchPrefetcherRunner {
259258
range = match unchangeable_constraints {
260259
Term::Positive(constraints) => range.intersection(constraints),
261260
Term::Negative(negative_constraints) => {
262-
range.intersection(&negative_constraints.complement())
261+
range.difference(negative_constraints)
263262
}
264263
};
265264
}

0 commit comments

Comments
 (0)