Engineering High-Performance Parsers with Data-Oriented Design

June 28, 2026

Yuku is a JavaScript/TypeScript parser written in Zig that runs 3–10x faster than the alternatives on npm. I wrote it alone, and it keeps pace with parsers built by teams. The grammar was never the hard part. Recursive descent is a solved problem; you can transcribe it from the ECMAScript spec. What decides whether the parser is fast is a question the spec says nothing about: what does a node look like in memory?

Two hardware facts drive everything below.

A load that misses cache and goes to main memory costs on the order of 100ns. Arithmetic costs a fraction of a nanosecond. A program that chases pointers through scattered heap objects spends its life stalled on loads.
A general-purpose allocator call costs tens to hundreds of nanoseconds and scatters related objects across the address space. A parser that allocates per node pays this tens of thousands of times per file.

Yuku budgets roughly one AST node per two source bytes, so a 100 KB file means ~50,000 nodes. Built the textbook way, that is 50,000 allocations, 50,000 frees, and every traversal afterward is a pointer chase through cold memory. Built as flat arrays, it is a handful of allocations, linear scans, and one free.

What the pointer tree costs

The textbook AST in a native language looks like this:

const Node = union(enum) {
    binary: struct { op: Op, left: *Node, right: *Node },
    call: struct { callee: *Node, args: []*Node },
    identifier: struct { name: []const u8 },
    // ...
};

It is correct and readable, and everything about it is hostile to the machine. Every *Node is a separate allocation. Every edge is 8 bytes of pointer, often more than the payload it points to. The children live wherever the allocator put them, so walking the tree is a series of unpredictable loads the prefetcher can do nothing with. And because the structure is full of absolute addresses, it is welded to one address space: you cannot write it to disk, share it between processes, or hand it to another language without a deep copy.

None of these costs come from the grammar. They come from the representation.

Indices, not pointers

Yuku replaces every pointer with an integer index into one flat array. This is the actual definition:

/// Index into the AST node array.
pub const NodeIndex = enum(u32) { null = std.math.maxInt(u32), _ };

Half the size of a pointer, position-independent, and with a reserved value for “no child” so optional children cost nothing extra. The tree itself is a handful of arrays plus the arena that owns them:

pub const Tree = struct {
    /// Index of the root node (always a `program` node).
    root: NodeIndex = undefined,
    /// All nodes in the AST.
    nodes: std.MultiArrayList(Node) = .empty,
    /// Backing storage for variadic node children.
    extras: std.ArrayList(NodeIndex) = .empty,
    /// String pool for AST node string fields.
    strings: ASTStringPool = .{},
    /// Arena allocator owning all the memory.
    arena: std.heap.ArenaAllocator,

    pub fn deinit(self: *const Tree) void {
        self.arena.deinit(); // the whole tree, freed in one call
    }
};

A node is a tagged union plus a source span, and the sizes are pinned by the compiler so a field added to one variant cannot silently bloat all 50,000 nodes:

pub const Node = struct {
    data: NodeData, // tagged union, one variant per node kind
    span: Span,     // { start: u32, end: u32 }
};

comptime {
    std.debug.assert(@sizeOf(NodeData) == 44);
    std.debug.assert(@sizeOf(Node) == 52);
}

std.MultiArrayList stores this as a struct of arrays: one column of payloads, one column of spans, the same index into both.

array of structs                      struct of arrays

[ data | span ][ data | span ] ...    data: [ d0 ][ d1 ][ d2 ] ...
                                      span: [ s0 ][ s1 ][ s2 ] ...

reading node kinds drags every        a kind-only pass reads one
span into cache as dead weight        dense column and nothing else

A pass that only switches on node kind never drags spans through the cache, and vice versa:

pub inline fn data(self: *const Tree, index: NodeIndex) NodeData {
    return self.nodes.items(.data)[@intFromEnum(index)];
}

pub inline fn span(self: *const Tree, index: NodeIndex) Span {
    return self.nodes.items(.span)[@intFromEnum(index)];
}

