Resolve extras and check marker reachability without DNF by charliermarsh · Pull Request #22608 · astral-sh/uv

charliermarsh · 2026-10-15T19:52:17Z

Summary

We represent markers as decision diagrams, but sometimes convert them to disjunctive normal form (DNF) to perform operations on them. Creating the DNF can be expensive: even a compact diagram can expand into exponentially many clauses.

This PR avoids DNF for two operations by working directly on the diagram:

When exporting, we replace extra markers with the conditions under which those extras are active. For example, extra == 'gpu' might be replaced with sys_platform == 'linux'. We reuse the result for shared parts of the diagram instead of rebuilding every DNF clause. Markers without extra expressions return before we build the replacement map.
When checking whether a marker is reachable, we account for the Python bounds and known platform exclusions directly in the diagram.

We still need DNF when rendering markers.

Related to #21954.

codspeed · 2026-10-15T20:24:31Z

Merging this PR will regress 11 benchmarks

⚠️

1 benchmark measured no execution time

Nothing ran under measurement, usually because the compiler removed the code under test. This result is not comparable, so it counts as unchanged.

Preventing compiler optimizations

imbibe_marker_no_conflicts[0]

⚠️

8 benchmarks spent significant time in system calls

System calls cannot be consistently instrumented, so they are not included in the measure, which understates the real cost. Please switch to the Walltime instrument to accurately measure system calls.

Measurement and system calls

discover_workspace_from_all_members

discover_workspace_from_all_members_with_excludes

install_wheel_many_files

run_python_version_synthetic_workspace

resolve_warm_airflow

resolve_warm_jupyter

resolve_warm_jupyter_universal

unpack_sdist_many_files

⚠️

Different runtime environments detected

Some benchmarks with significant performance changes were compared across different runtime environments,
which may affect the accuracy of the results.

Open the report in CodSpeed to investigate

⚡ 28 improved benchmarks
❌ 11 regressed benchmarks
✅ 80 untouched benchmarks
⏩ 54 skipped benchmarks¹

Warning

Please fix the performance issues or acknowledge them on CodSpeed.

Performance Changes

	Mode	Benchmark	`BASE`	`HEAD`	Efficiency
❌	Simulation	`imbibe_marker_no_conflicts[0]`	287.4 ns	343 ns	-16.2%
❌	Simulation	`finish_blake2b[65536]`	435.1 ms	514.2 ms	-15.39%
❌	Simulation	`imbibe_marker_environment_only[4]`	12.1 µs	14 µs	-13.69%
❌	Simulation	`imbibe_marker_environment_only[32]`	12 µs	13.9 µs	-13.39%
❌	Simulation	`imbibe_marker_environment_only[16]`	12.1 µs	13.9 µs	-13.33%
❌	Simulation	`finish_blake2b[4096]`	522.7 ms	602.5 ms	-13.24%
❌	Simulation	`imbibe_marker_conflict_dependent[32]`	13 µs	14.8 µs	-11.9%
❌	Simulation	`imbibe_marker_conflict_dependent[16]`	13.1 µs	14.8 µs	-11.85%
❌	Simulation	`imbibe_marker_conflict_dependent[4]`	13.2 µs	14.9 µs	-11.77%
❌	WallTime	`imbibe_marker_conflict_dependent[16]`	131 ns	139 ns	-5.76%
❌	WallTime	`imbibe_marker_conflict_dependent[4]`	131 ns	139 ns	-5.76%
⚡	WallTime	`resolve_activated_extras_independent_pairs[8]`	33,159.1 µs	1.2 µs	×27,000
⚡	Simulation	`resolve_activated_extras_independent_pairs[8]`	664,678.1 µs	43.7 µs	×15,000
⚡	WallTime	`resolve_activated_extras_independent_pairs[4]`	62,492 ns	656 ns	×95
⚡	Simulation	`resolve_activated_extras_independent_pairs[4]`	1,191.7 µs	30.7 µs	×39
⚡	WallTime	`resolve_activated_extras_independent_pairs[2]`	2,484 ns	341 ns	×7.3
⚡	Simulation	`resolve_activated_extras_independent_pairs[2]`	70.6 µs	24 µs	×2.9
⚡ ⚠️	Simulation	`discover_workspace_from_all_members`	155.6 ms	122.3 ms	+27.23%
⚡ ⚠️	Simulation	`discover_workspace_from_all_members_with_excludes`	165.3 ms	130.5 ms	+26.71%
⚡	WallTime	`marker_to_dnf_single_clause`	169 ns	134 ns	+26.12%
...	...	...	...	...	...

ℹ️ Only the first 20 benchmarks are displayed. Go to the app to view all benchmarks.

Tip

Investigate this regression by commenting @codspeedbot fix this regression on this PR, or directly use the CodSpeed MCP with your agent.

_{Comparing charlie/direct-marker-transform (50164be) with charlie/bench-conflicting-extras (d53836f)}

54 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

