[ty] hash-cons UseDefMap fields#23283
Merged
dcreager merged 9 commits intoastral-sh:mainfrom Feb 27, 2026
Merged
Conversation
Typing conformance resultsNo changes detected ✅ |
|
Memory usage reportSummary
Significant changesClick to expand detailed breakdownflake8
trio
sphinx
prefect
|
Merging this PR will not alter performance
Comparing 
Footnotes
|
mtshiba
force-pushed
the
intern-use-def-fields
branch
from
0e1f6f1 to
f6d0732
Compare
mtshiba
requested review from
AlexWaygood,
carljm,
dcreager,
ibraheemdev and
sharkdp
as code owners
Member
|
Some of the microbenchmarks are showing slowdowns of up to 4% on Codspeed, but the real-world benchmarks are showing much less dramatic slowdowns (and colour-science even shows a small speedup). Given that the memory reductions are pretty decent here, I agree that that seems like a worthwhile tradeoff. (I haven't reviewed the code here yet.) |
dcreager
approved these changes
Feb 26, 2026
Member
dcreager
left a comment
dcreager
left a comment
There was a problem hiding this comment.
Code looks good, thank you! I agree that a small microbenchmark hit is worth the savings on larger projects.
Comment on lines
+316
to
+319
| /// Interned [`Bindings`] values. | ||
| interned_bindings: IndexVec<InternedBindingsId, Bindings>, | ||
| /// Interned [`Declarations`] values. | ||
| interned_declarations: IndexVec<InternedDeclarationsId, Declarations>, |
Member
There was a problem hiding this comment.
I like how you chose to only do the interning in the final UseDefMap. An alternative would have been to build up the interned values in UseDefMapBuilder as bindings/etc are created. But that would add complexity to the building code, and would only be needed if you needed the intern IDs as references, to store in other bits of state. We don't, and so this approach is simpler. Very nice!
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
4 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
Implement hash-consing for several fields in
UseDefMapto reduce memory usage.The rationale for this optimization is the size and high duplication rate of the structs used in
UseDefMap. The size of each struct is:These elements are stored within
IndexVecwhere duplication of elements can occur.For example, taking these statistics (duplication rate) with hydra-zen yields the following:
The disparity in duplication rates between symbols and members was a bit surprising, but can be explained as follows:
obj.attrandobj["k"]might be tracked, but often end up in a similar undefined/unbound state, leading to a large number of identicalPlaceStateinstances.This PR implements hash-consing for these fields. Specifically, each
IndexVecfor these fields will only store IDs for each struct, and the actual struct instances will be stored in anotherIndexVecwithout duplication.According to the memory usage report, this change reduced the size of
SemanticIndexby about 10%.Performance analysis
What this PR is trying to do involves a trade-off between time complexity and space complexity.
In #23201, I aimed to achieve a more significant reduction in memory consumption by interning
Bindings, but this resulted in a major regression in time performance, so I decided to manually intern only items that seemed to have a high effect.This PR change is not very effective for microbenchmarks, and rather adds a time cost (due to hash calculations). However, looking at the trends in the memory report, it seems that for large codebases, it can achieve significant memory savings with relatively little overhead. The larger the
UseDefMap, the greater the reduction, so I think it's worth to do this.The commit that achieved the greatest memory consumption reduction in this PR was b9d067a, but it was reverted because it exceeded the threshold for codspeed microbenchmarks. There was almost no impact on walltime benchmarks (in fact, some even showed slight improvements).
Test Plan
N/A