Appending a node is a bump of a length. The parser estimates the node count from the source length up front, so the capacity check almost never fails and the allocator stays off the hot path entirely:

const estimated_nodes = if (source_len < 512_000)
    @max(256, source_len / 2)
else
    source_len / 4;
try self.tree.nodes.ensureTotalCapacity(alloc, estimated_nodes);

The array only grows and is never compacted, so an index stays valid for the life of the tree. Construction is bottom-up: a parse routine builds its children first, appends itself, and returns its index for the parent to store. The recursive descent on top is completely ordinary; the only difference from the textbook version is that left and right are integers.

Here is what that actually produces. Parsing let x = 1 + 2; yields seven nodes:

let x = 1 + 2;
0   4   8   12    byte offsets

nodes                                                         span
[0] binding_identifier   { name = source[4..5] }              4..5
[1] numeric_literal      { raw  = source[8..9] }              8..9
[2] numeric_literal      { raw  = source[12..13] }            12..13
[3] binary_expression    { left = 1, right = 2, op = + }      8..13
[4] variable_declarator  { id = 0, init = 3 }                 4..13
[5] variable_declaration { kind = let,
                           declarators = extras[0..1] }       0..14
[6] program              { body = extras[1..2] }              0..14

extras  [ 4 ][ 5 ]
          |    program body
          declarator list

Everything from the previous sections is visible in this little dump. Children precede their parents, and the root is the last node appended. Every edge is a small integer: binary_expression holds 1 and 2, not addresses. The identifier’s name is not a copied string but the byte range 4..5 of the source. And the two variable-length lists live in extras, referenced by offset and length. The whole tree is a few dozen integers in two flat arrays.

You can push this further. If the parser is an internal frontend with no external consumers, nothing forces a node to describe itself, and it can shrink to around 13 bytes:

const Node = struct {
    tag: Tag,        // 1 byte: node kind, and the key to reading `data`
    main_token: u32, // the token this node hangs off
    data: [2]u32,    // two words whose meaning depends on `tag`
};

The data word has no type of its own; the tag says how to read it, so every access goes through a switch:

switch (tree.tag(node)) {
    // binary op: both words are child indices
    .add, .mul => {
        const left = tree.data(node)[0];
        const right = tree.data(node)[1];
    },
    // block: the words are a (start, end) range into extras
    .block => {
        const range = tree.data(node);
        const statements = tree.extras[range[0]..range[1]];
    },
    else => {},
}

No span is stored at all; a position is recovered by re-lexing the main token on the rare occasion one is needed. I didn’t take that trade for Yuku, whose AST is a public API consumed from JavaScript as ESTree: positions are queried constantly, and a set of per-tag conventions is hostile to external readers, so it spends 52 bytes on a self-describing union with stored spans. Both designs are the same idea; they differ only in how much the consumer is willing to recompute.

Variable-length children

A binary expression has exactly two children and they fit in the node. A block has any number of statements. Rather than size every node for the worst case, variadic children go into one shared array, and the owning node stores an 8-byte descriptor:

pub const IndexRange = struct { start: u32, len: u32 };

/// Returns the extra node indices for the given range.
pub inline fn extra(self: *const Tree, range: IndexRange) []const NodeIndex {
    return self.extras.items[range.start..][0..range.len];
}

Building those lists has a wrinkle: the parser doesn’t know a block’s statement count until it hits the closing brace, and it must not allocate a growable list per block. The fix is a scratch buffer owned by the parser, used as a stack:

const ScratchBuffer = struct {
    items: std.ArrayList(ast.NodeIndex) = .empty,

    pub inline fn begin(self: *ScratchBuffer) usize {
        return self.items.items.len;
    }
    pub inline fn reset(self: *ScratchBuffer, checkpoint: usize) void {
        self.items.shrinkRetainingCapacity(checkpoint);
    }
};

