5 · Shaping the data Draft

Chapter 5 — Shaping the data

5 min read

On this page

The preceding chapters have priced what a program is given: the core and its caches, the operating system that lends it the core and its memory, the other threads it shares that memory with, and the network that brings its input. This chapter prices what the program chooses for itself: where the bytes its loop reads and writes live, how it finds one among many, and how it hands one to another thread. In the source code those choices look like nothing. updates.push(u) is one line, and so are positions.insert(id, p), Box::new(order) and tx.send(u). Behind each lies a chain that the source code does not show. The push usually stores 32 bytes and adds one to a length; once in a while it finds the vector full, asks the allocator for a block twice the size, copies every element across and frees the old one. The insert usually hashes a key and writes a slot; once in a while it finds the table full and rehashes every entry into a new table twice the size. Box::new usually pops a block from a list the allocator keeps for the thread; once in a while the allocator has run out, asks the kernel for pages with mmap, and each new page faults on first touch. The send usually writes a slot; once in a while it takes a lock and wakes a sleeping thread.

Put prices on those chains against the budget of 1 µs per hot-path iteration, 4,000 cycles at 4 GHz, and the shape of the problem appears again. The common case is cheap: a push within capacity costs 1–2 ns, an array index 1 ns when its line is in L1, a hash map lookup that hits 20–50 ns, an allocation 20–50 ns and about as much again to free, a lock nobody else wants 20–40 ns. A benchmark of any of them reports a reassuring number. The tail is in the once in a while. The push that doubles a vector of a million 32-byte entries moves 32 MB: a copy of 2–3 ms at 10–20 GB/s, two to three thousand budgets, if the allocator must move the bytes, tens of microseconds if the kernel can move their pages instead, which glibc asks for at this size, and in either case 0.5–1 µs for each of the 8,192 fresh 4 KB pages the first time one is touched. The insert that rehashes a map of 100,000 entries takes 1–5 ms. The allocation that finds its list empty takes 1–10 µs. A receiver asleep on an empty channel wakes 5–20 µs after the send, and a lock whose holder is preempted stays held for the holder’s time slice, 1–4 ms. Doubling, rehash, first touch, contention: each tail is paid by one unlucky operation, when the library’s bookkeeping runs out rather than when the program chose. The guiding rule of this chapter is: the hot path allocates nothing, locks nothing, and touches as few cache lines as possible. Every tail above begins with a call into the allocator or a wait on another thread, so a loop that makes neither has removed those rows from its histogram rather than made them rare, and what is left, the common case, is priced in cache lines: 1 ns for a line already in L1, 50–100 ns for one another core wrote last.

None of this is particular to trading. A game engine drawing sixty frames a second has 16.7 ms for each, and a frame 3 ms late is a visible stutter, so its bullets and particles come from object pools filled when the level loads. An audio thread must hand the sound card a buffer every few milliseconds or the speaker clicks, so in real-time audio that thread never allocates, locks or waits, and hears from the rest of the program through a lock-free ring. The Linux kernel takes its commonest objects, open files, network packets, processes, from its slab allocator, caches of ready-made objects of one type each. PostgreSQL gives each query a memory context, a region it allocates from and discards whole when the query ends. Each is the same answer to the same prices, reached by people who never traded anything.

The chapter starts with what memory is to a program: the stack and the heap, which Rust types allocate, how a Vec grows, and the three lifetimes of hot-path data. Then the ladder of what each operation on that data costs. Then one shape per section, from allocation and the structures that avoid it to finding by key, finding the next flag, passing between threads, batching and the compiler’s part, asking of each what it is, why it works that way and what it costs. What follows for a hot path is collected in one place near the end, after the understanding that justifies it. The code for every experiment is in the companion repository under ch05-structures/; the repository holds the code and this chapter holds the reasons.

Readings in this chapter