Repository navigation
perf: Speed up complex SpecifierSet filtering by implementing cost based ordering - #1105
Merged
notatallshaw merged 11 commits intoMar 8, 2026
Merged
Conversation
notatallshaw
force-pushed
the
specifier-cost-based-ordering
branch
from
March 7, 2026 04:50
1429ec5 to
e516a49
Compare
notatallshaw
changed the title
SpecifierSet.filter
notatallshaw
force-pushed
the
specifier-cost-based-ordering
branch
7 times, most recently
from
March 7, 2026 05:34
9fb9784 to
0bebcfb
Compare
henryiii
force-pushed
the
specifier-cost-based-ordering
branch
from
March 7, 2026 07:10
0bebcfb to
6acd57e
Compare
Contributor
|
https://github.com/pypa/packaging/actions/runs/22794469746 About 50% slower? Unless I got the order backward. |
Member
Author
That's benchmark variance and I've found the cause of why Once variance is fixed a real regression is revealed in the resolve loop benchmarks, I will come back to this PR after we land that. |
notatallshaw
marked this pull request as draft
March 7, 2026 15:13
henryiii
force-pushed
the
specifier-cost-based-ordering
branch
from
March 7, 2026 18:19
6acd57e to
f8c34cd
Compare
Contributor
|
Same results, just with a little less variance perhaps. The fact the mini resolver gets 15% slower worries me the most. All benchmarks:
SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY. |
Member
Author
|
FYI, I have fixes for the regressions in the benchmarks, but first I'm going to look at |
Skip CBO sorting overhead when there is only one specifier by delegating directly to Specifier.filter. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
Avoid re-sorting specifier checks on every _filter_specs call by caching the resolved and sorted checks list. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
Use hasattr guard for compatibility with main which lacks this attribute. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
Add filter and contains benchmarks using a multi-operator specifier set to measure CBO effectiveness. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
notatallshaw
force-pushed
the
specifier-cost-based-ordering
branch
from
March 8, 2026 02:57
f8c34cd to
7c645a4
Compare
Member
Author
|
Fixed regressions, added a new "complex" specifier set of benchmarks which are designed to show off the improvement, the resolver loop seems a little faster, possibly contains cold simple is a hair slower (but could be noise or could be the |
notatallshaw
marked this pull request as ready for review
March 8, 2026 03:09
Member
Author
|
This relates back to why SpecifierSet performance had such high variance, when specifiers were stored in a set they were randomly ordered when iterating. Some combinations of specifiers were much faster because the initial specifier was cheap and/or filtered lots of versions, meaning remaining specifiers didn't need to do anything. Whereas other combinations of specifiers were much slower because the initial specifier was expensive and/or didn't filter any versions meaning versions kept having to be checked by specifiers. This attempts to make the former situation more likely by using a heuristic on the cost and effectiveness of the operator in the specifier. |
henryiii
approved these changes
Mar 8, 2026
Member
Author
|
I slightly touched up the heuristic cost function as I realized that if Benchmarks are within noise values of prior to this commit: |
Member
Author
|
We could also take this further in the future, and implement a more complex optimizer, for example if there are two specifiers However there will be more complex trade offs there of cost to analyze vs. cost to run. |
ngoldbaum
pushed a commit
to ngoldbaum/packaging
that referenced
this pull request
Apr 1, 2026
This was referenced Apr 13, 2026
Closed
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.
This flattens out the execution of individual
Specifiers inSpecifierSet.filterso that it can re-order them based on cost and likelihood to reject, as some operators are more than 5x expensive to call than others.For example the
filtered_versionsis calculated about 3x faster:And despite the more complex code the performance of simple specifiers seems not to be measurably impacted.