Capacity and data lifetimes

Capacity, doubling and the copy

A Vec keeps its elements in one block and two numbers: its length, the elements in use, and its capacity, the room in the block. A push within capacity is a store and an increment. A push at capacity cannot write past the block, so it gets a bigger one, copies every element across and frees the old one. The standard library promises no growth factor, but today’s implementation doubles, from a first capacity of four for elements of 2 bytes to 1 KB. A Vec<Update> filled from empty grows like this, each u an element and each dot a free slot:

Growths get further apart as fast as they get bigger, so n pushes copy fewer than 2n elements in all under this doubling policy, fewer than two copied elements per push on average: that is why Vec is fast in general, and no comfort to the push that copies. The one that takes a vector of Updates from a million to two million moves 32 MB in one call, from the line that cost 2 ns the time before: a copy of the bytes, or, for a block this size, a request to the kernel to move their pages, the mremap of the operating-system chapter, which is faster but leaves every new page to be faulted in on first touch. Vec::with_capacity(n) sets the capacity up front, and clear empties a vector but keeps its block.

Three lifetimes

Everything a hot loop touches can be sorted by how long it lives, which decides where its memory should come from, into three kinds.

Data fixed for the run lives from startup to shutdown: the positions, how much of each of the desk’s 64 instruments it holds; each instrument’s book; the queue from the feed thread on core 2, which reads the venue’s market data and decodes it, to the strategy on core 3, the thread that decides what orders to send; and the slots for the open orders of the gateway thread on core 6, which sends orders to the venue and reads its replies. Its size is known from the configuration, so it is allocated once at startup, touched page by page so that each page’s first-touch fault is paid before trading, and never freed: preallocation.

Data that lives for one batch, one pass of the loop, dies all together at the end of the pass: the updates decoded from one read of the socket, the orders decided on this pass. So it can come from one block, handed out by moving a pointer forward and emptied by moving it back. That is an arena, in this chapter’s sense of the word; glibc’s per-thread regions, which bear the same name, are a larger and different thing, and are called regions from here on.

Data with a variable lifetime dies when nobody can predict: an order lives from being sent until it is filled, cancelled or rejected, a millisecond or a day later, in any order. For that the program keeps a fixed number of slots, made at startup, and a list of the free ones; taking a slot pops the list and giving it back pushes it. That is a pool, and when it runs out the program refuses rather than grows.

What “allocates nothing in the loop” means

A loop allocates nothing when, from the end of warm-up, its thread makes no call into the allocator, no allocation, reallocation or free, on any path, the rare ones included: a gap in the sequence numbers, a full pool, an error formatted into a log line. Warm-up is everything before that point: allocating what is fixed for the run, touching it, and running enough messages through that anything lazy has happened once. Not few calls but none, since one call in ten thousand iterations still meets the slow path whenever the allocator’s lists run dry.

The calls hide in libraries and in drops, so this is proved by counting, not by reading. Chapter 2’s counting allocator, which forwards each request to the system’s and adds one to an atomic counter, turns the claim into a number: read the counter after warm-up, run a replay, a recording of real messages fed from a file to the same code, read it again, and assert that it has not moved. Growth counts too, because its realloc, the trait’s default, allocates, copies and frees. The counter sees every thread, so the test runs alone in a binary of its own; a second counter in dealloc catches frees; and the proof covers only the paths the replay takes.

What it costs

A stack frame costs an instruction each way, its stores landing in L1 at about 1 ns. A heap block costs 20–50 ns, 80–200 cycles, 2–5% of a budget, and as much again to free, so a value made and dropped in one iteration costs up to a tenth of a budget; the slow path costs 1–10 µs, one to ten budgets. A push costs 1–2 ns within capacity; one that doubles adds the copy at 10–20 GB/s, 2–3 µs for 32 KB, or for 32 MB either a 2–3 ms copy or an mremap of tens of microseconds, and 0.5–1 µs a page when the new block is fresh. Preallocation moves these costs to startup, where zeroing at 50–100 µs a megabyte and the first-touch faults delay nothing.