5 · Shaping the data Draft
The data-operation latency ladder
On this page
5.2 The ladder of a hot-path data operation
This ladder prices what a hot loop does with its data, keeping a value, finding one, finding the next with work to do and handing one to another thread, cheapest first, on a 4 GHz core. Several rows name structures later sections take apart. A pool is a fixed set of slots made at startup, with a stack of the free slots’ indices and a flag per slot saying whether it holds a value; an arena, a block handed out by moving a pointer forward and emptied at once. A ring is a fixed array of slots used in a circle, filled by one thread and emptied by another, each moving its own counter; the SPSC (single-producer, single-consumer) ring joins exactly two threads, and its cached peer is the copy each side keeps of the other’s counter, so as not to read the other core’s line every time. A hash map turns a key into a number, its hash, which picks a place in a table; SipHash is the hash Rust’s HashMap uses by default, built to resist keys chosen to collide, and FxHash a far simpler one that is not. A BTreeMap is the standard library’s ordered map, a tree of small nodes searched by following pointers. A bitmap is a row of one-bit flags, 64 to a u64, and trailing_zeros and leading_zeros count the zeros at either end of a word, so one instruction finds the nearest set flag. A batch is the group of items a thread takes and handles together. mpsc is the standard library’s channel, many senders to one receiver, and Mutex<VecDeque> a growable queue behind a lock, which Chapter 3 timed between two threads. A rehash is a hash map’s doubling: a table twice the size, every entry’s place computed again. A table is cold when its lines have left L1 and L2. Real parts vary by a factor of two either way; the shape of the ladder does not.
| Rung | Typical cost | Cycles at 4 GHz | What sets it |
|---|---|---|---|
| Array index, line in L1 | 1 ns | 4 | one load from a computed address |
Vec::push within capacity | 1–2 ns | 4–8 | a store and a length increment |
| Bitmap test, set or clear | 1 ns | 4 | an AND or an OR on one word in L1 |
trailing_zeros / leading_zeros | 0.25–0.75 ns | 1–3 | one instruction, tzcnt or lzcnt |
| SPSC ring push or pop, cached peer valid | 5–20 ns | 20–80 | a load, an index from the counter, a store, a Release store; no line the other core writes |
HashMap<u32, Position> get, hit, SipHash, table in L1 or L2 | 20–50 ns | 80–200 | the hash, 15–25 ns; finding the key’s slot and comparing it, 5–15 ns |
| The same get with FxHash | 5–15 ns | 20–60 | the hash, 1–3 ns; the same search and compare |
Box::new, allocator fast path | 20–50 ns, about as much again to free | 80–200, and as much again | a pop from the thread’s cache of free blocks |
Mutex lock and unlock, uncontended, same core as the last holder | 20–40 ns | 80–160 | two locked instructions |
| Cross-core line transfer | 50–100 ns | 200–400 | a line another core wrote last, fetched from that core’s cache |
BTreeMap update, 1,000 keys | 100–300 ns | 400–1,200 | three node visits, a pointer chase each |
mpsc send and recv, receiver awake and polling | 100–300 ns | 400–1,200 | a linked list of blocks, an allocation per 31 messages; two read-modify-writes; the line transfers |
Mutex<VecDeque> push and pop between two cores | 150–400 ns uncontended, more under collision | 600–1,600 | the lock’s line and the data’s lines, crossing each way |
HashMap get, table cold in L3 | 50–100 ns | 200–400 | two lines of the table, both from L3 |
Vec::push that doubles, a million 32-byte entries | 2–3 ms if the bytes are copied; tens of µs if the kernel moves the pages (mremap), as glibc asks at this size; either way 0.5–1 µs per fresh 4 KB page, 4–8 ms over the 8,192 new pages as they are first touched | 8–12 million, or hundreds of thousands; plus 2,000–4,000 a page | a block twice the size, moved by copy or by remapping, its new half unfaulted |
HashMap insert that rehashes, 100,000 entries | 1–5 ms | 4–20 million | a table twice the size, every entry re-hashed and moved |
malloc slow path, with first touch | 1–10 µs | 4,000–40,000 | a system call for more memory and a page fault per new page |
mpsc recv that sleeps and is woken | 5–20 µs; 100–200 µs from a deep sleep state | 20,000–80,000; 400,000–800,000 | a futex wake and the scheduler |
| Lock holder preempted | 1–4 ms | 4–16 million | every waiter waits out the holder’s time slice |
Read the table against the budget. The first five rows fit in it a hundred times over, give or take, 1 ns being a thousandth of it and the ring’s 5–20 ns a two-hundredth to a fiftieth: they are what this chapter builds with. The hash map hit, the allocation and the lock are 2–5% of a budget each, cheap alone and not when a loop does several per message. A line transfer or a cold lookup is a tenth, and the tree, the channel and the locked queue a tenth to a half. The last five rows are not rungs, which every operation of their kind pays, but additions that land on one unlucky operation: two to three thousand budgets for the doubling, one to five thousand for the rehash, one to ten for the slow path, five to twenty for the wake, one to four thousand for the preemption. Each is paid by a call that looks, in the source, exactly like a cheap one.