pub fn parseBody(self: *Parser, terminator: ?TokenTag) !ast.IndexRange {
    const checkpoint = self.scratch_statements.begin();
    defer self.scratch_statements.reset(checkpoint);

    while (!self.isAtBodyEnd(terminator)) {
        const statement = try statements.parseStatement(self, .{});
        try self.scratch_statements.append(self.allocator(), statement);
    }
    // one bulk copy into tree.extras
    return self.flushToExtras(&self.scratch_statements, checkpoint);
}

Because every call records its own checkpoint and resets to it on the way out, the same buffer nests through recursion: an inner block uses the tail above the outer block’s region and restores it when done. Growing the buffer happens a few times per parse; appending a child is a bounds check and a store. Yuku keeps five of these for contexts that need to assemble lists concurrently (statements, cover grammars, decorators, and two general-purpose ones).

The same offset-and-length trick reappears wherever a node owns a variable number of things. Comments attach to nodes through a prefix-sum array of length node_count + 1: node i’s comments are the slice between offsets i and i + 1. One representation, reused.

Strings are offsets

The naive parser copies every identifier and string literal into its own heap allocation. But nearly every string the parser produces already exists, verbatim, in the source text it was given. So a string in Yuku is two offsets, and which backing store they point into is encoded in the offsets themselves:

pub const String = struct { start: u32, end: u32 };

pub fn get(self: *const ASTStringPool, id: String) []const u8 {
    if (id.start == id.end) return "";
    const src_len: u32 = @intCast(self.source.len);
    if (id.start < src_len) {
        return self.source[id.start..id.end]; // slice of the source, zero copy
    }
    return self.extra.items[id.start - src_len .. id.end - src_len];
}

Offsets below source.len are source slices and cost nothing. Offsets past it land in a small interned pool that holds the exceptions: identifiers written with unicode escapes, string literals whose escapes had to be decoded, names synthesized by transforms. The pool deduplicates through a hash map keyed by content, so a repeated synthetic name is stored once.

This only works because the lexer refuses to do work up front. It never decodes anything; it records a span and sets a flag if it saw a backslash. Decoding happens at the moment a name is actually needed, and only for the rare token that needs it:

pub inline fn identifierName(self: *Parser, token: Token) !ast.String {
    if (token.isEscaped()) // rare: decode into the pool
        return self.decodeEscapedIdentifier(token.span.start, token.span.end);
    // common: the name is the source bytes themselves
    return self.tree.sourceSlice(token.span.start, token.span.end);
}

Answers in the token’s bits

A token is three fields, and its size is enforced the same way as the node’s:

pub const Token = struct {
    span: Span,    // { start: u32, end: u32 }
    tag: TokenTag,
    flags: u8 = 0, // line_terminator_before, escaped, ...
};

comptime {
    std.debug.assert(@sizeOf(Token) <= 16);
}

(You can shrink this too: store only the start offset and re-lex one token whenever an end is needed. Same trade as the minimal node above, and rejected for the same reason: a public parser queries spans constantly.)

The interesting part is the tag. The parser asks the same questions of every token: what is its precedence, is it a binary operator, is it a keyword. Instead of answering with branches or lookup tables, the answers are encoded in the tag’s integer value at declaration:

pub const Mask = struct {
    pub const IsBinaryOp: u32 = 1 << 14;
    pub const IsUnaryOp: u32 = 1 << 16;
    pub const IsIdentifierLike: u32 = 1 << 18;
    pub const IsKeyword: u32 = 1 << 21;
    pub const PrecShift: u32 = 8; // bits 8..12 hold precedence
};

pub const TokenTag = enum(u32) {
    // low 8 bits: ordinal. the rest: precomputed answers.
    plus = 15 | (11 << Mask.PrecShift) | Mask.IsBinaryOp | Mask.IsUnaryOp,
    star = 17 | (12 << Mask.PrecShift) | Mask.IsBinaryOp,
    in = 119 | (9 << Mask.PrecShift) | Mask.IsBinaryOp | Mask.IsKeyword
        | Mask.IsIdentifierLike | Mask.IsUnconditionallyReserved,
    // ...

    pub fn precedence(self: TokenTag) u5 {
        return @intCast((@intFromEnum(self) >> Mask.PrecShift) & 0b11111);
    }
    pub fn isBinaryOperator(self: TokenTag) bool {
        return (@intFromEnum(self) & Mask.IsBinaryOp) != 0;
    }
};

