If you’ve read anything about compilers in the last two decades or so, you have almost certainly heard of SSA compilers, a popular architecture featured in many optimizing compilers, including ahead-of-time compilers such as LLVM, GCC, Go, CUDA (and various shader compilers), Swift¹, and MSVC², and just-in-time compilers such as HotSpot C2³, V8⁴, SpiderMonkey⁵, LuaJIT, and the Android Runtime⁶.

SSA is hugely popular, to the point that most compiler projects no longer bother with other IRs for optimization⁷. This is because SSA is incredibly nimble at the types of program analysis and transformation that compiler optimizations want to do on your code. But why? Many of my friends who don’t do compilers often say that compilers seem like opaque magical black boxes, and SSA, as it often appears in the literature, is impenetrably complex.

But it’s not! SSA is actually very simple once you forget everything you think your programs are actually doing. We will develop the concept of SSA form, a simple SSA IR, prove facts about it, and design some optimizations on it.

note

I have previously written about the granddaddy of all modern SSA compilers, LLVM. This article is about SSA in general, and won’t really have anything to do with LLVM. However, it may be helpful to read that article to make some of the things in this article feel more concrete.

What Is SSA?

SSA is a property of intermediate representations (IRs), primarily used by compilers for optimizing imperative code that target a register machine. Register machines are computers that feature a fixed set of registers that can be used as the operands for instructions: this includes virtually all physical processors, including CPUs, GPUs, and weird tings like DSPs.

SSA is most frequently found in compiler middle-ends, the optimizing component between the frontend (which deals with the surface language programmers write, and lowers it into the middle-end’s IR), and the backend (which takes the optimized IR and lowers it into the target platform’s assembly).

SSA IRs, however, often have little resemblance to the surface language they lower out of, or the assembly language they target. This is because neither of these representations make it easy for a compiler to intuit optimization opportunities.

Imperative Code Is Hard

Imperative code consists of a sequence of operations that mutate the executing machine’s state to produce a desired result. For example, consider the following C program:

int main(int argc, char** argv) {
  int a = argc;
  int b = a + 1;
  a = b + 2;
  b += 2;
  a -= b;
  return a;
}

This program returns 0 no matter what its input is, so we can optimize it down to this:

int main(int argc, char** argv) {
  return 0;
}

But, how would you write a general algorithm to detect that all of the operations cancel out? You’re forced to keep in mind program order to perform the necessary dataflow analysis, following mutations of a and b through the program. But this isn’t very general, and traversing all of those paths makes the search space for large functions very big. Instead, you would like to rewrite the program such that a and b gradually get replaced with the expression that calculates the most recent value, like this:

int main(int argc, char** argv) {
  int a = argc;
  int b = a + 1;
  int a2 = b + 2;
  int b2 = b + 2;
  int a3 = a2 - b2;
  return a3;
}

Then we can replace each occurrence of a variable with its right-hand side recursively…

int main(int argc, char** argv) {
  int a = argc;
  int b = argc + 1;
  int a2 = argc + 1 + 2;
  int b2 = argc + 1 + 2;
  int a3 = (argc + 1 + 2) - (argc + 1 + 2);
  return (argc + 1 + 2) - (argc + 1 + 2);
}

Then fold the constants together…

int main(int argc, char** argv) {
  int a = argc;
  int b = argc + 1;
  int a2 = argc + 3;
  int b2 = argc + 3;
  int a3 = argc - argc
  return argc - argc
}

And finally, we see that we’re returning argc - argc, and can replace it with 0. All the other variables are now unused, so we can delete them.

The reason this works so well is because we took a function with mutation, and converted it into a combinatorial circuit, a type of digital logic circuit that has no state, and which is very easy to analyze. The dependencies between nodes in the circuit (corresponding to primitive operations such as addition or multiplication) are obvious from its structure. For example, consider the following circuit diagram for a one-bit multiplier:

This graph representation of an operation program has two huge benefits:

1. The powerful tools of graph theory can be used to algorithmically analyze the program and discover useful properties, such as operations that are independent of each other or whose results are never used.

2. The operations are not ordered with respect to each other except when there is a dependency; this is useful for reordering operations, something compilers really like to do.

The reason combinatorial circuits are the best circuits is because they are directed acyclic graphs (DAGs) which admit really nice algorithms. For example, longest path in a graph is NP-hard (and because $P \neq NP$⁸, has complexity $O(2^n)$). However, if the graph is a DAG, it admits an $O(n)$ solution!

To understand this benefit, consider another program:

int f(int x) {
  int y = x * 2;
  x *= y;
  const int z = y;
  y *= y;
  return x + z;
}

Suppose we wanted to replace each variable with its definition like we did before. We can’t just replace each constant variable with the expression that defines it though, because we would wind up with a different program!

int f(int x) {
  int y = x * 2;
  x *= y;
  // const int z = y; // Replace z with its definition.
  y *= y;
  return x + y;
}

Now, we pick up an extra y term because the squaring operation is no longer unused! We can put this into circuit form, but it requires inserting new variables for every mutation.

But we can’t do this when complex control flow is involved! So all of our algorithms need to carefully account for mutations and program order, meaning that we don’t get to use the nice graph algorithms without careful modification.

The SSA Invariant

SSA stands for “static single assignment”, and was developed in the 80s as a way to enhance the existing three-argument code (where every statement is in the form x = y op z) so that every program was circuit-like, using a very similar procedure to the one described above.

The SSA invariant states that every variable in the program is assigned to by precisely one operation. If every operation in the program is visited once, they form a combinatorial circuit. Transformations are required to respect this invariant. In circuit form, a program is a graph where operations are nodes, and “registers” (which is what variables are usually called in SSA) are edges (specifically, each output of an operation corresponds to a register).

But, again, control flow. We can’t hope to circuitize a loop, right? The key observation of SSA is that most parts of a program are circuit-like. A basic block is a maximal circuital component of a program. Simply put, it is a sequence of non-control flow operations, and a final terminator operation that transfers control to another basic block.

The basic blocks themselves form a graph, the control flow graph, or CFG. This formulation of SSA is sometimes called SSA-CFG⁹. This graph is not a DAG in general; however, separating the program into basic blocks conveniently factors out the “non-DAG” parts of the program, allowing for simpler analysis within basic blocks.

There are two equivalent formalisms for SSA-CFG. The traditional one uses special “phi” operations (often called phi nodes, which is what I will call them here) to link registers across basic blocks. This is the formalism LLVM uses. A more modern approach, used by MLIR, is block arguments: each basic block specifies parameters, like a function, and blocks transferring control flow to it must pass arguments of those types to it.

My First IR

Let’s look at some code. First, consider the following C function which calculates Fibonacci numbers using a loop.

int fib(int n) {
  int a = 0, b = 1;
  for (; n > 0; --n) {
    int c = a + b;
    a = b, b = c;
  }
  return a;
}

How might we express this in an SSA-CFG IR? Let’s start inventing our SSA IR! It will look a little bit like LLVM IR, since that’s what I’m used to looking at.

// Globals (including functions) start with $, registers with %.
// Each function declares a signature.
func fib(%n: i32) -> (i32) {
    // The first block has no label and can't be "jumped to".
    //
    // Single-argument goto jumps directly into a block with
    // the given arguments.
    goto @loop.start(%n, 0, 1)

  // Block labels start with a `!`, can contain dots, and
  // define parameters. Register names are scoped to a block.
  @loop.start(%n, %a, %b: i32):
    // Integer comparison: %n > 0.
    %cont = cmp.gt %n, 0

    // Multi-argument goto is a switch statement. The compiler
    // may assume that `%cont` is among the cases listed in the
    // goto.
    goto %cont {
      0 -> @ret(%a), // Goto can jump to the function exit.
      1 -> @loop.body(%n, %a, %b),
    }

  @loop.body(%n, %a, %b: i32):
    // Addition and subtraction.
    %c    = add %a, %b
    %n.2  = sub %n, 1

    // Note the assignments in @loop.start:
    // %n = %n.2, %a = %b, %b = %c.
    goto @loop.start(%n.2, %b, %c)
}

Every block ends in a goto, which transfers control to one of several possible blocks. In the process, it calls that block with the given arguments. One can think of a basic block as a tiny function which tails¹⁰ into other basic blocks in the same function.

asidePhi Nodes

LLVM IR is… older, so it uses the older formalism of phi nodes. “Phi” comes from “phony”, because it is an operation that doesn’t do anything; it just links registers from predecessors.

A phi operation is essentially a switch-case on the predecessors, each case selecting a register from that predecessor (or an immediate). For example, @loop.start has two predecessors, the implicit entry block @entry, and @loop.body. In a phi node IR, instead of taking a block argument for %n, it would specify

>   %n = phi { @entry -> 0, @loop.body -> %n.2 }

SSA-CFG

The value of the phi operation is the value from whichever block jumped to this one.

This can be awkward to type out by hand and read, but is a more convenient representation for describing algorithms (just “add a phi node” instead of “add a parameter and a corresponding argument”) and for the in-memory representation, but is otherwise completely equivalent.

It’s a bit easier to understand the transformation from C to our IR if we first rewrite the C to use goto instead of a for loop:

int fib(int n) {
  int a = 0, b = 1;
 start:
  if (n > 0) goto ret;

  int c = a + b;
  a = b, b = c;
  goto start

ret:
  return a;
}

However, we still have mutation in the picture, so this isn’t SSA. To get into SSA, we need to replace every assignment with a new register, and somehow insert block arguments…

Entering SSA Form

The above IR code is already partially optimized; the named variables in the C program have been lifted out of memory and into registers. If we represent each named variable in our C program with a pointer, we can avoid needing to put the program into SSA form immediately. This technique is used by frontends that lower into LLVM, like Clang.

We’ll enhance our IR by adding a stack declaration for functions, which defines scratch space on the stack for the function to use. Each stack slot produces a pointer that we can load from and store to.

Our Fibonacci function would now look like so:

func &fib(%n: i32) -> (i32) {
    // Declare stack slots.
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    // Load initial values into them.
    store %np, %n
    store %ap, 0
    store %bp, 1

    // Start the loop.
    goto @loop.start(%np, %ap, %bp)

  @loop.start(%np, %ap, %bp: ptr):
    %n = load %np
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap)
      1 -> @loop.body(%n, %a, %b),
    }

  @loop.body(%np, %ap, %bp: ptr):
    %a = load %ap
    %b = load %bp
    %c = add %a, %b
    store %ap, %b
    store %bp, %c

    %n   = load %np
    %n.2 = sub %n, 1
    store %np, %n.2

    goto @loop.start(%np, %ap, %bp)

  @exit(%ap: ptr):
    %a = load %ap
    goto @ret(%ap)
}

Any time we reference a named variable, we load from its stack slot, and any time we assign it, we store to that slot. This is very easy to get into from C, but the code sucks because it’s doing lots of unnecessary pointer operations. How do we get from this to the register-only function I showed earlier?

asideProgram Order

We want program order to not matter for the purposes of reordering, but as we’ve written code here, program order does matter: loads depend on prior stores but stores don’t produce a value that can be used to link the two operations.

We can restore not having program order by introducing operands representing an “address space”; loads and stores take an address space as an argument, and stores return a new address space. An address space, or mem, represents the state of some region of memory. Loads and stores are independent when they are not connected by a mem argument.

This type of enhancement is used by Go’s SSA IR, for example. However, it adds a layer of complexity to the examples, so instead I will hand-wave this away.

The Dominance Relation

Now we need to prove some properties about CFGs that are important for the definition and correctness of our optimization passes.

First, some definitions.

definition

The predecessors (or “preds”) of a basic block is the set of blocks with an outgoing edge to that block. A block may be its own predecessors.

Some literature calls the above “direct” or immediate predecessors. For example, the preds of in our example are @loop.start are @entry (the special name for the function entry-point) @loop.body.

definition

The successors (no, not “succs”) of a basic block is the set of blocks with an outgoing edge from that block. A block may be its own successors.

The sucessors of @loop.start are @exit and @loop.body. The successors are listed in the loop’s goto.

If a block @a is a transitive pred of a block @b, we say that @a weakly dominates @b, or that it is a weak dominator of @b. For example, @entry, @loop.start and @loop.body both weakly dominate @exit.

However, this is not usually an especially useful relationship. Instead, we want to speak of dominators:

definition

A block @a is a dominator (or dominates) @b if every pred of @b is dominated by @a, or if @a is @b itself.

Equivalently, the dominator set of @b is the intersection of the dominator sets of its preds, plus @b.

The dominance relation has some nice order properties that are necessary for defining the core graph algorithms of SSA.

Some Graph Theory

We only consider CFGs which are flowgraphs, that is, all blocks are reachable from the root block @entry, which has no preds. This is necessary to eliminate some pathological graphs from our proofs. Importantly, we can always ask for an acyclic path¹¹ from @entry to any block @b.

An equivalent way to state the dominance relationship is that from every path from @entry to @b contains all of @b’s dominators.

proposition

@a dominates @b iff every path from @entry to @b contains @a.

proof

First, assume every @entry to @b path contains @a. If @b is @a, we’re done. Otherwise we need to prove each predecessor of @b is dominated by @a; we do this by induction on the length of acyclic paths from @entry to @b. Consider preds @p of @b that are not @a, and consider all acyclic paths $p$ from @entry to @p; by appending @b to them, we have an acyclic path $p'$ from @entry to @b, which must contain @a. Because both the last and second-to-last elements of this are not @a, it must be within the shorter path $p$ which is shorter than $p'$. Thus, by induction, @a dominates @p and therefore @b

Going the other way, if @a dominates @b, and consider a path $p$ from @entry to @b. The second-to-last element of $p$ is a pred @p of @b; if it is @a we are done. Otherwise, we can consider the path $p$ made by deleting @b at the end. @p is dominated by @a, and $p'$ is shorter than $p$, so we can proceed by induction as above.

Onto those nice properties. Dominance allows us to take an arbitrarily complicated CFG and extract from it a DAG, composed of blocks ordered by dominance.

theorem

The dominance relation is a partial order.

proof

Dominance is reflexive and transitive by definition, so we only need to show blocks can’t dominate each other.

Suppose distinct @a and @b dominate each other.Pick an acyclic path$p$ from @entry to @a. Because @b dominates @a, there is a prefix $p'$ of this path ending in @b. But because @a dominates @b, some prefix $p''$ of $p'$ ends in @a. But now $p$ must contain @a twice, contradicting that it is acyclic.

This allows us to write @a < @b when @a dominates @b. There is an even more refined graph structure that we can build out of dominators, which follows immediately from the partial order theorem.

corollary

The dominators of a basic block are totally ordered by the dominance relation.

proof

Suppose @a1 < @b and @a2 < @b, but neither dominates the other. Then, there must exist acyclic paths from @entry to @b which contain both, but in different orders. Take the subpaths of those paths which follow @entry ... @a1, and @a1 ... @b, neither of which contains @a2. Concatenating these paths yields a path from @entry to @b that does not contain @a2, a contradiction.

This tells us that the DAG we get from the dominance relation is actually a tree, rooted at @entry. The parent of a node in this tree is called its immediate dominator.

Computing dominators can be done iteratively: the dominator set of a block @b is the intersection the dominator sets of its preds, plus @b. This algorithm runs in quadratic time.

A better algorithm is the Lengauer-Tarjan algorithm[^lta]. It is relatively simple, but explaining how to implement it is a bit out of scope for this article. I found a nice treatment of it here.

What’s important is we can compute the dominator tree without breaking the bank, and given any node, we can ask for its immediate dominator. Using immediate dominators, we can introduce the final, important property of dominators.

definition

The dominance frontier of a block @a is the set of all blocks not dominated by @a with at least one pred which @a dominates.

These are points where control flow merges from distinct paths: one containing @a and one not. The dominance frontier of @loop.body is @loop.start, whose preds are @entry and @loop.body.

There are many ways to calculate dominance frontiers, but with a dominance tree in hand, we can do it like this:

algorithmDominance Frontiers.

For each block @b with more than one pred, for each of its preds, let @p be that pred. Add @b to the dominance frontier of @p and all of its dominators, stopping when encountering @b’ immediate dominator.

proof

We need to prove that every block examined by the algorithm winds up in the correct frontiers.

First, we check that every examined block @b is added to the correct frontier. If @a < @p, where @p is a pred of @b, and a @d is @b’s immediate dominator, then if @a < @d, @b is not in its frontier, because @a must dominate @b. Otherwise, @b must be in @a’s frontier, because @a dominates a pred but it cannot dominate @b, because then it would be dominated by @i, a contradiction.

Second, we check that every frontier is complete. Consider a block @a. If an examined block @b is in its frontier, then @a must be among the dominators of some pred @p, and it must be dominated by @b’s immediate dominator; otherwise, @a would dominate @b (and thus @b would not be in its frontier). Thus, @b gets added to @a’s dominator.

You might notice that all of these algorithms are quadratic. This is actually a very good time complexity for a compilers-related graph algorithm. Cubic and quartic algorithms are not especially uncommon, and yes, your optimizing compiler’s time complexity is probably cubic or quartic in the size of the program!

Lifting Memory

Ok. Let’s construct an optimization. We want to figure out if we can replace a load from a pointer with the most recent store to that pointer. This will allow us to fully lift values out of memory by cancelling out store/load pairs.

This will make use of yet another implicit graph data structure.

definition

The dataflow graph is the directed graph made up of the internal circuit graphs of each each basic block, connected along block arguments.

To follow a use-def chain is to walk this graph forward from an operation to discover operations that potentially depend on it, or backwards to find operations it potentially depends on.

It’s important to remember that the dataflow graph, like the CFG, does not have a well defined “up” direction. Navigating it and the CFG requires the dominator tree.

One other important thing to remember here is that every instruction in a basic block always executes if the block executes. In much of this analysis, we need to appeal to “program order” to select the last load in a block, but we are always able to do so. This is an important property of basic blocks that makes them essential for constructing optimizations.

