Performance: Monomorphic AST Nodes

[dragomirtitian]

The problem

JavaScript engines commonly use optimizing compilers that rely on objects having stable "shapes". Meaning access sites for object properties should hopefully only observe objects that all have the same properties, and each of those properties has a consistent internal type, e.g. an integer/string/boolean.

• Monomorphic means that only a single shape is observed at the site of a dynamic operation.
• Polymorphic means that 2-4 shapes are observed
• Megamorphic means that > 4 shapes are observed

Currently accessing common properties of Node such as kind is megamorphic. This means that constructs such as switch (node.kind) and type node type guards (is* functions which test the kind) are much slower than they need to be and this slows down the entire compiler.

The same issue is also present in Type

Proposed solution

Make node monomorphic by having a single object shape with common properties (such as kind, pos, end) and move all other properties in a separate data object in the node.

To preserve compatibility with existing code, we can add accessors for known properties of all nodes:

export class NodeImpl {
    pos: number;
    end: number;
    kind: number;
    id: number;    
    data: any;

    …
    get resolvedSymbol() {
    }
    set resolvedSymbol(value: any) {
        this.data.resolvedSymbol = value;
    }

    get modifiers() {
        return this.data?.modifiers;
    }
    set modifiers(value: any) {
        this.data.modifiers = value;
    }

    //// All other properties of all nodes

}

The same approach can also be used for Type.

Results

The proposed solution was implemented in #58928 for both Node, Type and signature. The performance results from the PR on Node are very promising:

• a total time win of 16.0% (ranging 10.5% to 23.7%)
• a checker time win of 20.8% (ranging 16.6% to 26.8%)
• a memory cost of 2.7% (ranging 1.9% to 4.4%)

This is a memory for performance exchange rate of 5.8 on total time, and 7.6 on checker time.

A breakdown of the contribution of making each type individually monomorphic is also available:

AST Nodes #59190 :
- total time win: 3.3% - 9%
- Check Time win: 3.7% - 11%
- Mem cost: ~0-1%

Types #59191:
- total time win: 4.1% - 20%
- Check Time win: 5.3% - 22.5%
- Mem cost: 0.75%-1.2%

Signatures #59192:
- total time win: 0.45% - 1.72%
- Check Time win: 0.56% - 2.04%
- Mem cost: ~0%

Acknowledgements

This work is the result of a collaboration between me and Ashley Claymore (@acutmore) . Ashley first noticed that all is* guard functions were megamorphic and switching to a switch statement can already improve performance considerably. We both hypothesized that speeding up access to kind in some way would speed up the compiler significantly.

This work builds on the work of Ron Buckton (@rbuckton). Both his work in Node-less megamorphic (without this work the current proposal would not be feasible) and also his creation of Deopt Explorer which was used to drive the experimentation.

Potential issues with the approach

For API clients that dynamically inspect what the properties of a Node are, this will be a breaking change since the properties of a node are no longer directly visible on the Node instance

This new approach allocates more memory, resulting in an increase in memory usage of between 1.9-4.4%. While this cost is not insignificant, the performance wins outweigh the cost.

This new approach is optimized for V8 - other runtimes might see different results both in terms of performance gain and memory usage.

Potential future improvements

Since some property names are common between multiple node kinds, the accessors for them will be megamorphic. While even with this extra cost we still get a significant amount of performance improvement, switching to using data directly might yield even better results.

Alternatively maybe v8 could improve access to base class properties, and this change might no longer be needed in a future version of v8. Ron has raised this issue with v8.

[robpalme]

V8 team have responded to Ron's issue.