6C++ for Latency I: Memory

Writing one byte to a page of memory that has just been mapped cost this book’s laptop about $1.3\,\text{µ}\mathrm{s}$; writing the same byte to the same page a second time cost $30\,\mathrm{n}\mathrm{s}$. The first write went to the kernel, which found a free physical page, zeroed it and installed it in the page tables; the second was an ordinary store. A trading process that asks the heap for memory while it handles a message may, now and then, take that path, or several others inside the allocator that are fast on average and slow once in a while. This chapter is about memory in C++ on the hot path: how objects are laid out, what an allocation costs and when, and the arenas, pools and fixed-capacity containers that let the hot path run without allocating at all.

6.1 Object layout, padding and alignment

Definition 6.1 (Structure padding)

Every scalar type has an alignment, equal to its size on x86-64 (a double starts at a multiple of 8). The compiler lays out a structure’s fields in declaration order and inserts structure padding, unused bytes, before any field that would otherwise be misaligned and at the end, so that the structure’s size is a multiple of its largest alignment.

Example 6.2 (Ordering fields)

An order written as a first draft declares a char side, a double price, a char flag, a 64-bit id, a 32-bit quantity and a char time in force: 23 bytes of data in 40 bytes, 17 of them padding. Ordered by size (id, price, quantity, then the three characters) the same fields take 24 bytes: eight orders occupy three 64-byte cache lines instead of five. The compiler will not reorder fields itself: the order is part of the type’s interface.

Three further rules. Put the fields the hot path reads together at the start of the structure, so that one line serves the common case, and move the rest (text, audit fields) to a separate structure. Align structures written by different threads to separate cache lines (chapter 3). And prefer indices into arrays to pointers in hot structures: a 32-bit index is half a pointer and survives a relocation of the array.

6.2 What an allocation costs, and when

new and malloc are fast on average. The GNU C library’s allocator keeps small freed blocks in per-thread caches and hands them back in a few tens of nanoseconds. It also, occasionally, does much more: it consolidates free blocks, grows the heap with a system call, maps large blocks directly from the kernel (by default at 128 KiB and above, a threshold it adjusts as the program runs), returns memory to the kernel when the top of the heap is free (by default beyond 128 KiB), and every new page it touches costs a page fault.

Definition 6.3 (Page fault, pre-faulting)

A page fault is the processor’s trap into the kernel when a program touches a virtual page that is not yet backed by physical memory (a minor fault: the kernel allocates and zeroes a page) or whose contents are on disk (a major fault). Pre-faulting is touching every page of a buffer at start-up, so that no fault happens later on the hot path.

Figure 6.2 measures both costs. Replacing one of 10 000 live 64-byte orders at random costs a new-and-delete pair about $25\,\mathrm{n}\mathrm{s}$ at the median, a pool slightly less, and both reach tens of microseconds at their maximum, where the thread was interrupted. The first write to each page of a fresh 64 MiB mapping costs over a microsecond a page: 16 384 faults, forty times the cost of the same writes once the pages exist. A hot path that allocates is exposed to the allocator’s slow paths and to faults on memory it has not touched; one that does not allocate is exposed to neither.

6.3 Arenas, pools and free lists

Definition 6.4 (Arena allocator)

An arena allocator hands out consecutive pieces of one pre-allocated block by advancing an offset, and frees them all at once by resetting it; individual objects are never freed.

Definition 6.5 (Object pool, free list)

An object pool pre-allocates storage for a fixed number of objects of one type and recycles it: creating takes a free slot, destroying returns it. A free list is the list of free slots; an intrusive free list stores its links inside the free slots themselves, so it needs no memory of its own.

An arena suits memory whose lifetime is a phase: the scratch space of one message, rebuilt for the next; the parsed fields of a batch. A pool suits objects of one type with independent lifetimes: orders, which are created and cancelled in any order. Both have fixed capacity decided in advance, and the design question they force is the right one: what happens when it runs out. On the hot path the answer is never “ask the heap”; it is to refuse (reject the order, drop to a degraded mode) and raise an alarm, and to size the pool from the measured peak with a margin.

