Engineering High-Performance Parsers with Data-Oriented Design - Arshad Yaseen<br>#Abstract<br>A parser is usually taught as a problem of grammars, but once the grammar is correct, almost all of the performance and most of the engineering difficulty live somewhere else, in how the resulting tree is represented in memory. This article describes the design discipline I used to build Yuku, a JavaScript and TypeScript parser written in Zig that runs several times faster than the established parsers in its category, and it applies to any parser or compiler frontend in a native language. The claim is simple. Design the data structure first, let the machine’s access patterns dictate its shape, and the speed follows almost for free, while unrelated-looking problems (memory layout, allocation, and serialization) collapse into one solution.<br>Although this article is framed around a parser, almost none of it is specific to parsing. Any system that builds a large structure once and then traverses it many times wins from the same moves. Query planners, game engines, simulations, and serializers all live or die on memory layout. Design the data for the machine.#1. The Single Idea<br>A parser’s performance is decided long before its first benchmark, by how its tree is laid out in memory. That is data-oriented design. Start from the access pattern and the hardware, derive the representation, and build everything else, the lexer, the recursive descent, the visitor API, to serve it.<br>Two facts about modern hardware drive the whole argument.<br>A cache miss to main memory costs on the order of a hundred nanoseconds. A floating-point operation costs a fraction of one. A parser that chases pointers is memory-latency-bound, stalling on loads rather than computing.<br>A general-purpose allocator call is not free, and a parser that allocates one node at a time pays that cost millions of times while scattering related objects across memory.<br>The stakes are concrete. A hundred-thousand-byte file produces roughly fifty thousand AST nodes. As separately allocated, pointer-linked objects, that is fifty thousand allocations, as many frees, and every later traversal chasing pointers into cold memory. In one flat array, it is a handful of allocations, a linear scan, and a single teardown. That is not a constant factor. It changes the slope of the curve.<br>#2. The Cost of the Obvious Design<br>The textbook AST is a tree of heap-allocated structs joined by pointers. In a native language it looks like this.<br>const Node = union(enum) {<br>binary: struct { op: Op, left: *Node, right: *Node },<br>call: struct { callee: *Node, args: []*Node },<br>identifier: struct { name: []const u8 },<br>// ...one variant per node kind<br>};<br>It is correct, it is readable, and it is the wrong shape for a machine. Consider what it costs.<br>Allocation per node. Each *Node is an allocator call. For our hundred-thousand-byte file that is tens of thousands of calls, each touching allocator metadata.<br>Pointer chasing. left and right point wherever the allocator happened to place them. Walking the tree is a sequence of unpredictable loads, each a potential cache miss. The prefetcher cannot help because the addresses are not a pattern.<br>Pointer overhead. On a 64-bit target every edge is eight bytes. A node with two children spends sixteen bytes just on pointers, often more than its actual payload. Pointers also pin the representation to one address space, which makes the tree impossible to hand to another language without a deep copy.<br>Fragmentation and teardown. Freeing the tree is another tens of thousands of calls, and the objects were never contiguous to begin with.<br>The variant payloads also differ wildly in size, so a naive node array would be sized to the largest variant and waste space on the common small ones. We will fix that too.<br>None of these costs come from the grammar. They come from the representation. So we change the representation.<br>#3. Nodes as Indices, Not Pointers<br>The first move is to replace every pointer with an integer index into one flat array of nodes.<br>pub const NodeIndex = enum(u32) {<br>null = std.math.maxInt(u32), // the universal "no child" sentinel<br>_,<br>};<br>A NodeIndex is a u32. It is half the size of a pointer. It does not pin the tree to an address space, so the same bytes are valid in this process, in a serialized file, or in another language’s heap. The reserved value null encodes “absent child” without a separate optional, which keeps payloads flat. Because the array only grows and is never compacted, an index stays valid for the entire life of the tree.<br>Tree<br>nodes [ n0 ][ n1 ][ n2 ][ n3 ] ... one flat, contiguous array<br>child reference is just the integer 1<br>All of this memory is owned by a single arena allocator. The parser asks the arena for storage as it grows the node array, and when the caller is done the entire tree is released in one operation.<br>pub fn deinit(self: *const Tree) void {<br>self.arena.deinit(); // frees every node, every list, every string at once<br>This is the...