Proposal: Flatten the AST to speed up tsgo

[no-yan]

We may be able to improve tsgo performance by changing the AST representation from a pointer-based tree to a flat array.

Problem

More than 20% of tsgo’s execution time is spent in GC, so optimizing GC should make it run faster.
For example, when running against the VSCode repository with GOGC=off, execution becomes 1.24 times faster:

Repository	default (s)	GOGC=off (s)	Ratio	Command
VSCode	6.567	5.292	1.24 ± 0.11 times faster	npm run compile-check-ts-native

According to pprof, most of the GC time is spent scanning objects, and the parser AST accounts for about 50% of inuse_space. This suggests that reducing the scan cost of the AST could reduce GC time.

Proposed solution

I propose adopting a flat AST. Flattening an AST means converting its tree data structure into a simple slice.

As background, Go’s garbage collector does not scan the backing array of a slice when the slice element type contains no pointers. This optimization can eliminate the scan cost of large arrays.

If we can apply this to the AST, we should be able to reduce the amount of memory scanned during each GC cycle, which could reduce GC time.

As a first step, we could remove pointers from the Node struct like this:

type Arena struct {  
	Node    []Node  
	Data    []nodeData // still contains 2 pointers because of interface boxing  
}  
  
type NodeId uint32  
  
type Node struct {  
	Parent      NodeId // replace the parent pointer  
	Kind        Kind  
	Flags       NodeFlags  
	Loc         core.TextRange  
}

This would reduce the number of pointers in the AST and allow scanning to be skipped for []Node.

Note that nodeData still contains pointers. It may be possible to optimize this further by making Arena hold separate arrays for each type.

Trade-offs

Pros:

• Better locality, which may improve CPU cache efficiency
• Pointer-free Node

Cons:

• Less intuitive API
• More complex dynamic updates and deletion in arrays

[jakebailey]

I don't see how we could do this without major pain, as much as I'd love the magic of data-oriented design.

I'll also note that the most recent version of Go has a garbage collector algorithm called "green tea", which scans entire pages. Because we already arena allocate AST nodes in huge chunks, nodes are already largely contiguous in memory, so it's unclear if we would actually benefit all that much.

Additionally, Go GC is concurrent; a profile might show a lot of time in GC, but if you use a runtime trace, you might find it happening on an unused core anyway.

It may be that there are just more places where we are allocating too many objects, too.

[jakebailey]

Additionally, Go GC is concurrent; a profile might show a lot of time in GC, but if you use a runtime trace, you might find it happening on an unused core anyway.

I do however recognize that you just did GOGC=off.

I do wonder if we can save perf by modifying that during a compile, which is what the Go compiler itself does.

[DanielRosenwasser]

Parent NodeId // replace the parent pointer

I don't see how we could do this without major pain

Right. Whenever we start talking about replacing pointers with indexes, the problem is that you now have to find a way to get back whatever you lost with plain pointers. In this case, you have an index into an arena, but it's not clear how to talk about which arena. Any function that took a *Node now needs to also take an *Arena, or an index into a global set of arenas, or possibly something very clever or hacky.

Data []nodeData // still contains 2 pointers because of interface boxing

The other thing is that the actual information pointed to by nodeData still needs to live somewhere - so that has to live somewhere else entirely.

It might be worth revisiting slimming down nodeData at some point, but it feels pretty risky (required using unsafe) and I think last time we tried the savings were much smaller than we thought. Maybe our measurements were off though.

[ahejlsberg]

For command-line compiles I'd say we allocate very little data that would be eligible for GC during the compilation process. We pretty much hold onto everything until the very end. So, might make sense to disable GC.

[no-yan]

Just to clarify my intent: this wasn’t about DoD/locality, but reducing GC scan cost.

Even if nodes are contiguous, as long as they contain pointers the GC still has to scan them. The potential win I had in mind was making large portions pointer-free so they can be skipped entirely.

That said, I agree the arena/index tradeoff looks quite painful. For command-line compiles, disabling or tuning GC (and reducing allocation-heavy paths like string-heavy resolver work) might be a more practical direction to try first.