Data-Oriented Design in Yuku's Parser

Yuku, a JavaScript and TypeScript parser written in Zig by developer Yuku, parses the 8 MB typescript.js file in about 19 ms on an M3 by replacing pointer-based AST nodes with u32 indices into flat arrays, following the data-oriented design used by the Zig compiler. The parser produces 852,919 nodes for that file, and the index representation halves pointer size, reserves the max u32 value for "no child," and places all nodes, extras, pooled strings and diagnostics in a single arena so 850,000 frees collapse into one deinit call. The author credits Andrew Kelley's data-oriented design talk and the Zig compiler's flat-index AST as the source of the technique, and pins node sizes with compile-time asserts to prevent a new field from growing all 852,919 nodes.

Data-Oriented Design in Yuku's Parser Yuku https://yuku.fyi is a JavaScript and TypeScript parser I write in Zig. It gets through typescript.js https://raw.githubusercontent.com/yuku-toolchain/parser-benchmark-files/refs/heads/main/typescript.js , an 8 MB file, in about 19 ms https://github.com/yuku-toolchain/ecmascript-parser-benchmark-native on my M3. The grammar was never the interesting part of that. Recursive descent is in every textbook and you can more or less transcribe it from the ECMAScript spec. What decides whether a parser is fast is a question the spec never asks: what does a node look like in memory, and who allocates it. The answer isn’t mine. The Zig compiler stores its AST as flat arrays of indices, and I learned the technique by reading it, along with Andrew Kelley’s talk on data-oriented design https://vimeo.com/649009599 , where the reasoning is laid out properly. Yuku applies the same idea with a looser grip than Zig does, on purpose. The last section is about exactly where, and why. What the pointer tree costs The AST most of us write first looks like this: js const Node = union enum { binary: struct { op: Op, left: Node, right: Node }, call: struct { callee: Node, args: Node }, identifier: struct { name: const u8 }, // ... }; Nothing wrong with it as a description of the grammar. It’s just bad for the machine, and you don’t feel it until the file gets big. Yuku produces 852,919 nodes for typescript.js , roughly one per ten bytes of source. In the pointer version every one is a separate malloc . At tens of nanoseconds a call, that’s tens of milliseconds spent asking for memory, and a similar bill to give it back, for a parse that should take 19 ms in total. Then the nodes live wherever the allocator felt like putting them. Every later walk is a chain of dependent loads to addresses the CPU can’t predict. A miss to main memory costs around 100 ns; arithmetic costs a fraction of one. A traversal over 850k scattered nodes spends most of its life stalled. The third cost is easy to miss: the tree is full of absolute addresses, so it’s welded to one process. You can’t write it to a file, map it back in, or hand it to another language without rebuilding it object by object. For Yuku that last one matters most, because JavaScript is the main consumer. None of these costs come from the grammar. They all come from the representation. Indices, not pointers Every pointer becomes a u32 index into one flat array: js /// Index into the AST node array. pub const NodeIndex = enum u32 { null = std.math.maxInt u32 , }; Half the size of a pointer, indifferent to which address space it lives in, and the max value is reserved for “no child” so an optional child costs nothing extra. The tree is a handful of arrays plus the arena that owns them: js 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: StringPool = .{}, /// The original source text passed to the parser. source: const u8 = "", /// 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 } }; That deinit is the first thing you get for free. Nodes, lists, pooled strings and diagnostics all live in one arena, so 850,000 frees become one. A node is a tagged union plus a source span, and I pin both sizes with compile-time asserts so a field added to one variant can’t quietly grow all 850k nodes. A field is cheap to add; 850,000 copies of it are not. js pub const Node = struct { data: NodeData, // tagged union, one variant per node kind 171 of them span: Span, // { start: u32, end: u32 }, byte offsets into source }; pub const BinaryExpression = struct { left: NodeIndex, right: NodeIndex, operator: BinaryOperator, }; comptime { std.debug.assert @sizeOf NodeData == 44 ; std.debug.assert @sizeOf Node == 52 ; } Here’s what that produces. let x = 1 + 2; , dumped straight out of the parser: js let x = 1 + 2; 0 4 8 12 byte offsets 0 binding identifier 4..5 name=4..5 "x" 1 numeric literal 8..9 raw=8..9 "1" 2 numeric literal 12..13 raw=12..13 "2" 3 binary expression 8..13 left=1 right=2 operator=add 4 variable declarator 4..13 id=0 init=3 5 variable declaration 0..14 kind=let declarators=extras 0..1 6 program 0..14 body=extras 1..2 extras: 4 5 | program body declarator list Four things to notice, and you’ll use every one of them later: - Children come before parents. Node 3 refers to 1 and 2, which already exist, and the root is the last node appended. This falls out of recursive descent for free: a parse function builds its children, appends itself, and hands its index back. - Every edge is a small integer. left=1 , right=2 . Not addresses. - The identifier’s name isn’t a copied string. It’s the byte range 4..5 of the source. - The two variable-length lists live in a shared extras array, and the node keeps a start and a length. Two columns, not one array of structs std.MultiArrayList stores those nodes as separate columns instead of one array of 52-byte structs: 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 js 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 ; } A pass that only switches on node kind, which is most passes, never pulls spans through the cache. A pass that only wants positions never pulls payloads. Appending is a bump Adding a node increments a length. The parser reserves capacity up front from the source size, so the allocator stays off the hot path: js 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 ; Those estimates are deliberately fat. Real files land near one node per ten bytes, so source len / 2 asks for several times what gets used. That’s fine: a large allocation is an mmap underneath, and the OS doesn’t hand you a page until you write to it. Reserve generously, pay for what you touch. The bonus nobody advertises Because every child has a lower index than its parent, a plain for loop over the node array from 0 to n is a post-order traversal. No recursion, no explicit stack, and the access is sequential so the prefetcher does the work. Any bottom-up pass can just be a loop. Stripping parenthesized expressions is exactly this: js fn stripParenthesizedNodes tree: ast.Tree void { const datas = tree.nodes.items .data ; const spans = tree.nodes.items .span ; for 0..datas.len |i| { var inner: u32 = switch datas i { .parenthesized expression = |p| @intFromEnum p.expression , .ts parenthesized type = |p| @intFromEnum p.type annotation , else = continue, }; // resolve to the innermost non-paren node while true { switch datas inner { .parenthesized expression = |p| inner = @intFromEnum p.expression , .ts parenthesized type = |p| inner = @intFromEnum p.type annotation , else = break, } } datas i = datas inner ; spans i = spans inner ; } } Variable-length children A binary expression has exactly two children and they fit inside the node. A block has any number of statements. Rather than size every node for the worst case, variadic children go into the shared array and the owner keeps an 8-byte descriptor: js 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 is the interesting part. 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. So there’s one scratch buffer used as a stack: each list-building function records where it started and truncates back to that point on the way out. pub fn parseBody self: Parser, terminator: ?TokenTag ast.IndexRange { const checkpoint = self.scratch statements.begin ; // current length defer self.scratch statements.reset checkpoint ; // truncate on exit while self.isAtBodyEnd terminator { const statement = try statements.parseStatement self, .{} ; try self.scratch statements.append self.allocator , statement ; } // one bulk copy of scratch checkpoint.. into tree.extras return self.flushToExtras &self.scratch statements, checkpoint ; } Nesting is where that pays off. Here’s { a; { b; c; } d; } : 0 identifier reference "a" 1 expression statement expression=0 2 identifier reference "b" 3 expression statement expression=2 4 identifier reference "c" 5 expression statement expression=4 6 block statement body=extras 0..2 the inner block 7 identifier reference "d" 8 expression statement expression=7 9 block statement body=extras 2..5 the outer block 10 program body=extras 5..6 extras: 3 5 | 1 6 8 | 9 inner outer program Read the extras left to right and you can see the recursion. The inner block finished first, so its two statements flushed first, at 0..2, while the outer block’s statement 1 sat lower in the same buffer, untouched. The outer block then resumed, collected 6 and 8 , and flushed all three at 2..5. The buffer grows a few times per parse and then never again; appending a child is a bounds check and a store. Yuku keeps five of these for contexts that assemble lists at the same time. The same offset-and-length shape shows up everywhere once you have it. 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 . Backtracking is just truncation This one is a side effect of the layout rather than something I designed in, and it matters more than it sounds. TypeScript needs speculation in a few places: <T x = x is a generic arrow in a .ts file and a JSX element in .tsx , and a < b and a<T b start out identical. Yuku covers the parenthesis cases with a cover grammar, but for arrows and type argument lists it simply tries, and rewinds if the attempt doesn’t pan out. A checkpoint is a handful of integers: js pub const Checkpoint = struct { lexer cursor: u32, lexer state: lexer.LexerState, current token: Token, // tree-backed append-only storage: just the lengths nodes len: usize, extra len: usize, diagnostics len: usize, // parser flags, small structs copied by value context: Context, ts context: TsContext, }; pub fn rewind self: Parser, cp: Checkpoint void { self.lexer.cursor = cp.lexer cursor; // ... self.tree.nodes.shrinkRetainingCapacity cp.nodes len ; self.tree.extras.shrinkRetainingCapacity cp.extra len ; self.diagnostics.shrinkRetainingCapacity cp.diagnostics len ; } Whatever the failed attempt built is the tail of three arrays, and rewinding cuts the tail off. No frees, no walking a half-built subtree, nothing left rotting in the arena. With a pointer tree you either free the subtree node by node or leak it and hope it doesn’t add up. Append-only storage hands you this for nothing, and once you have it you stop being nervous about speculative parsing. Strings are offsets Nearly every string a parser produces already exists, byte for byte, in the source it was handed. So a string in Yuku is two offsets, and the offsets themselves say which backing store they point into: js pub const String = struct { start: u32, end: u32 }; pub fn get self: const StringPool, 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 ; } Below source.len it’s a source slice and costs nothing. Past it, it lands in a small pool holding the exceptions: identifiers written with unicode escapes, string literals whose escapes had to be decoded, names a transform invented. Here is one, in a source 15 bytes long: js let x = "a\nb"; 1 string literal 8..14 raw=8..14 "a\nb" value=15..18 "a", newline, "b" string pool: 3 bytes raw is still a source slice. value starts at 15, exactly source.len , so it’s the first 3 bytes of the pool. That works only because the lexer refuses to do work early: it never decodes anything while scanning, it records a span and sets a flag if it saw a backslash. Decoding happens when a name is actually asked for, 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 ; } For an 8 MB file the whole pool ends up in the hundreds of bytes. Everything else is the source, already in memory, never copied. Answers baked into the token tag A token is 16 bytes, and Yuku never keeps an array of them. The lexer produces one on demand, the parser holds the current one, and each node records its own span. js 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 ; } The tag is the interesting part. 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 a lookup table, the answers are encoded into the tag’s integer value at declaration: js 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 runs these once per operator. Each is a shift and a mask on a value already sitting in a register. No table, no branch, no load. Keywords are the other question asked constantly. An ASCII identifier is scanned with a 256-entry table, and if it’s 2 to 11 bytes and starts lowercase it might be a keyword. Yuku answers that with a perfect hash over first byte, second byte, last byte, length . The multipliers came from an offline search, so every keyword lands in its own slot of a 512-entry table and the lookup is one probe, one length compare, one short memcmp: inline fn keywordHash c0: u8, c1: u8, c last: u8, length: usize u32 { const h = @as u32, c0 56 + @as u32, c1 97 + @as u32, c last 108 + @as u32, @intCast length 117; return h & 511; } fn getKeywordType lexeme: const u8 TokenTag { if lexeme.len < 2 or lexeme.len 11 return .identifier; const entry = &keyword table keywordHash lexeme 0 , lexeme 1 , lexeme lexeme.len - 1 , lexeme.len ; if entry.len = lexeme.len return .identifier; if std.mem.eql u8, entry.name 0..lexeme.len , lexeme return .identifier; return entry.tag; } The table is built at compile time from the keyword list, and a @compileError names the offending keyword if two ever collide, so adding one later is safe. Unicode identifiers without paying for them JavaScript identifiers aren’t 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 across the whole range. The obvious implementation is one bit per code point: 256 KB per property. It works, and it falls out of cache constantly. The fix, which I took from David Tolnay’s unicode-ident https://github.com/dtolnay/unicode-ident : the bitset is wildly repetitive. Slice the code point space into chunks of 512 and most chunks turn out identical to some other chunk. Unassigned planes are all zeros, long ideograph ranges are all ones, patterns repeat. Of the 4,096 chunks only 79 are distinct for ID Start and 86 for ID Continue . So store each distinct 512-bit pattern once and keep a 4,096-byte root array mapping each chunk to its pattern: about 29 KB for both properties, small enough to stay resident. js 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 for π U+03C0, code point 960 : chunk 1, and root 1 says pattern 1, which starts at word 16; offset 448 inside the chunk is word 14 of that pattern, bit 0. Two dependent loads from small hot tables and a bit test, no branches and no binary search over ranges. The tables are emitted as plain source by a build-time program that fetches the Unicode character database and deduplicates the chunks, so correctness is settled once at build time and the runtime sees two constant arrays. Just as important is what never touches those tables. ASCII is classified by a 256-entry table built at compile time, the identifier loop runs on it until it hits a byte with the high bit set, and that branch is marked cold: 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 pure ASCII file, 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. That sentence is most of the performance work in a parser: find the common case, make sure it pays for nothing else. The tree is its own wire format Here the flat layout pays its largest dividend, and Yuku’s design decisions start making sense. The primary consumer is JavaScript: the native code parses, and Node needs the AST as ordinary objects. This boundary is where native tooling usually loses. The common approach is to serialize to JSON and JSON.parse on the other side, and that deserialize typically costs more than the parse did. 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. Not a single pointer anywhere. The tree is already position-independent bytes , so serialization isn’t a transformation, it’s a copy. Yuku packs it into one buffer and returns it to JS as an ArrayBuffer : header | nodes | extras | string pool | comments | diagnostics 40 B 44 B each raw u32s raw bytes memcpy memcpy js 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 field0b: u16, // length of the second, if any field1: u32, field2: u32, field3: u32, field4: u32, // 7 u32 slots field5: u32, field6: u32, field7: u32, span start: u32, span end: u32, }; How each AST struct maps into that record isn’t written by hand. It’s derived at compile time from the struct fields, in declaration order: a bool 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 program that generates the JavaScript decoder all call the same layout functions, so the three can’t drift apart. And the budget is enforced where it belongs: comptime { // any AST struct needing more than 7 u32 slots // or 16 flag bits fails the build, by name. validateAllNodeLayouts ; } On the JavaScript side there’s no parsing step at all. The generated decoder reads fields straight out of the buffer through a typed array, one case per node kind. This is the real emitted code, just spaced out to read: js const u32 = new Int32Array buffer ; function decode i { const b = i 11 + 10; // 44-byte node = 11 words, after a 40-byte header const h0 = u32 b ; const tag = h0 & 255; const flags = h0 16; const ss = u32 b + 9 , se = u32 b + 10 ; const start = ss <= firstNa ? ss : pm ss - firstNa ; // utf-8 - utf-16 const end = se <= firstNa ? se : pm se - firstNa ; switch tag { case 8: { // binary expression const f1 = u32 b + 2 , f2 = u32 b + 3 ; return { type: "BinaryExpression", start, end, left: f1 == NULL ? node f1 : null, right: f2 == NULL ? node f2 : null, operator: BINARY OPS flags & 31 , }; } // ... one per node kind, all generated } } Strings never cross the boundary; the caller already holds the source, so a name is source.slice start, end . The one genuine mismatch is positions: Zig spans are UTF-8 byte offsets and JavaScript wants UTF-16 code units. The header records the offset of the first non-ASCII byte, firstNa above. Below it the two coincide, and the pm translation map is built only for the tail past that point. An all-ASCII file skips even that. And because the buffer is position-independent bytes, JavaScript is just one consumer. The same bytes deserialize 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. Where Yuku holds the idea more loosely than Zig Zig pushes this design much further than Yuku does, and the difference is worth being precise about, because it isn’t an accident and it isn’t a shortcut either. A Zig AST node is a tag plus two u32 words whose meaning depends on that tag, with anything larger spilled into a side array, and positions recovered from the token array rather than stored. That is the tightest packing available, and exactly right for a compiler that owns both ends of the pipe. The only consumer of that AST is the compiler itself, so there is nobody to be ergonomic for. | | Zig | Yuku | |---|---|---| | node payload | two u32 words, meaning depends on the tag | tagged union with named, typed fields | | reading a child | switch on the tag, then index a word | node.left, node.right | | positions | recovered from the token array | a span stored on every node | | tokens | whole file tokenized into an array first | lexed on demand, no array kept | | consumer | the compiler itself | tools built on top, in JavaScript and Zig | Yuku isn’t an internal frontend. The AST is the public API. It ships to npm as ESTree and it is a Zig package too, and the whole point is that other people build on it, linters and bundlers and formatters and codemods and editor tooling, from JavaScript and from Zig alike. That changes what the representation has to optimize for. It has to cross into JavaScript fast, and it has to stay pleasant to work with once it gets there. A tool reads node.left by name, constantly. Every rule and every source map wants a position, so recovering spans by re-lexing would put the rare path in the hot seat. And the decoders on both sides are generated from the struct definitions, which only works because those definitions have named, typed fields. You can generate a decoder from a struct, not from “two words, meaning depends on the tag”. So the bytes went into a node that describes itself rather than into density. Yuku keeps everything that costs its consumers nothing, indices instead of pointers, arena instead of per-node allocation, columns instead of structs, offsets instead of copies, and stops at the point where more packing would start costing the people downstream. Same idea, different consumer, different stopping point. If you’re writing an internal frontend nobody else links against, go denser than I did. You’ll get more out of it and give up nothing you need. What generalizes Little of this is specific to JavaScript, and most isn’t specific to parsing. Any system that builds a large structure once and traverses it many times, compiler frontends, query planners, entity systems, wins from the same handful of moves: - Pick 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, and rewindable by truncation. - Amortize everything. 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 invariants compile-time checks. A node size the compiler asserts can’t regress. A wire layout derived from one definition can’t drift. - Know who reads the tree. That single question decides how far down this road you should go, and the answer isn’t the same for everyone. The parser sitting on top of all this is plain recursive descent, the kind you’d write straight from the spec. All the speed is in the data underneath it.