[ty] Hand-roll memoization caches for constraint sets#23538
Merged
Conversation
fe70bea to
0895b23
Compare
Typing conformance resultsNo changes detected ✅ |
|
Memory usage reportSummary
Significant changesClick to expand detailed breakdownflake8
trio
sphinx
prefect
|
Merging this PR will degrade performance by 5.67%
Performance Changes
Comparing 
Footnotes
|
0895b23 to
186ff10
Compare
|
| Lint rule | Added | Removed | Changed |
|---|---|---|---|
invalid-await |
0 | 40 | 0 |
no-matching-overload |
0 | 20 | 0 |
invalid-return-type |
1 | 5 | 0 |
unresolved-attribute |
0 | 5 | 0 |
type-assertion-failure |
0 | 0 | 3 |
invalid-argument-type |
1 | 1 | 0 |
unsupported-operator |
0 | 2 | 0 |
invalid-assignment |
0 | 0 | 1 |
not-subscriptable |
0 | 1 | 0 |
| Total | 2 | 74 | 4 |
bcf548a to
ab4ce4e
Compare
Member
Author
|
#23541 is a no-op PR that tests whether this helps with the nondeterminism we have been seeing. And good news, it does help! There is still some lingering nondeterminism, but it seems more related to salsa cycle handling, and not the constraint set implementation. Next I am going to break this PR up into at least 2 for easier review. I am also including details about the unrelated nondeterminism so that we can dig into it further in other PRs. @carljm had already noticed some lingering nondet that shows up as Codex was able to track down a minimal repro: $ uv run scripts/setup_primer_project.py prefect /tmp/prefect
$ cd /tmp/prefect
$ ty check \
--python=.venv \
src/prefect/utilities/_engine.py \
src/prefect/cache_policies.pyThe narrowing checks at In the most common run, those narrowing checks up with and the narrowed results (and downstream diagnostics) would include an intersection with that additional callable type. Interestingly, this example is only nondeterministic in |
ab4ce4e to
08b9d50
Compare
sharkdp
pushed a commit
that referenced
this pull request
Feb 27, 2026
This is a pure refactoring PR that exists solely to set up #23538. That PR will update how we memoize the constraint sets that we build, with hand-rolled cached instead of relying on salsa interning. To do that, we need a create a new `ConstraintSetBuilder` type and thread it around through all of the various `has_relation_to` methods and friends. That's a slog to review, so I've pulled that out into this separate PR to make reviewing easier. This PR is a pure refactoring. There should be no behavioral changes. In particular, the new `ConstraintSetBuilder` type is currently empty! We're still using salsa interning at this stage of the migration, and so the builder doesn't need to hold onto any internal state. But don't worry, it will soon.
Base automatically changed from
dcreager/constraint-builder-refactor
to
main
February 27, 2026 12:40
08b9d50 to
dbb1981
Compare
Member
Member
Author
carljm
approved these changes
Mar 2, 2026
| /// This is usually passed around by shared reference to avoid convoluted APIs that thread mutable | ||
| /// references to the builder back and forth. | ||
| /// | ||
| /// Most core type inference algorithms create one of these, create one or more constraint sets in |
Contributor
There was a problem hiding this comment.
Is it worth mentioning here as a possible TODO the idea of in future sharing one across a TypeInferenceBuilder?
carljm
added a commit
that referenced
this pull request
Mar 2, 2026
* main: [ty] Hand-roll memoization caches for constraint sets (#23538)
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
3 participants
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 PR updates how we manage the interning and memoization of our constraint set BDD implementation. Before we relied on Salsa interning and tracking. This had the nice property that everything was cached globally across the entire process, which in theory gives us space savings when the same constraint sets are created for different regions of source code.
However, it made us very susceptible to changes in the ordering of salsa IDs. Salsa IDs are also assigned globally, in the order that interned structs or tracked method results are created. That means that if e.g. a particular constraint is created for two unrelated regions of code, there's no guarantee about how that constraint's salsa ID will compare to the IDs of the other constraints in the BDD. Since we were using constraint IDs to define our BDD variable ordering, this would sometimes give us different BDD structures for different (identical) invocations of ty. This was leading to a lot of nondeterminism in our CI jobs.
We now rely on a new
ConstraintSetBuildertype to define local caching of BDD nodes and operations. The type was introduced as a no-op refactoring in #23600. This PR updates that type to actually take over responsiblity for the interning and memoization caches.This opens up some other potential optimizations, but I've kept this PR purposefully limited in scope — with one exception, we cache exactly the same things as before, just in a hand-roll
FxHashMapinstead of via a magic salsa macro. (That one exception is that we now intern typevars locally in the new builder, even though they are already salsa-interned globally. This is needed to give them a stable ID within the builder.)