Watch the companion video for this post: A data-oriented approach to updating TeX’s memory model

At the center of TeX’s internal architecture sits a famous (“famous”) data structure: the mem[] array.

In original TeX, virtually everything in memory (tokens in the macro expander, horizontal lists of text, vertical lists of lines, boxes, glue items, kerns, penalties, and so on) lives inside a single, massive, contiguous array of “memory words.” Each memory word was a collection of a fixed number of bits, where the engine would interpret those bits differently depending on its current purposes.

This unified design was an ingenious solution to the memory constraints of 1982. But as TeX engines were ported to 64-bit systems over the decades, this monolithic structure became increasingly awkward. Looking closely at how tex.web and modern successors like LuaTeX manage this memory reveals a surprising opportunity: by applying modern Data-Oriented Design (DOD) principles, we can dismantle the monolith into safe, typed memory pools that improve both performance and readability.

The memory_word

To expand a bit on the point above, in TeX82, a memory_word is a union that can be interpreted in several ways depending on context: as a 32-bit integer, as a fixed-point scaled dimension, as two 16-bit halfword pointers (link and info), as four 8-bit quarterwords (b0, b1, b2, b3), or one half word and a pair of quarterwords.

Nodes in a document (such as a character, a piece of glue, or an \hbox) are formed by taking contiguous slices of this mem[] array. A box node might require several such nodes (to track its dimensions, pointers to its contents, etc), whereas a glue node might need fewer – just enough to store the glue specification and its stretch and shrink components.

To allocate and free these variable-sized chunks within a single array, Knuth implemented a custom allocator in tex.web known as get_node. It maintained a doubly-linked free list of available blocks inside the array itself, using the memory words of inactive nodes to store forward and backward pointers.

The 64-Bit Expansion Problem

When TeX engines were ported to 64-bit architectures, this union model ran into structural friction. In 64-bit systems, pointers and word alignments expand to 8 bytes.

In engines like LuaTeX, widening memory_word to 64 bits meant that structures like box nodes ballooned in size. To access individual fields within these widened words, the engines relied on sprawling hierarchies of macro accessors (e.g., width(p), depth(p), shift_amount(p), which might be accessing the semantic width field in a box node, but be used to access something completely different for other nodes). Computing these complex byte offsets and bit shifts into raw memory buffers was extremely efficient. It also feels a bit like staring into the abyss.

From a data-oriented perspective, packing heterogeneous node types into a single contiguous array also leads to poor CPU cache locality. When the line-breaking algorithm iterates over a paragraph, it only needs to examine width, stretch, and penalty fields. In a monolithic array, fetching those fields constantly pulls unrelated box attributes into CPU cache lines.

Memory Pools and Facades

I tried to rethink this architecture, in part by following in the footsteps of the approach LuaTeX took in splitting the memory array in two.

Rather than maintaining one monolithic array with an ad-hoc free-list allocator, or one fixed-size-element array and one variable-sized-element array, we segregate node allocations into dedicated typed memory pools (arena and pool allocators tailored to specific node sizes). Character nodes, glue specifications, and box records live in contiguous, cache-friendly pools of their own.

To make interacting with these nodes safe and expressive in C++23 without introducing runtime overhead, I tried to use a standard facade pattern. This could be simultaneously readable / udnerstandable, but also be optimized away by SROA during the compilation phase:

//! Most nodes have a standard "node header"
struct NodeView {
    memory_word* words;

    pointer& link()       { return words[0].mw_node_header.link.ptr_val; }
    eighthword& type()    { return words[0].mw_node_header.props.type; }
    eighthword& subtype() { return words[0].mw_node_header.props.subtype; }

    template<typename T> T as() const { return T{words}; }
};

// ...but if we need to we can semantically define how every node type wants its different data to be laid out
struct CharNodeView : public NodeView {
    static constexpr int SIZE = 1;
    uint32_t character() const { return words[0].mw_node_header.info.int_val & 0x1FFFFF; }
    uint16_t font() const      { return words[0].mw_node_header.info.int_val >> 21; }
};

At least in principle, this is the “zero-overhead-abstraction” promise that C++ gives us. Because there are no virtual methods, and no stateful members other than a single pointer to a memory word, they can be easily optimized away. At the same time, when writing engine logic, code interacts with strongly typed methods (node.character(), node.font(), node.link()) rather than inscrutable array offset macros like mem[p + 1].hh.b0.

1980s Scarcity Meets 2020s Cache Optimization

One of the fascinating aspects of studying TeX is discovering that the constraints of the 1980s often rhyme with modern performance best practices. In 1982, Knuth packed multiple values into a single memory word because RAM was scarce. Today, RAM is plentiful and pointer-chasing through linked lists is bad, and sometimes CPU cache latency can be the dominant bottleneck in high-throughput computing. By moving to segregated memory pools and lightweight facade views, we can honor TeX’s original commitment to dense data packing while giving modern hardware the predictability and cache locality it needs to run at full speed.