Allocation-Free Hot Paths

A small malloc/free pair from glibc's per-thread cache (tcache) or from jemalloc/mimalloc costs tens of nanoseconds in a microbenchmark. If that were the whole story, nobody would bother. The trouble is the distribution:

• Slow paths inside the allocator. When the thread cache is empty or full, the allocator falls back to shared arenas with locks, coalesces free chunks, or asks the kernel for memory (brk, mmap) or gives it back (madvise, munmap) — a syscall, sometimes with a TLB shootdown that interrupts other cores.
• Page faults. Fresh heap memory is not backed by physical pages until it is first touched. Each first touch of a 4 KiB page is a minor fault: a kernel entry, a page zeroed, a page-table update — on the order of a microsecond, often more.
• Cross-thread frees. In a pipeline, the engine allocates an event and the publisher thread frees it. Memory migrates between threads' caches, and allocator metadata cache lines bounce between cores.
• Cache pollution. Allocator metadata and freshly allocated memory evict the book's hot data.

None of these show up in the median. All of them show up at p99.9 — exactly where week 25 taught you to look. So the hot-path rule is simple: no allocation and no deallocation between "order received" and "events published", after warmup.

A slab is a Vec<Entry<T>> sized once, where each entry is either occupied or vacant, and vacant entries form a singly linked free list through their own storage. Insert pops the free-list head; remove pushes onto it. Both are O(1), and nothing ever moves, so a key (an index) stays valid for the life of the element — unlike Vec::remove or swap_remove, which shift or relocate elements.

Two details turn this into a production structure:

• Generations. An order id maps to a slab key. The order is cancelled, its slot is reused by a new order — and then a late, duplicate cancel for the old id arrives. With a bare index you would cancel the wrong order. Store a generation counter in each slot, bump it on remove, and put it in the key: a stale key no longer matches. This is the ABA problem again, in index form.
• LIFO reuse. Pushing freed slots on the front of the free list means the next insert reuses the most recently freed slot — the one most likely still in L1. A FIFO free list cycles through the whole slab and touches cold memory.

What do you do when the slab is full? On the hot path, never grow: growth means a reallocation and a copy of every order, which invalidates every pointer and takes milliseconds. Reject the order with a typed capacity reject and size the slab from configuration (week 22) with headroom.

/// A handle into the slab. `generation` makes stale handles detectable:
/// when a slot is freed its generation is bumped, so a key that still
/// carries the old generation no longer resolves.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Key {
    pub index: u32,
    pub generation: u32,
}

enum Entry<T> {
    Occupied { generation: u32, value: T },
    Vacant { generation: u32, next_free: u32 },
}

const NIL: u32 = u32::MAX;

/// Fixed-capacity slab: every slot is allocated up front, free slots form
/// an intrusive LIFO list threaded through the vacant entries.
pub struct Slab<T> {
    entries: Vec<Entry<T>>,
    free_head: u32,
    len: usize,
}

impl<T> Slab<T> {
    /// Allocate every slot up front (generation 0) and thread them onto the
    /// free list 0 -> 1 -> 2 -> ... -> NIL. The Vec must never grow after this.
    pub fn with_capacity(capacity: usize) -> Self {
        todo!()
    }

    /// Pop the head of the free list. Err(value) when full — never grow.
    pub fn insert(&mut self, value: T) -> Result<Key, T> {
        todo!()
    }

    /// None for out-of-range indices, vacant slots and stale generations.
    pub fn get(&self, key: Key) -> Option<&T> {
        todo!()
    }

    pub fn get_mut(&mut self, key: Key) -> Option<&mut T> {
        todo!()
    }

    /// Free the slot: bump its generation (wrapping) so old keys go stale,
    /// and push it on the FRONT of the free list. Hint: std::mem::replace.
    pub fn remove(&mut self, key: Key) -> Option<T> {
        todo!()
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn capacity(&self) -> usize {
        self.entries.len()
    }
}

#[global_allocator] lets you replace the allocator for the whole program. A counting wrapper forwards every call to the real allocator (System, or jemalloc in production) and increments a few counters. Then a test can say: after warmup, process 100,000 mixed orders; assert zero allocations.

The rules for code inside an allocator are strict, because it is called from everywhere, including from inside println! and the panic machinery:

• It must not allocate, directly or indirectly — no format!, no Vec, no printing. Recursion into yourself is a stack overflow or a deadlock.
• It must not panic or unwind.
• Keep it cheap: Relaxed atomic adds are enough for counters that you read after the fact.

What surprises people about what allocates in Rust: Vec::new(), String::new() and Vec::with_capacity(0) do not; vec![0; n] goes through alloc_zeroed; growing a Vec is a realloc; format!, to_string(), clone() of a String, collect(), Box<dyn Trait>, Arc::new and every HashMap insert that crosses the load factor do. std::mem::take(&mut vec) silently throws your capacity away; vec.clear() keeps it.

The pattern the drill ends with is the one you will use everywhere: the caller owns a buffer, the hot function fills it. encode_fills(&fills, &mut out) clears and refills a Vec whose capacity was reserved at startup — zero allocations per call, forever.

use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicU64, Ordering};

