Location memory optimizations

[TwitchBronBron]

Flatten location data onto tokens and AST nodes

Summary

Replace the per-token/per-node Location object tree — { uri, range: { start: { line, character }, end: { line, character } } } — with flat fields directly on each token and AST node: pos, end, and a shared source reference. Line/character coordinates are computed on demand at LSP, diagnostic, and sourcemap boundaries only.

This eliminates 4 heap objects per token/node, cuts per-item location memory by ~86%, and reduces GC pressure across the language server's lifetime.

Note on memory numbers: All byte counts below assume V8 pointer compression (4-byte slots), which is active in Electron and VS Code — the language server's primary runtime. Without pointer compression (plain Node CLI), every slot doubles to 8 bytes, so absolute savings are larger. The compressed numbers are the conservative case.

What is being replaced

Every Token and AstNode carries a location: Location, where Location (from vscode-languageserver-types) is:

// on Token
location: Location;
// on AstNode
abstract location?: Location;

// Location is a tree of 4 objects:
interface Location {
    uri: DocumentUri;              // string pointer
    range: Range;
}
interface Range {
    start: Position;
    end: Position;
}
interface Position {
    line: uinteger;
    character: uinteger;
}

That is 4 heap objects per token/node to hold 4 integers and a string pointer:

Object	Header	Fields	Total
Location (uri, range)	12	8	20
Range (start, end)	12	8	20
Position ×2 (line, character)	24	16	40
location pointer on owner	–	4	4
Total			84 bytes

The actual payload is ~20 bytes. The rest is V8 object headers — 4× the data size spent on overhead.

The Lexer already tracks absolute offsets internally (this.start, this.current) but throws them away when emitting tokens, eagerly converting to line/character. AST nodes then recompute bounding locations from their tokens via util.createBoundingLocation() (~81 call sites), each allocating another 4-object tree.

Proposal

Tokens and AST nodes implement Locatable directly — the item is its own location:

interface Locatable {
    pos: number;           // absolute UTF-16 offset into the source string
    end: number;           // absolute UTF-16 offset, exclusive — [pos, end)
    source?: SourceInfo;   // shared per parse, one instance per file
}

interface SourceInfo {
    uri: string;           // file URI
    lineStarts: number[];  // offset of each line start, built during lexing
}

• pos + end follow TypeScript's TextRange convention. Containment is pos <= t && t < end — no arithmetic. String.prototype.slice(pos, end) works directly. Bounding ranges are Math.min/Math.max over child offsets.
• source is one shared object per file (~20 bytes). All tokens and nodes from the same parse share a single reference. The uri that currently lives on each Location moves into source.uri.
• lineStarts is a Uint32Array built once during lexing. A 10,000-line file costs ~40 KB, shared across all items from that parse.
• getLocation() is a standalone utility that builds a Location on demand from pos/end/source. It binary-searches lineStarts (~14 compares for a 10K-line file). It is never cached on the item.
• source is bound to the parse, not the file. Each reparse creates a new SourceInfo, so stale tokens from a previous parse never resolve against new line starts.

The location property is removed, not deprecated. This is a v1 breaking change.

Memory savings

Per item

	Per-item bytes	Heap objects
Current (location: Location)	84	4
Proposed (pos + end + source)	12	0
Reduction	86%	100%

At scale

Locatables	Current	Proposed	Saved
100K	8.4 MB	1.2 MB	7.2 MB
1M	84 MB	12 MB	72 MB
5M	420 MB	60 MB	360 MB

These numbers cover location storage only — the token/node objects themselves (kind, text, parent, children) are unchanged.

CPU impact

What gets faster

• Lex time: the Lexer currently allocates 3–4 objects per token via locationOf(). With this change: two integer writes (pos = this.start, end = this.current), zero allocations.
• Parse time: createBoundingLocation() iterates children, compares line/char pairs, and allocates 4 objects per node. Replaced by Math.min/Math.max over integer offsets.
• Containment/overlap checks: pos <= t && t < end replaces the branchy compare-line-then-compare-character pattern used by rangeContains, findChildAtPosition, etc.
• GC: ~170K fewer traceable objects per file. In a language server with 50 open files, that is ~8.5M fewer objects the GC must walk on every major collection. This reduces GC pause duration — the primary source of user-visible language server hitches.

What gets slightly slower

