oxc-project / oxc-project/backlog

Pre-calculate capacity required in bindings hashmaps for each scope

Open
#76 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
No language data
Stars
7
Forks
0
PR merge metrics
No merged PRs in 30d

Description

https://github.com/oxc-project/oxc/pull/4367 added an AST traversal at start of building Semantic, to count how many nodes, scopes, symbols, and references there are in the AST.

It uses these counts to pre-allocate sufficient capacity in AstNodes, ScopeTree and SymbolTable before the main traversal which populates these structures with data. This avoids these structures needing to grow during the main traversal, with all the memory-copying involved in that. The result was a big boost for performance.

@Dunqing suggested:

Maybe we can do more, even count the number of each scope bindings?

I replied:

Yes, maybe that would be good - could size the bindings hash map for each scope correctly up front. But where do we store those "bindings per scope" counts? Would have to be in a Vec which we don't know the right size for until Counter pass has finished, so it'd resize all the time - i.e. that creates the same kind of problem again that this PR solves!

I can now see a way around this problem.

ScopeId is just a wrapper around u32, and scope_id fields of AST nodes are unused at this point. So we could store the binding counts in scope_id fields. In SemanticBuilder's main AST pass, it'd retrieve the binding count from scope_id field, use that count to initialize Bindings for that scope with appropriate capacity, and then write actual ScopeId into scope_id field.

A bit hacky to misuse scope_id fields in this way, but should work.

What we don't know is whether the gain of pre-allocating Bindings hashmaps to required capacity will outweigh the cost of calculating the counts. Maybe it won't because most scopes contain less than 4 bindings anyway (which is probably default capacity of HashMap), and these hashmaps are usually fairly small so growth is not so costly. But probably worth trying and measuring it.

NB: If we do try this, we may need to take into account the load factor of HashMap. To be able to store 8 items in a hashmap requires the hashmap to have space for more than 8 elements. Docs for HashMap::with_capacity suggest it takes load factor into account, but we should make sure or we may misread benchmark results as it won't be doing quite what we think it is.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading the Counter pass and SemanticBuilder's main AST pass, focusing on scope_id, ScopeId, Bindings, and HashMap allocation. Measure whether calculating per-scope binding counts and pre-allocating Bindings improves performance after accounting for HashMap load factors; done means the benchmark shows a worthwhile net gain.

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
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.