Forward Dataflow

For a given store %p, %v, we want to identify all loads that depend on it. We can follow the use-def chain of %p to find which blocks contain loads that potentially depend on the store (call it %s).

First, we can eliminate loads within the same basic block (call it @a). Replace all load %p instructions after s (but before any other store %p, _s, in program order) with %v’s def. If s is not the last store in this block, we’re done.

Otherwise, follow the use-def chain of %p to successors which use %p, i.e., successors whose goto case has %p as at least one argument. Recurse into those successors, and now replacing the pointer %p of interest with the parameters of the successor which were set to %p (more than one argument may be %p).

If successor @b loads from one of the registers holding %p, replace all such loads before a store to %p. We also now need to send %v into @b somehow.

This is where we run into something of a wrinkle. If @b has exactly one predecessor, we need to add a new block argument to pass whichever register is holding %v (which exists by induction). If %v is already passed into @b by another argument, we can use that one.

However, if @b has multiple predecessors, we need to make sure that every path from @a to @b sends %v, and canonicalizing those will be tricky. Worse still, if @b is in @a’s domination frontier, a different store could be contributing to that load! For this reason, dataflow from stores to loads is not a great strategy.

Instead, we’ll look at dataflow from loads backwards to stores (in general, dataflow from uses to defs tends to be more useful), which we can use to augment the above forward dataflow analysis to remove the complex issues around domination frontiers.

Dependency Analysis

Let’s analyze loads instead. For each load %p in @a, we want to determine all stores that could potentially contribute to its value. We can find those stores as follows:

We want to be able to determine which register in a given block corresponds to the value of %p, and then find its last store in that block.

To do this, we’ll flood-fill the CFG backwards in BFS order. This means that we’ll follow preds (through the use-def chain) recursively, visiting each pred before visiting their preds, and never revisiting a basic block (except we may need to come back to @a at the end).

Determining the “equivalent”¹² of %p in @b (we’ll call it %p.b) can be done recursively: while examining @b, follow the def of %p.b. If %p.b is a block parameter, for each pred @c, set %p.c to the corresponding argument in the @b(...) case in @c’s goto.

Using this information, we can collect all stores that the load potentially depends on. If a predecessor @b stores to %p.b, we add the last such store in @b (in program order) to our set of stores, and do not recurse to @b’s preds (because this store overwrites all past stores). Note that we may revisit @a in this process, and collect a store to %p from it occurs in the block. This is necessary in the case of loops.

The result is a set stores of (store %p.s %v.s, @s) pairs. In the process, we also collected a set of all blocks visited, subgraph, which are dominators of @a which we need to plumb a %v.b through. This process is called memory dependency analysis, and is a key component of many optimizations.

note

Not all contributing operations are stores. Some may be references to globals (which we’re disregarding), or function arguments or the results of a function call (which means we probably can’t lift this load). For example %p gets traced all the way back to a function argument, there is a code path which loads from a pointer whose stores we can’t see.

It may also trace back to a stack slot that is potentially not stored to. This means there is a code path that can potentially load uninitialized memory. Like LLVM, we can assume this is not observable behavior, so we can discount such dependencies. If all of the dependencies are uninitialized loads, we can potentially delete not just the load, but operations which depend on it (reverse dataflow analysis is the origin of so-called “time-traveling” UB).

Lifting Loads

Now that we have the full set of dependency information, we can start lifting loads. Loads can be safely lifted when all of their dependencies are stores in the current function, or dependencies we can disregard thanks to UB in the surface language (such as null loads or uninitialized loads).

note

There is a lot of fuss in this algorithm about plumbing values through block arguments. A lot of IRs make a simplifying change, where every block implicitly receives the registers from its dominators as block arguments.

I am keeping the fuss because it makes it clearer what’s going on, but in practice, most of this plumbing, except at dominance frontiers, would be happening in the background.

Suppose we can safely lift some load. Now we need to plumb the stored values down to the load. For each block @b in subgraph (all other blocks will now be in subgraph unless stated otherwise). We will be building two mappings: one (@s, @b) -> %v.s.b, which is the register equivalent to %v.s in that block. We will also be building a map @b -> %v.b, which is the value that %p must have in that block.

1. Prepare a work queue, with each @s in it initially.

2. Pop a block @a form the queue. For each successor @b (in subgraph):

   1. If %v.b isn’t already defined, add it as a block argument. Have @a pass %v.a to that argument.

   2. If @b hasn’t been visited yet, and isn’t the block containing the load we’re deleting, add it to the queue.

Once we’re done, if @a is the block that contains the load, we can now replace all loads to %p before any stores to %p with %v.a.

tip

There are cases where this whole process can be skipped, by applying a “peephole” optimization. For example, stores followed by loads within the same basic block can be optimized away locally, leaving the heavy-weight analysis for cross-block store/load pairs.

Worked Example

Here’s the result of doing dependency analysis on our Fibonacci function. Each load is annotated with the blocks and stores in stores.

func &fib(%n: i32) -> (i32) {
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    store %np, %n  // S1
    store %ap, 0   // S2
    store %bp, 1   // S3

    goto @loop.start(%np, %ap, %bp)

  @loop.start(%np, %ap, %bp: ptr):
    // @entry: S1
    // @loop.body: S6
    %n = load %np  // L1
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap)
      1 -> @loop.body(%np, %ap, %bp),
    }

  @loop.body(%np, %ap, %bp: ptr):
    // @entry: S1
    // @loop.body: S4
    %a = load %ap  // L2
    // @entry: S2
    // @loop.body: S5
    %b = load %bp  // L3
    %c = add %a, %b
    store %ap, %b // S4
    store %bp, %c // S5

    // @entry: S1
    // @loop.body: S6
    %n   = load %np  // L3
    %n.2 = sub %n, 1
    store %np, %n.2  // S6

    goto @loop.start(%np, %ap, %bp)

  @exit(%ap: ptr):
    // @entry: S2
    // @loop.body: S5
    %a = load %ap  // L4
    goto @ret(%ap)
}

Let’s look at L1. Is contributing loads are in @entry and @loop.body. So we add a new parameter %n: in @entry, we call that parameter with %n (since that’s stored to it in @entry), while in @loop.body, we pass %n.2.

What about L4? The contributing loads are also in @entry and @loop.body, but one of those isn’t a pred of @exit. @loop.start is also in the subgraph for this load, though. So, starting from @entry, we add a new parameter %a to @loop.body and feed 0 (the stored value, an immediate this time) through it. Now looking at @loop.body, we see there is already a parameter for this load (%a), so we just pass %b as that argument. Now we process @loop.start, which @entry pushed onto the queue. @exit gets a new parameter %a, which is fed @loop.start’s own %a. We do not re-process @loop.body, even though it also appears in @loop.start’s gotos, because we already visited it.

After doing this for the other two loads, we get this:

func &fib(%n: i32) -> (i32) {
    %np = stack i32
    %ap = stack i32
    %bp = stack i32

    store %np, %n  // S1
    store %ap, 0   // S2
    store %bp, 1   // S3

    goto @loop.start(%np, %ap, %bp, %n, 0, 1)

  @loop.start(%np, %ap, %bp: ptr, %n, %a, %b: i32):
    // @entry: S1
    // @loop.body: S6
    // %n = load %np  // L1
    %cont = cmp.gt %n, 0

    goto %cont {
      0 -> @exit(%ap, %a)
      1 -> @loop.body(%np, %ap, %bp, %n, %a, %b),
    }

  @loop.body(%np, %ap, %bp: ptr, %n, %a, %b: i32):
    // @entry: S1
    // @loop.body: S4
    // %a = load %ap  // L2
    // @entry: S2
    // @loop.body: S5
    // %b = load %bp  // L3
    %c = add %a, %b
    store %ap, %b // S4
    store %bp, %c // S5

    // @entry: S1
    // @loop.body: S6
    // %n   = load %np  // L3
    %n.2 = sub %n, 1
    store %np, %n.2  // S6

    goto @loop.start(%np, %ap, %bp, %n.2, %b, %c)

  @exit(%ap: ptr, %a: i32):
    // @entry: S2
    // @loop.body: S5
    // %a = load %ap  // L4
    goto @ret(%a)
}

After lifting, if we know that a stack slot’s pointer does not escape (i.e., none of its uses wind up going into a function call¹³) or a write to a global (or a pointer that escapes), we can delete every store to that pointer. If we delete every store to a stack slot, we can delete the stack slot altogether (there should be no loads left for that stack slot at this point).

Complications

This analysis is simple, because it assumes pointers do not alias in general. Alias analysis is necessary for more accurate dependency analysis. This is necessary, for example, for lifting loads of fields of structs through subobject pointers, and dealing with pointer arithmetic in general.

However, our dependency analysis is robust to passing different pointers as arguments to the same block from different predecessors. This is the case that is specifically handled by all of the fussing about with dominance frontiers. This robustness ultimately comes from SSA’s circuital nature.

Similarly, this analysis needs to be tweaked to deal with something like select %cond, %a, %b (a ternary, essentially). selects of pointers need to be replaced with selects of the loaded values, which means we need to do the lifting transformation “all at once”: lifting some liftable loads will leave the IR in an inconsistent state, until all of them have been lifted.

Cleanup Passes

Many optimizations will make a mess of the CFG, so it’s useful to have simple passes that “clean up” the mess left by transformations. Here’s some easy examples.

Unused Result Elimination

If an operation’s result has zero uses, and the operation has no side-effects, it can be deleted. This allows us to then delete operations that it depended on that now have no side effects. Doing this is very simple, due to the circuital nature of SSA: collect all instructions whose outputs have zero uses, and delete them. Then, examine the defs of their operands; if those operations now have no uses, delete them, and recurse.

This bubbles up all the way to block arguments. Deleting block arguments is a bit trickier, but we can use a work queue to do it. Put all of the blocks into a work queue.

1. Pop a block from the queue.

2. Run unused result elimination on its operations.

3. If it now has parameters with no uses, remove those parameters.

4. For each pred, delete the corresponding arguments to this block. Then, Place those preds into the work queue (since some of their operations may have lost their last use).

5. If there is still work left, go to 1.

Simplifying the CFG

There are many CFG configurations that are redundant and can be simplified to reduce the number of basic blocks.

For example, unreachable code can help delete blocks. Other optimizations may cause the goto at the end of a function to be empty (because all of its successors were optimized away). We treat an empty goto as being unreachable (since it has no cases!), so we can delete every operation in the block up to the last non-pure operation. If we delete every instruction in the block, we can delete the block entirely, and delete it from its preds’ gotos. This is a form of dead code elimination, or DCE, which combines with the previous optimization to aggressively delete redundant code.

Some jumps are redundant. For example, if a block has exactly one pred and one successor, the pred’s goto case for that block can be wired directly to the successor. Similarly, if two blocks are each other’s unique predecessor/successor, they can be fused, creating a single block by connecting the input blocks’ circuits directly, instead of through a goto.

If we have a ternary select operation, we can do more sophisticated fusion. If a block has two successors, both of which the same unique successor, and those successors consist only of gotos, we can fuse all four blocks, replacing the CFG diamond with a select. In terms of C, this is this transformation:

// Before.
int x;
if (cond) {
  x = a;
} else {
  x = 0;
}

// After.
int x = cond ? a : 0;

LLVM’s CFG simplification pass is very sophisticated and can eliminate complex forms of control flow.

Conclusion

I am hoping to write more about SSA optimization passes. This is a very rich subject, and viewing optimizations in isolation is a great way to understand how a sophisticated optimization pipeline is built out of simple, dumb components.

It’s also a practical application of graph theory that shows just how powerful it can be, and (at least in my opinion), is an intuitive setting for understanding graph theory, which can feel very abstract otherwise.

In the future, I’d like to cover CSE/GVN, loop optimizations, and, if I’m feeling brave, getting out of SSA into a finite-register machine (backends are not my strong suit!).

Go’s interfaces are very funny. Rather than being explicitly implemented, like in Java or Rust, they are simply a collection of methods (a “method set”) that the concrete type must happen to have. This is called structural typing, which is the opposite of nominal typing.

Go interfaces are very cute, but this conceptual simplicity leads to a lot of implementation problems (a theme with Go, honestly). It removes a lot of intentionality from implementing interfaces, and there is no canonical way to document that A satisfies¹ B, nor can you avoid conforming to interfaces, especially if one forces a particular method on you.

It also has very quirky results for the language runtime. To cast an interface value to another interface type (via the type assertion syntax a.(B)), the runtime essentially has to use reflection to go through the method set of the concrete type of a. I go into detail on how this is implemented here.

Because of their structural nature, this also means that you can’t add new methods to an interface without breaking existing code, because there is no way to attach default implementations to interface methods. This results in very silly APIs because someone screwed up an interface.

flag.Value is a Mess

For example, in the standard library’s package flag, the interface flag.Value represents a value which can be parsed as a CLI flag. It looks like this:

type Value interface {
  // Get a string representation of the value.
  String() string

  // Parse a value from a string, possibly returning an error.
  Set(string) error
}

flag.Value also has an optional method, which is only specified in the documentation. If the concrete type happens to provide IsBoolFlag() bool, it will be queries for determining if the flag should have bool-like behavior. Essentially, this means that something like this exists in the flag library:

var isBool bool
if b, ok := value.(interface{ IsBoolFlag() bool }); ok {
  isBool = b.IsBoolFlag()
}

The flag package already uses reflection, but you can see how it might be a problem if this interface-to-interface cast happens regularly, even taking into account Go’s caching of cast results.

There is also flag.Getter, which exists because they messed up and didn’t provide a way for a flag.Value to unwrap into the value it contains. For example, if a flag is defined with flag.Int, and then that flag is looked up with flag.Lookup, there’s no straightforward way to get the int out of the returned flag.Value.

Instead, you have to side-cast to flag.Getter:

type Getter interface {
  Value

  // Returns the value of the flag.
  Get() any
}

As a result, flag.Lookup("...").(flag.Getter) needs to do a lot more work than if flag.Value had just added Get() any, with a default return value of nil.

It turns out that there is a rather elegant workaround for this.

Struct Embeddings

Go has this quirky feature called embedding, where a a field in a struct is declared without a name:

type (
  A int
  B struct{
    A
    Foo int
  }
)

The A-typed embedded field behaves as if we had declared the field A A, but selectors on var b B will search in A if they do not match something on the B level. For example, if A has a method Bar, and B does not, b.Bar() will resolve to b.A.Bar(). However, if A has a method Foo, b.Foo resolves to b.Foo, not b.A.Foo, because b has a field Foo.

Importantly, any methods from A which B does not already have will be added to B’s method set. So this works:

type (
  A int
  B struct{ A }
  C interface {
    Foo()
    Bar()
  }
)

func (A) Foo() {}
func (B) Bar() {}

var _ C = B{}  // B satisfies C.

Now, suppose that we were trying to add Get() any to flag.Value. Let’s suppose that we had also defined flag.ValueDefaults, a type that all satisfiers of flag.Value must embed. Then, we can write the following:

type Value interface{
  String() string
  Set(string) error

  Get() any  // New method.
}

type ValueDefaults struct{}

func (ValueDefaults) Get() { return nil }

Then, no code change is required for all clients to pick up the new implementation of Get().

Required Embeds

Now, this only works if we had required in the first place that anyone satisfying flag.Value embeds flag.ValueDefaults. How can we force that?

A little-known Go feature is that interfaces can have unexported methods. The way these work, for the purposes of interface conformance, is that exported methods are matched just by their name, but unexported methods must match both name and package.

So, if we have an interface like interface { foo() }, then foo will only match methods defined in the same package that this interface expression appears. This is useful for preventing satisfaction of interfaces.

However, there is a loophole: embedding inherits the entire method set, including unexported methods. Therefore, we can enhance Value to account for this:

type Value interface{
  String() string
  Set(string) error

  Get() any  // New method.

  value() // Unexported!
}

type ValueDefaults struct{}

func (ValueDefaults) Get() { return nil }
func (ValueDefaults) value() {}

Now, it’s impossible for any type defined outside of this package to satisfy flag.Value, without embedding flag.ValueDefaults (either directly or through another embedded flag.Value).

Exported Struct Fields

Now, another problem is that you can’t control the name of embedded fields. If the embedded type is Foo, the field’s name is Foo. Except, it’s not based on the name of the type itself; it will pick up the name of a type alias. So, if you want to unexport the defaults struct, you can simply write:

type MyValue struct {
  valueDefaults

  // ...
}

type valueDefaults = flag.ValueDefaults

This also has the side-effect of hiding all of ValueDefaults’ methods from MyValue’s documentation, despite the fact that exported and fields methods are still selectable and callable by other packages (including via interfaces). As far as I can tell, this is simply a bug in godoc, since this behavior is not documented.

What About Same-Name Methods?

There is still a failure mode: if a user type satisfying flag.Value happened to define a Get method with a different interface. In this case, that Get takes precedence, and changes to flag.Value will break users.

There are two workarounds:

1. Tell people not to define methods on their satisfying type, and if they do, they’re screwed. Because satisfying flag.Value is now explicit, this is not too difficult to ask for.

2. Pick a name for new methods that is unlikely to collide with anything.

Unfortunately, this runs into a big issue with structural typing, which is that it is very difficult to avoid making mistakes when making changes, due to the lack of intent involved. A similar problem occurs with C++ templates, where the interfaces defined by concepts are implicit, and can result in violating contract expectations.

Go has historically be relatively cavalier about this kind of issue, so I think that breaking people based on this is fine.

And of course, you cannot retrofit a default struct into a interface; you have to define it from day one.

Using Defaults

Now that we have defaults, we can also enhance flag.Value with bool flag detection:

type Value interface{
  String() string
  Set(string) error

  Get() any
  IsBoolFlag() bool

  value() // Unexported!
}

type ValueDefaults struct{}

func (ValueDefaults) Get() { return nil }
func (ValueDefaults) IsBoolFlag() { return false }
func (ValueDefaults) value() {}

