All my marbles in one place

A blog about course design, data display, C++, and Python. Yes, these are related, at least as I see them.

© 2026. All rights reserved.

Part 2: Reimplementing the TeX data structures in C++

28 Sep 2026 Tags: Programming, C++
<- Part 1: Reading TeX: The Program in 2026 Part 3: A Benchmark Harness -> (Not yet published)
   

While reading the TeX source code (see Part 1), I repeatedly asked myself, “What if we implemented the data structures using modern tools? Would the design be clearer? Would it perform better?”. Knuth took enormous pains to save memory. He also designed TeX’s dynamic memory allocator to be compatible with the early virtual memory systems of the 1980s. While he did his best, the resulting code is obscure compared to how we would implement this design using modern language facilities.

It might well perform better, too. The memory hierarchy of modern processors differs substantially from those of the 1980s. In particular, the large cache hierarchies and data prefetch algorithms, when combined with branch prediction strategies in execution pipelines, favour data structures with high locality and predictable execution paths, requirements not present when classical data structures were developed.

I decided to reimplement TeX’s data structures twice, once using identical memory layout and once using the modern features provided by the language, and compare their clarity and performance.

Choosing C++ as the implementation language

I chose C++ as much from necessity as habit. I needed a language that could directly implement both the statically-allocated structures of TeX and the more modern dynamically-allocated class hierarchy. The largest limitation of C++, its lack of garbage collection, is not an issue for TeX, which has no circular data structures.

Implementing required a different style of reading

In Part 1 I described how the sequence of topics in TeX: The Program matched the order in which you might want to learn the levels of its design, giving the book a natural flow but not leading to a deep understanding. I predicted that a very different style of reading would be required to modify the code.

The prediction was borne out as soon as I began replicating TeX’s Pascal data structures in C++. I found myself inserting multiple bookmarks, flipping between sections. I realized I didn’t actually understand most of what I’d originally read. I might have gotten the gist but when programming, details matter, and I most definitely had more details to learn. There are also concepts such as token lists and how they are distinct from character lists that are more implied than explicit in the book. Implementing them required me to learn those distinctions down to the last detail.

Still, the book format wasn’t much of an impediment. The cross-referencing at the base of each two-page spread, combined with the thorough index, allowed me to track relationships as quickly as if I were using an integrated development environment (IDE). The main limitation compared to an IDE was the limitation of seeing only two pages at once in the book, where an IDE can display many more sections of a program on contemporary large displays. Ultimately though, the small display was more an annoyance than a hindrance to serious work.

I reimplemented the structures that might require most change to adapt to modern processors

TeX’s key data structures are described in Parts 4–20 of TeX: The Program. They comprise:

These structures can be organized into six groups:

The string pool is not heavily used. It only contains strings hardcoded in the Pascal code (that are then extracted by the WEB preprocessor and preloaded into the TeX image via INITEX) and a small number of strings defined in the current document, typically csnames. Due to this limited use, I did not reimplement it.

TeX’s dynamic memory is a high-use, home-grown substitute for the standard memory management provided by every modern language. I reimplemented this because I wanted to see how TeX’s version from the 1980s holds upon 2020-era processors when compared to more modern libraries.

The remaining categories of data structure, the semantic nest, the equivalents table and its stack, and the hash table, are more specialized and less central to TeX, so I will not implement them at this time.

The code is publicly available at tedkirkpatrick/tex-memory.

The “TeX-like” implementation follows the Pascal closely

My first implementation, the “TeX-like” version, is in directory original-approach.

I chose to follow TeX’s style closely, even when it contradicted typical C++ best practices. In particular, whenever TeX has an if block, else block, or loop with a single statement, it doesn’t enclose them with a Pascal begin/end pair. I used the corresponding convention for this version, only brace-enclosing such blocks when they contained more than one statement. The resulting code was essentially written in the C subset of C++.

In some cases this meant ignoring recent improvements in the language in favour of much older approaches. For example, I distinguished internal and external linkages via the longstanding static and extern keywords, rather than the more refined approach possible with namespaces.

