Pre-allocate sufficient capacity for transformer to create new scopes, symbols, references

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.

However, this is not completely ideal for transformer. ScopeTree and SymbolTable are sized exactly for the number of scopes/symbols in the AST. But transformer creates new scopes, symbols and references, and when it does so, it will require these structures to grow, which incurs a slow-down.

Probably it's not a massive slow-down, because at present the transformer does not create AstNodes. AstNodes is the biggest of the structures, and most of the perf gain of https://github.com/oxc-project/oxc/pull/4367 probably came from preventing it needing to grow. Growing ScopeTree or SymbolTable is less expensive.

But (a) we should still try to avoid this growth and (b) transformer may in future create AstNodes too.

Question is, how do we determine how many scopes and symbols transformer will need to create?

• It depends on what transforms are enabled.
• It depends on how many of certain AST node types are in the AST (which dictates how many transformations will occur).

We could either:

• Attempt to calculate exactly how many additional symbols/scopes/references will be required when compiling counts.
• Use a heuristic e.g. allocate 20% more capacity than required to leave "headroom" for transformer.

If going the heuristic route, I have no idea if 20% is a good number. It may be that there's so much diversity among source files Oxc is expected to handle that there is no good number.

Another approach

Just a thought: Is there a way to sidestep this issue entirely?

Presently we need the structures in ScopeTree etc to be contiguous blocks of memory, so they can be indexed into. Can we change that by e.g. using pointers instead of indexes?

Or use an alternative indexing scheme where the underlying storage is a series of blocks, each double the size of the previous block? Such a storage structure could grow without any memory copies, but at the cost of making indexing into it require more operations to convert ID to block number & index into that block. Something like:

fn id_to_block(id: NonZeroU32) -> (u32, u32) {
    let block_number = 32 - id.leading_zeros();
    // index = id with highest bit unset
    let index_within_block = u32::from(id) & ((1 << (block_number - 1)) - 1);
    (block_number, index_within_block)
}

Start by reading oxc-project/oxc PR #4367 and the capacity handling for AstNodes, ScopeTree, and SymbolTable. Trace how compiling counts and the transformer create scopes, symbols, and references, then compare exact counting with heuristic or alternative storage approaches. Done means transformer growth is avoided or reduced without breaking indexed access, with the performance impact measured.