Pointer tagging

What is pointer tagging?

I think on most (or quite possibly all) Oxc's supported 64-bit architectures, the top 6 or 7 bits of pointers are unused, and could be used to pack additional data into the pointer's bytes ("pointer tagging").

One useful article on this subject: https://muxup.com/2023q4/storing-data-in-pointers

What could we do with it?

Potentially we could squeeze Expression and Statement down from 16 to 8 bytes, by storing the enum discriminant in top 6/7 bits.

Expression and Statement are both extremely common in AST, and also are often passed around between functions. So squeezing their size might make a significant difference to performance.

Difficulties

However, there are challenges:

1. Platform support

• Need to define which platforms we support.
• Need to make sure all those platforms support pointer tagging.
• Need to test on those platforms.

2. Enum matching

• How to support match on enums where our memory representation of enums does not match Rust's native representation?
• There may be ways to do this and preserve an ergonomic interface, but it's unclear.

What to do for now?

There are major challenges to implementing pointer tagging. So unlikely that we'd want to attempt this now.

But I've opened this issue to have as a reference, and as a reminder that we may not want to use the high bits of pointers to pack other data, to leave the door open for the enum optimization in future.

Are there alternatives?

Yes. We could also reduce the size of AST types by more efficiently storing the data backing enums e.g.:

Vec<T>

Store enum discriminants and enum "payloads" separately in e.g. Vec<Statement>.

Essentially it'd be an SoA pair of Vecs - Vec<u8> (discriminants) + Vec<NonNull<()>> (pointers) = 9 bytes per element, vs current 16 bytes.

Structs

Storing enum discriminants in structs separately from the "payloads". e.g. BinaryExpression would be stored as:

struct BinaryExpressionRepr {
    span: Span,
    left_ptr: NonNull<()>,
    right_ptr: NonNull<()>,
    left_discriminant: u8,
    right_discriminant: u8,
    operator: BinaryOperator,
}

This is 32 bytes (vs 48 bytes at present) - and still has 5 padding bytes which could fit a u32 Node ID.

Start with the linked pointer-tagging article and the Expression and Statement representations described in this issue. Establish supported 64-bit platforms, Rust enum-matching constraints, and measurable size or performance targets before proposing an implementation; done would require an agreed design and cross-platform tests.