Now IsBoolFlag is more than just a random throw-away comment on a type.

We can also use defaults to speed up side casts. Many functions around the io package will cast an io.Reader into an io.Seeker or io.ReadAt to perform more efficient I/O.

In a hypothetical world where we had defaults structs for all the io interfaces, we can enhance io.Reader with a ReadAt default method that by default returns an error.

type Reader interface {
  Read([]byte) (int, error)
  ReadAt([]byte, int64) (int, error)

  reader()
}

type ReaderDefaults struct{}

func (ReaderDefaults) ReadAt([]byte, int64) (int, error) {
  return 0, errors.ErrUnsupported
}
func (ReaderDefaults) reader() {}

We can do something similar for io.Seeker, but because it’s a rather general interface, it’s better to keep io.Seeker as-is. So, we can add a conversion method:

type Reader interface {
  Seeker() io.Seeker

  // ...
}

type ReaderDefaults struct{}

func (ReaderDefaults) Seeker([]byte, int64) io.Seeker {
  return nil
}

Here, Reader.Seeker() converts to an io.Seeker, returning nil if that’s not possible. How is this faster than r.(io.Seeker)? Well, consider what this would look like in user code:

type MyIO struct{
  io.ReaderDefaults
  // ...
}

func (m *MyIO) Read(b []byte) (int, error) { /* ... */ }
func (m *MyIO) Seek(offset int64, whence int) (int64, error) { /* ... */ }

func (m *MyIO) Seeker() io.Seeker {
  return m
}

Calling r.Seeker(), if r is an io.Reader containing a MyIO, lowers to the following machine code:

1. Load the function pointer for Seeker out of r’s itab.
2. Perform an indirect jump on that function pointer.
3. Inside of (*MyIO).Seeker, load a pointer to the itab symbol go:itab.*MyIO,io.Seeker and m into the return slots.
4. Return.

The main cost of this conversion is the indirect jump, compared to, at minimum, hitting a hashmap lookup loop for the cache for r.(io.Seeker).

Does this performance matter? Not for I/O interfaces, probably, but it can matter for some uses!

Shouldn’t This Be a Language Feature?

Yes, it should, but here we are. Although making it a language feature has a few rather unfortunate quirks that we need to keep in mind.

Suppose we can define defaults on interface methods somehow, like this:

type Foo interface{
  Bar()
  Baz()
}

func (f Foo) Baz() {
  // ...
}

Then, any type which provides Bar() automatically satisfies Foo. Suppose MyFoo satisfies Foo, but does not provide Baz. Then we have a problem:

var x MyFoo
x.Baz()       // Error!
Foo(x).Baz()  // Ok!

Now, we might consider looking past that, but it becomes a big problem with reflection. If we passed Foo(x) into reflect.ValueOf, the resulting any conversion would discard the defaulted method, meaning that it would not be findable by reflect.Value.MethodByName(). Oops.

So we need to somehow add Baz to MyFoo’s method set. Maybe we say that if MyFoo is ever converted into Foo, it gets the method. But this doesn’t work, because the compiler might not be able to see through something like any(MyFoo{...}).(Foo). This means that Baz must be applied unconditionally. But, now we have the problem that if we have another interface interface { Bar(); Baz(int) }, MyFoo would need to receive incompatible signatures for Baz.

Again, we’re screwed by the non-intentionality of structural typing.

Missing Methods

Ok, let’s forget about default method implementations, that doesn’t seem to be workable. What if we make some methods optional, like IsBoolFlag() earlier? Let’s invent some syntax for it.

type Foo interface {
  Bar()
  ?Baz() // Optional method.
}

Then, suppose that MyFoo provides Bar but not Baz (or Baz with the wrong signature). Then, the entry in the itab for Baz would contain a nil function pointer, such that x.Baz() panics! To determine if Baz is safe to call, we would use the following idiom:

if x.Baz != nil {
  x.Baz()
}

The compiler is already smart enough to elide construction of funcvals for cases like this, although it does mean that x.Func in general, for an interface value x, requires an extra cmov or similar to make sure that x.Func is nil when it’s a missing method.

All of the use cases described above would work Just Fine using this construction, though! However, we run into the same issue that Foo(x) appears to have a larger method set than x. It is not clear if Foo(x) should conform to interface { Bar(); Baz() }, where Baz is required. My intuition would be no: Foo is a strictly weaker interface. Perhaps it might be necessary to avoid the method access syntax for optional methods, but that’s a question of aesthetics.

This idea of having nulls in place of function pointers in a vtable is not new, but to my knowledge is not used especially widely. It would be very useful in C++, for example, to be able to determine if no implementation was provided for a non-pure virtual function. However, the nominal nature of C++’s virtual functions does not make this as big of a need.

Related Interfaces

Another alternative is to store a related interfaces’ itabs on in an itab. For example, suppose that we invent the syntax A<- within an interface{} to indicate that that interface will likely get cast to A. For example:

type (
  A interface{
    Foo()
  }

  B interface{
    Bar()

    A<-
  }
)

Satisfying B does not require satisfying A. However, the A<- must be part of public API, because a interface{ Bar() } cannot be used in place of an interface{ A<- }

Within B’s itab, after all of the methods, there is a pointer to an itab for A, if the concrete type for this itab also happens to satisfy A. Then, a cast from B to A is just loading a pointer from the itab. If the cast would fail, the loaded pointer will be nil.

I had always assumed that Go did an optimization like this for embedding interfaces, but no! Any inter-interface conversion, including upcasts, goes through the whole type assertion machinery! Of course, Go cannot hope to generate an itab for every possible subset of the method set of an interface (exponential blow-up), but it’s surprising that they don’t do this for embedded interfaces, which are Go’s equivalent of superinterfaces (present in basically every language with interfaces).

Using this feature, we can update flag.Value to look like this:

type Value interface {
  String() string
  Set(string) error

  BoolValue<-
  Getter<-
}

type BoolValue interface {
  Value
  IsBoolFlag() bool
}

type Getter interface {
  Value
  Get() any
}

Unfortunately, because A<- changes the ABI of an interface, it does not seem possible to actually add this to existing interfaces, because the following code is valid:

type A interface {
  Foo()
}

var (
  a A
  b interface{ Foo() }
)

a, b = b, a

Even though this fix seems really clean, it doesn’t work! The only way it could work is if PGO determines that a particular interface conversion A to B happens a lot, and updates the ABI of all interfaces with the method set of A, program-globally, to contain a pointer to a B itab if available.

Conclusion

Go’s interfaces are pretty bad; in my opinion, a feature that looks good on a slide, but which results in a lot of mess due to its granular and intention-less nature. We can sort of patch over it with embeds, but there’s still problems.

Due to how method sets work in Go, it’s very hard to “add” methods through an interface, and honestly at this point, any interface mechanism that makes it impossible (or expensive) to add new functions is going to be a huge problem.

Missing methods seems like the best way out of this problem, but for now, we can stick to the janky embedded structs.

Historically I have worked on many projects related to high-performance Protobuf, be that on the C++ runtime, on the Rust runtime, or on integrating UPB, the fastest Protobuf runtime, written by my colleague Josh Haberman. I generally don’t post directly about my current job, but my most recent toy-turned-product is something I’m very excited to write about: hyperpb.

Here’s how we measure up against other Go Protobuf parsers. This is a subset of my benchmarks, since the benchmark suite contains many dozens of specimens. This was recorded on an AMD Zen 4 machine.

Traditionally, Protobuf backends would generate parsers by generating source code specialized to each type. Naively, this would give the best performance, because everything would be “right-sized” to a particular message type. Unfortunately, now that we know better, there are a bunch of drawbacks:

1. Every type you care about must be compiled ahead-of-time. Tricky for when you want to build something generic over schemas your users provide you.
2. Every type contributes to a cost on the instruction cache, meaning that if your program parses a lot of different types, it will essentially flush your instruction cache any time you enter a parser. Worse still, if a parse involves enough types, the parser itself will hit instruction decoding throughput issues.

These effects are not directly visible in normal workloads, but other side-effects are visible: for example, giant switches on field numbers can turn into chains of branch instructions, meaning that higher-numbered fields will be quite slow. Even binary-searching on field numbers isn’t exactly ideal. However, we know that every Protobuf codec ever emits fields in index order (i.e., declaration order in the .proto file), which is a data conditioning fact we don’t take advantage of with a switch.

UPB solves this problem. It is a small C kernel for parsing Protobuf messages, which is completely dynamic: a UPB “parser” is actually a collection of data tables that are evaluated by a table-driven parser. In other words, a UPB parser is actually configuration for an interpreter VM, which executes Protobuf messages as its bytecode. UPB also contains many arena optimizations to improve allocation throughput when parsing complex messages.

hyperpb is a brand new library, written in the most cursed Go imaginable, which brings many of the optimizations of UPB to Go, and many new ones, while being tuned to Go’s own weird needs. The result leaves the competition in the dust in virtually every benchmark, while being completely runtime-dynamic. This means it’s faster than Protobuf Go’s own generated code, and vtprotobuf (a popular but non-conforming¹ parser generator for Go).

This post is about some of the internals of hyperpb. I have also prepared a more sales-ey writeup, which you can read on the Buf blog.

Why Reinvent UPB?

UPB is awesome. It can slot easily into any language that has C FFI, which is basically every language ever.

Unfortunately, Go’s C FFI is really, really bad. It’s hard to overstate how bad cgo is. There isn’t a good way to cooperate with C on memory allocation (C can’t really handle Go memory without a lot of problems, due to the GC). Having C memory get cleaned up by the GC requires finalizers, which are very slow. Calling into C is very slow, because Go pessimistically assumes that C requires a large stack, and also calling into C does nasty things to the scheduler.

All of these things can be worked around, of course. For a while I considered compiling UPB to assembly, and rewriting that assembly into Go’s awful assembly syntax², and then having Go assemble UPB out of that. This presents a few issues though, particularly because Go’s assembly calling convention is still in the stone age³ (arguments are passed on the stack), and because we would still need to do a lot of work to get UPB to match the protoreflect API.

Go also has a few… unique qualities that make writing a Protobuf interpreter an interesting challenge with exciting optimization opportunities.

First, of course, is the register ABI, which on x86_64 gives us a whopping nine argument and return registers, meaning that we can simply pass the entire parser state in registers all the time.

Second is that Go does not have much UB to speak of, so we can get away with a lot of very evil pointer crimes that we could not in C++ or Rust.

Third is that Protobuf Go has a robust reflection system that we can target if we design specifically for it.

Also, the Go ecosystem seems much more tolerant of less-than-ideal startup times (because the language loves life-before-main due to init() functions), so unlike UPB, we can require that the interpreter’s program be generated at runtime, meaning that we can design for online PGO. In other words, we have the perfect storm to create the first-ever Protobuf JIT compiler (which we also refer to as “online PGO” or “real-time PGO”).

hyperpb’s API

Right now, hyperpb’s API is very simple. There are hyperpb.Compile* functions that accept some representation of a message descriptor, and return a *hyperpb.MessageType, which implements the protoreflect type APIs. This can be used to allocate a new *hyperpb.Message , which you can shove into proto.Unmarshal and do reflection on the result. However, you can’t mutate *hyperpb.Messages currently, because the main use-cases I am optimizing for are read-only. All mutations panic instead.

The hero use-case, using Buf’s protovalidate library, uses reflection to execute validation predicates. It looks like this:

// Compile a new message type, deserializing an encoded FileDescriptorSet.
msgType := hyperpb.CompileForBytes(schema, "my.api.v1.Request")

// Allocate a new message of that type.
msg := hyperpb.NewMessage(msgType)

// Unmarshal like you would any other message, using proto.Unmarshal.
if err := proto.Unmarshal(data, msg); err != nil {
    // Handle parse failure.
}

// Validate the message. Protovalidate uses reflection, so this Just Works.
if err := protovalidate.Validate(msg); err != nil {
    // Handle validation failure.
}

We tell users to make sure to cache the compilation step because compilation can be arbitrarily slow: it’s an optimizing compiler! This is not unlike the same warning on regexp.Compile, which makes it easy to teach users how to use this API correctly.

In addition to the main API, there’s a bunch of performance tuning knobs for the compiler, for unmarshaling, and for recording profiles. Types can be recompiled using a recorded profile to be more optimized for the kinds of messages that actually come on the wire. hyperpb PGO⁴ affects a number of things that we’ll get into as I dive into the implementation details.

The Guts

Most of the core implementation lives under internal/tdp. The main components are as follows:

1. tdp, which defines the “object code format” for the interpreter. This includes definitions for describing types and fields to the parser.
2. tdp/compiler, which contains all of the code for converting a protoreflect.MessageDescriptor into a tdp.Library, which contains all of the types relevant to a particular parsing operation.
3. tdp/dynamic defines what dynamic message types look like. The compiler does a bunch of layout work that gets stored in tdp.Type values, which a dynamic.Message interprets to find the offsets of fields within itself.
4. tdp/vm contains the core interpreter implementation, including the VM state that is passed in registers everywhere. It also includes hand-optimized routines for parsing varints and validating UTF-8.
5. tdp/thunks defines archetypes, which are classes of fields that all use the same layout and parsers. This corresponds roughly to a (presence, kind) pair, but not exactly. There are around 200 different archetypes.

This article won’t be a deep-dive into everything in the parser, and even this excludes large portions of hyperpb. For example, the internal/arena package is already described in a different blogpost of mine. I recommend taking a look at that to learn about how we implement a GC-friendly arena for hyperpb .

Instead, I will give a brief overview of how the object code is organized and how the parser interprets it. I will also go over a few of the more interesting optimizations we have.

tdp.Type

Every MessageDescriptor that is reachable from the root message (either as a field or as an extension) becomes a tdp.Type . This contains the dynamic size of the corresponding message type, a pointer to the type’s default parser (there can be more than one parser for a type) and a variable number of tdp.Field values. These specify the offset of each field and provide accessor thunks, for actually extracting the value of the field.

A tdp.TypeParser is what the parser VM interprets alongside encoded Protobuf data. It contains all of the information needed for decoding a message in compact form, including tdp.FieldParsers for each of its fields (and extensions), as well as a hashtable for looking up a field by tag, which is used by the VM as a fallback.

The tdp.FieldParsers each contain:

1. The same offset information as a tdp.Field.
2. The field’s tag, in a special format.
3. A function pointer that gets called to parse the field.
4. The next field(s) to try parsing after this one is parsed.

Each tdp.FieldParser actually corresponds to a possible tag on a record for this message. Some fields have multiple different tags: for example, a repeated int32 can have a VARINT-type tag for the repeated representation, and a LEN-type tag for the packed representation.

Each field specifies which fields to try next. This allows the compiler to perform field scheduling, by carefully deciding which order to try fields in based both on their declaration order and a rough estimation of their “hotness”, much like branch scheduling happens in a program compiler. This avoids almost all of the work of looking up the next field in the common case, because we have already pre-loaded the correct guess.

I haven’t managed to nail down a good algorithm for this yet, but I am working on a system for implementing a type of “branch prediction” for PGO, that tries to provide better predictions for the next fields to try based on what has been seen before.

The offset information for a field is more than just a memory offset. A tdp.Offset includes a bit offset, for fields which request allocation of individual bits in the message’s bitfields. These are used to implement the hasbits of optional fields (and the values of bool fields). It also includes a byte offset for larger storage. However, this byte offset can be negative, in which case it’s actually an offset into the cold region.

In many messages, most fields won’t be set, particularly extensions. But we would like to avoid having to allocate memory for the very rare (i.e., “cold”) fields. For this, a special “cold region” exists in a separate allocation from the main message, which is referenced via a compressed pointer. If a message happens to need a cold field set, it takes a slow path to allocate a cold region only if needed. Whether a field is cold is a dynamic property that can be affected by PGO.

The Parser VM

The parser is designed to make maximal use of Go’s generous ABI without spilling anything to the stack that isn’t absolutely necessary. The parser state consists of eight 64-bit integers, split across two types: vm.P1 and vm.P2. Unfortunately, these can’t be merged due to a compiler bug, as documented in vm/vm.go.

Every parser function takes these two structs as its first two arguments, and returns them as its first two results. This ensures that register allocation tries its darnedest to keep those eight integers in the first eight argument registers, even across calls. This leads to the common idiom of

var n int
p1, p2, n = DoSomething(p1, p2)

Overwriting the parser state like this ensures that future uses of p1 and p2 use the values that DoSomething places in registers for us.

I spent a lot of time and a lot of profiling catching all of the places where Go would incorrectly spill parser state to the stack, which would result in stalls. I found quite a few codegen bugs in the process. Particularly notable (and shocking!) is #73589. Go has somehow made it a decade without a very basic pointer-to-SSA lifting pass (for comparison, this is a heavy-lifting cleanup pass (mem2reg) in LLVM).

The core loop of the VM goes something like this:

1. Are we out of bytes to parse? If so, pop a parser stack frame⁵. If we popped the last stack frame, parsing is done; return success.
2. Parse a tag. This does not fully decode the tag, because tdp.FieldParsers contain a carefully-formatted, partially-decoded tag to reduce decoding work.
3. Check if the next field we would parse matches the tag.
   1. If yes, call the function pointer tdp.Field.Parser; update the current field to tdp.Field.NextOk; goto 1.
   2. If no, update the current field to tdp.Field.NextErr; goto 3.
   3. If no “enough times”, fall through.
4. Slow path: hit tdp.Field.Tags to find the matching field for that tag.
   1. If matched, go to 3a.
   2. If not, this is an unknown field; put it into the unknown field set; parse a tag and goto 4.

Naturally, this is implemented as a single function whose control flow consists exclusively of ifs and gotos, because getting Go to generate good control flow otherwise proved too hard.

