Low-Latency Software · Technology

3Memory Hierarchy and Caches

On this book’s laptop, reading one price level of an order book costs about a nanosecond when the level is in the core’s first-level cache, three or four nanoseconds when it is in the second level, and about 150 nanoseconds when it has to come from memory: a factor of more than a hundred for the same instruction. Chapter 1’s toy book, built on balanced trees whose nodes are scattered across the heap, spent most of its time waiting for such loads. Most of the difference between a fast order book and a slow one is not the algorithm but where its bytes live, and this chapter is about that: the levels of the hierarchy and their costs, what happens when two cores share a line, how virtual addresses are translated, and what the hardware does to hide all of it.

3.1 Cache levels, lines and associativity

Definition 3.1 (Cache line, set-associative cache)

Memory moves between the levels of the hierarchy in fixed blocks called cache lines, 64 bytes on current x86 processors. In a set-associative cache with $S$ sets of $W$ ways, a line can be stored only in the set given by bits of its address, in any of that set’s $W$ slots; the cache holds $S \cdot W$ lines.

Definition 3.2 (Cache miss, working set)

A cache miss is an access to a line that is not in a given level, which must then be fetched from the next level down. The working set of a piece of code over an interval is the set of lines it touches in that interval; the level whose capacity it fits in sets its speed.

An address splits into three fields (Figure 3.1): the low 6 bits are the offset within the 64-byte line; the next $\log_2 S$ bits choose the set; the rest, the tag, identify the line among those that map to the set. Two consequences for data layout. A structure that straddles two lines costs two misses where one would do. And addresses that differ by a multiple of $S \times 64$ bytes compete for the same $W$ slots: a program that walks several arrays whose strides are that multiple (a power of two, typically 4 KiB) can miss in a cache that is mostly empty.

Figure 3.1. How an address selects its place in a set-associative cache. A 48 KiB, 12-way cache of 64-byte lines has 64 sets; bits 6 to 11 of the address choose the set, so addresses 4 KiB apart share a set.

Example 3.3 (Geometry of a first-level cache)

A 48 KiB, 12-way cache with 64-byte lines has $48 \times 1024 / (64 \times 12) = 64$ sets. The set index is bits 6 to 11; addresses that are equal modulo $64 \times 64 = 4\,096$ bytes fall into the same set. Thirteen hot structures placed at the same offset of thirteen 4 KiB pages cannot all stay in this cache, although together they occupy 832 bytes.

Figure 3.2 measures the hierarchy with a pointer chase: a buffer of $n$ slots, one per cache line, laid out as a single random cycle, each slot holding the address of the next. Each load’s address is the previous load’s result, so no two loads overlap and the time per step is the latency of the level the buffer fits in. The staircase shows the first level up to 48 KiB at about $1.1\,\mathrm{n}\mathrm{s}$ (five cycles), the second level up to about a megabyte and a half at about $3.5\,\mathrm{n}\mathrm{s}$ , the third level from about three to eight megabytes at 15 to $23\,\mathrm{n}\mathrm{s}$ , close to its published latency of 75 cycles or more (about $20\,\mathrm{n}\mathrm{s}$ ), and memory from about twelve megabytes on, at 100 to $175\,\mathrm{n}\mathrm{s}$ : the low-power memory of a laptop, which a published measurement puts at 150 to 175 nanoseconds for this processor. The third level is 24 MiB, shared by all the cores; a random chase through a virtual machine’s pages starts to miss in it well before its nominal size.

The memory staircase: time per dependent load through a buffer of one slot per cache line, against the buffer’s size. In address order the prefetcher hides almost all of it. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores, pinned to one CPU, the machine otherwise idle. Data: bench_mem.py. — **Figure 3.2.** The memory staircase: time per dependent load through a buffer of one slot per cache line, against the buffer’s size. In address order the prefetcher hides almost all of it. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores, pinned to one CPU, the machine otherwise idle. Data: `bench_mem.py`.

3.2 Coherence and false sharing

Definition 3.4 (Cache coherence)

Cache coherence is the protocol by which the private caches of several cores keep one view of each line: before a core writes a line it must obtain the line in an exclusive state, invalidating every other core’s copy; a later read by another core must fetch the modified line from the writer. In the MESI family each line in each cache is Modified, Exclusive, Shared or Invalid.

Definition 3.5 (False sharing)

False sharing occurs when two cores repeatedly write different variables that lie in the same cache line: neither shares data with the other, yet every write invalidates the other core’s copy and the line travels between them.

