Stack, heap, and allocating types

5.1 What memory is to a program

To a program, memory is its address space, one long row of numbered bytes. Where a value goes depends on how long it must live and whether its size is known at compile time, and Rust answers with two regions that work in opposite ways.

The stack

Every thread has a stack, a region of a few megabytes reserved when the thread starts. A register, the stack pointer (rsp on x86-64), marks its current end. A function needs room for its locals and its return address, and the compiler knows how many bytes, because every local’s type has a fixed size; so the function begins by moving the stack pointer down that far, and the bytes passed over are its stack frame, scratch space for this one call, given back when it returns. Calls nest, so frames come and go last in, first out.

That is why the stack is fast: a frame costs an instruction to make and one to drop, with no search and no bookkeeping, and the top of the stack, touched by every call, is nearly always in L1. It is also the stack’s limit. A frame lives exactly as long as its call, so a value that must outlive its function, an order kept until it is filled, a message handed to another thread, cannot live there; and a frame’s size is fixed at compile time, so neither can a value sized only at run time, a message whose length is in its header, a list that grows. Those are the two reasons the heap exists.

The heap

The heap is memory asked for while the program runs, in pieces of any size, and given back in any order. Tracking which ranges are free is the work of the allocator Chapter 2 described, a cache of memory in front of the kernel with a 20–50 ns fast path and a slow path that asks the kernel for pages. A Rust value that uses the heap keeps a fixed part where it lives and the rest in a block it points to: a Vec<Update>, a vector of the 32-byte market-data updates this chapter passes between threads, is 24 bytes, a pointer, a capacity and a length, and a Box<T> is an 8-byte pointer. When the value goes out of scope, Rust frees the block, a second call into the allocator.

Which types allocate

A type allocates when making, growing or cloning a value of it calls the allocator, and dropping the value calls it again; the test is whether the type owns a pointer to a heap block. Box, Vec, VecDeque, String, HashMap, BTreeMap, Rc, Arc and the standard library’s channels do, and so do format!, collect, to_owned, to_string and clone of an owning collection or string. Cloning an Rc or an Arc only adds one to a count, an atomic one for Arc. Plain values do not: numbers, arrays, tuples, structs and enums of plain fields, references, fixed byte arrays. Allocation is catching: one String field makes a struct allocate.

// Six lines that call the allocator
let b = Box::new(update);                       // a block of 32 bytes
let v: Vec<Update> = Vec::with_capacity(4096);  // a block of 128 KB
let s = String::from("BTC-USDT-PERP");          // a block for 13 bytes
let t = format!("{s} {price}");                 // one or more, as the String grows
let ids: Vec<u32> = (0..64).collect();          // a block for 64 u32s
let s2 = s.clone();                             // a copy of the heap block

// Six lines that do not
let u = Update { seq, price, qty, instrument, side }; // 32 bytes in this frame
let a = [0u64; 64];                             // 512 bytes in this frame
let pair = (42u32, price);                      // plain values, in the frame
let name: &str = "BTC-USDT-PERP";               // a pointer and a length into the binary
let sym: [u8; 16] = *b"BTC-USDT-PERP\0\0\0";    // 16 fixed bytes
let empty: Vec<Update> = Vec::new();            // nothing until the first push

The last line matters most: Vec::new, String::new and HashMap::new allocate nothing until the first push or insert, so a hot-path collection is judged by where it is first filled and whether it ever outgrows its room.