The standard library has the same ideas as memory resources (std::pmr, since C++17): a monotonic buffer resource is an arena, a pool resource keeps free lists by size. They let standard containers use them, at the price of an indirect call per allocation; the general-purpose pool of Figure 6.2 is slower than a pool for one type.

6.4 Small buffers and fixed-capacity containers

Definition 6.6 (Small-buffer optimisation, fixed-capacity container)

A type with a small-buffer optimisation stores small contents inside the object and allocates only for large ones: the GNU implementation of std::string holds up to 15 characters inline. A fixed-capacity container always stores its elements inside the object, up to a capacity fixed at compile time, and refuses to grow beyond it.

The small-buffer optimisation makes allocation depend on the data: a symbol of four letters does not allocate, a client order identifier of 22 characters does, and a test with short identifiers will not see it. The handler of Listing 6.1 is typical of first drafts. Counted with a replaced global operator new, it allocates nine times per message: one for the long identifier, three as the vector of fills grows to three, two for the new map entry (the tree node and its copy of the identifier), one when the lambda copies the fills, and two when std::function stores the lambda on the heap and copies it. The rewrite with a fixed string, a fixed vector of fills and a fixed table of entries does the same work with none.

Method 6.7 (Removing allocation from a hot path)

1. Count: replace the global operator new in a test build and assert the count per message after warm-up.
2. For each allocation, decide the capacity: identifiers and symbols in fixed strings, per-message lists in fixed vectors, objects with lifetimes in pools, per-message scratch in an arena reset per message.
3. Replace type-erased callables that allocate (std::function with large captures) by templates (chapter 7) or function pointers with a context.
4. Allocate and touch every pool, arena and table at start-up, on the thread that will use it (chapter 4).
5. Keep the assertion in the tests, so that a later change that allocates fails the build.

6.5 Tutorial: counting and removing allocations

6.6 Build: the allocation-free toolkit

6.7 Exercises

Exercise 6.1 ★

What are the size and padding of a structure holding, in this order, a char, an int32, a char, a double and an int16? And with the fields sorted by size?

Solution

Solution of Exercise 6.1.

Offsets 0, 4, 8, 16 and 24; the data end at 26 and the size rounds up to 32: 16 bytes of padding for 16 of data. Sorted (double, int32, int16, two chars): 16 bytes, no padding.

Exercise 6.2 ★

A pool of 50 000 orders of 64 bytes: how much memory, and how many 4 KiB pages must be pre-faulted?

Solution

Solution of Exercise 6.2.

$50\,000 \times 64 = 3\,200\,000$ bytes, about 3.05 MiB: 782 pages of 4 KiB (two huge pages).

Exercise 6.3 ★

At the measured cost per page, how long does touching a fresh 512 MiB buffer take at start-up, and what would it cost if it happened on the hot path instead, a page at a time?

Solution

Solution of Exercise 6.3.

512 MiB is 131 072 pages; at about $1.3\,\text{µ}\mathrm{s}$ each, some 0.17 seconds at start-up, harmless. On the hot path it is $1.3\,\text{µ}\mathrm{s}$ added to whichever message first touches each page, 131 072 times, at random moments.

Exercise 6.4 ★★

Which of these allocate with the GNU standard library: std::string s("AAPL"); std::string s("CLIENT-ORDER-ID-42"); std::vector<int> v; v.reserve(0); std::vector<int> v(1)?

Solution

Solution of Exercise 6.4.

"AAPL" fits the 15-character inline buffer: no allocation. The 18-character identifier allocates. reserve(0) does not allocate. v(1) allocates storage for one element.

Exercise 6.5 ★★

The draft handler allocates nine times per message. Which three changes remove the most allocations, and how many does each remove?

Solution

Solution of Exercise 6.5.

Replacing the std::function with a direct call or a template removes three (the lambda’s copy of the fills and the function’s heap copy of the lambda with its capture); a fixed vector of fills removes three; a fixed table instead of the map removes two. Together eight; the fixed identifier removes the last.

Exercise 6.6 ★★