static ALLOCS: AtomicU64 = AtomicU64::new(0);
static REALLOCS: AtomicU64 = AtomicU64::new(0);
static DEALLOCS: AtomicU64 = AtomicU64::new(0);
static BYTES: AtomicU64 = AtomicU64::new(0);

/// Forwards to the system allocator and counts every call. Must never
/// allocate, lock or print itself — it IS the allocator.
pub struct Counting;

unsafe impl GlobalAlloc for Counting {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        // TODO: count one allocation and layout.size() bytes.
        System.alloc(layout)
    }

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
        // TODO: same as alloc — vec![0; n] lands here.
        System.alloc_zeroed(layout)
    }

    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
        // TODO: count one realloc (not an alloc) and new_size bytes.
        System.realloc(ptr, layout, new_size)
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        // TODO: count one deallocation.
        System.dealloc(ptr, layout)
    }
}

#[global_allocator]
static GLOBAL: Counting = Counting;

#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct AllocStats {
    pub allocs: u64,
    pub reallocs: u64,
    pub deallocs: u64,
    pub bytes: u64,
}

/// Current totals since process start.
pub fn snapshot() -> AllocStats {
    todo!()
}

/// Run `f` and report what it allocated: the difference between a snapshot
/// taken before and one taken after. Only meaningful while no other thread
/// allocates.
pub fn measure<R>(f: impl FnOnce() -> R) -> (R, AllocStats) {
    todo!()
}

#[derive(Clone, Copy, Debug)]
pub struct Fill {
    pub maker: u64,
    pub taker: u64,
    pub px: i64,
    pub qty: u64,
}

/// The slow way: one String per fill. Kept for comparison.
pub fn render_fills(fills: &[Fill]) -> Vec<String> {
    fills
        .iter()
        .map(|f| format!("{}:{}@{}x{}", f.maker, f.taker, f.px, f.qty))
        .collect()
}

/// Hot-path encoder: clear `out` and append one 32-byte record per fill
/// (maker, taker, px, qty — each 8 bytes little-endian). Must not allocate
/// when `out` already has capacity for 32 * fills.len() bytes.
pub fn encode_fills(fills: &[Fill], out: &mut Vec<u8>) {
    todo!()
}

Sort every object on the order path by its lifetime, and the strategy picks itself:

• Lives as long as the order (the order itself, its level membership): a slab slot. Freed explicitly on fill or cancel.
• Lives for one message or one batch (match results, scratch vectors, decoded fields): reused buffers owned by the engine — a Vec<Fill> that is cleared, never dropped — or an arena reset after each batch.
• Crosses threads (event buffers handed from engine to publisher): a pool with a return path. The consumer does not free the buffer; it sends it back on an SPSC queue (week 5) and the producer reuses it. If the pool is empty you have discovered backpressure (week 24) — block, drop, or reject, but do not silently allocate.
• Lives forever (instrument reference data, configuration): allocate freely at startup.

Inline storage helps for small, bounded collections: arrayvec::ArrayVec<Fill, 8> never touches the heap, and smallvec::SmallVec spills to the heap only past its inline capacity — fine if the spill is rare and you have measured that it is.

Vec::with_capacity(1 << 20) returns instantly — the allocator reserved address space, but for large sizes the kernel has not given you any physical memory yet. The first write to each 4 KiB page faults. So a slab that was "preallocated" at startup can still take a page fault the first time the market reaches an untouched slot — in the middle of the open, of course.

The startup checklist:

• Prefault: write to every page of every preallocated structure (filling the free list in with_capacity does this for the slab), or mmap with MAP_POPULATE.
• Lock it: mlockall(MCL_CURRENT | MCL_FUTURE) stops the kernel from paging hot memory out. Needs CAP_IPC_LOCK or a large enough RLIMIT_MEMLOCK.
• Mind the TLB: the second-level TLB on many recent cores holds around 1.5 thousand entries — about 6 MiB of coverage with 4 KiB pages. A book plus order slab bigger than that misses the TLB as well as the cache. 2 MiB huge pages cover gigabytes with the same entries.
• But beware transparent huge pages in always mode: background compaction and khugepaged can stall a thread. Many latency-sensitive deployments use madvise mode (opt in per region) or explicit hugetlbfs pages allocated at boot.

"Allocation-free" needs a precise definition or it becomes an argument. Use this one: after a warmup phase that exercises every message type and every code path you care about, a run of N mixed messages performs zero allocations, zero reallocations and zero deallocations on the engine thread. Warmup exists because some structures legitimately reach their steady-state capacity on first use; the test proves they stop there.

Rejects count. In a real exchange a large fraction of inbound messages can be rejected or cancelled, so an error path that builds a String reason or a Box<dyn Error> is a hot path. Make reject reasons a Copy enum.