The special case of WEB constants and macros

As you may recall from Part 1, TeX’s code makes extensive use of the WEB preprocessor facilities. These are used to define named constants via the = operator

define width_offset = 1

and to define macros using the ≡ operator

define width(#) ≡ mem[# + width_offset].sc

Part 1 describes how TeX makes extensive use of WEB constants and macros to implement higher-level abstractions on top of basic Pascal. The WEB constructs correspond closely to features in the C/C++ preprocessor. Indeed, the WEB preprocessor might well have been inspired by the C preprocessor.

But preprocessors have widely-discussed disadvantages. First, they introduce a new syntax and semantics, distinct from that of the underlying language. More importantly, they do not work within the standard type system and are not type-checked. Type checking is an essential feature of statically-typed languages and a design compatible with that is a much better fit.

In light of this, I decided to implement the WEB variables and functions not in preprocessor syntax but as constexpr variables and functions, which work within regular C++ syntax and type-checking. They also ultimately generate the same object code as if they’d been implemented in the preprocessor. The route to that efficient object code is subtle however, resulting from coordinated choices in the language specification and the compilers implementing it.

Strap in, this one’s going to take a while to explain.

Implementing WEB constants as constexpr constants

The case of WEB constants is straightforward. Given the WEB definition of width_offset above, WEB translates the statement

a = mem[width_offset]

to the Pascal statement

a = mem[7]

which is all the Pascal compiler sees. The width_offset identifier simply doesn’t exist in Pascal because it’s been translated by WEB first.

In contrast, the C++ definition

constexpr int width_offset = 7;

is seen by the compiler, as it is a valid definition in the language, and width_offset is entered in the symbol table. The constexpr qualifier restricts the identifier’s initialization to a constant expression, which can be evaluated at compile time. The identifier is also implicitly const, meaning it is immutable. And so, unlike WEB, the C++ compiler will directly parse the statement

a = mem[width_offset]

but because width_offset was initialized at compile time and known to be immutable, the compiler will replace it with the value 7, generating the same object code as the Pascal compiler.

Note the relationship between the language definition and the compiler: The requirements of the constexpr qualifier, restricting the initialization to an expression executable at compile-time and guaranteeing that the value will not change during execution, give the compiler leeway to directly substitute the value whenever the identifier appears. The language definition specifically doesn’t require this, leaving it as a potential optimization choice by compiler authors. A conformant compiler could in fact assign a memory location to width_offset, initialize it to 7, and generate code to load the value from that location every time the identifier is referenced. The language definition just makes it easy for the compiler to generate the more optimal code and virtually all of them will.

There is one case however, where the language does require the compiler to replace the identifier with its constant value: when referenced in a constant expression, such as used to set array limits. The language expressly permits definitions such as

int value[width_offset];

and in this case the compiler must directly substitute the value the value 7 to set the size of array value.

I went into this level of detail for the simpler case of constexpr constants because it provides a context for discussing the more complicated case of constexpr functions.

Implementing WEB macros as constexpr functions

The broad principles of how constexpr functions can be used in place of WEB macros are similar to how constexpr constants can replace WEB constants but there are more steps to the logic.

In TeX, given the definitions above, the statement

a = width(n)

is translated by WEB to the Pascal statement

a = mem[n + 7].sc

expanding the width macro and the width_offset constant to their definitions and substituting the variable n for the parameter #. As with WEB constants, the Pascal compiler only sees the result of the expansion; the names of the macro and constant do not exist in Pascal.

The use of WEB macros that are preprocessed into an inline expression has a potential efficiency benefit: Inline code is typically more efficient than a function call because the function call adds the overhead of parameter setup, a branch to different location, and a return. The inline code for this macro, by contrast, just does a simple addition and indexed memory reference, which is much faster.

On the other hand, the corresponding constexpr function in C++

constexpr int width(int n) { return mem[n + width_offset].sc; }

works differently. It is a C++ function parsed according to the language’s typing rules. As with constant definitions, the constexpr qualifier states that the compiler may execute this at compile time and, in specialized contexts, even must do so. It so happens that, for all the functions corresponding to the WEB macros used in TeX, none will be executed at compile time but all of them will ultimately produce the same inline code. Getting to that conclusion will a few steps.

When C++ requires compile time execution of a constexpr function

I want to begin with the case of required compile-time execution, despite it never arising for my implementation of the TeX WEB macros, because it highlights some issues we’ll need to understand for those macros. Consider the following code (admittedly silly but it makes the point):

// This case does not arise in TeX!
constexpr int mem[8] {0, 1, 2, 3, 4, 5, 6, 7};
constexpr int width_offset = 7;
constexpr int width(int n) { return mem[n + width_offset]; }
int array[width(0)]; // width(0) must be executed at compile-time

Note: For this section, I’m going to elide the .sc suffix in the actual definition of width. That simply selects an entry in the memory_word union. For simplicity, I’ll assume that mem is just an array of ints and that is the return type of width.

This compiles (example on Compiler Explorer). The size of array must be available at compile time, so width(0) is executed by the compiler to compute the size, returning 7.

When a constexpr function cannot be executed at compile time

Compare that with a similar example where mem is not qualified by constexpr and is not initialized:

// How mem is actually defined in TeX!
int mem[8]; // Actual array is much bigger
constexpr int width_offset = 7;
constexpr int width(int n) { return mem[n + width_offset]; }
// This line just illustrates the problem---it doesn't arise in TeX
int array[width(0)]; // width(0) cannot be executed at compile time

This fails to compile (example on Compiler Explorer) because the contents of mem are unknown at compile time. Due to its reliance on mem, the function width can never be executed at compile time and so the required size of array cannot be computed.

How a runtime constexpr function gets compiled inline

Given the actual definitions of mem and width, a C++ definition such as

int q = width(n);

will always generate runtime code for the width(n) call. So how does its code become compiled inline rather than as a call? As with constexpr constants, this results from the coordinated but separate designs of the language and its compilers.

A function like width() poses an apparent paradox: Its constexpr qualification supposedly makes it eligible for compile time execution but its reliance on the runtime contents of mem makes actual execution at compile time impossible. What’s the point of constexpr here?

The answer lies in an implied consequence of constexpr, that constexpr functions are also inline.

The semantics of the inline qualifier are themselves subtle. They don’t require a compiler to compile the function inline, as the C++ language definition does not wish to impose optimizations on the compiler. Instead, inline enables that optimization by specifying that identical definitions of this function are permtted in different files.

The practical way to insert the same definition of a function in multiple files (technically, in the language of the C++ specification, “translation units”) is to define the function body along with its signature in a header file. Defining an ordinary function that way will produce a link-time error but a constexpr- or inline-qualified function is permitted. The header file will be included in every file where the function is called.

This creates the context for the compiler to perform an inline optimization of the function’s code. The language guarantees that every call will be to the identical function definition, allowing the compiler to directly compile the function body at each point of call. There is no need to create a single copy of the function referenced by every call.

This choice remains an option but it’s one that compilers typically take if any optimization is requested. For example, both gcc 15.2 and clang 19.1 compile width() out of line at -O0 but begin inlining it at -O1.

Examples in Compiler Explorer for ARM64 code generation:

Summary of constexpr constants and functions

Implementing the WEB macros as constexpr constants and functions was a complete win. It kept the code within regular C++ syntax and type-checking while producing the same object code as if I’d used the C++ preprocessor. However, determining that this was going to be the outcome from any modern compiler required looking carefully into the semantics of the language, what the definition promised and what it left up to the compiler.

One final detail remains. Earlier, I wrote “Inline code is typically more efficient than a function call” [emphasis added]. Under what circumstances might inline code in fact be slower than calling a function? The potential problem is the size of the executable. Replacing each function call with inline code increases that size and this in turn can cause key execution paths to be too large for the instruction cache (I-cache). This results in higher I-cache misses, slowing the program.

TeX is a small enough program that this effect is unlikely to arise. Ultimately though the question can only be answered through benchmarks, coming in future entries in this series.

Some other small uses of C++ features

In addition to constexpr constants and functions, I used a few other C++ features that don’t match the original WEB/Pascal code:

Testing was exhaustive

Translating the TeX code required understanding subtle points of the underlying semantics. The essentially typeless Pascal code, where the macros expand down to make every value an 8-, 16-, or 32-bit integer, occasionally hid the underlying semantics. To check my translation, I wrote extensive test routines in the Catch2 framework. I chose the v2 version, which is header-only.

The resulting tests feature almost 200 assertions, testing the underlying memory allocation routines in basic_memory.{hpp,cpp} and the node routines built atop those in boxes.{hpp,cpp}.

These tests were essential for ensuring that my code matched the semantics of the original TeX.

Reimplementing in modern C++ was straightforward

In contrast to reimplementing the exact code, simply reimplementing its intent in modern C++ was straightforward. The reimplementation is in directory modern-approach.

There was no need to write underlying memory management (files basic_memory.{hpp,cpp} in the original version) because in this version I was relying on the facilities provided by the base language. The complex macro structures defining the node types in the original simply became a class hierarchy in this version, with each class defining its specific fields. The hierarchy has only two levels, with the top level defining the base Node and each node type (vertical box, horizontal box, etc.) derived from that.

The hierarchy made explicit a point that I found confusing in the original code: Although GlueSpecs are allocated from the same general memory pool as Nodes, they are not themselves Nodes because they do not link to anything else. The word that would have contained that link instead contains a reference count, as GlueSpecs can be linked to by multiple Nodes. This is a good example of how implementing the design in the actual types of the language clarified a point that was obscured by the more typeless approach in the original.

Using modern (C++ 11) smart pointers

In the Pascal code, pointers between Nodes (and from Nodes to GlueSpecs) are implemented as integer indices into the mem array. In C++, I implemented pointers to Nodes using std::unique_ptr and pointers to GlueSpecs using std::shared_ptr. These features are sufficient to handle any structure used in TeX, which does not have circular references. They guarantee that there will be no memory leaks, as they ensure that the referenced object will be deleted whenever the single pointer to it (for Nodes) or the last pointer to it (for GlueSpecs) goes out of lifetime.

Consequently, my implementation never calls delete, as that is done automatically by the smart pointers. This approach has one disadvantage that might arise for larger data structures: When the top-level object is deleted, the system must recurse down the hierarchy, traversing the tree of Nodes referred by the top object. If the height of the underlying tree is high, the recursive calls can exceed the function call stack size.

A robust implementation must either guarantee that the call stack is large enough to accommodate the deletion—a challenging guarantee—or implement a traversal with an explicit stack. In that case, the value of smart pointers is that any deletions missed by the traversal will be performed by the system. The traversal algorithm is the belt, the pointers are the suspenders.

Testing was near-trivial

Where reimplementing the original Pascal code required extensive testing to ensure I had done it correctly, the was essentially one test case required for the modern C++ implementaton. I just wrote a function that creates an instance of every Node type and several GlueSpecs. Their deletion was performed automatically upon the top-level pointer leaving scope.

The modern C++ implementation was far clearer

Taking the above into account, the modern C++ was shorter, clearer, more direct, and supported far more comprehensive static checking at compile time.

If I had reimplemented the other layers of TeX atop this base, this code would have supported far cleaner separation between the layers, with decisions in lower levels hidden from their higher-level callers.

So the code was a win but what about performance? My original speculation was that the facilities of a modern language should be better-adapted to the performance requirements of modern processors, which are quite different from the requirements of processors in the 1980s. I turned my attention to benchmarking the two approaches.

Performing reliable benchmarks requires an automated harness to run the tests under controlled conditions and reliably record the results. In Part 3 I’ll describe the requirements and the system of tools I built to meet them.