[ty] Add caching for pattern match narrowing#25613
Merged
Merged
Conversation
Typing conformance resultsNo changes detected ✅Current numbersThe percentage of diagnostics emitted that were expected errors held steady at 92.13%. The percentage of expected errors that received a diagnostic held steady at 87.18%. The number of fully passing files held steady at 92/134. |
Memory usage reportMemory usage unchanged ✅ |
|
Merging this PR will improve performance by 14.83%
|
| Mode | Benchmark | BASE |
HEAD |
Efficiency | |
|---|---|---|---|---|---|
| ❌ | Memory | ty_micro[literal_match_fallthrough_guarded_any] |
15.1 MB | 15.9 MB | -5.54% |
| ⚡ | Simulation | ty_micro[large_union_narrowing] |
560.7 ms | 347.3 ms | +61.47% |
| ⚡ | Simulation | ty_micro[literal_match_fallthrough] |
81.8 ms | 68.5 ms | +19.44% |
| ⚡ | Memory | ty_micro[large_union_narrowing] |
18.5 MB | 16.6 MB | +11.91% |
| ⚡ | Simulation | ty_micro[literal_match_fallthrough_guarded_any] |
275.5 ms | 256.8 ms | +7.29% |
| ⚡ | Simulation | ty_micro[many_enum_members_2] |
96.5 ms | 92.1 ms | +4.8% |
Tip
Investigate this regression with the CodSpeed MCP and your agent.
Comparing charlie/cache-pattern-match-narrowing (ca71699) with main (27058fc)
Footnotes
-
60 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. ↩
d61232c to
6e11f43
Compare
6e11f43 to
e28faa1
Compare
3c911ae to
12eb9a2
Compare
f7512ba to
35a5ea1
Compare
35a5ea1 to
e436717
Compare
AlexWaygood
reviewed
Jun 4, 2026
AlexWaygood
approved these changes
Jun 4, 2026
AlexWaygood
left a comment
Member
There was a problem hiding this comment.
Sweet, it looks like the multithreaded benchmark impact is negligible now!
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.
Summary
When analyzing a
matchstatement, we currently rebuild the narrowed subject for every case by collecting all preceding unguarded patterns into a union and intersecting the subject with its negation. As pattern types become richer, this can repeatedly distribute the same intersections and make a chain of adjacent cases exponentially expensive. For example, without this change, #25493 starts to surface significant slowdowns in select projects.As a concrete example, this small
matchblows up with a 9x regression after #25493, without the caching introduced here: https://github.com/kornia/kornia/blob/7c2fee7216599a5e6ef149d4ab2fe33dd70f18c3/kornia/io/io.py#L132-L156. Without caching, every branch has to recompute the prefix insubject & ~(pattern_1 | pattern_2 | ... | pattern_k-1); with caching, we turn it into:(Prior to #25493, the sequence patterns generally contributed
Neverhere, making it inexpensive.)