charliermarsh deployed to automations October 15, 2026 19:53 — with GitHub Actions Active

charliermarsh had a problem deploying to automations October 15, 2026 20:25 — with GitHub Actions Error

charliermarsh mentioned this pull request Oct 15, 2026

Skip marker DNF simplification for Boolean transformations #22605

Closed

charliermarsh added this pull request to stack #22609 October 15, 2026 20:27

charliermarsh added the performance label Oct 15, 2026

charliermarsh marked this pull request as ready for review October 15, 2026 20:27

charliermarsh mentioned this pull request Oct 15, 2026

Use bit sets to simplify large marker DNFs #22604

Merged

charliermarsh had a problem deploying to automations October 15, 2026 20:31 — with GitHub Actions Error

charliermarsh removed this pull request from stack #22609 October 15, 2026 20:31

charliermarsh force-pushed the charlie/direct-marker-transform branch from f2cf8c9 to f99cf40 Compare October 15, 2026 20:31

charliermarsh changed the base branch from main to charlie/bench-conflicting-extras October 15, 2026 20:32

charliermarsh added this pull request to stack #22611 October 15, 2026 20:32

charliermarsh had a problem deploying to automations October 15, 2026 20:37 — with GitHub Actions Error

charliermarsh force-pushed the charlie/direct-marker-transform branch from f99cf40 to 51f5610 Compare October 15, 2026 20:40

charliermarsh had a problem deploying to automations October 15, 2026 20:42 — with GitHub Actions Error

charliermarsh force-pushed the charlie/direct-marker-transform branch from 51f5610 to 8f3e5b3 Compare October 15, 2026 20:43

charliermarsh deployed to automations October 15, 2026 20:49 — with GitHub Actions Active

charliermarsh mentioned this pull request Oct 15, 2026

Avoid expanding environment-only conflict markers #22615

Merged

charliermarsh removed this pull request from stack #22611 October 15, 2026 20:58

charliermarsh added this pull request to stack #22616 October 15, 2026 20:58

charliermarsh force-pushed the charlie/direct-marker-transform branch from 8f3e5b3 to d66f9eb Compare October 15, 2026 21:06

charliermarsh deployed to automations October 15, 2026 21:07 — with GitHub Actions Active

charliermarsh force-pushed the charlie/direct-marker-transform branch from d66f9eb to 97ebb1d Compare October 15, 2026 21:18

charliermarsh deployed to automations October 15, 2026 21:20 — with GitHub Actions Active

Resolve extras and check marker reachability without DNF

5324cb0

charliermarsh added 2 commits October 15, 2026 18:56

Replace randomized marker tests with focused cases

5adae19

Fix typo check in marker test

9f461ef

charliermarsh force-pushed the charlie/direct-marker-transform branch from 97ebb1d to 9f461ef Compare October 15, 2026 22:57

charliermarsh deployed to automations October 15, 2026 22:58 — with GitHub Actions Active

charliermarsh mentioned this pull request Oct 15, 2026

Share DNF simplification across clause representations #22626

Merged

charliermarsh removed this pull request from stack #22616 October 16, 2026 01:15

charliermarsh added this pull request to stack #22628 October 16, 2026 01:15

charliermarsh removed this pull request from stack #22628 October 16, 2026 15:11

This was referenced Oct 16, 2026

Use bit sets to simplify large marker DNFs #22640

Closed

Share DNF simplification across clause representations #22642

Closed

charliermarsh added this pull request to stack #22643 October 16, 2026 15:13

charliermarsh mentioned this pull request Oct 16, 2026

Extract marker DNF covers from decision diagrams #22651

Merged

charliermarsh removed this pull request from stack #22643 October 16, 2026 23:53

charliermarsh added this pull request to stack #22671 October 16, 2026 23:53

Skip unused extra substitutions in markers

50164be

charliermarsh deployed to automations October 18, 2026 02:44 — with GitHub Actions Active

charliermarsh merged commit 8f8d72e into main Oct 18, 2026
63 of 64 checks passed

charliermarsh deleted the charlie/direct-marker-transform branch October 18, 2026 03:24

Navigation Menu

Repository navigation

Resolve extras and check marker reachability without DNF - #22608

Resolve extras and check marker reachability without DNF#22608
charliermarsh merged 4 commits into
charlie/bench-conflicting-extrasfrom
charlie/direct-marker-transform

charliermarsh commented Oct 15, 2026 •

edited

Loading

Uh oh!

codspeed Bot commented Oct 15, 2026 •

edited

Loading

Uh oh!

Uh oh!

This branch was successfully deployed

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Conversation

charliermarsh commented Oct 15, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Uh oh!

codspeed Bot commented Oct 15, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merging this PR will regress 11 benchmarks

Performance Changes

Footnotes

Uh oh!

Uh oh!

This branch was successfully deployed

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

charliermarsh commented Oct 15, 2026 •

edited

Loading

codspeed Bot commented Oct 15, 2026 •

edited

Loading