oxc-project / oxc-project/backlog
Optimize `Semantic`
Open
Nobody has claimed this yet.
- Dominant language
- No language data
- Stars
- 7
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
Possible optimizations to Semantic. I'll add to this list as I learn more about how it works:
- Optimize structs-of-arrays (#11, oxc-project/oxc#4269)
- Store Semantic data in arena (#31)
- Re-design
ScopeFlags(#16) unresolved_referencesdoesn't need to be stored inScopeTree, only a singleVecforroot_unresolved_references.unresolved_referencesis used internally withinSemanticwhile resolving references, but at the end, it's an emptyVecfor every scope except root scope. Store it inSemanticBuilderinstead and discard at the end. https://github.com/oxc-project/oxc/pull/4107unresolved_referencesdoes not need to retain entries for every scope. Could be a stack where we reuse hash maps from previous scopes (see https://github.com/oxc-project/oxc/pull/4107#issuecomment-2214167393).unresolved_referencescould be a linked list / chunked linked list instead of aVec. I don't think it's ever indexed into.- Reduce hashing when resolving references. If current
unresolved_referenceshash map contains hashes already, no need to hash each identifier again when finding entry in parent hash map (maybe hash map doesn't contain hashes - SwissTable-style hash maps don't, I think - in which case we could store hashes in entries). - Store binding names as
Atom<'a>notCompactStr. Conversion toCompactStrcauses unnecessary allocations. We can just reference strings in source text (asAtomdoes). Reference::namefield is unnecessary for bound references - can be got fromSymbolId. Is needed for unbound references, but they could be stored elsewhere and referenced.- Add a scope for "global" which would contain unbound references (replacing root
unresolved_references)? Then every reference has aSymbolId. - Initialize
Semantic'sVecs with sufficient capacity so they don't need to grow (see oxc-project/backlog#31). - Get rid of
Reference.- Store
SymbolIdinstead ofReferenceIdinIdentifierReference. - Store a reference count for each symbol so you can check if a symbol is referenced or not.
- Need some way in semantic to update
SymbolIdforIdentifierReferences long after exiting the node. Would need a pointer-based solution, orCell<SymbolId>. - Only thing we lose is the
AstNodeIdinReference. This is probably used in linter, but I don't know what for, and how easy to replace it. - This would allow removing the
resolved_references: IndexVec<SymbolId, Vec<ReferenceId>>field inSymbolTablewhich is major source of reallocation in semantic, asVec<ReferenceId>is pushed to every time aIdentifierReferenceis found, and has an inherently unpredictable growth pattern (can't know in advance how big it needs to be).
- Store
- Don't use
NodeswithinSemanticBuilder. We can get type of parent node etc by maintaining stacks in the visitor. This will enable us to have a cut-down version ofSemanticBuilderwhich doesn't buildNodes.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
The issue names Semantic, SemanticBuilder, ScopeTree, SymbolTable, Reference, and related data structures, but no files or tests. Start by locating those entry points and tracing how unresolved references, bindings, and resolved references are stored. This is done only after narrowing the list to a specific optimization with measurable scope and validation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100