Line/character coordinates are no longer precomputed. They are needed at three boundaries:

Boundary	Conversion cost	Frequency
Diagnostics	1 binary search per position (~14 compares / 10K-line file)	Per diagnostic
LSP responses	1 binary search per position	Per request
Transpile + sourcemaps	1–2 compares/token via last-hit cache (checks previous line first)	Per token, only with sourcemaps enabled

Transpile with sourcemaps disabled needs zero line/char conversions.

Net

The allocation and GC savings dominate. The on-demand conversion cost is a few compares per position, only when line/char is actually needed, replacing an allocation and GC cost paid on every token all the time.

Alternatives considered

Four flat integers instead of offsets

Flatten startLine, startChar, endLine, endChar, uri onto each item. This also eliminates the 4-object tree.

	Fields	Per-item bytes	Reduction
Four flat ints + uri	5	20	76%
pos + end + source	3	12	86%

Offsets are better because containment is 2 compares instead of branchy line/char logic, slice(pos, end) works directly, and the Lexer can drop its line/column tracking entirely (lineBegin, lineEnd, columnBegin, columnEnd) in favor of building lineStarts in one pass. TypeScript and Roslyn both chose this approach.

Flatten uri and lineStarts directly onto each item (no SourceInfo)

Eliminating the shared SourceInfo object means storing two pointers per item (uri + lineStarts) instead of one (source). That is 16 bytes per item vs 12 — 400 KB more at 100K items — to avoid a single 20-byte shared object. One pointer to a shared struct is cheaper than two pointers per item.

Walk parents to find the source (TypeScript's getSourceFile())

TypeScript nodes walk parent to the root SourceFile instead of storing a reference. This is O(depth) — 20–30 levels in a deeply nested expression. TypeScript's emitter avoids this by threading currentSourceFile as local state. BrighterScript nodes transpile themselves (node.transpile(state)), and plugins need source info at arbitrary points, so neither can rely on context threaded from above. Storing the pointer is 4 bytes per node and O(1).

Per-instance closure getter (Object.defineProperty)

A per-instance getter closing over SourceInfo costs ~64+ bytes (closure function + property descriptor) — more than the 4-byte pointer. Worse, per-instance defineProperty breaks V8's hidden class chain, making all property access on tokens megamorphic.

Design

• Internal logic runs on offsets only. Helpers can assert a.source === b.source, since offsets from different files are meaningless to compare.
• Boundary conversion:
  • Inbound (line/char → offset): lineStarts[line] + character.
  • Outbound (offset → line/char): binary search lineStarts, then character = offset - lineStarts[line].
  • Utility function: getLocation(item): Location | undefined.
• Half-open ranges [pos, end), enforced everywhere.
• Offsets are UTF-16 code units, matching JS string indexing and the LSP default position encoding.
• Synthetic tokens/nodes have source = undefined, so getLocation() returns undefined.
• Consistent V8 shape: initialize pos, end, and source in the same order on every token/node, including synthetic ones, to keep hot paths monomorphic.

Compatibility / risks

• Breaking change. location is removed from Token and AstNode. All code reading .location, .location.uri, .location.range, .range must be updated.
• ~81 createBoundingLocation call sites in Statement.ts and Expression.ts → offset arithmetic.
• ~12 .location.uri access sites → .source?.uri.
• Location overrides (plugins pointing synthetic nodes at other sources): WeakMap<Locatable, Location> side table. Zero cost for the common case.
• Serialization: a node is not a Location. Passing one where Location was expected would walk the subtree via JSON.stringify and throw on circular parent references.
• Retention: long-lived caches (diagnostics, reference indexes) must store getLocation() results, not the node, or they retain the entire old AST after a reparse.
• Plugin API: anything that constructs or reads range/location needs a migration note.

Validation

1. Heap snapshot of a large real project on v1: count Location / Range / Position instances and compare with the theoretical numbers above.
2. Benchmark parse + validate + transpile on both branches, measuring total time, GC time, and peak heap.
3. Fallback: if transpile with the last-hit cache is slower than current v1, reconsider the four-flat-ints alternative.

[markwpearce]

I like this. It will save a lot of memory!

[TwitchBronBron]

Sweet. I'm still working on a few tweaks to the writeup, so hold off for a bit. but yeah, i think this is a direction we need to go. Typescript uses a similar approach and they have a much better memory footprint than us.