Read Figure 6.2: at the median the heap is almost as fast as the pool. Why use a pool at all?

Solution

Solution of Exercise 6.6.

For the tail and for control. The heap’s median hides its rare slow paths (consolidation, system calls, faults on new pages); a pool has none, its slots are contiguous and pre-faulted, it refuses rather than grows, and its capacity is a number the team chose and monitors.

Exercise 6.7 ★★★

Coding. Give firm::arena::Pool a capacity check that records the high-water mark of live objects, run the churn benchmark with it, and propose a sizing rule for a pool whose peak is measured over a year of busy days.

Solution

Solution of Exercise 6.7.

Record the maximum of live() after each create. The churn benchmark’s high-water mark is its 10 000 live orders by construction. A sizing rule: take the year’s measured peak, multiply by a safety factor for days worse than any seen (1.5 to 2), round up to a power of two, and alarm when live objects pass a fraction (say 80%) of it.

Exercise 6.8 ★★★

Find the flaw. “Our handler allocates nothing: we checked it with a test that sends the same message, symbol ESZ6 and client id A1, a million times.”

Solution

Solution of Exercise 6.8.

Both identifiers are short enough for the inline buffer, and the same message makes the same map key every time, so no new node is ever created: the test cannot see the allocations of long identifiers and new keys. Test with production-shaped messages (long identifiers, new keys, many fills) and assert the allocation count after warm-up.

6.8 Problem: Four Hundred Microseconds, Once a Minute

Problem 6.1

Weekend problem — a handler that allocated

A strategy’s handler takes about $2\,\text{µ}\mathrm{s}$ a message, except once or twice a minute when it takes several hundred. The team suspects memory. The handler is the draft of Listing 6.1, fed 50 000 messages a second.

Part I — Counting.

1. How many allocations a second does the draft make?
2. List the nine allocations of one message and the line that makes each.
3. Which of them would disappear with an identifier of 15 characters or fewer?
4. Why does the count not depend on how many fills a message has, beyond three?

Part II — The costs.

5. From Figure 6.2, what does a pair of heap operations cost at the median?
6. How much time a second do the draft’s allocations cost at that median?
7. What does a page fault cost, and how many would put a message at several hundred microseconds?
8. Name three events inside the allocator that are rare but slow.

Part III — The rewrite.

9. What replaces each allocation in the fixed handler?
10. What capacities did the rewrite choose, and what happens when one is exceeded?
11. Why must the fixed handler’s storage be touched at start-up, and by which thread?
12. What does the rewrite’s linear search over 64 entries cost, and when would it need a hash table instead?

Part IV — The verdict.

13. State the named result: allocations per message before and after the rewrite, and the cost of a page fault against a pre-faulted write on this laptop.
14. How does the test keep the result from regressing?
15. What else, besides allocation, can make one message in a minute slow?
16. How would you show which cause it was on the production host?
17. Why is “refuse when full” acceptable on the hot path, and “allocate when full” not?
18. Where does the Rust twin enforce the same rule?
19. What should the pool’s size be if the peak of live orders in a year was 38 000?
20. In one sentence: what is the memory rule of a hot path?

Solution

Solution of Problem 6.1.