Now, you might be wondering why the hot loop for the parser includes calling a virtual function. Conventional wisdom holds that virtual calls are slow. After all, the actual virtual call instruction is quite slow, because it’s an indirect branch, meaning that it can easily stall the CPU. However, it’s actually much faster than the alternatives in this case, due to a few quirks of our workload and how modern CPUs are designed:

1. Modern CPUs are not great at traversing complex “branch mazes”. This means that selecting one of ~100 alternatives using branches, even if they are well-predicted and you use unrolled binary search, is still likely to result in frequent mispredictions, and is an obstacle to other JIT optimizations in the processor’s backend.
2. Predicting a single indirect branch with dozens of popular targets is something modern CPUs are pretty good at. Chips and Cheese have a great writeup on the indirect prediction characteristics of Zen 4 chips.

In fact, the “optimized” form of a large switch is a jump table, which is essentially an array of function pointers. Rather than doing a large number of comparisons and direct branches, a jump table turns a switch into a load and an indirect branch.

This is great news for us, because it means we can make use of a powerful assumption about most messages: most messages only feature a handful of field archetypes. How often is it that you see a message which has more in it than int32, int64, string , and submessages? In effect, this allows us to have a very large “instruction set”, consisting of all of the different field archetypes, but a particular message only pays for what it uses. The fewer archetypes it uses at runtime, the better the CPU can predict this indirect jump.

On the other hand, we can just keep adding archetypes over time to specialize for common parse workloads, which PGO can select for. Adding new archetypes that are not used by most messages does not incur a performance penalty.

Other Optimizations

We’ve already discussed the hot/cold split, and briefly touched on the message bitfields used for bools and hasbits. I’d like to mention a few other cool optimizations that help cover all our bases, as far as high-performance parsing does.

Zerocopy Strings

The fastest memcpy implementation is the one you don’t call. For this reason, we try to, whenever possible, avoid copying anything out of the input buffer. strings and bytes are represented as zc.Ranges, which are a packed pair of offset+length in a uint64. Protobuf is not able to handle lengths greater than 2GB properly, so we can assume that this covers all the data we could ever care about. This means that a bytes field is 8 bytes, rather than 24, in our representation.

Zerocopy is also used for packed fields. For example, a repeated double will typically be encoded as a LEN record. The number of float64s in this record is equal to its length divided by 8, and the float64s are already encoded in IEEE754 format for us. So we can just retain the whole repeated fields as a zc.Range . Of course, we need to be able to handle cases where there are multiple disjoint records, so the backing repeated.Scalars can also function as a 24-byte arena slice. Being able to switch between these modes gracefully is a delicate and carefully-tested part of the repeated field thunks.

Surprisingly, we also use zerocopy for varint fields, such as repeated int32. Varints are variable-length, so we can’t just index directly into the packed buffer to get the n th element… unless all of the elements happen to be the same size. In the case that every varint is one byte (so, between 0 and 127), we can zerocopy the packed field. This is a relatively common scenario, too, so it results in big savings⁶. We already count the number of varints in the packed field in order to preallocate space for it, so this doesn’t add extra cost. This counting is very efficient because I have manually vectorized the loop.

Repeated Preloads

PGO records the median size of each repeated/map field, and that is used to calculate a “preload” for each repeated field. Whenever the field is first allocated, it is pre-allocated using the preload to try to right-size the field with minimal waste.

Using the median ensures that large outliers don’t result in huge memory waste; instead, this guarantees that at least 50% of repeated fields will only need to allocate from the arena once. Packed fields don’t use the preload, since in the common case only one record appears for packed fields. This mostly benefits string- and message-typed repeated fields, which can’t be packed.

Map Optimizations

We don’t use Go’s built-in map, because it has significant overhead in some cases: in particular, it has to support Go’s mutation-during-iteration semantics, as well as deletion. Although both are Swisstables⁷ under the hood, my implementation can afford to take a few shortcuts. It also allows our implementation to use arena-managed memory. swiss.Tables are used both for the backing store of map fields, and for maps inside of tdp.Types.

Currently, the hash used is the variant of fxhash used by the Rust compiler. This greatly out-performs Go’s maphash for integers, but maphash is better for larger strings. I hope to maybe switch to maphash at some point for large strings, but it hasn’t been a priority.

Arena Reuse

Hitting the Go allocator is always going to be a little slow, because it’s a general-case allocator. Ideally, we should learn the estimated memory requirements for a particular workload, and then allocate a single block of that size for the arena to portion out.

The best way to do this is via arena reuse In the context of a service, each request has a bounded lifetime on the message that it parses. Once that lifetime is over (the request is complete), the message is discarded. This gives the programmer an opportunity to reset the backing arena, so that it keeps its largest memory block for re-allocation.

You can show that over time, this will cause the arena to never hit the Go allocator. If the largest block is too small for a message, a block twice as large will wind up getting allocated. Messages that use the same amount of memory will keep doubling the largest block, until the largest block is large enough to fit the whole message. Memory usage will be at worst 2x the size of this message. Note that, thanks to extensive use of zero-copy optimizations, we can often avoid allocating memory for large portions of the message.

Of course, arena re-use poses a memory safety danger, if the previously allocated message is kept around after the arena is reset. For this reason, it’s not the default behavior. Using arena resets is a double-digit percentage improvement, however.

Oneof Unions

Go does not properly support unions, because the GC does not keep the necessary book-keeping to distinguish a memory location that may be an integer or a pointer at runtime. Instead, this gets worked around using interfaces, which is always a pointer to some memory. Go’s GC can handle untyped pointers just fine, so this just works.

The generated API for Protobuf Go uses interface values for oneofs. This API is… pretty messy to use, unfortunately, and triggers unnecessary allocations, (much like optional fields do in the open API).

However, my arena design (read about it here) makes it possible to store arena pointers on the arena as if they are integers, since the GC does not need to scan through arena memory. Thus, our oneofs are true unions, like in C++.

Conclusion

hyperpb is really exciting because its growing JIT capabilities offer an improvement in the state of the art over UPB. It’s also been a really fun challenge working around Go compiler bugs to get the best assembly possible. The code is already so well-optimized that re-building the benchmarks with the Go compiler’s own PGO mode (based on a profile collected from the benchmarks) didn’t really seem to move the needle!

I’m always working on making hyperpb better (I get paid for it!) and I’m always excited to try new optimizations. If you think of something, file an issue! I have meticulously commented most things within hyperpb , so it should be pretty easy to get an idea of where things are if you want to contribute.

I would like to write more posts diving into some of the weeds of the implementation. I can’t promise anything, but there’s lots to talk about. For now… have fun source-diving!

There’s a lot of other things we could be doing: for example, we could be using SIMD to parse varints, we could have smarter parser scheduling, we could be allocating small submessages inline to improve locality… there’s still so much we can do!

And most importantly, I hope you’ve learned something new about performance optimization!

It’s no secret that my taste in programming languages is very weird for a programming language enthusiast professional. Several of my last few posts are about Go, broadly regarded as the programming language equivalent of eating plain oatmeal for breakfast.

To make up for that, I’m going to write about the programming language equivalent of diluting your morning coffee with Everclear. I am, of course, talking about C++.

If you’ve ever had the misfortune of doing C++ professionally, you’ll know that the C++ standard library is really bad. Where to begin?

Well, the associative containers are terrible. Due to bone-headed API decisions, std::unordered_map MUST be a closed-addressing, array-of-linked-lists map, not a Swisstable, despite closed-addressing being an outdated technology. std::map, which is not what you usually want, must be a red-black tree. It can’t be a b-tree, like every sensible language provides for the ordered map.

std::optional is a massive pain in the ass to use, and is full of footguns, like operator*. std::variant is also really annoying to use. std::filesystem is full of sharp edges. And where are the APIs for signals?

Everything is extremely wordy. std::hardware_destructive_interference_size could have been called std::cache_line. std::span::subspan could have used opeartor[]. The standard algorithms are super wordy, because they deal with iterator pairs. Oh my god, iterator pairs. They added std::ranges, which do not measure up to Rust’s Iterator at all!

I’m so mad about all this! The people in charge of C++ clearly, actively hate their users!¹ They want C++ to be as hard and unpleasant as possible to use. Many brilliant people that I am lucky to consider friends and colleagues, including Titus Winters, JeanHeyd Meneide, Matt Fowles-Kulukundis, and Andy Soffer, have tried and mostly failed² to improve the language.

This is much to say that I believe C++ in its current form is unfixable. But that’s only due to the small-mindedness of a small cabal based out of Redmond. What if we could do whatever we wanted? What if we used C++’s incredible library-building language features to build a brand-new language?

For the last year-or-so I’ve been playing with a wild idea: what would C++ look like if we did it over again? Starting from an empty C++20 file with no access to the standard library, what can we build in its place?

Starting Over

Titus started Abseil while at Google, whose namespace, absl, is sometimes said to stand for “a better standard library”³. To me, Abseil is important because it was an attempt to work with the existing standard library and make it better, while retaining a high level of implementation quality that a C++ shop’s home-grown utility library won’t have, and a uniformity of vision that Boost is too all-over-the-place to achieve.

Rather than trying to coexist with the standard library, I want to surpass it. As a form of performance art, I want to discover what the standard library would look like if we designed it today, in 2025.

In this sense, I want to build something that isn’t just better. It should be the C++ standard library from the best possible world. It is the best possible library. This is why my library’s namespace is best.

In general, I am trying not to directly copy either what C++, or Abseil, or Rust, or Go did. However, each of them has really interesting ideas, and the best library probably lies in some middle-ground somewhere.

The rest of this post will be about what I have achieved with best so far, and where I want to take it. You can look at the code here.

Building a Foundation

We’re throwing out everything, and that includes <type_traits>. This is a header which shows its age: alias templates were’t added until C++14, and variable templates were added in C++17. As a result, many things that really aught to be concepts have names like best::is_same_v. All of these now have concept equivalents in <concepts>.

I have opted to try to classify type traits into separate headers to make them easier to find. They all live under //best/meta/traits, and they form the leaves of the dependency graph.

For example, arrays.h contains all of the array traits, such as best::is_array, best::un_array (to remove an array extent), and best::as_array, which applies an extent to a type T, such that best::as_array<T, 0> is not an error.

types.h contains very low-level metaprogramming helpers, such as:

• best::id and best::val, the identity traits for type- and value-kinded traits.
• best::same<...>, which returns whether an entire pack of types is all equal.
• best::lie, our version of std::declval.
• best::select, our std::conditional_t.
• best::abridge, a “symbol compression” mechanism for shortening the names of otherwise huge symbols.

funcs.h provides best::tame, which removes the qualifiers from an abominable function type. quals.h provides best::qualifies_to, necessary for determining if a type is “more const” than another. empty.h provides a standard empty type that interoperates cleanly with void.

On top of the type traits is the metaprogramming library //best/meta, which includes generalized constructibility traits in init.h (e.g., to check that you can, in fact, initialize a T& from a T&&, for example). tlist.h provides a very general type-level heterogenous list abstraction; a parameter pack as-a-type.

The other part of “the foundation” is //best/base, which mostly provides access to intrinsics, portability helpers, macros, and “tag types” such as our versions of std::in_place. For example, macro.h provides BEST_STRINGIFY(), port.h provides BEST_HAS_INCLUDE(), and hint.h provides best::unreachable().

guard.h provides our version of the Rust ? operator, which is not an expression because statement expressions are broken in Clang.

Finally, within //best/container we find best::object, a special type for turning any C++ type into an object (i.e., a type that you can form a reference to). This is useful for manipulating any type generically, without tripping over the assign-through semantics of references. For example, best::object<T&> is essentially a pointer.

“ADT” Containers

On top of this foundation we build the basic algebraic data types of best: best::row and best::choice, which replace std::tuple and std::variant.

best::row<A, B, C> is a heterogenous collection of values, stored inside of best::objects. This means that best::row<int&> has natural rebinding, rather than assign-through, semantics.

Accessing elements is done with at(): my_row.at<0>() returns a reference to the first element. Getting the first element is so common that you can also use my_row.first(). Using my_row.object<0>() will return a reference to a best::object instead, which can be used for rebinding references. For example:

int x = 0, y = 0;
best::row<int&> a{x};
a.at<0>() = 42;     // Writes to x.
a.object<0>() = y;  // Rebinds a.0 to y.
a.at<0>() = 2*x;    // Writes to y.

There is also second() and last(), for the other two most common elements to access.

best::row is named so in reference to database rows: it provides many operations for slicing and dicing that std::tuple does not.

For example, in addition to extracting single elements, it’s also possible to access contiguous subsequences, using best::bounds: a.at<best::bounds{.start = 1, .end = 10}>()! There are also a plethora of mutation operations:

• a + b concatenates tuples, copying or moving as appropriate (a + BEST_MOVE(b) will move out of the elements of b, for example).
• a.push(x) returns a copy of a with x appended, while a.insert<n>(x) does the same at an arbitrary index.
• a.update<n>(x) replaces the nth element with x, potentially of a different type.
• a.remove<n>() deletes the nth element, while a.erase<...>() deletes a contiguous range.
• a.splice<best::bounds{...}>(...) splices a row into another row, offering a general replace/delete operation that all of the above operations are implemented in terms of.
• gather() and scatter() are even more general, allowing for non-contiguous indexing.

Meanwhile, std::apply is a method now: a.apply(f) calls f with a’s elements as its arguments. a.each(f) is similar, but instead expands to n unary calls of f, one with each element.

And of course, best::row supports structured bindings.

Meanwhile, best::choice<A, B, C> contains precisely one value from various types. There is an underlying best::pun<A, B, C> type that implements a variadic untagged union that works around many of C++’s bugs relating to unions with members of non-trivial type.

The most common way to operate on a choice is to match on it:

best::choice<int, *int, void> z = 42;
int result = z.match(
  [](int x) { return x; },
  [](int* x) { return *x; },
  [] { return 0; }
);

Which case gets called here is chosen by overload resolution, allowing us to write a default case as [](auto&&) { ... }.

Which variant is currently selected can be checked with z.which(), while specific variants can be accessed with z.at(), just like a best::row, except that it returns a best::option<T&>.

best::choice is what all of the other sum types, like best::option and best::result, are built out of. All of the clever layout optimizations live here.

Speaking of best::option<T>, that’s our option type. It’s close in spirit to what Option<T> is in Rust. best has a generic niche mechanism that user types can opt into, allowing best::option<T&> to be the same size as a pointer, using nullptr for the best::none variant.

best::option provides the usual transformation operations: map, then, filter. Emptiness can be checked with is_empty() or has_value(). You can even pass a predicate to has_value() to check the value with, if it’s present: x.has_value([](auto& x) { return x == 42; }).

The value can be accessed using operator* and operator->, like std::optional; however, this operation is checked, instead of causing UB if the option is empty. value_or() can be used to unwrap with a default; the default can be any number of arguments, which are used to construct the default, or even a callback. For example:

best::option<Foo> x;

// Pass arguments to the constructor.
do_something(x.value_or(args, to, foo));

// Execute arbitrary logic if the value is missing.
do_something(x.value_or([] {
  return Foo(...);
}))

best::option<void> also Just Works (in fact, best::option<T> is a best::choice<void, T> internally), allowing for truly generic manipulation of optional results.

best::result<T, E> is, unsurprisingly, the analogue of Rust’s Result<T, E>. Because it’s a best::choice internally, best::result<void, E> works as you might expect, and is a common return value for I/O operations.

It’s very similar to best::option, including offering operator-> for accessing the “ok” variant. This enables succinct idioms:

if (auto r = fallible()) {
  r->do_something();
} else {
  best::println("{}", *r.err());
}

r.ok() and r.err() return best::options containing references to the ok and error variants, depending on which is actually present; meanwhile, a best::option can be converted into a best::result using ok_or() or err_or(), just like in Rust.

best::results are constructed using best::ok and best::err. For example:

best::result<Foo, Error> r = best::ok(args, to, foo);

These internally use best::args, a wrapper over best::row that represents a “delayed initialization” that can be stored in a value. It will implicitly convert into any type that can be constructed from its elements. For example:

Foo foo = best::args(args, to, foo);  // Calls Foo::Foo(args, to, foo).

Also, every one of the above types is a structural type, meaning it can be used for non-type template parameters!

Memory and Pointers

Of course, all of these ADTs need to be built on top of pointer operations, which is where //best/memory comes in. best::ptr<T> is a generalized pointer type that provides many of the same operations as Rust’s raw pointers, including offsetting, copying, and indexing. Like Rust pointers, best::ptr<T> can be a fat pointer, i.e., it can carry additional metadata on top of the pointer. For example, best::ptr<int[]> remembers the size of the array.

Providing metadata for a best::ptr is done through a member alias called BestPtrMetadata. This alias should be private, which best is given access to by befriending best::access. Types with custom metadata will usually not be directly constructible (because they are of variable size), and must be manipulated exclusively through types like best::ptr.

Specifying custom metadata allows specifying what the pointer dereferences to. For example, best::ptr<int[]> dereferences to a best::span<int>, meaning that all the span operations are accessible through operator->: for example, my_array_ptr->first().

Most of this may seem a bit over-complicated, since ordinary C++ raw pointers and references are fine for most uses. However, best::ptr is the foundation upon which best::box<T> is built on. best::box<T> is a replacement for std::unique_ptr<T> that fixes its const correctness and adds Rust Box-like helpers. best::box<T[]> also works, but unlike std::unique_ptr<T[]>, it remembers its size, just like best::ptr<T[]>.

best::box is parameterized by its allocator, which must satisfy best::allocator, a much less insane API than what std::allocator offers. best::malloc is a singleton allocator representing the system allocator.

best::span<T>, mentioned before, is the contiguous memory abstraction, replacing std::span. Like std::span, best::span<T, n> is a fixed-length span of n elements. Unlike std::span, the second parameter is a best::option<size_t>, not a size_t that uses -1 as a sentinel.

best::span<T> tries to approximate the API of Rust slices, providing indexing, slicing, splicing, search, sort, and more. Naturally, it’s also iterable, both forwards and backwards, and provides splitting iterators, just like Rust.

