Reserve arena iterator capacity#68
Merged
charliermarsh merged 1 commit intoJun 29, 2026
Merged
Conversation
charliermarsh
added a commit
that referenced
this pull request
Jun 29, 2026
## What Dependency incompatibilities now store only the dependent and dependency package IDs in `Kind::FromDependencyOf`. The corresponding version sets are moved directly into the incompatibility terms instead of being cloned into both representations, and the unchanged four-field `External::FromDependencyOf` report is reconstructed from those terms on the cold error-reporting path. The latest `main` branch also indexes merge candidates by dependency-range hash. To preserve that behavior without restoring a clone or adding another field to every incompatibility, `as_dependency` borrows the optional dependency range from the terms and the merge cache hashes that optional reference. Empty dependencies remain represented by an omitted negative term; self-dependencies, duplicate dependencies, merged dependents, iteration order, and public `Incompatibility::iter` behavior are preserved. This changes the public `Kind::FromDependencyOf` variant from four fields to two, so it is intended for a 0.5.0-or-later release. [The dependent uv draft](astral-sh/uv#20048) updates the four consumer matches and temporarily pins this commit. ## Why `Incompatibility::from_dependency` is on the dependency-construction hot path. Previously, it cloned both version sets into `Kind` even though the same sets were already owned by `package_terms`. With clone-counting coverage, the constructor now performs zero `VersionSet` clones for both empty and non-empty dependencies. The clone-removal mechanism was measured against the independent [reserve-only control](#68) over five CodSpeed CPU-simulation samples: | Benchmark | Reserve-only control | Clone removal | Change | | --- | ---: | ---: | ---: | | `sudoku-easy` | 4.70 ms | 3.55 ms | 24.47% faster | | `sudoku-hard` | 4.86 ms | 4.17 ms | 14.20% faster | Against the original baseline, the cumulative candidate was 26.35% faster on `sudoku-easy` and 18.87% faster on `sudoku-hard`. `backtracking_ranges` moved from 1.89 s to 1.90 s, a disclosed 0.53% regression; the other measured benchmarks were neutral to modestly faster. [Representative CodSpeed report](https://app.codspeed.io/astral-sh/pubgrub/runs/6a41c50ad94dafe8c8334e3a). The full workspace and focused semantic tests pass, including zero-clone construction, empty and self-dependencies, duplicate term ordering, derivation-tree reconstruction, merged ranges, and package self-dependency behavior. Strict Clippy, formatting, documentation, and diff checks also pass. The small latest-main merge-cache adaptation is integration-only and was not measured separately from the validated clone-removal mechanism.
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
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.
What
Arena::alloc_iternow reserves the iterator'ssize_hintlower bound before appending its values. The lower bound is guaranteed to be available from the iterator, so this gives the backingVecenough room for at least the known items while preserving normal growth if the iterator yields more. Allocation order, duplicate values, returned ID ranges, and empty iterators are unchanged.Why
PubGrub allocates batches of incompatibilities through this path. Appending a known-size batch one item at a time can otherwise grow the arena repeatedly as it crosses capacity boundaries. Reserving once avoids that geometric reallocation and copying without changing the allocator, build profile, or public API.