Improve performance of repeated conflicts with an extra by zanieb · Pull Request #18094 · astral-sh/uv

zanieb · 2026-02-18T22:03:55Z

In #18026, we received a report that resolution took >90m and the root cause appears to be that repeated conflicts with a single extra causes an exponential explosion.

I used Codex to find an optimization to avoid this.

When processing N pairwise conflict sets that share a common extra (e.g., {pinned, a}, {pinned, b}, {pinned, c}, ...), the resolver creates forks by iterating over each conflict set and splitting every existing fork into N+1 sub-forks. Without the optimization, this is multiplicative — each conflict set multiplies the fork count, producing O(2^N) forks even though most are redundant.

The key observation is: if a prior conflict set already excluded an extra from a fork, then a later conflict set involving that same extra is already satisfied in that fork — there's nothing left to separate. For example, after processing {pinned, a}, one fork has pinned excluded. When we then process {pinned, b}, that fork already can't have pinned active, so the constraint "at most one of pinned or b" is trivially true. We call this fork dominated by the earlier split — no further forking is needed.

The one subtlety: even if a conflict set is satisfied in a fork, we might still need to fork if the remaining non-excluded item appears in another conflict set that's still live (i.e., has two or more non-excluded items). That's the refined check — we only skip forking when the item is truly dominated across all conflict sets, not just the current one.

I then did some rough benchmarking

 ┌────┬────────┬───────┬─────────┐                                                                       
 │ N  │ Before │ After │ Speedup │                                                                       
 ├────┼────────┼───────┼─────────┤                                                                       
 │ 5  │ 29ms   │ 27ms  │ ~1×     │                                                                       
 ├────┼────────┼───────┼─────────┤                                                                       
 │ 8  │ 58ms   │ 27ms  │ 2×      │                                                                       
 ├────┼────────┼───────┼─────────┤                                                                       
 │ 10 │ 185ms  │ 26ms  │ 7×      │                                                                       
 ├────┼────────┼───────┼─────────┤                                                                       
 │ 15 │ 20.0s  │ 46ms  │ 435×    │                                                                       
 ├────┼────────┼───────┼─────────┤                                                                       
 │ 20 │ >60s   │ 28ms  │ >2,000× │                                                                       
 └────┴────────┴───────┴─────────┘

BurntSushi · 2026-02-19T14:00:17Z

I think this makes sense to me. So to work out an example, if we previously had conflicts {foo, a} and {foo, b}, then we'd get the following forks (without simplifying)?

not foo and not a and not foo and not b
not foo and not a and not foo
not foo and not a and not b
not foo and not foo and not b
not foo and not foo
not foo and not b
not a and not foo and not b
not a and not foo
not a and not b

So I guess the insight here is that since a and b are not conflicting with each other, some of the forks above are not actually necessary. I think that makes sense. I think this PR works by starting with the initial set of forks based on (without loss of generality) {foo, a}:

not foo and not a
not foo
not a

Then when {foo, b} is considered, we have to consider each of the already existing forks:

For not foo and not a, non_excluded contains just b and since b doesn't appear in any other conflict set, dominated is true. Then rules contains not foo (I think) and this fork is filtered by that rule. (This seems superfluous, so perhaps I am misunderstanding here.) No new forks are added.
For not foo, non_excluded contains just b and I think the same logic as above applies. No new forks are added.
For not a, non_excluded contains both foo and b. So the usual forking happens here and we end up with not a and not foo and not b, not a and not foo and not a and not b.

So the final set of forks are:

not foo and not a
not foo
not a and not foo and not b
not a and not foo
not a and not b

Which I think seems right to me?

fkiraly · 2026-02-21T16:28:03Z

I am happy to double check if you explain what a "fork" is in your parlance, and/or point me to a write-up of the algorithm. E.g., what is the SAT problem you are mapping this to?

BurntSushi · 2026-02-24T14:14:23Z

For "fork," this is probably the best reference:

uv/crates/uv-resolver/src/resolver/mod.rs