The precedence-climbing loop at the core of expression parsing runs these queries once per operator. Each one is a shift and a mask on a value already in a register. No table, no branch, no load.

Unicode identifiers without paying for them

JavaScript identifiers are not ASCII. The spec defines them by the Unicode ID_Start and ID_Continue properties, so π, 変数, and a few hundred thousand other code points are legal, and the lexer needs an exact membership test over the full code point range. Concretely it needs two functions:

pub fn canStartId(cp: u32) bool;    // may a codepoint begin an identifier?
pub fn canContinueId(cp: u32) bool; // may it appear after the first?

The obvious implementation is one bit per code point. The code point space runs to 0x10FFFF, so that is 256 KB per property, 512 KB for both. It works, but a table that size does not stay in cache, and a lexer consults it constantly.

The observation that fixes it: the bitset is wildly repetitive. Slice the code point space into chunks of 512, and most chunks are identical, entire unassigned planes are all zeros, long ideograph ranges are all ones, and many patterns repeat. Yuku’s tables, generated from Unicode 17.0, contain 4,096 chunks of which only 79 are distinct for ID_Start and 86 for ID_Continue.

So: store each distinct 512-bit pattern once (a “leaf”), and keep a root array of 4,096 bytes mapping each chunk to its leaf. Since there are fewer than 256 distinct leaves, the root entry fits in a u8. Both properties together come to about 29 KB instead of 512 KB, small enough to stay resident. This is the entire lookup:

inline fn queryBitTable(cp: u32, comptime root: []const u8, comptime leaf: []const u64) bool {
    const chunk_idx = cp / 512;                       // which 512-codepoint chunk
    const leaf_base = @as(u32, root[chunk_idx]) * 16; // where its pattern lives
    const offset_in_chunk = cp % 512;
    const word = leaf[leaf_base + offset_in_chunk / 32];
    const bit: u5 = @truncate(offset_in_chunk % 32);
    return (word >> bit) & 1 == 1;
}

Walk it once by hand for π (U+03C0, code point 960):

cp        = 960
chunk_idx = 960 / 512  = 1          codepoints 512..1023
root[1]   = 1                        this chunk uses leaf pattern #1
leaf_base = 1 * 16     = 16          pattern #1 starts at word 16
offset    = 960 % 512  = 448
word      = leaf[16 + 448/32] = leaf[30]
bit       = 448 % 32   = 0
(leaf[30] >> 0) & 1    = 1           π may start an identifier

Two dependent loads from small, hot tables and a bit test. No branches, no binary search over ranges. The tables are emitted as plain source by a build-time program (tools/gen_unicode_id.zig) that downloads the Unicode character database, parses DerivedCoreProperties.txt, builds the chunks, and deduplicates them with a hash map. Correctness is settled once at build time; the runtime sees two constant arrays.

Just as important is what never touches these tables. ASCII is classified by a 256-entry boolean table built at compile time, and the identifier scanner runs on that table until it hits a byte with the high bit set:

const ident_start_table_ascii: [256]bool = blk: {
    var t = [_]bool{false} ** 256;
    for ('a'..('z' + 1)) |c| t[c] = true;
    for ('A'..('Z' + 1)) |c| t[c] = true;
    t['_'] = true;
    t['$'] = true;
    break :blk t;
};

// the hot loop of identifier scanning
while (pos < src.len and ident_continue_table_ascii[src[pos]]) {
    pos += 1;
}
// ...
if (c >= 0x80) {
    @branchHint(.cold);
    const cp = try util.Utf.codePointAt(src, pos);
    if (util.UnicodeId.canContinueId(cp.value)) {
        pos += cp.len;
        continue;
    }
}

A file that is pure ASCII, which is nearly every file, never executes the unicode path at all. The general case is fully supported and the common case never pays for it.

