Indices, not Pointers

Summary

Indices, not Pointers Jul 15, 2025 There is a pattern I’ve learned while using Zig which I’ve never seen used in any other language. It’s an extremely simple trick which - when applied to a data structure - reduces memory usage, reduces memory allocations, speeds up accesses, makes freeing instantaneous, and generally makes everything much, much faster. The trick is to use indices, not pointers.This is something I learned from a talk by Andrew Kelley (Zig’s creator) on data-oriented design. It’s used in Zig’s compiler to make very memory-efficient ASTs, and can be applied to pretty much any node-based data structure, usually trees.So what does this mean exactly? Well, to use indices means to store the nodes of the data structure in a dynamic array, appending new nodes instead of individually allocating them. Nodes can then reference each other via indices instead of pointers. A comparison of memory layouts with different storage methodsPretty simple, right? But this strategy has some major performance benefits.A pointer costs 8 bytes to store on a modern 64-bit system, but unless your planning on storing over 4 billion nodes in memory, an index can be stored in just 4 bytes.Due to the reduced node size and the fact that nodes are stored contiguously in memory, the data structure will fit into fewer memory pages and more nodes will fit in the cpu’s cache line, which generally improves access times significantly.The way most people learn to implement data structures like trees is to make a separate allocation for each individual node, one at a time. This is a very naive way of allocating memory, however, as each memory allocation comes with a small but significant overhead which can really slow things down for a large number of nodes. Storing nodes in a growable arraylist minimizes this overhead as arraylists grow superlinearly (e.g, doubling in size each time more space is needed) meaning the majority of new nodes can just be placed in the next available slot without...