A market-data thread that updates a sequence counter and a strategy thread that updates its own statistics, placed next to each other in one structure, pay the price of the line moving between cores on every update, without any data being shared. Figure 3.3 measures it: one thread incrementing a counter pays about $4\,\mathrm{n}\mathrm{s}$ per atomic increment; two threads each incrementing their own counter on separate lines pay about the same; two threads whose counters share a line pay about five times as much. The cure is layout: give each independently written variable its own line (CachePadded, below), and keep variables written by one thread together and away from those written by another.

False sharing: two threads, pinned to two CPUs, each incrementing its own atomic counter 20 million times, with the counters on one cache line or on two. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_mem.py. — **Figure 3.3.** False sharing: two threads, pinned to two CPUs, each incrementing its own atomic counter 20 million times, with the counters on one cache line or on two. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_mem.py`.

3.3 Translation buffers and huge pages

Definition 3.6 (Translation lookaside buffer, huge page)

Programs use virtual addresses, translated to physical addresses through page tables. The translation lookaside buffer (TLB) caches recent translations; a TLB miss makes the processor walk the page tables, several dependent memory accesses. A huge page is a page larger than the base 4 KiB (2 MiB or 1 GiB on x86-64), which one TLB entry covers.

The TLB’s reach is its number of entries times the page size. A second-level TLB of 2 048 entries covers 8 MiB of 4 KiB pages and 4 GiB of 2 MiB pages; an order book, a symbol table and a few rings of a trading process can easily exceed the first and never the second. Linux offers huge pages two ways: reserved pages from a pool, and transparent huge pages, which the kernel assembles on its own; in the default madvise mode it does so only for regions the program has marked with madvise(MADV_HUGEPAGE). The kernel’s documentation notes that the gain is larger under virtualisation, where each walk goes through two levels of page tables, the guest’s and the hypervisor’s. On this laptop, which is virtualised, a random chase over 256 MiB costs about $180\,\mathrm{n}\mathrm{s}$ a step with 4 KiB pages and about $150\,\mathrm{n}\mathrm{s}$ with huge pages (measured_huge.csv): the difference is the page walk.

3.4 Prefetching and access patterns

Definition 3.7 (Hardware prefetching)

Hardware prefetching is the processor’s fetching of lines before they are requested, by recognising patterns in recent misses: consecutive lines, constant strides.

The dashed curve of Figure 3.2 is the same chase with the slots visited in address order: the prefetcher recognises the stream and the loads cost under $2\,\mathrm{n}\mathrm{s}$ until the buffer leaves the second level, and four or five nanoseconds from memory, some thirty times less than the random chase. Nothing changed but the order. The practical rules follow: store what the hot path reads together in contiguous arrays, not in nodes linked by pointers; iterate in address order; keep the hot data of a message (price, quantity, side) in the first line of its structure; and when the access is truly random, as an order-id lookup is, make the table small enough to stay in cache (chapter 19).

3.5 Tutorial: measuring the staircase

Goal. Measure the latency of each level of the hierarchy, the cost of false sharing and the effect of huge pages. End state: Figures 3.2 and 3.3 and the huge-page table.

A ring of pointers. Shuffle the slot order with Fisher–Yates, then store in each slot the address of the next: a single cycle through every line, which no prefetcher can predict.

// Lay out `n` slots of `stride` bytes as one random cycle: slot i holds the address of the next slot.
// With random=false the cycle visits the slots in address order (what a prefetcher can follow).
inline void chase_ring(std::uint8_t* base, std::size_t n, std::size_t stride, bool random, std::uint64_t seed = 1) {
    std::vector<std::size_t> order(n);
    for (std::size_t i = 0; i < n; ++i) order[i] = i;
    if (random) {
        std::mt19937_64 rng(seed);
        for (std::size_t i = n - 1; i > 0; --i) std::swap(order[i], order[rng() % (i + 1)]);  // Fisher-Yates
    }
    for (std::size_t i = 0; i < n; ++i) {
        void* next = base + order[(i + 1) % n] * stride;
        std::memcpy(base + order[i] * stride, &next, sizeof next);
    }
}

// Follow the ring for `steps` loads; each load's address is the previous load's value.
inline const void* chase(const void* start, std::size_t steps) {
    const void* p = start;
    for (std::size_t i = 0; i < steps; ++i) p = *static_cast<const void* const*>(p);
    return p;
}

Listing 3.1. Building and following a pointer-chase ring. code/firm/memkit/cpp/firm_memkit.hpp

Huge pages on request. Buffer maps anonymous memory, asks for transparent huge pages with madvise, and writes every page once so that no page fault happens later on the hot path (chapter 6).


class Buffer {
public:
    Buffer(std::size_t bytes, bool huge) : size_(round_up(bytes, huge ? (2u << 20) : 4096u)) {
        void* p = mmap(nullptr, size_, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (p == MAP_FAILED) throw std::bad_alloc();
        data_ = static_cast<std::uint8_t*>(p);
        huge_ = huge && madvise(data_, size_, MADV_HUGEPAGE) == 0;
        if (!huge) madvise(data_, size_, MADV_NOHUGEPAGE);
        std::memset(data_, 0, size_);  // pre-fault every page now, not on the hot path

Listing 3.2. A buffer with huge pages and pre-faulting. code/firm/memkit/cpp/firm_memkit.hpp

A counter per line. CachePadded aligns its value on a line of its own; two threads increment their counters with relaxed atomic additions, once padded and once packed in one structure.
```
template <class T>
struct alignas(kLine) CachePadded {
    T value{};
    char pad[kLine - (sizeof(T) % kLine == 0 ? kLine : sizeof(T) % kLine)];
};
```
Listing 3.3. A value alone on its cache line. code/firm/memkit/cpp/firm_memkit.hpp
Run python bench_mem.py (about a minute): the staircase with 4 KiB and huge pages and in address order, the huge-page comparison over 256 MiB, and the false-sharing test on CPUs 2 and 4.

What to change next. Use a stride of 4 096 bytes instead of 64 in the chase and find the working set at which the first level fails, far earlier than 48 KiB; pin the two false-sharing threads to the same CPU and explain the result.

3.6 Build: memory placement tools

Purpose. The layout primitives every later component uses: counters and sequence numbers written by different threads (rings, chapter 12; the feed handler’s statistics, chapter 18) and buffers that must not fault or miss the TLB on the hot path (books, journals).

Interface. C++20 firm::memkit: kLine, CachePadded<T>, Buffer(bytes, huge) with data(), size(), huge_requested(), chase_ring(base, n, stride, random, seed), chase(start, steps). Rust firm_memkit: CachePadded<T>, chase_ring, chase on a byte buffer.

Rules. Padded values occupy whole lines; buffers are page-aligned, rounded up to the page size requested, and pre-faulted at construction; a failed huge-page request falls back to base pages and says so.

Acceptance tests. code/firm/memkit/: sizes and alignments of padded values, neighbouring padded values one line apart, a 2 MiB-rounded huge buffer, and the ring as a single cycle in both orders, in C++ and Rust.

Stretch. Report the huge pages actually obtained, from /proc/self/smaps; allocate from reserved 1 GiB pages when the host has them.

Sources and further reading

U. Drepper, “What every programmer should know about memory”, LWN.net, 2007.
M. Papamarcos and J. Patel, “A low-overhead coherence solution for multiprocessors with private cache memories”, ISCA 1984.
Linux kernel documentation, “Transparent hugepage support”.
Chips and Cheese, “Intel’s Redwood Cove: baby steps are still steps” (2024) and “Update on Meteor Lake DRAM latency measurements” (2024).

3.7 Exercises

Exercise 3.1 ★

In a cache with 64-byte lines and 64 sets, which set does address 0x7f3a12345e48 map to, and what is its offset within the line?

Solution

Solution of Exercise 3.1.

The offset is the low 6 bits: $\texttt{0x48} \bmod 64 = 8$ . The set is bits 6 to 11: $\lfloor\texttt{0x5e48}/64\rfloor \bmod 64 = 377 \bmod 64 = 57$ .

Exercise 3.2 ★

A 2 MiB, 16-way cache has 64-byte lines. How many sets does it have, and at what stride do addresses alias to the same set?

Solution

Solution of Exercise 3.2.

$2\,097\,152 / (64 \times 16) = 2\,048$ sets; addresses $2\,048 \times 64 = 131\,072$ bytes (128 KiB) apart share a set.

Exercise 3.3 ★

A process uses 600 MiB of hot data. How many TLB entries does it need with 4 KiB pages, and with 2 MiB pages?

Solution

Solution of Exercise 3.3.

$600~\text{MiB}/4~\text{KiB} = 153\,600$ entries with base pages, far beyond any TLB; 300 with 2 MiB pages.

Exercise 3.4 ★★

A message structure holds an 8-byte sequence number written by the feed thread and a 4-byte counter written by the strategy thread, next to each other. What happens, and how do you fix it at a cost of how many bytes?

Solution

Solution of Exercise 3.4.

False sharing: every write by one thread invalidates the other’s copy of the line, and both pay a transfer between cores on most writes (about five times the cost of an uncontended atomic increment in Figure 3.3). Put each field on its own line: 128 bytes instead of 16.

Exercise 3.5 ★★

From Figure 3.2, how long does a book update that makes four dependent random loads take when its data fit in the second level, and when they come from memory?

Solution

Solution of Exercise 3.5.

About $4 \times 3.5 = 14\,\mathrm{n}\mathrm{s}$ from the second level and $4 \times 150 = 600\,\mathrm{n}\mathrm{s}$ from memory: the dependent loads cannot overlap.

Exercise 3.6 ★★

Why does the address-order chase stay fast far beyond the second level, while the random chase does not? What does that say about linked lists and balanced trees on a hot path?

Solution

Solution of Exercise 3.6.

In address order the next line is predictable, so the prefetcher fetches it before it is needed and the loads overlap; in random order each address is known only when the previous load returns. Pointer-linked structures (lists, trees, node-based maps) put their nodes wherever the allocator did, so traversals are random chases: on a hot path, prefer contiguous arrays.

Exercise 3.7 ★★★

Coding. Rewrite the Rust chase of firm_memkit with raw pointers and unsafe, as the C++ does, and compare both with the index version on a 64 MiB ring. Is the bounds check visible in the time per step? Why or why not?

Solution

Solution of Exercise 3.7.

The bounds check is a comparison and a branch that is always predicted not taken, independent of the load’s result, so the core executes it while the dependent load it guards is outstanding. On a 64 MiB ring each step waits for memory (about $150\,\mathrm{n}\mathrm{s}$ here); a check of a cycle or two cannot show. It would show on a ring that fits the first level, where the load itself takes five cycles.

Exercise 3.8 ★★★

Find the flaw. “We benchmarked our order-book update at $20\,\mathrm{n}\mathrm{s}$ by applying the same add and delete messages to one instrument ten million times in a loop.”

Solution

Solution of Exercise 3.8.

One instrument and the same few messages keep the whole working set in the first level and the predictor trained: the $20\,\mathrm{n}\mathrm{s}$ is the first-level figure. In production the updates hit many instruments and many price levels, most of them out of the first level and some out of the second. Replay a recorded day across all instruments and report percentiles.

3.8 Problem: The Staircase

Problem 3.1

Weekend problem — how many books fit

A market-making process quotes a set of instruments. For each it keeps a dense price ladder of 256 levels per side, each level 32 bytes (price, quantity, order count, flags), plus 4 KiB of per-instrument state. The team wants every instrument’s hot data in the second-level cache of the core that runs the strategy.

Part I — The measurement.

Read the latency of the first level, the second level and memory from Figure 3.2.
Where are the steps, and what capacities do they suggest?
Why does the third-level step end at about eight megabytes, not at 24 MiB?
What sets the height of the step between the second level and memory?

Part II — The layout.

How many bytes does one instrument’s hot data occupy?
How many cache lines?
If three quarters of a 2 MiB second level is available to the books, how many instruments fit?
How many fit in a 48 KiB first level, at most?

Part III — When they do not fit.

The desk wants 300 instruments. What fraction of updates will miss the second level if instruments are updated uniformly at random, and the second level holds the most recent ones?
If an update makes three dependent loads, what is its average memory time with that miss rate, taking the second-level and memory latencies of Part I?
What would huge pages change, and why especially here?
Name two layout changes that shrink the hot data.

Part IV — The verdict.

State the named result: the latency of each level on this laptop and the number of instruments whose book fits in the second level.
Why is 32 bytes a good size for a level, and 48 a bad one?
Should the ladder store levels as structures of four fields or four arrays of one field? When does each win?
What does the chase measure that a sequential benchmark hides?
Why must the benchmark visit every line once per lap?
What is the cost of one false-shared counter in the book, per update?
How would you confirm on the production host that the books stay in the second level?
In one sentence: what decides the speed of an order book?

Solution

Solution of Problem 3.1.

About $1.1\,\mathrm{n}\mathrm{s}$ , $3.5\,\mathrm{n}\mathrm{s}$ and 100 to $175\,\mathrm{n}\mathrm{s}$ .
At about 48 KiB, at one and a half to two megabytes, and between eight and twelve megabytes: a 48 KiB first level, a second level of about 2 MiB, and a third level that the chase uses up to about eight megabytes.
The 24 MiB are shared by all the cores and hold their data too, and a random chase through the virtual machine’s pages maps lines to sets unevenly, so some sets overflow long before the whole cache is full.
The third level’s latency, 75 cycles or more (about $20\,\mathrm{n}\mathrm{s}$ ); measured, 15 to $23\,\mathrm{n}\mathrm{s}$ .
$2 \times 256 \times 32 + 4\,096 = 20\,480$ bytes.
320 lines.
$0.75 \times 2\,097\,152 / 20\,480 = 76.8$ : 76 instruments.
Two, at most, with nothing else in the first level.
$1 - 76/300 = 74.7\%$ .
$3 \times (0.253 \times 3.5 + 0.747 \times 150) \approx 339\,\mathrm{n}\mathrm{s}$ .
The 300 books span about 6 MB, 1 500 base pages, more than the first-level TLB covers; with 2 MiB pages three entries suffice. The gain is larger on a virtualised host, where each walk is two-dimensional.
Store levels closer to the touch only (a narrower ladder, chapter 19) and use smaller fields (32-bit prices and quantities in ticks and lots); keep cold state in another structure.
Named result. On this laptop: about $1.1\,\mathrm{n}\mathrm{s}$ from the first level, $3.5\,\mathrm{n}\mathrm{s}$ from the second, 100 to $175\,\mathrm{n}\mathrm{s}$ from memory; 76 instruments’ books fit in three quarters of a 2 MiB second level.
32 divides 64, so two levels share a line and none straddles two; with 48 bytes half the levels straddle a line boundary and cost two misses.
Four arrays of one field (structure of arrays) when a scan reads one field over many levels (a depth sum); one structure when an update reads all fields of one level.
The latency of each access alone, without prefetching or overlap, which a sequential benchmark hides.
So that the time per step is set by the buffer’s size and not by a shorter cycle that fits a smaller level.
Several times an uncontended update, some tens of nanoseconds, each time the other thread has written it.
Measure the update’s latency percentiles under a replay against the second-level latency, and, where hardware counters are available, count second-level misses.
Where its bytes are: how many dependent loads an update makes and which level each is served from.

3.9 Interview questions

Interview question 3.1 ★ developer

Why is iterating over a std::vector faster than over a std::list of the same elements?

Solution

Solution of Interview question 3.1.

A vector is contiguous: its elements share cache lines and the prefetcher streams them. A list’s nodes are scattered, one dependent load each, each a potential cache miss.

What the interviewer is looking for: contiguity, prefetching, and dependent loads.

Interview question 3.2 ★★ developer

What is false sharing? How would you detect it and fix it?

Solution

Solution of Interview question 3.2.

Two threads writing different variables in the same cache line, so that the line bounces between their cores. Detect it with a profiler’s cache-contention report (perf c2c) or by timing with padding; fix it by aligning independently written variables to separate lines.

What the interviewer is looking for: the coherence mechanism and padding or regrouping by writer.

Interview question 3.3 ★★ developer

What is a TLB, and why do trading systems use huge pages?

Solution

Solution of Interview question 3.3.

The cache of virtual-to-physical translations; a miss costs a page walk of several dependent loads, more under virtualisation. Huge pages let one entry cover 2 MiB or 1 GiB, so the hot data’s translations stay cached.

What the interviewer is looking for: reach = entries times page size, and the page walk.

Interview question 3.4 ★★ developer

How would you measure the latency of each level of a machine’s cache hierarchy?

Solution

Solution of Interview question 3.4.

A pointer chase: a random single cycle through a buffer, one slot per line, timing dependent loads for sizes from a few kilobytes to beyond the last level; the time per step against size is a staircase. Pin the thread, use huge pages to separate TLB effects, repeat.

What the interviewer is looking for: dependent random loads defeating prefetching and overlap.

Interview question 3.5 ★★ developer

Two arrays of 4 096 doubles are processed element by element together and the loop is unexpectedly slow. What might be happening?

Solution

Solution of Interview question 3.5.

Arrays of 32 KiB each, allocated page-aligned, so element $i$ of both arrays maps to the same cache set (4 KiB aliasing): with more such streams than ways, lines evict each other. Offset one array by a line or two.

What the interviewer is looking for: set conflicts from power-of-two strides.

Interview question 3.6 ★★★ developer

Design the memory layout of an order-id to order lookup for a feed with a million live orders, for the lowest p99.

Solution

Solution of Interview question 3.6.

An open-addressing hash table with linear probing, keys and values in one flat array of small slots (order id and a 32-bit index into an order pool), sized to a power of two with a low load factor, backed by huge pages and pre-faulted; one expected cache miss per lookup, no allocation, no pointer chasing. Chapter 19 builds it.

What the interviewer is looking for: flat storage, one miss per lookup, no allocation on insert.

Terms defined in this chapter

See all 2333 terms in the glossary