Slicing and indexing is always bounds-checked. Indexing can be done with size_t values, while slicing uses a best::bounds:

best::span<int> xs = ...;
auto x = xs[5];
auto ys = xs[{.start = 1, .end = 6}];

best::bounds is a generic mechanism for specifying slicing bounds, similar to Rust’s range types. You can specify the start and end (exclusive), like x..y in Rust. You can also specify an inclusive end using .inclusive_end = 5, equivalent to Rust’s x..=y. And you can specify a count, like C++’s slicing operations prefer: {.start = 1, .count = 5}. best::bounds itself provides all of the necessary helpers for performing bounds checks and crashing with a nice error message. best::bounds is also iterable, as we’ll see shortly.

best::layout is a copy of Rust’s Layout type, providing similar helpers for performing C++-specific size and address calculations.

Iterators

C++ iterator pairs suck. C++ ranges suck. best provides a new paradigm for iteration that is essentially just Rust Iterators hammered into a C++ shape. This library lives in //best/iter.

To define an iterator, you define an iterator implementation type, which must define a member function named next() that returns a best::option:

class my_iter_impl final {
  public:
    best::option<int> next();
};

This type is an implementation detail; the actual iterator type is best::iter<my_iter_impl>. best::iter provides all kinds of helpers, just like Iterator, for adapting the iterator or consuming items out of it.

Iterators can override the behavior of some of these adaptors to be more efficient, such as for making count() constant-time rather than linear. Iterators can also offer extra methods if they define the member alias BestIterArrow; for example, the iterators for best::span have a ->rest() method for returning the part of the slice that has not been yielded by next() yet.

One of the most important extension points is size_hint(), analogous to Iterator::size_hint(), for right-sizing containers that the iterator is converted to, such as a best::vec.

And of course, best::iter provides begin/end so that it can be used in a C++ range-for loop, just like C++20 ranges do. best::int_range<I>⁴, which best::bounds is an instantiation of, is also an iterator, and can be used much like Rust ranges would:

for (auto i : best::int_range<int>{.start = 1, .count = 200}) {
  // ...
}

best::int_range will carefully handle all of the awkward corner cases around overflow, such as best::int_range<uint8_t>{.end_inclusive = 255}.

Heap Containers

Iterators brings us to the most complex container type that’s checked in right now, best::vec. Not only can you customize its allocator type, but you can customize its small vector optimization type.

In libc++, std::strings of at most 23 bytes are stored inline, meaning that the strings’s own storage, rather than heap storage, is used to hold them. best::vec generalizes this, by allowing any trivially copyable type to be inlined. Thus, a best::vec<int> will hold at most five ints inline, on 64-bit targets.

best::vec mostly copies the APIs of std::vector and Rust’s Vec. Indexing and slicing works the same as with best::span, and all of the best::span operations can be accessed through ->, allowing for things like my_vec->sort(...).

I have an active (failing) PR which adds best::table<K, V>, a general hash table implementation that can be used as either a map or a set. Internally it’s backed by a Swisstable⁵ implementation. Its API resembles neither std::unordered_map, absl::flat_hash_map, or Rust’s HashMap. Instead, everything is done through a general entry API, similar to that of Rust, but optimized for clarity and minimizing hash lookups. I want to get it merged soonish.

Beyond best::table, I plan to add at least the following containers:

• best::tree, a btree map/set with a similar API.
• best::heap, a simple min-heap implementation.
• best::lru, a best::table with a linked list running through it for in-order iteration and oldest-member eviction.
• best::ring, a ring buffer like VecDeque.
• best::trie, a port of my twie crate.

Possible other ideas: Russ’s sparse array, splay trees, something like Java’s EnumMap, bitset types, and so on.

Text Handling

best’s string handling is intended to resemble Rust’s as much as possible; it lives within //best/text. best::rune is the Unicode scalar type, which is such that it is always within the valid range for a Unicode scalar, but including the unpaired surrogates. It offers a number of relatively simple character operations, but I plan to extend it to all kinds of character classes in the future.

best::str is our replacement for best::string_view, close to Rust’s str: a sequence of valid UTF-8 bytes, with all kinds of string manipulation operations, such as rune search, splitting, indexing, and so on.

best::rune and best::str use compiler extensions to ensure that when constructed from literals, they’re constructed from valid literals. This means that the following won’t compile!

best::str invalid = "\xFF";

best::str is a best::span under the hood, which can be accessed and manipulated the same way as the underlying &[u8] to &str is.

best::strbuf is our std::string equivalent. There isn’t very much to say about it, because it works just like you’d expect, and provides a Rust String-like API.

Where this library really shines is that everything is parametrized over encodings. best::str is actually a best::text<best::utf8>; best::str16 is then best::text<best::utf16>. You can write your own text encodings, too, so long as they are relatively tame and you provide rune encode/decode for them. best::encoding is the concept

best::text is always validly encoded; however, sometimes, that’s not possible. For this reason we have best::pretext, which is “presumed validly encoded”; its operations can fail or produce replacement characters if invalid code units are found. There is no best::pretextbuf; instead, you would generally use something like a best::vec<uint8_t> instead.

Unlike C++, the fact that a best::textbuf is a best::vec under the hood is part of the public interface, allowing for cheap conversions and, of course, we get best::vec’s small vector optimization for free.

best provides the following encodings out of the box: best::utf8, best::utf16, best::utf32, best::wtf8, best::ascii, and best::latin1.

Formatting

//best/text:format provides a Rust format!()-style text formatting library. It’s as easy as:

auto str = best::format("my number: 0x{:08x}", n);

Through the power of compiler extensions and constexpr, the format is actually checked at compile time!

The available formats are the same as Rust’s, including the {} vs {:?} distinction. But it’s actually way more flexible. You can use any ASCII letter, and types can provide multiple custom formatting schemes using letters. By convention, x, X, b, and o all mean numeric bases. q will quote strings, runes, and other text objects; p will print pointer addresses.

The special format {:!} “forwards from above”; when used in a formatting implementation, it uses the format specifier the caller used. This is useful for causing formats to be “passed through”, such as when printing lists or best::option.

Any type can be made formattable by providing a friend template ADL extension (FTADLE) called BestFmt. This is analogous to implementing a trait like fmt::Debug in Rust, however, all formatting operations use the same function; this is similar to fmt.Formatter in Go.

The best::formatter type, which gets passed into BestFmt, is similar to Rust’s Formatter. Beyond being a sink, it also exposes information on the specifier for the formatting operation via current_spec(), and helpers for printing indented lists and blocks.

BestFmtQuery is a related FTADLE that is called to determine what the valid format specifiers for this type are. This allows the format validator to reject formats that a type does not support, such as formatting a best::str with {:x}.

best::format returns (or appends to) a best::strbuf; best::println and best::eprintln can be used to write to stdout and stderr.

Reflection

Within the metaprogramming library, //best/meta:reflect offers a basic form of reflection. It’s not C++26 reflection, because that’s wholely overkill. Instead, it provides a method for introspecting the members of structs and enums.

For example, suppose that we want to have a default way of formatting arbitrary aggregate structs. The code for doing this is actually devilishly simple:

void BestFmt(auto& fmt, const best::is_reflected_struct auto& value) {
  // Reflect the type of the struct.
  auto refl = best::reflect<decltype(value)>;
  // Start formatting a "record" (key-value pairs).
  auto rec = fmt.record(refl.name());

  // For each field in the struct...
  refl.each([&](auto field) {
    // Add a field to the formatting record...
    rec.field(
      field.name(),   // ...whose name is the field...
      value->*field,  // ...and with the appropriate value.
    );
  });
}

best::reflect provides access to the fields (or enum variants) of a user-defined type that opts itself in by providing the BestReflect FTADLE, which tells the reflection framework what the fields are. The simplest version of this FTADLE looks like this:

friend constexpr auto BestReflect(auto& mirror, MyStruct*) {
  return mirror.infer();
}

best::mirror is essentially a “reflection builder” that offers fine-grained control over what reflection actually shows of a struct. This allows for hiding fields, or attaching tags to specific fields, which generic functions can then introspect using best::reflected_field::tags().

The functions on best::reflected_type allow iterating over and searching for specific fields (or enum variants); these best::reflected_fields provide metadata about a field (such as its name) and allow accessing it, with the same syntax as a pointer-to-member: value->*field.

Explaining the full breadth (and implementation tricks) of best::reflect would be a post of its own, so I’ll leave it at that.

Unit Tests and Apps

best provides a unit testing framework under //best/test, like any good standard library should. To define a test, you define a special kind of global variable:

best::test MyTest = [](best::test& t) {
  // Test code.
};

This is very similar to a Go unit test, which defines a function that starts with Test and takes a *testing.T as its argument. The best::test& value offers test assertions and test failures. Through the power of looking at debuginfo, we can extract the name MyTest from the binary, and use that as the name of the test directly.

That’s right, this is a C++ test framework with no macros at all!

Meanwhile, at //best/cli we can find a robust CLI parsing library, in the spirit of #[derive(clap::Parser)] and other similar Rust libraries. The way it works is you first define a reflectable struct, whose fields correspond to CLI flags. A very basic example of this can be found in test.h, since test binaries define their own flags:

struct test::flags final {
  best::vec<best::strbuf> skip;
  best::vec<best::strbuf> filters;

  constexpr friend auto BestReflect(auto& m, flags*) {
    return m.infer()
      .with(best::cli::app{.about = "a best unit test binary"})
      .with(&flags::skip,
            best::cli::flag{
              .arg = "FILTER",
              .help = "Skip tests whose names contain FILTER",
            })
      .with(&flags::filters,
            best::cli::positional{
              .name = "FILTERS",
              .help = "Include only tests whose names contain FILTER",
            });
  }
};

Using best::mirror::with, we can apply tags to the individual fields that describe how they should be parsed and displayed as CLI flags. A more complicated, full-featured example can be found at toy_flags.h, which exercises most of the CLI parser’s features.

best::parse_flags<MyFlags>(...) can be used to parse a particular flag struct from program inputs, independent of the actual argv of the program. A best::cli contains the actual parser metadata, but this is not generally user-accessible; it is constructed automatically using reflection.

Streamlining top-level app execution can be done using best::app, which fully replaces the main() function. Defining an app is very similar to defining a test:

best::app MyApp = [](MyFlags& flags) {
  // Do something cool!
};

This will automatically record the program inputs, run the flag parser for MyFlags (printing --help and existing, when requested), and then call the body of the lambda.

The lambda can either return void, an int (as an exit code) or even a best::result, like Rust. best::app is also where the argv of the program can be requested by other parts of the program.

What’s Next?

There’s still a lot of stuff I want to add to best. There’s no synchronization primitives, neither atomics nor locks or channels. There’s no I/O; I have a work-in-progress PR to add best::path and best::file. I’d like to write my own math library, best::rc (reference-counting), and portable SIMD. There’s also some other OS APIs I want to build, such as signals and subprocesses. I want to add a robust PRNG, time APIs, networking, and stack symbolization.

Building the best C++ library is a lot of work, not the least because C++ is a very tricky language and writing exhaustive tests is tedious. But it manages to make C++ fun for me again!

I would love to see contributions some day. I don’t expect anyone to actually use this, but to me, it proves C++ could be so much better.

Most people don’t know that Go has special syntax for directives. Unfortunately, it’s not real syntax, it’s just a comment. For example, //go:noinline causes the next function declaration to never get inlined, which is useful for changing the inlining cost of functions that call it.

There are three types of directives:

1. The ones documented in gc’s doc comment. This includes //go:noinline and //line.

2. The ones documented elsewhere, such as //go:build and //go:generate.

3. The ones documented in runtime/HACKING.md, which can only be used if the -+ flag is passed to gc. This includes //go:nowritebarrier.

4. The ones not documented at all, whose existence can be discovered by searching the compiler’s tests. These include //go:nocheckptr, //go:nointerface, and //go:debug.

We are most interested in a directive of the first type, //go:nosplit. According to the documentation:

reference

The //go:nosplit directive must be followed by a function declaration. It specifies that the function must omit its usual stack overflow check. This is most commonly used by low-level runtime code invoked at times when it is unsafe for the calling goroutine to be preempted.

What does this even mean? Normal program code can use this annotation, but its behavior is poorly specified. Let’s dig in.

Go Stack Growth

Go allocates very small stacks for new goroutines, which grow their stack dynamically. This allows a program to spawn a large number of short-lived goroutines without spending a lot of memory on their stacks.

This means that it’s very easy to overflow the stack. Every function knows how large its stack is, and runtime.g, the goroutine struct, contains the end position of the stack; if the stack pointer is less than it (the stack grows up) control passes to runtime.morestack, which effectively preempts the goroutine while its stack is resized.

In effect, every Go function has the following code around it:

TEXT    .f(SB), ABIInternal, $24-16
  CMPQ    SP, 16(R14)
  JLS     grow
  PUSHQ   BP
  MOVQ    SP, BP
  SUBQ    $16, SP
  // Function body...
  ADDQ    $16, SP
  POPQ    BP
  RET
grow:
  MOVQ    AX, 8(SP)
  MOVQ    BX, 16(SP)
  CALL    runtime.morestack_noctxt(SB)
  MOVQ    8(SP), AX
  MOVQ    16(SP), BX
  JMP     .f(SB)

Note that r14 holds a pointer to the current runtime.g, and the stack limit is the third word-sized field (runtime.g.stackguard0) in that struct, hence the offset of 16. If the stack is about to be exhausted, it jumps to a special block at the end of the function that spills all of the argument registers, traps into the runtime, and, once that’s done, unspills the arguments and re-starts the function.

Note that arguments are spilled before adjusting rsp, which means that the arguments are written to the caller’s stack frame. This is part of Go’s ABI; callers must allocate space at the top of their stack frames for any function that they call to spill all of its registers for preemption¹.

Preemption is not reentrant, which means that functions that are running in the context of a preempted G or with no G at all must not be preempted by this check.

Nosplit Functions

The //go:nosplit directive marks a function as “nosplit”, or a “non-splitting function”. “Splitting” has nothing to do with what this directive does.

asideSegmented Stacks

In the bad old days, Go’s stacks were split up into segments, where each segment ended with a pointer to the next, effectively replacing the stack’s single array with a linked list of such arrays.

Segmented stacks were terrible. Instead of triggering a resize, these prologues were responsible for updating rsp to the next (or previous) block by following this pointer, whenever the current segment bottomed out. This meant that if a function call happened to be on a segment boundary, it would be extremely slow in comparison to other function calls, due to the significant work required to update rsp correctly.

This meant that unlucky sizing of stack frames meant sudden performance cliffs. Fun!

Go has since figured out that segmented stacks are a terrible idea. In the process of implementing a correct GC stack scanning algorithm (which it did not have for many stable releases), it also gained the ability to copy the contents of a stack from one location to another, updating pointers in such a way that user code wouldn’t notice.

This stack splitting code is where the name “nosplit” comes from.

A nosplit function does not load and branch on runtime.g.stackguard0, and simply assumes it has enough stack. This means that nosplit functions will not preempt themselves, and, as a result, are noticeably faster to call in a hot loop. Don’t believe me?

//go:noinline
func noinline(x int) {}

//go:nosplit
func nosplit(x int) { noinline(x) }
func yessplit(x int) { noinline(x) }

func BenchmarkCall(b *testing.B) {
  b.Run("nosplit", func(b *testing.B) {
    for b.Loop() { nosplit(42) }
  })
  b.Run("yessplit", func(b *testing.B) {
    for b.Loop() { yessplit(42) }
  })
}

If we profile this and pull up the timings for each function, here’s what we get:

390ms      390ms           func nosplit(x int) { noinline(x) }
 60ms       60ms   51fd80:     PUSHQ BP
 10ms       10ms   51fd81:     MOVQ SP, BP
    .          .   51fd84:     SUBQ $0x8, SP
 60ms       60ms   51fd88:     CALL .noinline(SB)
190ms      190ms   51fd8d:     ADDQ $0x8, SP
    .          .   51fd91:     POPQ BP
 70ms       70ms   51fd92:     RET

440ms      490ms           func yessplit(x int) { noinline(x) }
 50ms       50ms   51fda0:     CMPQ SP, 0x10(R14)
 20ms       20ms   51fda4:     JBE 0x51fdb9
    .          .   51fda6:     PUSHQ BP
 20ms       20ms   51fda7:     MOVQ SP, BP
    .          .   51fdaa:     SUBQ $0x8, SP
 10ms       60ms   51fdae:     CALL .noinline(SB)
200ms      200ms   51fdb3:     ADDQ $0x8, SP
    .          .   51fdb7:     POPQ BP
140ms      140ms   51fdb8:     RET
    .          .   51fdb9:     MOVQ AX, 0x8(SP)
    .          .   51fdbe:     NOPW
    .          .   51fdc0:     CALL runtime.morestack_noctxt.abi0(SB)
    .          .   51fdc5:     MOVQ 0x8(SP), AX
    .          .   51fdca:     JMP .yessplit(SB)

The time spent at each instruction (for the whole benchmark, where I made sure equal time was spent on each test case with -benchtime Nx) is comparable for all of the instructions these functions share, but an additional ~2% cost is incurred for the stack check.

This is a very artificial setup, because the g struct is always in L1 in the yessplit benchmark due to the fact that no other memory operations occur in the loop. However, for very hot code that needs to saturate the cache, this can have an outsized effect due to cache misses. We can enhance this benchmark by adding an assembly function that executes clflush [r14], which causes the g struct to be ejected from all caches.

TEXT .clflush(SB)
  CLFLUSH (R14)  // Eject the pointee of r14 from all caches.
  RET

If we add a call to this function to both benchmark loops, we see the staggering cost of a cold fetch from RAM show up in every function call: 120.1 nanosecods for BenchmarkCall/nosplit, versus 332.1 nanoseconds for BenchmarkCall/yessplit. The 200 nanosecond difference is a fetch from main memory. An L1 miss is about 15 times less expensive, so if the g struct manages to get kicked out of L1, you’re paying about 15 or so nanoseconds, or about two map lookups!