Lines 3883 to 3921 in 50eb601

    
           /// A single fork in a list of dependencies. 
        
           /// 
        
           /// A fork corresponds to the full list of dependencies for a package, 
        
           /// but with any conflicting dependency specifications omitted. For 
        
           /// example, if we have `a<2 ; sys_platform == 'foo'` and `a>=2 ; 
        
           /// sys_platform == 'bar'`, then because the dependency specifications 
        
           /// have the same name and because the marker expressions are disjoint, 
        
           /// a fork occurs. One fork will contain `a<2` but not `a>=2`, while 
        
           /// the other fork will contain `a>=2` but not `a<2`. 
        
           #[derive(Clone, Debug)] 
        
           struct Fork { 
        
               /// The list of dependencies for this fork, guaranteed to be conflict 
        
               /// free. (i.e., There are no two packages with the same name with 
        
               /// non-overlapping marker expressions.) 
        
               /// 
        
               /// Note that callers shouldn't mutate this sequence directly. Instead, 
        
               /// they should use `add_forked_package` or `add_nonfork_package`. Namely, 
        
               /// it should be impossible for a package with a marker expression that is 
        
               /// disjoint from the marker expression on this fork to be added. 
        
               dependencies: Vec<PubGrubDependency>, 
        
               /// The conflicting groups in this fork. 
        
               /// 
        
               /// This exists to make some access patterns more efficient. Namely, 
        
               /// it makes it easy to check whether there's a dependency with a 
        
               /// particular conflicting group in this fork. 
        
               conflicts: crate::FxHashbrownSet<ConflictItem>, 
        
               /// The resolver environment for this fork. 
        
               /// 
        
               /// Principally, this corresponds to the markers in this for. So in the 
        
               /// example above, the `a<2` fork would have `sys_platform == 'foo'`, while 
        
               /// the `a>=2` fork would have `sys_platform == 'bar'`. 
        
               /// 
        
               /// If this fork was generated from another fork, then this *includes* 
        
               /// the criteria from its parent. i.e., Its marker expression represents 
        
               /// the intersection of the marker expression from its parent and any 
        
               /// additional marker expression generated by addition forking based on 
        
               /// conflicting dependency specifications. 
        
               env: ResolverEnvironment, 
        
           }

As for the actual dependency resolution, we do that via pubgrub which tries to map the problem to the boolean satisfiability problem.

As for a description of our own "forking" algorithm, there is no reference material for that other than the code.

konstin · 2026-02-24T14:52:31Z

There is some now, it's in the docs :) https://docs.astral.sh/uv/reference/internals/resolver/#forking

BurntSushi · 2026-02-24T14:58:00Z

Oh nice! I forgot about that! Thank you.

