Removing allocations from an update

Worked example: what one decoded update allocates

At 14:30 UTC the feed thread on core 2 is decoding 20,000 updates a second across the desk’s 64 instruments, BTC-USDT-PERP, instrument 42, among the busiest. A first version builds this per message and hands it to the strategy on core 3:

pub struct Update {            // first version
    pub symbol: String,        // "BTC-USDT-PERP": 24 bytes here, 13 on the heap
    pub side: String,          // "bid" or "ask": 24 bytes here, 3 on the heap
    pub price: f64,            // dollars
    pub qty: f64,              // bitcoin
    pub seq: u64,
}

Each message makes two allocations on core 2, the symbol’s String::from and the side’s to_string, and two frees on core 3 when the strategy drops it: four calls at 20–50 ns, 80–200 ns in all, 320–800 cycles, 8–20% of a budget, before a price has moved. The struct is 72 bytes, more than a line, and its strings lie in two more blocks wherever the allocator found room, so an update spans at least three lines in three places, each crossing from core 2 to core 3 at 50–100 ns. And the fast path lasts only while the allocator has free blocks to hand out: the first burst that keeps more updates alive at once than any before it sends the allocator to the kernel, and one message pays 1–10 µs.

The fixed version:

#[derive(Clone, Copy)]
pub struct Update {            // fixed: 32 bytes, nothing on the heap
    pub seq: u64,              // the venue's update number
    pub price: i64,            // ticks
    pub qty: i64,              // lots; 0: none left at this price
    pub instrument: u32,       // a small id for the symbol, 42 here, given at startup
    pub side: Side,            // a one-byte enum, Bid or Ask; three bytes of padding follow
}

It has no symbol: the instrument is a 4-byte id, 42 here, assigned in place of the string when the program starts, and it chooses whose state the update goes to; Side is a one-byte enum, Bid or Ask; price and quantity are whole numbers of the venue’s price and size steps. It is 32 bytes, half a line, Copy, built in the decoder’s frame or written straight into a slot of the queue to core 3: no allocation, no free, a store of 1–2 ns. Per message, 80–200 ns and three line transfers have become 1–2 ns and half of one.

Seeing it

The proof is a test, with a second counter, FREES, in the counting allocator’s dealloc:

// tests/no_alloc.rs, a binary of its own
mod common;                    // the counting allocator, plus FREES
use common::{ALLOCS, FREES};
use std::sync::atomic::Ordering::Relaxed;

#[test]
fn feed_loop_allocates_nothing() {
    let msgs = replay::load("btc-usdt-perp-1430.bin"); // all read in before timing
    let mut feed = Feed::new(64);                       // everything fixed for the run
    for m in &msgs[..10_000] { feed.on_message(m); }    // warm-up

    let (a0, f0) = (ALLOCS.load(Relaxed), FREES.load(Relaxed));
    for m in &msgs { feed.on_message(m); }
    let (a1, f1) = (ALLOCS.load(Relaxed), FREES.load(Relaxed));

    assert_eq!((a1 - a0, f1 - f0), (0, 0), "allocated in the loop");
}

Feed stands for whatever owns the loop’s state. With the first Update the test fails, two allocations and two frees a message; with the fixed one it passes, until the day someone adds a format! to the loop. On a running process:

strace -f -e trace=mmap,brk,mremap -p <pid>
grep VmRSS /proc/<pid>/status

-p attaches strace to the process and -f to all of its threads. During warm-up it prints mmap calls, the size asked for as the second argument, and brk calls, the heap’s new end; once the loop runs, any line it prints is the allocator going to the kernel during trading. strace stops each thread at every system call while attached, so it is a check, not a measurement. VmRSS, the memory backed by physical frames, read each second after warm-up, should not move: a climb is growth, a sawtooth memory handed back to the kernel and faulted in again.

Read more: Steve Klabnik and Carol Nichols, The Rust Programming Language (No Starch Press, 2nd ed., 2023, and free online), section 4.1, “What Is Ownership?” (https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html), explains the stack and the heap from a program’s side and how Rust decides when a heap block is freed. Ulrich Drepper, What Every Programmer Should Know About Memory (Red Hat, 2007), sections 7.3, “Measuring Memory Usage”, and 7.5, “Page Fault Optimization”, show where a program’s memory goes and when its pages are first touched.