Inside an allocation

5.3 Anatomy of an allocation, and the structures that avoid it

Box::new(order) is one line, and on most calls a cheap one. This section follows one boxed order through the allocator and back, then the structures that avoid the trip, none of them trading’s invention.

One Box::new, end to end

The gateway’s Order is 64 bytes. Box::new asks Rust’s global allocator for them, by default glibc’s malloc, Chapter 2’s cache in front of the kernel, which cuts ranges taken with brk or mmap into pieces in per-thread regions.

The first step is the size class. An allocator rounds each request up to one of a fixed set of sizes, its size classes, and keeps each class’s free blocks on a list of their own, so that a block freed by one request can serve the next of its class without being measured, split or merged. glibc’s small classes are 16 bytes apart and every block carries a header recording its size, so the 64-byte order gets an 80-byte block.

The second step is the thread cache, glibc’s tcache: a short list of recently freed blocks for each small class, private to its thread and so used without a lock. A free block holds the link to the next in its own first bytes, so malloc reads that link, makes it the list’s new head and returns the block. That is the fast path, 20–50 ns with its bookkeeping, 80–200 cycles, 2–5% of a budget, and in a steady state nearly every call takes it.

When the list is empty, malloc turns to the thread’s region, with its longer lists of free blocks and an untouched remainder at its end: more work, but no system call. When the remainder is used up, the region grows by a brk or mmap of 100–300 ns, and the first write to each new 4 KB page takes a minor fault of 0.5–1 µs. That slow path costs 1–10 µs, one to ten budgets, on a call chosen by the allocator’s state, not by the program.

On the way back, drop runs Order’s destructor, nothing for plain fields, and free reads the header to learn the class and pushes the block onto the thread cache’s list, for about what the allocation cost. The list is last in, first out, so the next 64-byte Box::new gets the same block back, its line probably still in L1, which is why a box-and-drop benchmark looks fine. A full list sends the block back to the thread’s region, merged with any free neighbour, and free space gathered at the top of the heap goes back to the kernel: the next growth faults again, and the unmapping sends a TLB shootdown, an interrupt to drop stale translations, to every other core running the process’s threads.

Fragmentation

Fragmentation is memory that is free but cannot serve what is asked: inside a block, internal fragmentation, such as the 16 bytes of header and slack in the order’s 80; between blocks, external fragmentation, free pieces scattered among live ones, each too small or misplaced for the next request. A process that allocates and frees blocks of many sizes all day ends with a patchwork heap, its footprint grown and its live blocks spread over many pages and lines. Boxes allocated in sequence at 09:00 sit side by side, where the prefetcher can follow them; boxes allocated at 15:00 sit wherever a hole was, and a structure of them behaves like a linked list, each step a dependent miss to DRAM at 80–100 ns. A benchmark in a fresh process never sees it.

The allocator’s lines in the cache

Every call also touches the allocator’s own data, the thread cache’s heads and counts, the block’s header and link, on a refill the region’s lists: lines the strategy did not ask for, each evicting one it did from an L1 of 32–48 KB. The blocks are aligned to 16 bytes, not 64, so 64-byte orders cut end to end at 80-byte strides straddle two lines three times in four. None of this shows under malloc in a profile; it shows as misses in the code after it.

The fixed-capacity Vec

A fixed-capacity Vec is an ordinary Vec whose capacity, its room before it must reallocate, is set once at startup with Vec::with_capacity(n) and never exceeded. A push within capacity is a store and a length increment, 1–2 ns, and clear empties it but keeps the room, so a Vec that collects each batch’s fills allocates once per process. A push past capacity would double it, 2–3 µs at 32 KB and milliseconds at 32 MB, between moving the bytes and faulting in the new pages. Here that push is a bug, a wrong startup estimate, and growing would hide it and pay at the worst moment. So it is caught: in tests by debug_assert!(v.len() < v.capacity()) before the push, an assertion checked in debug and test builds and compiled out of release ones, or always by a push that refuses:

/// A push that refuses, rather than grows, when the Vec is full.
pub fn try_push<T>(v: &mut Vec<T>, x: T) -> Result<(), T> {
    if v.len() == v.capacity() {
        return Err(x); // the caller decides: reject, count, raise an alarm
    }
    v.push(x); // within capacity: a store and a length increment
    Ok(())
}

When the size is known at compile time, an array [T; N] needs no allocator at all: the five best levels a strategy keeps are a [Level; 5], stored inline in whatever holds them.