1. $9 \times 50\,000 = 450\,000$ allocations a second.
2. The long identifier’s string (1); the vector of fills growing to one, two and four elements (3); the map’s new node and its copy of the key (2); the lambda’s copy of the fills (1); std::function’s heap storage for the lambda and the copy of its captures (2).
3. The identifier’s string and the map key’s copy: two.
4. The vector’s capacity doubles, so fills four to eight add one allocation, not four; beyond three the count grows only logarithmically.
5. About $25\,\mathrm{n}\mathrm{s}$ (a destroy and a create) on the committed measurement.
6. Nine pairs at about $27\,\mathrm{n}\mathrm{s}$: $243\,\mathrm{n}\mathrm{s}$ a message, some 12 milliseconds a second, about 1% of the thread.
7. About $1.3\,\text{µ}\mathrm{s}$; some three hundred faults would make $400\,\text{µ}\mathrm{s}$.
8. Consolidating fragmented free blocks; growing or trimming the heap with a system call; mapping a large block directly, zeroed by the kernel; faulting in new pages.
9. A fixed string for the identifier, a fixed vector of fills, a fixed table of entries, a direct computation instead of the callback.
10. Identifiers of 24 characters, eight fills, 64 entries; when exceeded, the handler refuses (the entry is not created) and the condition must be counted and alarmed.
11. So that its pages are faulted in, and on the right node, before trading starts: by the thread that uses it, after pinning (chapter 4).
12. 64 comparisons of short strings, some tens of nanoseconds; with thousands of entries it needs an open-addressing hash table (chapter 19).
13. Named result. Nine allocations per message before, none after; on this laptop a page fault costs about $1.3\,\text{µ}\mathrm{s}$, forty times a write to a page already present.
14. It replaces operator new with a counter and asserts zero allocations per message after warm-up; a change that allocates fails the build.
15. Interrupts and scheduling (chapter 13), cold caches after a quiet period, a lock held by another thread, a logging call on the hot path.
16. Timestamp each stage of the slow message and correlate the slow ones with the allocator’s statistics, the minor-fault counter (getrusage) and the scheduler’s context switches for the thread.
17. Refusing is a decision with a bounded cost and an alarm; allocating is an unbounded cost at an unknown moment.
18. In the test binary’s counting global allocator (firm_arena::CountingAlloc), and in the pool’s API, which returns None rather than growing.
19. About 57 000 with a factor of 1.5, rounded up to 65 536, with an alarm at 80%.
20. Decide every byte the hot path will use before trading starts, touch it, and never ask the heap again.

6.9 Interview questions

Interview question 6.1 ★ developer

Why can reordering the fields of a structure make a program faster?

Solution

Solution of Interview question 6.1.

Padding shrinks, more objects fit per cache line, and the fields read together share a line: fewer misses per operation.

What the interviewer is looking for: alignment rules and cache lines.

Interview question 6.2 ★★ developer

Why do low-latency systems avoid heap allocation on the hot path, if malloc takes 20 nanoseconds?

Solution

Solution of Interview question 6.2.

The median hides the slow paths: consolidation, system calls to grow or trim the heap, zeroed pages from the kernel, faults on new pages, and locks shared with other threads; their timing is not under the program’s control.

What the interviewer is looking for: tails and determinism rather than the average cost.

Interview question 6.3 ★★ developer

Implement an object pool for a fixed-size type. What happens when it is empty?

Solution

Solution of Interview question 6.3.

An array of slots, each a union of the object’s storage and a next pointer; a head pointer to the first free slot; create pops and placement-constructs, destroy calls the destructor and pushes. When empty, return null and let the caller refuse the work and raise an alarm; never fall back to the heap on the hot path.

What the interviewer is looking for: an intrusive free list and a deliberate exhaustion policy.

Interview question 6.4 ★★ developer

What is the small-string optimisation, and why can it hide allocations from a test?

Solution

Solution of Interview question 6.4.

Short strings are stored inside the object (15 characters in the GNU library), long ones on the heap, so allocation depends on the data: tests with short identifiers never allocate, production with long ones does.

What the interviewer is looking for: data-dependent allocation.

Interview question 6.5 ★★ developer

What is a page fault, and how do you keep them off a hot path?

Solution

Solution of Interview question 6.5.

A trap to the kernel on touching a page not yet backed by memory; it allocates and zeroes a page (microseconds). Allocate everything at start-up, write every page (pre-fault), lock memory against paging (mlockall, chapter 13), and use huge pages.

What the interviewer is looking for: pre-faulting and locking.

Interview question 6.6 ★★★ developer

How would you prove, in continuous integration, that a component never allocates after start-up?

Solution

Solution of Interview question 6.6.

A test build that replaces the global allocation functions with counting ones (or a counting global allocator in Rust), drives the component with production-shaped data past its warm-up, and asserts that the count does not change; the test runs in continuous integration on every change.

What the interviewer is looking for: an automated assertion, with realistic data.