Finding and counting allocations

Smells in the loop

A smell in the loop is a call that is not wrong in itself but that in a hot loop nearly always means an allocation, and so earns a second look in review: Box::new, Rc::new and Arc::new, the last with an atomic read-modify-write on every clone and drop; String::from, to_string, to_owned and format!, each a new string even if thrown away a line later; Vec::new and then pushes, doubling up from nothing; collect, which allocates what it builds; and clone of any of these, as deep as the value goes. Symbols are the commonest case, because venues name instruments with strings, yet 16 bytes hold BTC-USDT-PERP as a plain Copy value, stored inline and compared as bytes:

/// A venue symbol in 16 bytes, zero-padded: Copy, comparable, no heap.
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct Symbol([u8; 16]);

impl Symbol {
    pub fn new(s: &str) -> Option<Symbol> {
        let b = s.as_bytes();
        let mut buf = [0u8; 16];
        buf.get_mut(..b.len())?.copy_from_slice(b); // None if longer than 16
        Some(Symbol(buf))
    }
}

On the hot path itself the instrument travels as a small integer id, and the fixed symbol stays at the edges.

What it costs

A Box::new and its drop cost 40–100 ns together, 160–400 cycles, 4–10% of a budget, and 1–10 µs, one to ten budgets, when the thread cache and its region are empty. A push within capacity costs 1–2 ns, against 2–3 µs to 2–3 ms for the doubling it forbids; a pool’s alloc and free 2–4 ns together; an arena allocation 1–2 ns and its reset one store; an array nothing. Only the allocator adds indirect costs: its own lines in L1, blocks straddling two lines, and by afternoon scattered blocks, each step between them a miss of 10–40 ns to L3 or 80–100 ns to DRAM.

Worked example: an order boxed per cancel-replace, then pooled

At 09:30:00 New York time, the US stock market’s open, BTC-USDT-PERP turns busy, and the gateway thread on core 6 sends 2,000 cancel-replaces a second, each one message asking the venue to cancel one of the desk’s waiting orders and place a new one at a new price. Each builds a new 64-byte Order and retires the old one when the venue confirms the cancel: an allocation and a free.

Boxed, each pays 40–100 ns, 4–10% of a budget, on the way from the strategy’s decision to the wire: 80–200 µs of core 6 over the second. The tail is the slow path, and the open is when it comes. In the quiet hours glibc returned the free top of the heap to the kernel; now the burst raises the orders in flight, the thread cache’s 80-byte list runs dry and then the thread’s region, and malloc asks the kernel for more and the new pages fault: 1–10 µs, one to ten budgets, charged to an unlucky cancel-replace, likely one of the first in the burst, sent because the market had just moved. It strikes fewer than one call in a hundred, so it is the max, not the p99.

Pooled, the gateway allocates Pool::<Order>::with_capacity(4_096) at startup, 256 KB in L2, a line per slot with Order declared #[repr(align(64))], and allocates and frees every slot once so that their pages fault before the open. A cancel-replace pops an index and writes the order; the confirmation drops it and pushes the index: 2–4 ns, 0.2–0.4% of a budget, 4–8 µs over the second. There is no slow path, and the worst case is a slot line fallen to L2, 3.5–4 ns more. If 4,096 orders are ever in flight, far beyond what the desk sends, alloc returns None and the gateway refuses the order: a failure designed, counted and visible, not 10 µs hidden in a tail.

Seeing it

The proof is a test, with the counting global allocator installed, the GlobalAlloc that adds one to ALLOCS on every allocation:

#[test]
fn cancel_replace_allocates_nothing() {
    let mut pool: Pool<Order> = Pool::with_capacity(4_096); // startup allocates here
    let before = ALLOCS.load(Relaxed);
    for n in 0..1_000_000u64 {
        let i = pool.alloc(Order::new(n)).expect("pool exhausted");
        pool.free(i);
    }
    assert_eq!(ALLOCS.load(Relaxed), before); // the loop allocated nothing
}

With Box::new the loop fails by a million. On the running gateway three tools, all needing root, watch from outside. perf trace -e syscalls:sys_enter_mmap,syscalls:sys_enter_brk,syscalls:sys_enter_munmap -p <pid> prints a line, with time, thread and arguments, for each call to the kernel for memory: a brk with a rising address in the open is the main heap growing, an mmap a new heap for another thread’s region or a block above the threshold, a munmap memory returned and a shootdown sent. For calls that never reach the kernel, perf probe -x /lib/x86_64-linux-gnu/libc.so.6 malloc places a probe on glibc’s malloc, named probe_libc:malloc, and perf stat -e probe_libc:malloc -p <pid> -- sleep 10 counts its calls for ten seconds: one per cancel-replace boxed, zero pooled. For the whole run, heaptrack ./gateway records each allocation with its stack, and heaptrack_gui lists them by call site, with peak memory and the temporary allocations, freed almost as soon as made, which is what an order boxed per cancel-replace looks like.

Read more: Jeff Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator”, USENIX Summer 1994 Technical Conference, on per-type caches of constructed objects. Jason Evans, “A Scalable Concurrent malloc(3) Implementation for FreeBSD”, BSDCan 2006, the paper behind jemalloc, on size classes and on spreading threads across separately locked regions of the heap. Daan Leijen, Benjamin Zorn and Leonardo de Moura, “Mimalloc: Free List Sharding in Action”, Microsoft Research technical report MSR-TR-2019-18, 2019, which keeps a free list per page so that each stays short. The bumpalo documentation on docs.rs, for bump allocation and reset.