Despite the language resisting adding an inlining heuristic, which programmers would place everywhere without knowing what it does, they did provide something worse that makes code noticeably faster: nosplit.

But It’s Harmless…?

Consider the following program²:

//go:nosplit
func x(y int) { x(y+1) }

Naturally, this will instantly overflow the stack. Instead, we get a really scary linker error:

x.x: nosplit stack over 792 byte limit
x.x<1>
    grows 24 bytes, calls x.x<1>
    infinite cycle

The Go linker contains a check to verify that any chain of nosplit functions which call nosplit functions do not overflow a small window of extra stack, which is where the stack frames of nosplit functions live if they go past stackguard0.

Every stack frame contributes some stack use (for the return address, at minimum), so the number of functions you can call before you get this error is limited. And because every function needs to allocate space for all of its callees to spill their arguments if necessary, you can hit this limit every fast if every one of these functions uses every available argument register (ask me how I know).

Also, turning on fuzzing instruments the code by inserting nosplit calls into the fuzzer runtime around branches, meaning that turning on fuzzing can previously fine code to no longer link. Stack usage also varies slightly by architecture, meaning that code which builds in one architecture fails to link in others (most visible when going from 32-bit to 64-bit).

There is no easy way to control directives using build tags (two poorly-designed features collide), so you cannot just “turn off” performance-sensitive nosplits for debugging, either.

For this reason, you must be very very careful about using nosplit for performance.

Virtual Nosplit Functions

Excitingly, nosplit functions whose addresses are taken do not have special codegen, allowing us to defeat the linker stack check by using virtual function calls.

Consider the following program:

package main

var f func(int)

//go:nosplit
func x(y int) { f(y+1) }

func main() {
  f = x
  f(0)
}

This will quickly exhaust the main G’s tiny stack and segfault in the most violent way imaginable, preventing the runtime from printing a debug trace. All this program outputs is signal: segmentation fault.

This is probably a bug.

Other Side Effects

It turns out that nosplit has various other fun side-effects that are not documented anywhere. The main thing it does is it contributes to whether a function is considered “unsafe” by the runtime.

Consider the following program:

package main

import (
  "fmt"
  "os"
  "runtime"
  "time"
)

func main() {
  for range runtime.GOMAXPROCS(0) {
    go func() {
      for {}
    }()
  }
  time.Sleep(time.Second) // Wait for all the other Gs to start.

  fmt.Println("Hello, world!")
  os.Exit(0)
}

This program will make sure that every P becomes bound to a G that loops forever, meaning they will never trap into the runtime. Thus, this program will hang forever, never printing its result and exiting. But that’s not what happens.

Thanks to asynchronous preemption, the scheduler will detect Gs that have been running for too long, and preempt its M by sending a signal to it (due to happenstance, this is SIGURG of all things.)

However, asynchronous preemption is only possible when the M stops due to the signal at a safe point, as determined by runtime.isAsyncSafePoint. It includes the following block of code:

	up, startpc := pcdatavalue2(f, abi.PCDATA_UnsafePoint, pc)
	if up == abi.UnsafePointUnsafe {
		// Unsafe-point marked by compiler. This includes
		// atomic sequences (e.g., write barrier) and nosplit
		// functions (except at calls).
		return false, 0
	}

If we chase down where this value is set, we’ll find that it is set explicitly for write barrier sequences, for any function that is “part of the runtime” (as defined by being built with the -+ flag) and for any nosplit function.

With a small modification of hoisting the go body into a nosplit function, the following program will run forever: it will never wake up from time.Sleep.

package main

import (
  "fmt"
  "os"
  "runtime"
  "time"
)

//go:nosplit
func forever() {
  for {}
}

func main() {
  for range runtime.GOMAXPROCS(0) {
    go forever()
  }
  time.Sleep(time.Second) // Wait for all the other Gs to start.

  fmt.Println("Hello, world!")
  os.Exit(0)
}

Even though there is work to do, every P is bound to a G that will never reach a safe point, so there will never be a P available to run the main goroutine.

This represents another potential danger of using nosplit functions: those that do not call preemptable functions must terminate promptly, or risk livelocking the whole runtime.

Conclusion

I use nosplit a lot, because I write high-performance, low-latency Go. This is a very insane thing to do, which has caused me to slowly generate bug reports whenever I hit strange corner cases.

For example, there are many cases where spill regions are allocated for functions that never use them, for example, functions which only call nosplit functions allocate space for them to spill their arguments, which they don’t do.³

This is a documented Go language feature which:

1. Isn’t very well-documented (the async preemption behavior certainly isn’t)!
2. Has very scary optimization-dependent build failures.
3. Can cause livelock and mysterious segfaults.
4. Can be used in user programs that don’t import "unsafe"!
5. And it makes code faster!

I’m surprised such a massive footgun exists at all, buuuut it’s a measureable benchmark improvement for me, so it’s impossible to tell if it’s bad or not.

You’d need a very specialized electron microscope to get down to the level to actually see a single strand of DNA. – Craig Venter

TL;DR: buf convert is a powerful tool for examining wire format dumps, by converting them to JSON and using existing JSON analysis tooling. protoscope can be used for lower-level analysis, such debugging messages that have been corrupted.

note

I’m editing a series of best practice pieces on Protobuf, a language that I work on which has lots of evil corner-cases.These are shorter than what I typically post here, but I think it fits with what you, dear reader, come to this blog for. These tips are also posted on the buf.build blog.

JSON from Protobuf?

JSON’s human-readable syntax is a big reason why it’s so popular, possibly second only to built-in support in browsers and many languages. It’s easy to examine any JSON document using tools like online prettifiers and the inimitable jq.

But Protobuf is a binary format! This means that you can’t easily use jq -like tools with it…or can you?

Transcoding with buf convert

The Buf CLI offers a utility for transcoding messages between the three Protobuf encoding formats: the wire format, JSON, and textproto; it also supports YAML. This is buf convert, and it’s very powerful.

To perform a conversion, we need four inputs:

1. A Protobuf source to get types out of. This can be a local .proto file, an encoded FileDescriptorSet , or a remote BSR module.
   • If not provided, but run in a directory that is within a local Buf module, that module will be used as the Protobuf type source.
2. The name of the top-level type for the message we want to transcode, via the --type flag.
3. The input message, via the --from flag.
4. A location to output to, via the --to flag.

buf convert supports input and output redirection, making it usable as part of a shell pipeline. For example, consider the following Protobuf code in our local Buf module:

// my_api.proto
syntax = "proto3";
package my.api.v1;

message Cart {
  int32 user_id = 1;
  repeated Order orders = 2;
}

message Order {
  fixed64 sku = 1;
  string sku_name = 2;
  int64 count = 3;
}

Then, let’s say we’ve dumped a message of type my.api.v1.Cart from a service to debug it. And let’s say…well—you can’t just cat it.

$ cat dump.pb | xxd -ps
08a946121b097ac8e80400000000120e76616375756d20636c65616e6572
18011220096709b519000000001213686570612066696c7465722c203220
7061636b1806122c093aa8188900000000121f69736f70726f70796c2061
6c636f686f6c203730252c20312067616c6c6f6e1802

However, we can use buf convert to turn it into some nice JSON. We can then pipe it into jq to format it.

$ buf convert --type my.api.v1.Cart --from dump.pb --to -#format=json | jq
{
  "userId": 9001,
  "orders": [
    {
      "sku": "82364538",
      "skuName": "vacuum cleaner",
      "count": "1"
    },
    {
      "sku": "431294823",
      "skuName": "hepa filter, 2 pack",
      "count": "6"
    },
    {
	    "sku": "2300094522",
      "skuName": "isopropyl alcohol 70%, 1 gallon",
      "count": "2"
    }
  ]
}

Now you have the full expressivity of jq at your disposal. For example, we could pull out the user ID for the cart:

$ function buf-jq() { buf convert --type $1 --from $2 --to -#format=json | jq $3 }
$ buf-jq my.api.v1.Cart dump.pb '.userId'
9001

Or we can extract all of the SKUs that appear in the cart:

$ buf-jq my.api.v1.Cart dump.pb '[.orders[].sku]'
[
  "82364538",
  "431294823",
  "2300094522"
]

Or we could try calculating how many items are in the cart, total:

$ buf-jq my.api.v1.Cart dump.pb '[.orders[].count] | add'
"162"

Wait. That’s wrong. The answer should be 9. This illustrates one pitfall to keep in mind when using jq with Protobuf. Protobuf will sometimes serialize numbers as quoted strings (the C++ reference implementation only does this when they’re integers outside of the IEEE754 representable range, but Go is somewhat lazier, and does it for all 64-bit values).

You can test if an x int64 is in the representable float range with this very simple check: int64(float64(x)) == x). See https://go.dev/play/p/T81SbbFg3br. The equivalent version in C++ is much more complicated.

This means we need to use the tonumber conversion function:

$ buf-jq my.api.v1.Cart dump.pb '[.orders[].count | tonumber] | add'
9

jq ’s whole deal is JSON, so it brings with it all of JSON’s pitfalls. This is notable for Protobuf when trying to do arithmetic on 64-bit values. As we saw above, Protobuf serializes integers outside of the 64-bit float representable range (and in some runtimes, some integers inside it).

For example, if you have a repeated int64 that you want to sum over, it may produce incorrect answers due to floating-point rounding. For notes on conversions in jq, see https://jqlang.org/manual/#identity.

Disassembling with protoscope

protoscope is a tool provided by the Protobuf team (which I originally wrote!) for decoding arbitrary data as if it were encoded in the Protobuf wire format. This process is called disassembly. It’s designed to work without a schema available, although it doesn’t produce especially clean output.

$ go install github.com/protocolbuffers/protoscope/cmd/protoscope...@latest
$ protoscope dump.pb
1: 9001
2: {
  1: 82364538i64
  2: {"vacuum cleaner"}
  3: 1
}
2: {
  1: 431294823i64
  2: {
    13: 101
    14: 97
    4: 102
    13: 1.3518748403899336e-153   # 0x2032202c7265746ci64
    14: 97
    12:SGROUP
    13:SGROUP
  }
  3: 6
}
2: {
  1: 2300094522i64
  2: {"isopropyl alcohol 70%, 1 gallon"}
  3: 2
}

The field names are gone; only field numbers are shown. This example also reveals an especially glaring limitation of protoscope, which is that it can’t tell the difference between string and message fields, so it guesses according to some heuristics. For the first and third elements it was able to grok them as strings, but for orders[1].sku_name, it incorrectly guessed it was a message and produced garbage.

The tradeoff is that not only does protoscope not need a schema, it also tolerates almost any error, making it possible to analyze messages that have been partly corrupted. If we flip a random bit somewhere in orders[0], disassembling the message still succeeds:

$ protoscope dump.pb
1: 9001
2: {`0f7ac8e80400000000120e76616375756d20636c65616e65721801`}
2: {
  1: 431294823i64
  2: {
    13: 101
    14: 97
    4: 102
    13: 1.3518748403899336e-153   # 0x2032202c7265746ci64
    14: 97
    12:SGROUP
    13:SGROUP
  }
  3: 6
}
2: {
  1: 2300094522i64
  2: {"isopropyl alcohol 70%, 1 gallon"}
  3: 2
}

Although protoscope did give up on disassembling the corrupted submessage, it still made it through the rest of the dump.

Like buf convert, we can give protoscope a FileDescriptorSet to make its heuristic a little smarter.

$ protoscope \
  --descriptor-set <(buf build -o -) \
  --message-type my.api.v1.Cart \
  --print-field-names \
  dump.pb
1: 9001                   # user_id
2: {                      # orders
  1: 82364538i64          # sku
  2: {"vacuum cleaner"}   # sku_name
  3: 1                    # count
}
2: {                          # orders
  1: 431294823i64             # sku
  2: {"hepa filter, 2 pack"}  # sku_name
  3: 6                        # count
}
2: {                                      # orders
  1: 2300094522i64                        # sku
  2: {"isopropyl alcohol 70%, 1 gallon"}  # sku_name
  3: 2                                    # count
}

Not only is the second order decoded correctly now, but protoscope shows the name of each field (via --print-field-names ). In this mode, protoscope still decodes partially-valid messages.

protoscope also provides a number of other flags for customizing its heuristic in the absence of a FileDescriporSet. This enables it to be used as a forensic tool for debugging messy data corruption bugs.

I’ve been very fortunate to dodge a nickname throughout my entire career. I’ve never had one. – Jimmie Johnson

TL;DR: Enum values can have aliases. This feature is poorly designed and shouldn’t be used. The ENUM_NO_ALLOW_ALIAS Buf lint rule prevents you from using them by default.

note

I’m editing a series of best practice pieces on Protobuf, a language that I work on which has lots of evil corner-cases.These are shorter than what I typically post here, but I think it fits with what you, dear reader, come to this blog for. These tips are also posted on the buf.build blog.

Confusion and Breakage

Protobuf permits multiple enum values to have the same number. Such enum values are said to be aliases of each other. Protobuf used to allow this by default, but now you have to set a special option, allow_alias, for the compiler to not reject it.

This can be used to effectively rename values without breaking existing code:

package myapi.v1;

enum MyEnum {
  option allow_alias = true;
  MY_ENUM_UNSPECIFIED = 0;
  MY_ENUM_BAD = 1 [deprecated = true];
  MY_ENUM_MORE_SPECIFIC = 1;
}