The tree is its own wire format

Here the flat representation pays its largest dividend. Yuku’s primary consumer is JavaScript: the native parser runs, and Node needs the AST as ordinary objects. This boundary is where native tooling usually loses. The common approach, serialize to JSON in native code, JSON.parse on the other side, spends more time deserializing than the parse took. Building JS objects one at a time through N-API is worse.

But look at what the tree contains. Children are u32 indices. Lists are offsets into extras. Strings are offsets into the source. There is not a single pointer anywhere. The tree is already position-independent bytes, which means serialization is not a transformation, it is a copy. Yuku packs everything into one buffer and returns it to JS as an ArrayBuffer:

header | nodes | extras | string pool | comments | diagnostics
fixed    48 B     raw u32s  raw bytes
         each     (memcpy)  (memcpy)

Each node becomes a fixed 48-byte record:

const PackedNode = extern struct {
    tag: u8,
    _pad0: u8 = 0,
    flags: u16,  // packed bools and small enums
    field0: u16, // length of the node's first IndexRange
    _pad1: u16 = 0,
    field1: u32, field2: u32, field3: u32, field4: u32,
    field5: u32, field6: u32, field7: u32, field8: u32,
    span_start: u32,
    span_end: u32,
};

How each AST struct maps into that record is not written by hand. It is derived at compile time from the struct declarations themselves: a bool field claims the next flag bit, an enum claims ceil(log2(n)) bits, a NodeIndex claims one u32 slot, a String two. The encoder, the Zig decoder, and the generator that emits the JavaScript decoder all call the same layout functions, so the three cannot disagree. And the budget is enforced where it belongs:

comptime {
    // any AST struct needing more than 8 u32 slots
    // or 16 flag bits fails the build, by name.
    validateAllNodeLayouts();
}

On the JavaScript side there is no parsing step. The decoder reads fields straight out of the buffer through typed-array views, one switch case per node kind, generated from the Zig definitions:

const _u32 = new Int32Array(buffer);

function _decode(i) {
  const b = (_nodesOff + i * 48) >> 2;
  const tag = _u32[b] & 255;
  const f1 = _u32[b + 2], f2 = _u32[b + 3]; // u32 slots
  switch (tag) {
    // one case per node kind, emitted by tools/estree/decoder.zig
  }
}

Strings never cross the boundary at all: the JS caller already holds the source string, so a name is source.slice(start, end). The one genuine mismatch is positions, Zig spans are UTF-8 byte offsets, JS wants UTF-16 code unit offsets. The header records the offset of the first non-ASCII byte; below it the two coincide, and a translation map is built only for the tail past it. An all-ASCII file skips even that.

This is validated the only way that counts: the conformance suite runs 53,000+ cases and compares the tree decoded in JavaScript against the expected ESTree output node for node, at 100%. And because the buffer is position-independent bytes, JavaScript is just one consumer. The same buffer deserializes back into a Zig Tree for the codegen path, and could as easily be cached to disk and mapped back in, or shared read-only across threads. The buffer is the tree.

What generalizes

Nothing above is specific to JavaScript, and most of it is not specific to parsing. Any system that builds a large structure once and traverses it many times, compiler frontends, query planners, game entity systems, wins from the same small set of moves:

Choose the representation from the access pattern, then write the algorithms to fit. The algorithm on top of Yuku is textbook recursive descent; only the data is unusual.
Indices over pointers. Smaller, position-independent, bulk-freeable, serializable with a copy.
Amortize. Reserve from an estimate, reuse scratch space, batch the rare expensive operation out of the hot loop.
Never let the common case pay for the general one. ASCII before unicode tables, source slices before interning, spans recorded before escapes decoded.
Make the invariants compile-time checks. A node size the compiler asserts cannot regress. A wire layout derived from one definition cannot drift.

A fast parser is not a clever algorithm bolted onto an ordinary data structure. It is an ordinary algorithm running over a data structure shaped for the machine. Design the data first and the speed is mostly already there.