This MR contains the following updates: | Package | Update | Change | |---|---|---| | [uv](https://github.com/astral-sh/uv) | patch | `0.10.4` → `0.10.6` | MR created with the help of [el-capitano/tools/renovate-bot](https://gitlab.com/el-capitano/tools/renovate-bot). **Proposed changes to behavior should be submitted there as MRs.** --- ### Release Notes <details> <summary>astral-sh/uv (uv)</summary> ### [`v0.10.6`](https://github.com/astral-sh/uv/blob/HEAD/CHANGELOG.md#0106) [Compare Source](astral-sh/uv@0.10.5...0.10.6) Released on 2026-02-24. ##### Bug fixes - Apply lockfile marker normalization for fork markers ([#18116](astral-sh/uv#18116)) - Fix Python version selection for scripts with a `requires-python` conflicting with `.python-version` ([#18097](astral-sh/uv#18097)) - Preserve file permissions when using reflinks on Linux ([#18187](astral-sh/uv#18187)) ##### Documentation - Remove verbose documentation from optional dependencies help text ([#18180](astral-sh/uv#18180)) ### [`v0.10.5`](https://github.com/astral-sh/uv/blob/HEAD/CHANGELOG.md#0105) [Compare Source](astral-sh/uv@0.10.4...0.10.5) Released on 2026-02-23. ##### Enhancements - Add hint when named index is found in a parent config file ([#18087](astral-sh/uv#18087)) - Add warning for `uv lock --frozen` ([#17859](astral-sh/uv#17859)) - Attempt to use reflinks by default on Linux ([#18117](astral-sh/uv#18117)) - Fallback to hardlinks after reflink failure before copying ([#18104](astral-sh/uv#18104)) - Filter `pylock.toml` wheels by tags and `requires-python` ([#18081](astral-sh/uv#18081)) - Validate wheel filenames are normalized during `uv publish` ([#17783](astral-sh/uv#17783)) - Fix message when `exclude-newer` invalidates the lock file ([#18100](astral-sh/uv#18100)) - Change the missing files log level to debug ([#18075](astral-sh/uv#18075)) ##### Performance - Improve performance of repeated conflicts with an extra ([#18094](astral-sh/uv#18094)) ##### Bug fixes - Fix `--no-emit-workspace` with `--all-packages` on single-member workspaces ([#18098](astral-sh/uv#18098)) - Fix `UV_NO_DEFAULT_GROUPS` rejecting truthy values like `1` ([#18057](astral-sh/uv#18057)) - Fix iOS detection ([#17973](astral-sh/uv#17973)) - Propagate project-level conflicts to package extras ([#18096](astral-sh/uv#18096)) - Use a global build concurrency semaphore ([#18054](astral-sh/uv#18054)) ##### Documentation - Update documentation heading for environment variable files ([#18122](astral-sh/uv#18122)) - Fix comment about `uv export` formats ([#17900](astral-sh/uv#17900)) - Make it clear that Windows is supported in user- and system- level configuration docs ([#18106](astral-sh/uv#18106)) </details> --- ### Configuration 📅 **Schedule**: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined). 🚦 **Automerge**: Disabled by config. Please merge this manually once you are satisfied. ♻ **Rebasing**: Whenever MR becomes conflicted, or you tick the rebase/retry checkbox. 🔕 **Ignore**: Close this MR and you won't be reminded about this update again. --- - [ ] If you want to rebase/retry this MR, check this box --- This MR has been generated by [Renovate Bot](https://github.com/renovatebot/renovate).

zanieb added the performance Potential performance improvement label Feb 18, 2026

zanieb force-pushed the zb/fork-repeat branch 2 times, most recently from ac16317 to 28d30d7 Compare February 18, 2026 22:50

zanieb mentioned this pull request Feb 19, 2026

Fix combinatorial explosion in conflicted marker expressions #18099

Closed

Improve performance of repeated conflicts with an extra

24e2ae8

zanieb force-pushed the zb/fork-repeat branch from 28d30d7 to 24e2ae8 Compare February 19, 2026 18:29

Merge branch 'main' into zb/fork-repeat

e6db4cc

zanieb marked this pull request as ready for review February 20, 2026 15:59

zanieb enabled auto-merge (squash) February 20, 2026 15:59

zanieb merged commit f7e9a33 into main Feb 20, 2026
52 checks passed

zanieb deleted the zb/fork-repeat branch February 20, 2026 16:08

BrewTestBot mentioned this pull request Feb 24, 2026

uv 0.10.5 Homebrew/homebrew-core#269129

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve performance of repeated conflicts with an extra#18094

Improve performance of repeated conflicts with an extra#18094
zanieb merged 2 commits intomainfrom
zb/fork-repeat

zanieb commented Feb 18, 2026 •

edited

Loading

Uh oh!

BurntSushi commented Feb 19, 2026

Uh oh!

Uh oh!

fkiraly commented Feb 21, 2026

Uh oh!

BurntSushi commented Feb 24, 2026

Uh oh!

konstin commented Feb 24, 2026

Uh oh!

BurntSushi commented Feb 24, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

zanieb commented Feb 18, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BurntSushi commented Feb 19, 2026

Uh oh!

Uh oh!

fkiraly commented Feb 21, 2026

Uh oh!

BurntSushi commented Feb 24, 2026

Uh oh!

konstin commented Feb 24, 2026

Uh oh!

BurntSushi commented Feb 24, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

zanieb commented Feb 18, 2026 •

edited

Loading