This works perfectly fine, and is fully wire-compatible! And unlike renaming a field (see TotW #1), it won’t result in source code breakages.

But if you use either reflection or JSON, or a runtime like Java that doesn’t cleanly allow enums with multiple names, you’ll be in for a nasty surprise.

For example, if you request an enum value from an enum using reflection, such as with protoreflect.EnumValueDescriptors.ByNumber(), the value you’ll get is the one that appears in the file lexically. In fact, both myapipb.MyEnum_MY_ENUM_BAD.String() and myapipb.MyEnum_MY_ENUM_MORE_SPECIFIC.String() return the same value, leading to potential confusion, as the old “bad” value will be used in printed output like logs.

You might think, “oh, I’ll switch the order of the aliases”. But that would be an actual wire format break. Not for the binary format, but for JSON. That’s because JSON preferentially stringifies enum values by using their declared name (if the value is in range). So, reordering the values means that what once serialized as {"my_field": "MY_ENUM_BAD"} now serializes as {"my_field": "MY_ENUM_MORE_SPECIFIC"} .

If an old binary that hasn’t had the new enum value added sees this JSON document, it won’t parse correctly, and you’ll be in for a bad time.

You can argue that this is a language bug, and it kind of is. Protobuf should include an equivalent of json_name for enum values, or mandate that JSON should serialize enum values with multiple names as a number, rather than an arbitrarily chosen enum name. The feature is intended to allow renaming of enum values, but unfortunately Protobuf hobbled it enough that it’s pretty dangerous.

What To Do

Instead, if you really need to rename an enum value for usability or compliance reasons (ideally, not just aesthetics) you’re better off making a new enum type in a new version of your API. As long as the enum value numbers are the same, it’ll be binary-compatible, but it will somewhat reduce the risk of the above JSON confusion.

Buf provides a lint rule against this feature, ENUM_NO_ALLOW_ALIAS , and Protobuf requires that you specify a magic option to enable this behavior, so in practice you don’t need to worry about this. But remember, the consequences of enum aliases go much further than JSON—they affect anything that uses reflection. So even if you don’t use JSON, you can still get burned.

My dad had a guitar but it was acoustic, so I smashed a mirror and glued broken glass to it to make it look more metal. It looked ridiculous! –Max Cavalera

TL;DR: Avoid import public and import weak. The Buf lint rules IMPORT_NO_PUBLIC and IMPORT_NO_WEAK enforce this for you by default.

note

I’m editing a series of best practice pieces on Protobuf, a language that I work on which has lots of evil corner-cases.These are shorter than what I typically post here, but I think it fits with what you, dear reader, come to this blog for. These tips are also posted on the buf.build blog.

Protobuf imports allow you to specify two special modes: import public and import weak. The Buf CLI lints against these by default, but you might be tempted to try using them anyway, especially because some GCP APIs use import public. What are these modes, and why do they exist?

Import Visibility

Protobuf imports are by file path, a fact that is very strongly baked into the language and its reflection model.

import "my/other/api.proto";

Importing a file dumps all of its symbols into the current file. For the purposes of name resolution, it’s as if all if the declarations in that file have been pasted into the current file. However, this isn’t transitive. If:

• a.proto imports b.proto …
• and b.proto imports c.proto …
• and c.proto defines foo.Bar…
• then, a.proto must import c.proto to refer to foo.Bar, even though b.proto imports it.

This is similar to how importing a package as . works in Go. When you write import . "strings", it dumps all of the declarations from the strings package into the current file, but not those of any files that "strings" imports.

Now, what’s nice about Go is that packages can be broken up into files in a way that is transparent to users; users of a package import the package, not the files of that package. Unfortunately, Protobuf is not like that, so the file structure of a package leaks to its callers.

import public was intended as a mechanism for allowing API writers to break up files that were getting out of control. You can define a new file new.proto for some of the definitions in big.proto, move them to the new file, and then add import public "new.proto"; to big.proto. Existing imports of big.proto won’t be broken, hooray!

Except this feature was designed for C++. In C++, each .proto file maps to a .proto.h header, which you #include in your application code. In C++, #include behaves like import public, so marking an import as public only changes name resolution in Protobuf—the C++ backend doesn’t have to do anything to maintain source compatibility when an import is changed to public.

But other backends, like Go, do not work this way: import in Go doesn’t pull in symbols transitively, so Go would need to explicitly add aliases for all of the symbols that come in through a public import. That is, if you had:

// foo.proto
package myapi.v1;
message Foo { ... }

// bar.proto
package myotherapi.v1;
import public "foo.proto";

Then the Go backend has to generate a type Foo = foopb.Foo in bar.pb.go to emulate this behavior (in fact, I was surprised to learn Go Protobuf implements this at all). Go happens to implement public imports correctly, but not all backends are as careful, because this feature is obscure.

The spanner.proto example of an import public isn’t even used for breaking up an existing file; instead, it’s used to not make a huge file bigger and avoid making callers have to add an additional import. This is a bad use of a bad feature!

Using import public to effectively “hide” imports makes it harder to understand what a .proto file is pulling in. If Protobuf imports were at the package/symbol level, like Go or Java, this feature would not need to exist. Unfortunately, Protobuf is closely tailored for C++, and this is one of the consequences.

Instead of using import public to break up a file, simply plan to break up the file in the next version of the API.

The IMPORT_NO_PUBLIC Buf lint rule enforces that no one uses this feature by default. It’s tempting, but the footguns aren’t worth it.

Weak Imports

Public imports have a good, if flawed, reason to exist. Their implementation details are the main thing that kneecaps them.

Weak imports, however, simply should not exist. They were added to the language to make it easier for some of Google’s enormous binaries to avoid running out of linker memory, by making it so that message types could be dropped if they weren’t accessed. This means that weak imports are “optional”—if the corresponding descriptors are missing at runtime, the C++ runtime can handle it gracefully.

This leads to all kinds of implementation complexity and subtle behavior differences across runtimes. Most runtimes implement (or implemented, in the case of those that removed support) import weak in a buggy or inconsistent way. It’s unlikely the feature will ever be truly removed, even though Google has tried.

Don’t use import weak. It should be treated as completely non-functional. The IMPORT_NO_WEAK Buf lint rule takes care of this for you.

Bad humor is an evasion of reality; good humor is an acceptance of it. –Malcolm Muggeridge

TL;DR: Protobuf’s distributed nature introduces evolution risks that make it hard to fix some types of mistakes. Sometimes the best thing to do is to just let it be.

note

I’m editing a series of best practice pieces on Protobuf, a language that I work on which has lots of evil corner-cases.These are shorter than what I typically post here, but I think it fits with what you, dear reader, come to this blog for. These tips are also posted on the buf.build blog.

A Different Mindset

Often, you’ll design and implement a feature for the software you work on, and despite your best efforts to test it, something terrible happens in production. We have a playbook for this, though: fix the bug in your program and ship or deploy the new, fixed version to your users. It might mean working late for big emergencies, but turnaround for most organizations is a day to a week.

Most bugs aren’t emergencies, though. Sometimes a function has a confusing name, or an integer type is just a bit too small for real-world data, or an API conflates “zero” and “null”. You fix the API, refactor all usages in your API in one commit, merge, and the fix rolls out gradually.

Unless, of course, it’s a bug in a communication API, like a serialization format: your Protobuf types, or your JSON schema, or the not-too-pretty code that parses fields out of dict built from a YAML file. Here, you can’t just atomically fix the world. Fixing bugs in your APIs (from here on, “APIs” means “Protobuf definitions”) requires a different mindset than fixing bugs in ordinary code.

What Are the Risks?

Protobuf’s wire format is designed so that you can safely add new fields to a type, or values to an enum, without needing to perform an atomic upgrade. But other changes, like renaming fields or changing their type, are very dangerous.

This is because Protobuf types exist on a temporal axis: different versions of the same type exist simultaneously among programs in the field that are actively talking to each other. This means that writers from the future (that is, new serialization code) must be careful to not confuse the many readers from the past (old versions of the deserialization code). Conversely, future readers must tolerate anything past writers produce.

In a modern distributed deployment, the number of versions that exist at once can be quite large. This is true even in self-hosted clusters, but becomes much more fraught whenever user-upgradable software is involved. This can include mobile applications that talk to your servers, or appliance software managed by a third-party administrator, or even just browser-service communication.

The most important principle: you can’t easily control when old versions of a type or service are no longer relevant. As soon as a type escapes out of the scope of even a single team, upgrading types becomes a departmental effort.

Learning to Love the Bomb

There are many places where Protobuf could have made schema evolution easier, but didn’t. For example, changing int32 foo = 1; to sfixed32 foo = 1; is a breakage, even though at the wire format level, it is possible for a parser to distinguish and accept both forms of foo correctly. There too many other examples to list, but it’s important to understand that the language is not always working in our favor.

For example, if we notice a int32 value is too small, and should have been 64-bit, you can’t upgrade it without readers from the past potentially truncating it. But we really have to upgrade it! What are our options?

1. Issue a new version of the message and all of its dependencies. This is the main reason why sticking a version number in the package name, as enforced by Buf’s PACKAGE_VERSION_SUFFIX lint rule, is so important.
2. Do the upgrade anyway and hope nothing breaks. This can work for certain kinds of upgrades, if the underlying format is compatible, but it can have disastrous consequences if you don’t know what you’re doing, especially if it’s a type that’s not completely internal to a team’s project. Buf breaking change detection helps you avoid changes with potential for breakage.

Of course, there is a third option, which is to accept that some things aren’t worth fixing. When the cost of a fix is so high, fixes just aren’t worth it, especially when the language is working against us.

This means that even in Buf’s own APIs, we sometimes do things in a way that isn’t quite ideal, or is inconsistent with our own best practices. Sometimes, the ecosystem changes in a way that changes best practice, but we can’t upgrade to it without breaking our users. In the same way, you shouldn’t rush to use new, better language features if they would cause protocol breaks: sometimes, the right thing is to do nothing, because not breaking your users is more important.

Smart people learn from their mistakes. But the real sharp ones learn from the mistakes of others. –Brandon Mull

TL;DR: enums inherit some unfortunate behaviors from C++. Use the Buf lint rules ENUM_VALUE_PREFIX and ENUM_ZERO_VALUE_SUFFIX  to avoid this problem (they’re part of the DEFAULT category).

note

I’m editing a series of best practice pieces on Protobuf, a language that I work on which has lots of evil corner-cases.These are shorter than what I typically post here, but I think it fits with what you, dear reader, come to this blog for. These tips are also posted on the buf.build blog.

C++-Style Enums

Protobuf’s enums define data types that represent a small set of valid values. For example, google.rpc.Code lists status codes used by various RPC frameworks, such as GRPC. Under the hood, every enum is just an int32  on the wire, although codegen backends will generate custom types and constants for the enum to make it easier to use.

Unfortunately, enums were originally designed to match C++ enums exactly, and they inadvertently replicate many of those behaviors.

If you look at the source for google.rpc.Code, and compare it to, say, google.protobuf.FieldDescriptorProto.Type, you will notice a subtle difference:

package google.rpc;
enum Code {
  OK = 0;
  CANCELLED = 1;
  UNKNOWN = 2;
  // ...
}

package google.protobuf;
message FieldDescriptorProto {
  enum Type {
    // 0 is reserved for errors.
    TYPE_DOUBLE = 1;
    TYPE_FLOAT = 2;
    TYPE_INT64 = 3;
    // ...
  }
}

FieldDescriptorProto.Type has values starting with TYPE_, but Code ‘s values don’t have a CODE_ prefix.  This is because the fully-qualified names (FQN) of an enum value don’t include the name of the enum. That is, TYPE_DOUBLE actually refers to google.protobuf.FieldDescriptorProto.TYPE_DOUBLE. Thus, OK is not google.rpc.Code.OK, but google.rpc.OK.

This is because it matches the behavior of unscoped C++ enums. C++ is the “reference” implementation, so the language often bends for the sake of the C++ backend.

When generating code, protoc’s C++ backend emits the above as follows:

namespace google::rpc {
enum Code {
  OK = 0,
  CANCELLED = 1,
  UNSPECIFIED = 2,
  // ...
};
}

namespace google::protobuf {
class FieldDescriptorProto final {
 public:
  enum Type {
   TYPE_DOUBLE = 1;
   TYPE_FLOAT = 2;
   // ...
  };
};
}

And in C++, enums don’t scope their enumerators: you write google::rpc::OK, NOT google::rpc::Code::OK.

If you know C++, you might be thinking, “why didn’t they use enum class?!”? Enums were added in proto2, which was developed around 2007-2008, but Google didn’t start using C++11, which introduced enum class , until much, much later.

Now, if you’re a Go or Java programmer, you’re probably wondering why you even care about C++. Both Go and Java do scope enum values to the enum type (although Go does it in a somewhat grody way: rpcpb.Code_OK).

Unfortunately, this affects name collision detection in Protobuf. You can’t write the following code:

package myapi.v1;

enum Stoplight {
  UNSPECIFIED = 0;
  RED = 1;
  YELLOW = 2;
  GREEN = 3;
}

enum Speed {
  UNSPECIFIED = 0;
  SLOW = 1;
  FAST = 2;
}

Because the enum name is not part of the FQN for an enum value, both UNSPECIFIEDs here have the FQN myapi.v1.UNSPECIFIED, so Protobuf complains about duplicate symbols.

Thus, the convention we see in FieldDescriptorProto.Type:

package myapi.v1;

enum Stoplight {
  STOPLIGHT_UNSPECIFIED = 0;
  STOPLIGHT_RED = 1;
  STOPLIGHT_YELLOW = 2;
  STOPLIGHT_GREEN = 3;
}

enum Speed {
  SPEED_UNSPECIFIED = 0;
  SPEED_SLOW = 1;
  SPEED_FAST = 2;
}

Buf provides a lint rule to enforce this convention: ENUM_VALUE_PREFIX. Even though you might think that an enum name will be unique, because top-level enums bleed their names into the containing package, the problem spreads across packages!

Zero Values

proto3 relies heavily on the concept of “zero values” – all non-message fields that are neither repeated nor optional are implicitly zero if they are not present. Thus, proto3 requires that enums specify a value equal to zero.

By convention, this value shouldn’t be a specific value of the enum, but rather a value representing that no value is specified. ENUM_ZERO_VALUE_SUFFIX enforces this, with a default of _UNSPECIFIED. Of course, there are situations where this might not make sense for you, and a suffix like _ZERO or _UNKNOWN might make more sense.

It may be tempting to have a specific “good default” value for the zero value. Beware though, because that choice is forever. Picking a generic “unknown” as the default reduces the chance you’ll burn yourself.

Why Don’t All of Google’s Protobuf Files Do This?

Name prefixes and zero values also teach us an important lesson: because Protobuf names are forever, it’s really hard to fix style mistakes, especially as we collectively get better at using Protobuf.

google.rpc.Code is intended to be source-compatible with very old existing C++ code, so it throws caution to the wind. FieldDescriptorProto.Type doesn’t have a zero value because in proto2 , which doesn’t have zero value footguns in its wire format, you don’t need to worry about that. The lesson isn’t just to use Buf’s linter to try to avoid some of the known pitfalls, but also to remember that even APIs designed by the authors of the language make unfixable mistakes, so unlike other programming languages, imitating “existing practice” isn’t always the best strategy.

Even though I am a C++ programmer at heart, Go fascinates me for none of the reasons you think. Go has made several interesting design decisions:

1. It has virtually no Undefined Behavior¹.

2. It has very simple GC semantics that they’re mostly stuck with due to design decisions in the surface language.

These things mean that despite Go having a GC, it’s possible to do manual memory management in pure Go and in cooperation with the GC (although without any help from the runtime package). To demonstrate this, we will be building an untyped, garbage-collected arena abstraction in Go which relies on several GC implementation details.

I would never play this kind of game in Rust or C++, because LLVM is extremely intelligent and able to find all kinds of ways to break you over the course of frequent compiler upgrades. On the other hand, although Go does not promise any compatibility across versions for code that imports unsafe, in practice, two forces work against Go doing this:

1. Go does not attempt to define what is and isn’t allowed: unsafe lacks any operational semantics.

2. Go prioritizes not breaking the ecosystem; this allows to assume that Hyrum’s Law will protect certain observable behaviors of the runtime, from which we may infer what can or cannot break easily.

This is in contrast to a high-performance native compiler like LLVM, which has a carefully defined boundary around all UB, allowing them to arbitrarily break programs that cross it (mostly) without fear of breaking the ecosystem.

So, let’s dive in and cheat death.

What Are We Building?

Our goal is to build an arena, which is a data structure for efficient allocation of memory that has the same lifetime. This reduces pressure on the general-purpose allocator by only requesting memory in large chunks and then freeing it all at once.

For a comparison in Go, consider the following program:

package main

import "fmt"

func main() {
  var s []int
  for i := range 1000 {
    prev := cap(s)
    s = append(s, i)
    if cap(s) != prev {
      fmt.Println(cap(s))
    }
  }
}

This program will print successive powers of 2: this is because append is implemented approximately like so:

func append[S ~[]T, T any](a, b S) S {
  // If needed, grow the allocation.
  if cap(a) - len(a) < len(b) {
    // Either double the size, or allocate just enough if doubling is
    // too little.
    newCap := max(2*cap(a), len(a)+len(b))

    // Grow a.
    a2 := make([]T, len(a), newCap)
    copy(a2, a)
    a = a2
  }

  // Increase the length of a to fit b, then write b into the freshly
  // grown region.
  a = a[:len(a)+len(b)]
  copy(a[len(a)-len(b):], b)
  return a
}

For appending small pieces, make is only called $O(\log n)$ times, a big improvement over calling it for every call to append. Virtually every programming language’s dynamic array abstraction makes this optimization.

An arena generalizes this concept, but instead of resizing exponentially, it allocates new blocks and vends pointers into them. The interface we want to conform to is as follows:

type Allocator interface {
  Alloc(size, align uintptr) unsafe.Pointer
}

In go a size and and an alignment, out comes a pointer fresh memory with that layout. Go does not have user-visible uninitialized memory, so we additionally require that the returned region be zeroed. We also require that align be a power of two.

We can give this a type-safe interface by writing a generic New function:

// New allocates a fresh zero value of type T on the given allocator, and
// returns a pointer to it.
func New[T any](a Allocator) *T {
  var t T
  p := a.Alloc(unsafe.Sizeof(t), unsafe.Alignof(t))
  return (*T)(p)
}

This all feels very fine and dandy to anyone used to hurting themselves with malloc or operator new in C++, but there is a small problem. What happens when we allocate pointer-typed memory into this allocator?

// Allocate a pointer in our custom allocator, and then
// initialize it to a pointer on the Go heap.
p := New[*int](myAlloc)
*p = new(int)

runtime.GC()
**p = 42  // Use after free!

Allocator.Alloc takes a size and an alignment, which is sufficient to describe the layout of any type. For example, on 64-bit systems, int and *int have the same layout: 8 bytes of size, and 8 bytes of alignment.

However, the Go GC (and all garbage collectors, generally) require one additional piece of information, which is somewhere between the layout of a value (how it is placed in memory) and the type of a value (rich information on its structure). To understand this, we need a brief overview on what a GC does.

Mark and Sweep

note

For a complete overview on how to build a simple GC, take a look at a toy GC I designed some time ago: The Alkyne GC.

A garbage collector’s responsibility is to maintain a memory allocator and an accounting of:

1. What memory has been allocated.
2. Whether that memory is still in use.

Memory that is not in use can be reclaimed and marked as unallocated, for re-use.

The most popular way to accomplish this is via a “mark and sweep” architecture. The GC will periodically walk the entire object graph of the program from certain pre-determined roots; anything it finds is “marked” as alive. After a mark is complete, all other memory is “swept”, which means to mark it is unallocated for future re-use, or to return it to the OS, in the case of significant surplus.

The roots are typically entities that are actively being manipulated by the program. In the case of Go, this is anything currently on the stack of some G², or anything in a global (of which there is a compile-time-known set).

The marking phase begins with stack scanning, which looks at the stack of each G and locates any pointers contained therein. The Go compiler generates metadata for each function that specifies which stack slots in a function’s frame contain pointers. All of these pointers are live by definition.

These pointers are placed into a queue, and each pointer is traced to its allocation on the heap. If the GC does not know anything about a particular address, it is discarded as foreign memory that does not need to be marked. If it does, each pointer in that allocation is pushed onto the queue if it has not already been marked as alive. The process continues until the queue is empty.

The critical step here is to take the address of some allocation, and convert it into all of the pointer values within. Go has precise garbage collection, which means that it only treats things declared as pointers in the surface language as pointers: an integer that happens to look like an address will not result in sweeping. This results in more efficient memory usage, but trades off some more complexity in the GC.

For example, the types *int, map[int]byte, string, struct {A int; B *int} all contain at least one pointer, while int, [1000]byte, struct {X bool; F uintptr} do not. The latter are called pointer-free types.

Go enhances the layout of a type into a shape by adding a bitset that specifies which pointer-aligned, pointer-sized words of the type’s memory region contain a pointer. These are called the pointer bits. For example, here are the shapes of a few Go types on a 64-bit system.

In the Go GC, each allocation is tagged with its shape (this is done in a variety of ways in the GC, either through an explicit header on the allocation, itself (a “malloc header”), a runtime type stored in the allocation’s runtime.mspan, or another mechanism). When scanning a value, it uses this information to determine where the pointers to scan through are.

The most obvious problem with our Allocator.Alloc type is that it does not discriminate shapes, so it cannot allocate memory that contains pointers: the GC will not be able to find the pointers, and will free them prematurely!

In our example where we allocated an *int in our custom allocator, we wind up with a **int on the stack. You would think that Go would simply trace through the first * to find an *int and mark it as being alive, but that is not what happens! Go instead finds a pointer into some chunk that the custom allocator grabbed from the heap, which is missing the pointer bits of its shape!

Why does go not look at the type of the pointer it steps through? Two reasons.

1. All pointers in Go are untyped from the runtime’s perspective; every *T gets erased into an unsafe.Pointer. This allows much of the Go runtime to be “generic” without using actual generics.

2. Pointee metadata can be aggregated, so that each pointer to an object does not have to remember its type at runtime.

The end result for us is that we can’t put pointers on the arena. This makes our New API unsafe, especially since Go does not provide a standard constraint for marking generic parameters as pointer-free: unsurprisingly, the don’t expect most users to care about such a detail.

It is possible to deduce the pointer bits of a type using reflection, but that’s very slow, and the whole point of using arenas is to go fast. As we design our arena, though, it will become clear that there is a safe way to have pointers on it.

Designing The Arena

Now that we have a pretty good understanding about what the Go GC is doing, we can go about designing a fast arena structure.

The ideal case is that a call to Alloc is very fast: just offsetting a pointer in the common case. One assumption we can make off the bat is that all memory can be forced to have maximum alignment: most objects are a pointer or larger, and Go does have a maximum alignment for ordinary user types, so we can just ignore the align parameter and always align to say, 8 bytes. This means that the pointer to the next unallocated chunk will always be well-aligned. Thus, we might come up with a structure like this one:

type Arena struct {
  next      unsafe.Pointer
  left, cap uintptr
}

const (
  // Power of two size of the minimum allocation granularity.
  wordBytes = 8  // Depends on target, this is for 64-bit.
  minWords  = 8
)

func (a *Arena) Alloc(size, align uintptr) unsafe.Pointer {
  // First, round the size up to the alignment of every object in
  // the arena.
  mask := wordBytes - 1
  size = (size + mask) &^ mask
  // Then, replace the size with the size in pointer-sized words.
  // This does not result in any loss of size, since size is now
  // a multiple of the uintptr size.
  words := size / wordBytes

  // Next, check if we have enough space left for this chunk. If
  // there isn't, we need to grow.
  if a.left < words {
    // Pick whichever is largest: the minimum allocation size,
    // twice the last allocation, or the next power of two
    // after words.
    a.cap = max(minWords, a.cap*2, nextPow2(words))
    a.next = unsafe.Pointer(unsafe.SliceData(make([]uintptr, a.cap)))
    a.left = a.cap
  }

  // Allocate the chunk by incrementing the pointer.
  p := a.next
  a.left -= words
  if a.left > 0 {
    a.next = unsafe.Add(a.next, size)
  } else {
    // Beware, offsetting to one-past-the-end is one of the few
    // things explicitly not allowed by Go.
    a.next = nil
  }

  return p
}

// nextPow2 returns the smallest power of two greater than n.
func nextPow2(n uintptr) uintptr {
  return uintptr(1) << bits.Len(uint(n))
}

How fast is this really? Here’s a simple benchmark for it.

func BenchmarkArena(b *testing.B) {
  bench[int](b)
  bench[[2]int](b)
  bench[[64]int](b)
  bench[[1024]int](b)
}

const runs = 100000

var sink any

func bench[T any](b *testing.B) {
  var z T
  n := int64(runs * unsafe.Sizeof(z))
  name := fmt.Sprintf("%v", reflect.TypeFor[T]())

  b.Run(name, func(b *testing.B) {
    b.Run("arena", func(b *testing.B) {
      b.SetBytes(n)
      for b.Loop() {
        a := new(arena.Arena)
        for range runs {
          sink = arena.New[T](a)
        }
      }
    })

    b.Run("new", func(b *testing.B) {
      b.SetBytes(n)
      for b.Loop() {
        for range runs {
          sink = new(T)
        }
      }
    })
  })
}

The focus of this benchmark is to measure the cost of allocating many objects of the same size. The number of times the for b.Loop() loop will execute is unknown, and determined by the benchmarking framework to try to reduce statistical anomaly. This means that if we instead just benchmark a single allocation, the result will be very sensitive to the number of runs.

We also use b.SetBytes to get a throughput measurement on the benchmark. This is a bit easier to interpret than the gross ns/op, the benchmark would otherwise produce. It tells us how much memory each allocator can allocate per unit time.

We want to compare against new, but just writing _ = new(T) will get optimized out, since the resulting pointer does not escape. Writing it to a global is sufficient to convince Go that it escapes.

Here’s the results, abbreviated to show only the bytes per second. All benchmarks were performed on my AMD Ryzen Threadripper 3960X. Larger is better.

BenchmarkArena/int/arena-48         794.84 MB/s
BenchmarkArena/int/new-48           390.59 MB/s
BenchmarkArena/[2]int/arena-48      1263.58 MB/s
BenchmarkArena/[2]int/new-48        528.06 MB/s
BenchmarkArena/[64]int/arena-48     7370.08 MB/s
BenchmarkArena/[64]int/new-48       2865.24 MB/s
BenchmarkArena/[1024]int/arena-48   9889.20 MB/s
BenchmarkArena/[1024]int/new-48     2875.75 MB/s

This is quite nice, and certainly worth pursuing! The performance increase seems to scale up with the amount of memory allocated, for a 2x-4x improvement across different cases.

Now we need to contend with the fact that our implementation is completely broken if we want to have pointers in it.

Not Dropping Memory on the Ground

In (*Arena).Alloc, when we assign a freshly-allocated chunk, we overwrite a.next, which means the GC can reclaim it. But this is fine: as long as pointers into that arena chunk are alive, the GC will not free it, independent of the arena. So it seems like we don’t need to worry about it?

However, the whole point of an arena is to allocate lots of memory that has the same lifetime. This is common for graph data structures, such as an AST or a compiler IR, which performs a lot of work that allocates a lot and then throws the result away.

We are not allowed to put pointers in the arena, because they would disappear from the view of the GC and become freed too soon. But, if a pointer wants to go on an arena, it necessarily outlive the whole arena, since it outlives part of the arena, and the arena is meant to have the same lifetime.

In particular, if we could make it so that holding any pointer returned by Alloc prevents the entire arena from being swept by the GC, the arena can safely contain pointers into itself! Consider this:

1. We have a pointer p **int. It is allocated on some arena a.

2. The GC sees our pointer (as a type-erased unsafe.Pointer) and marks its allocation as live.

3. Somehow, the GC also marks a as alive as a consequence.

4. Somehow, the GC then marks every chunk a has allocated as alive.

5. Therefore he chunk that *p points to is also alive, so *p does not need to be marked directly, and will not be freed early.

The step (3) is crucial. By forcing the whole arena to be marked, any pointers stored in the arena into itself will be kept alive automatically, without the GC needing to know how to scan for them.

So, even though *New[*int](a) = new(int) is still going to result in a use-after-free, *New[*int](a) = New[int](a) would not! This small improvement does not make arenas themselves safe, but a data structure with an internal arena can be completely safe, so long as the only pointers that go into the arena are from the arena itself.

How can we make this work? The easy part is (4), which we can implement by adding a []unsafe.Pointer to the arena, and sticking every pointer we allocate into it.

type Arena struct {
  next      unsafe.Pointer
  left, cap uintptr

  chunks []unsafe.Pointer  // New field.
}

func (a *Arena) Alloc(size, align uintptr) unsafe.Pointer {
  // ... snip ...
  if a.left < words {
    // Pick whichever is largest: the minimum allocation size,
    // twice the last allocation, or the next power of two
    // after words.
    a.cap = max(minWords, a.cap*2, nextPow2(words))
    a.next = unsafe.Pointer(unsafe.SliceData(make([]uintptr, a.cap)))
    a.left = a.cap
    a.chunks = append(a.chunks, a.next)
  }
  // ... snip ...
}

The cost of the append is amortized: to allocate n bytes, we wind up allocating an additional $O(\log \log n)$ times. But what does this do to our benchmarks?

BenchmarkArena/int/arena-48         800.08 MB/s
BenchmarkArena/int/new-48           386.81 MB/s
BenchmarkArena/[2]int/arena-48      1236.00 MB/s
BenchmarkArena/[2]int/new-48        520.84 MB/s
BenchmarkArena/[64]int/arena-48     7999.71 MB/s
BenchmarkArena/[64]int/new-48       2706.68 MB/s
BenchmarkArena/[1024]int/arena-48   9998.00 MB/s
BenchmarkArena/[1024]int/new-48     2816.28 MB/s

Seems pretty much the same, which is a good sign.

Back Pointers

Now that the arena does not discard any allocated memory, we can focus on condition (3): making it so that if any pointer returned by Alloc is alive, then so is the whole arena.

Here we can make use of an important property of how Go’s GC works: any pointer into an allocation will keep it alive, as well as anything reachable from that pointer. But the chunks we’re allocating are []uintptrs, which will not be scanned. If there could somehow be a single pointer in this slice that was scanned, we would be able to stick the pointer a *Arena there, and so when anything that Alloc returns is scanned, it would cause a to be marked as alive.

So far, we have been allocating [N]uintptr using make([]T), but we would actually like to allocate struct { A [N]uintptr; P unsafe.Pointer }, where N is some dynamic value.

In its infintie wisdom, the Go standard library actually gives us a dedicated mechanism to do this: reflect.StructOf. This can be used to construct arbitrary anonymous struct types at runtime, which we can then allocate on the heap.

So, instead of calling make, we might call this function:

func (a *Arena) allocChunk(words uintptr) unsafe.Pointer {
  chunk := reflect.New(reflect.StructOf([]reflect.StructField{
    {
      Name: "X0",
      Type: reflect.ArrayOf(int(words), reflect.TypeFor[uintptr]()),
    },
    {Name: "X1", Type: reflect.TypeFor[unsafe.Pointer]()},
  })).UnsafePointer()

  // Offset to the end of the chunk, and write a to it.
  end := unsafe.Add(chunk, words * unsafe.Sizeof(uintptr(0)))
  *(**Arena)(end) = a

  return chunk
}

This appears to have a minor but noticeable effect on performance⁶.

BenchmarkArena/int/arena-48         763.91 MB/s
BenchmarkArena/int/new-48           385.49 MB/s
BenchmarkArena/[2]int/arena-48      1174.00 MB/s
BenchmarkArena/[2]int/new-48        524.32 MB/s
BenchmarkArena/[64]int/arena-48     7563.54 MB/s
BenchmarkArena/[64]int/new-48       2649.63 MB/s
BenchmarkArena/[1024]int/arena-48   8668.02 MB/s
BenchmarkArena/[1024]int/new-48     2648.10 MB/s

More Optimizations

Looking back at Arena.Alloc, the end of this function has a branch:

func (a *Arena) Alloc(size, align uintptr) unsafe.Pointer {
  // ... snip...

  // Allocate the chunk by incrementing the pointer.
  p := a.next
  a.left -= words
  if a.left > 0 {
    a.next = unsafe.Add(a.next, size)
  } else {
    // Beware, offsetting to one-past-the-end is one of the few
    // things explicitly not allowed by Go.
    a.next = nil
  }

  return p
}

This is the absolute hottest part of allocation, since it is executed every time we call this function. The branch is a bit unfortunate, but it’s necessary, as noted by the comment.

In C++, if we have an array of int with n elements in it, and int* p is a pointer to the start of the array, p + n is a valid pointer, even though it can’t be dereferenced; it points “one past the end” of the array. This is a useful construction, since, for example, you can use it to eliminate a loop induction variable:

// Naive for loop, has an induction variable i.
for (int i = 0; i < n; i++) {
  do_something(p[i]);
}

// Faster: avoids the extra variable increment in the loop
// body for doing p[i].
for (auto end = p + n; p < end; p++) {
  do_something(*p);
}

Go, however, gets very upset if you do this, because it confuses the garbage collector. The GC can’t tell the difference between a one-past-the-end pointer for allocation A, and for the start of allocation B immediately after it. At best this causes memory to stay alive for longer, and at worst it triggers safety interlocks in the GC. The GC will panic if it happens to scan a pointer for an address that it knows has been freed.

But in our code above, every chunk now has an extra element at the very end that is not used for allocation, so we can have a pointer that is one-past-the-end of the [N]uintptr that we are vending memory from.

The updated allocation function would look like this:

func (a *Arena) Alloc(size, align uintptr) unsafe.Pointer {
  // ... snip ...

  // Allocate the chunk by incrementing the pointer.
  p := a.next
  a.next = unsafe.Add(a.next, size)
  a.left -= words

  return p
}

Notably, we do not replace a.left with an end pointer, because of the if a.left < words comparison. We can’t actually avoid the subtraction a.left -= words because we would have to do it to make this comparison work if we got rid of a.left.

So how much better is this?

BenchmarkArena/int/arena-48         780.07 MB/s
BenchmarkArena/int/new-48           383.16 MB/s
BenchmarkArena/[2]int/arena-48      1245.73 MB/s
BenchmarkArena/[2]int/new-48        530.39 MB/s
BenchmarkArena/[64]int/arena-48     7684.39 MB/s
BenchmarkArena/[64]int/new-48       2679.94 MB/s
BenchmarkArena/[1024]int/arena-48   8859.99 MB/s
BenchmarkArena/[1024]int/new-48     2611.33 MB/s

Remarkably, not very! This is an improvement on the order of magnitude of one or two percentage points. This is because the branch we deleted is extremely predictable. Because Go’s codegen is relatively mediocre, the effect of highly predictable branches (assuming Go actually schedules the branches correctly 🙄) is quite minor.

Turns out there’s a bigger improvement we can make.

Write Barriers

Here’s the assembly Go generated for this function, heavily abridged, and annotated with the corresponding Go source code.

TEXT (*Arena).Alloc(SB)
  CMPQ    SP, 0x10(R14)
  JBE     moreStack  ; Stack growth prologue.
  PUSHQ   BP
  MOVQ    SP, BP
  SUBQ    $0x58, SP

  ; size = (size + mask) &^ mask
  LEAQ    0x7(BX), DX
  ANDQ    $-0x8, DX
  ; words := size / wordBytes
  MOVQ    DX, SI
  SHRQ    $0x3, DX

  ; if a.left < words
  CMPQ    0x8(AX), DX
  JAE     alloc

  MOVQ    AX, 0x68(SP)
  MOVQ    SI, 0x48(SP)
  MOVQ    DX, 0x40(SP)

  ; nextPow2(words)
  MOVZX   runtime.x86HasPOPCNT(SB), DI
  TESTL   DI, DI
  JE      1f
  XORL    DI, DI
  POPCNTQ DX, DI
  JMP     2f
1:
  MOVQ    DX, AX
  CALL    math/bits.OnesCount(SB)
  MOVQ    0x40(SP), DX
  MOVQ    0x48(SP), SI
  MOVQ    AX, DI
  MOVQ    0x68(SP), AX
2:
  CMPQ    DI, $0x1
  JE      1f
  BSRQ    DX, CX
  MOVQ    $-0x1, DI
  CMOVE   DI, CX
  INCQ    CX
  MOVL    $0x1, DI
  SHLQ    CL, DI
  CMPQ    CX, $0x40
  SBBQ    R8, R8
  ANDQ    R8, DI
  MOVQ    DI, DX
1:
  MOVQ    0x10(AX), CX
  SHLQ    $0x1, CX

  ; a.cap = max(minWords, a.cap*2, nextPow2(words))
  CMPQ    CX, $0x8
  MOVL    $0x8, BX
  CMOVA   CX, BX
  CMPQ    DX, BX
  CMOVA   DX, BX
  MOVQ    BX, 0x10(AX)

  ; a.next = a.allocChunk(a.cap)
  CALL    github.com/mcy/go-arena.(*Arena).allocChunk(SB)
  CMPL    runtime.writeBarrier(SB), $0x0
  JNE     1f
  MOVQ    0x68(SP), DX
  JMP     2f
1:
  CALL    runtime.gcWriteBarrier2(SB)
  MOVQ    AX, 0(R11)
  MOVQ    0x68(SP), DX
  MOVQ    0(DX), R8
  MOVQ    R8, 0x8(R11)
2:
  MOVQ    AX, 0(DX)

  ; a.left = a.cap
  MOVQ    0x10(DX), R8
  MOVQ    R8, 0x8(DX)
  MOVQ    0x28(DX), CX
  MOVQ    0x20(DX), BX
  INCQ    BX
  MOVQ    0x18(DX), R8
  CMPQ    CX, BX
  JAE     2f

  ; a.chunks = append(a.chunks, a.next)
  MOVQ    AX, 0x50(SP)
  MOVQ    R8, AX
  MOVL    $0x1, DI
  LEAQ    0x28f70(IP), SI
  CALL    runtime.growslice(SB)
  MOVQ    0x68(SP), DX
  MOVQ    CX, 0x28(DX)
  CMPL    runtime.writeBarrier(SB), $0x0
  JE      1f
  CALL    runtime.gcWriteBarrier2(SB)
  MOVQ    AX, 0(R11)
  MOVQ    0x18(DX), CX
  MOVQ    CX, 0x8(R11)
1:
  MOVQ    AX, 0x18(DX)
  MOVQ    AX, R8
  MOVQ    0x50(SP), AX
2:
  MOVQ    BX, 0x20(DX)
  CMPL    runtime.writeBarrier(SB), $0x0
  JE      1f
  CALL    runtime.gcWriteBarrier2(SB)
  MOVQ    AX, 0(R11)
  MOVQ    -0x8(R8)(BX*8), CX
  MOVQ    CX, 0x8(R11)
1:
  MOVQ    AX, -0x8(R8)(BX*8)
  MOVQ    DX, AX
  MOVQ    0x40(SP), DX
  MOVQ    0x48(SP), SI

alloc:
  ; p := a.next
  MOVQ    0(AX), CX

  ; a.next = unsafe.Add(a.next, size)
  LEAQ    0(CX)(SI*1), BX
  CMPL    runtime.writeBarrier(SB), $0x0
  JE      1f
  CALL    runtime.gcWriteBarrier2(SB)
  MOVQ    BX, 0(R11)
  MOVQ    0(AX), SI
  MOVQ    SI, 0x8(R11)
1:
  MOVQ    BX, 0(AX)

  ; a.left -= words
  LEAQ    0(CX)(SI*1), BX
  SUBQ    DX, 0x8(AX)

  ; return p
  MOVQ    CX, AX
  ADDQ    $0x58, SP
  POPQ    BP
  RET