Skip to content

Reserve arena iterator capacity#68

Merged
charliermarsh merged 1 commit into
mainfrom
charlie/codex-reserve-arena-iterator-capacity
Jun 29, 2026
Merged

Reserve arena iterator capacity#68
charliermarsh merged 1 commit into
mainfrom
charlie/codex-reserve-arena-iterator-capacity

Conversation

@charliermarsh

@charliermarsh charliermarsh commented Jun 29, 2026

Copy link
Copy Markdown
Member

What

Arena::alloc_iter now reserves the iterator's size_hint lower bound before appending its values. The lower bound is guaranteed to be available from the iterator, so this gives the backing Vec enough 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.

@codspeed-hq

codspeed-hq Bot commented Jun 29, 2026

Copy link
Copy Markdown

Merging this PR will not alter performance

✅ 6 untouched benchmarks


Comparing charlie/codex-reserve-arena-iterator-capacity (2edbcd3) with main (cfe9498)

Open in CodSpeed

@charliermarsh charliermarsh changed the title [codex] Reserve arena iterator capacity Reserve arena iterator capacity Jun 29, 2026
@charliermarsh charliermarsh marked this pull request as ready for review June 29, 2026 13:12
@charliermarsh charliermarsh merged commit 7c5a0eb into main Jun 29, 2026
11 checks passed
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant