oxc-project / oxc-project/backlog

Store `Span`s outside AST in a side table?

Open
#168 0 comments 1 reaction 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

Making AstKind consistent (https://github.com/oxc-project/oxc/issues/11490) is close to reaching completion, which will open the door to adding NodeId to all AST nodes (https://github.com/oxc-project/oxc/discussions/5689).

Once we have NodeIds stored in AST, we could consider:

  • Remove span: Span fields from all AST types.
  • Instead store Spans in a side table - IndexVec<NodeId, Span>.

The rationale for this change, as I see it, are:

  • Span adds 8 bytes to every single AST node type. At a guess they account for 10%-15% of total memory footprint of the AST.
  • Spans are created in the parser, but then barely used until codegen.
  • By moving Spans out of AST types, the rest of the AST is more compact in memory.
  • All the intermediate stages in pipeline (semantic, transform, minify) which don't care about Spans will benefit from higher CPU cache hit rate while traversing the AST.
  • Linter also will benefit for same reason. It (mostly) doesn't use Spans either.
  • Codegen with source maps, which does use Spans, uses all of them. It will read them mostly in the same order as they were created in parser, so its pattern of reads from the IndexVec<NodeId, Span> will be largely linear, working from start to end - very efficient cache utilization.

So, in short, I think this change would follow the principle of data-oriented design - store data together which is accessed together.

There are some exceptions, but they all have good alternatives:

  • All parts of pipeline use spans for diagnostics. But errors are rare, so these are cold paths - not important.
  • Comment attachment in codegen and formatter uses spans. However, once we have NodeIds in AST, we may well change comment attachment logic to use NodeIds instead.
  • Various other logic uses spans to compare nodes (e.g. "is this node the left or right side of its parent BinaryExpression?"). But we will use NodeIds for this instead once we have them. We also have Address as an alternative solution, or the possibility of augmenting AstNodes to help with this. We shouldn't be using spans for this.

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 linked AstKind issue and NodeId discussion, then examine how spans are used across parsing, diagnostics, codegen, comment attachment, and formatting. Done would require an agreed design for storing spans outside AST nodes and resolving the listed exceptions.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.