Memory Hierarchy, Locality, and NUMA

A load instruction names an address, not a delivery time. The data might already be in a register, arrive from a nearby cache, require an address translation and a DRAM access, cross a socket interconnect, or trigger a page fault whose resolution is measured on an entirely different scale. The same source expression can therefore be cheap, delayed, or capable of stalling many otherwise idle execution slots.

A back-end-bound lookup whose pointer-heavy representation reduces instructions but increases cycles moves CPU diagnosis to its memory side. The decision is architectural: should the team change layout, access order, page policy, thread/data placement, ownership, or capacity before touching the computation again?

Cycles per correct operation that rise with cache or translation evidence, a throughput plateau while cores remain available, placement-sensitive performance, and tail latency during memory pressure all demand the same separation: dependent-access latency versus streaming bandwidth, cache and translation capacity, CPU versus page placement, and useful movement versus false sharing, reclaim, or copying.

Follow the bytes, not the variable name

The useful model is a hierarchy of capacity, access cost, and concurrency. Smaller structures close to a core are generally faster but cannot hold the whole working set. Larger structures are farther away, shared more broadly, and reached through more machinery.

These are orders of magnitude for reasoning, not a processor specification. The file-backed model for this chapter uses 4, 12, 42, 180, and 285 cycles as illustrative L1, L2, LLC, local-DRAM, and remote-DRAM costs. It never presents them as observations. Obtain actual topology and event definitions for the deployed machine before using a threshold.

The hierarchy is not a serial toll booth through which every load visibly passes. Hardware checks caches concurrently where possible, overlaps misses, speculates, prefetches, and holds many operations in flight. A single cache miss may disappear behind independent work. A chain of dependent misses cannot. This distinction is why “cache-miss count” alone does not predict elapsed time.

Cache lines turn layout into traffic

Caches transfer fixed-size lines, not language objects. If a 64-byte line contains four adjacent records needed by the next computation, one fill supplies useful future work. If it contains one 8-byte pointer and unrelated allocator metadata, most transferred bytes are unused. The exact line size is platform-specific; use 64 bytes here only because the teaching fixture declares it.

Spatial locality means nearby addresses are used close together. Temporal locality means recently used data is used again. Reuse distance describes the amount of distinct intervening data touched before an item is reused. Reuse survives a cache when the competing footprint and mapping behavior let the item remain resident; elapsed time alone is not the governing variable.

Layout changes both capacity and traffic. An array of compact route records can eliminate pointers, reduce allocator metadata, pack more keys per line, and let the prefetcher see a regular stream. It can also make updates expensive, move larger blocks, or complicate stable references. A linked tree supports local mutation and stable nodes but pays for allocation, pointer loads, low line utilization, and unpredictable traversal. Neither layout is universally superior.

The modeled Mercury table contains one million records:

The packed representation fits the declared cache budget while the pointer representation does not. That is a hypothesis about a phase change, not proof that every lookup hits in cache. Conflict, concurrency, other tenants, instruction/data sharing, and request mix still matter. The decisive experiment holds keys, outputs, request order, and CPU placement fixed while changing representation; it measures cycles, cache/TLB evidence, bytes transferred, and correct lookup latency together.

Regular access gives hardware room to help

Hardware prefetchers infer patterns such as sequential or strided access and fetch likely future lines before demand reaches them. Software prefetch can express a prediction explicitly. Both trade bandwidth and cache capacity for latency hiding. A correct prefetch that arrives too late does nothing; one that arrives too early may be evicted; a wrong one consumes shared resources.

Pointer chasing is difficult because the next address does not exist until the current node arrives. Out-of-order execution can overlap several independent chains, but it cannot invent independence within one chain. Restructuring work across a batch of lookups can expose memory-level parallelism: advance lookup A, then B, then C while A waits. That raises in-flight work and may hurt per-item tail latency or cancellation cost, so the batch boundary and deadline remain part of the decision.

Traversal order matters even when the algorithm is unchanged. A row-major pass over row-major storage uses each fetched line; a column-wise pass over a wide matrix may touch one useful value per line. Sorting work by key or partition can improve locality while adding queueing and fairness risk. The global design must price both movement saved and waiting introduced.

Translation is another cache hierarchy

Programs use virtual addresses. The processor translates them to physical addresses through page tables, caching recent translations in translation lookaside buffers (TLBs). When a needed translation is absent, a page walk reads page-table entries; those reads themselves use the memory hierarchy. A data-cache-friendly loop can therefore stall on translation when it touches many pages with little reuse.

Larger pages let one translation cover more bytes and can reduce TLB pressure. They are not free acceleration. Larger allocation/fault work, internal fragmentation, compaction, promotion/demotion behavior, copy costs, and longer stalls can offset the translation gain. Linux Transparent Huge Pages can automatically use larger pages for eligible mappings, but policy and supported sizes vary; validate the actual mapping and fault behavior rather than inferring it from a global toggle.

Use a paired test:

1. Hold layout, workload, placement, and memory footprint constant.
2. Record data-cache and translation evidence supported by the processor.
3. Verify actual page sizes and residency, including warm-up and faults.
4. Compare cycles and latency per correct operation, not only TLB events.
5. Repeat under nominal, memory-pressure, and recovery states.

If huge pages reduce translation misses without moving the user objective, translation was measurable but not limiting. Keep the simpler policy unless the capacity or cost effect still justifies it.

NUMA makes “in memory” an incomplete location

In a non-uniform memory access machine, CPUs and memory are grouped into nodes. A core reaches memory attached to its local node through a shorter path than memory attached to another node. Remote access is valid, but it consumes interconnect capacity and often adds latency. Shared last-level caches may also be partitioned by topology rather than acting as one uniform pool.

On Linux, memory policy determines the nodes from which pages are allocated. Default local allocation, preferred, bind, interleave, and other modes express different placement behavior. Policy applies at task, virtual-memory-area, or shared-object scopes with important inheritance and fallback rules. Crucially, changing policy does not necessarily move pages already faulted: first-touch placement and the time policy is installed matter.

A valid NUMA experiment controls two variables separately:

CPU placement:  socket 0  |  socket 1  |  migrating
page placement: node 0    |  node 1    |  interleaved

Four pinned combinations distinguish local from remote access. A fifth production-like run restores scheduler movement. Record node-specific memory bandwidth, remote/local access evidence where supported, cycles and latency per correct operation, page location, migrations, and interconnect saturation. “Pinning made it faster” is ambiguous if pinning changed both cache warmth and page locality.

Binding everything to one node can fix a microbenchmark while creating imbalance or allocation failure under pressure. Interleaving can improve aggregate bandwidth for streaming work while making every thread partly remote. Local allocation preserves affinity only if thread ownership and page ownership remain aligned. Choose policy from access ownership and failure behavior, then validate it during restart, resharding, failover, and backlog drain—not just after a clean warm-up.

False sharing moves ownership without sharing data

Coherence keeps cached copies consistent at cache-line granularity. Two cores can update different variables and still contend if those variables occupy the same writable line. Each write requests ownership, invalidating the other’s copy. The source code shows private counters; the hardware sees one shared coherence unit.

time →       t0              t1              t2              t3
core 0       own line; A++   invalidated     own line; A++   invalidated
core 8       invalidated     own line; B++   invalidated     own line; B++
traffic      S0 → S1         S1 → S0         S0 → S1         S1 → S0

Padding or separating write-hot fields can stop the ping-pong, but padding every structure inflates the working set and may create new cache misses. Better options include per-owner counters with periodic reduction, sharding by writer, immutability, or changing the update frequency. Diagnose with scaling behavior and coherence/remote-hit evidence supported by the machine; do not label every multi-core regression “false sharing.” Locks, scheduler migration, memory bandwidth, and real shared data can produce similar curves.

Latency stalls and bandwidth saturation require different remedies

A latency-bound workload has too few independent misses to hide access delay. Pointer chains, serialized hash probes, and dependent index walks are common shapes. Improve locality, reduce chain depth, expose independent work, or move data closer.

A bandwidth-bound workload sustains enough concurrent traffic to fill a memory channel or interconnect. Additional workers do not add throughput because bytes, not cores, are the scarce resource. Reduce bytes transferred, improve line utilization, compress or recompute selectively, partition traffic across memory controllers, or accept the hardware ceiling.

The teaching packet transfers 256 bytes per lookup against a modeled 32 GiB/s socket budget:

ceiling = 32 GiB/s ÷ 256 B/lookup
        = 134,217,728 lookups/s

Simulated throughput rises from 42 million lookups/s at four workers to 119 million at twelve, then flattens at 126–127 million at sixteen and twenty-four workers. CPU headroom remains. The plateau reaches about 94.6% of the modeled bandwidth ceiling. More threads add queueing and interference; they cannot create memory bandwidth. Validate bytes per lookup and the actual channel/controller counters before accepting this explanation in production.

Copy avoidance is an ownership contract

Copies cost reads, writes, allocation, cache capacity, and sometimes translation or NUMA traffic. Eliminating a copy can improve a bandwidth-bound path, but “zero copy” is a boundary claim, not an end-to-end fact. A kernel may map pages while a codec copies; a network API may reference a buffer while encryption creates another representation.

Avoidance also transfers obligations:

• the producer cannot mutate or recycle a buffer while a consumer still owns it;
• cancellation and partial writes need explicit lifetime rules;
• shared buffers can pin memory and defeat reclaim;
• scatter/gather increases descriptor and downstream complexity;
• cross-node ownership can avoid one copy but preserve remote access on every read;
• security boundaries may require validation, redaction, or isolation that copying supplied.

Count bytes moved per correct completion at each boundary. Prefer an ownership design that makes lifetime and locality explicit over an API advertised as zero-copy without a path inventory.

Pressure changes the path

Working sets compete with page cache, runtime heaps, kernel objects, telemetry buffers, neighboring workloads, and recovery work. Under pressure, allocation may enter reclaim, dirty pages may require writeback, cached pages disappear, huge-page promotion may fail, and a page fault may reach storage. Swap can preserve liveness while making a latency objective impossible. An out-of-memory policy can terminate the process, another workload, or an entire constrained group depending on deployment controls.

Measure resident and active working sets by operating state, not only allocated bytes. Track major/minor faults, reclaim and compaction activity, swap I/O, dirty/writeback pressure, cgroup or container events, OOM outcomes, and latency distributions. Treat a cold restart and post-failover backlog as first-class states: both can fault pages, rebuild caches, and contend with foreground traffic.

A robust design bounds memory, makes eviction/reload cost visible, preserves admission control during reclaim, and has an explicit OOM/restart policy. It does not assume memory pressure is a slow capacity trend; a large fan-out, query, compaction, or telemetry burst can make it a request-scale event.

Observable signatures form a ladder, not a verdict

Memory diagnosis becomes credible when evidence agrees across layers. Begin with the user or capacity symptom, then move downward only far enough to separate competing mechanisms.

No single row establishes cause. Cache misses can rise because a request does more useful work. Remote accesses can rise because the scheduler moved threads after a failover. Memory bandwidth can look full because speculative or prefetched bytes are useless. Always preserve instructions, cycles, elapsed time, transferred bytes, and correct output together.

The order of experiments matters. First reproduce the symptom with the smallest representative population. Next pin only to make placement observable, not to declare a deployment solution. Change one boundary—layout, traversal, page policy, CPU placement, or memory placement—and predict which counters and end-to-end measure must move. Finally restore production scheduling, contention, skew, overload, and recovery. A mechanism isolated under pinning still needs a design that survives unpinned operation.

Workload phases can invalidate a single layout win

Mercury’s packed lookup table improves read locality, but production also refreshes routes. Suppose the pointer form updates one node in place while the packed form rebuilds and publishes a 23 MiB generation. The packed form may dominate for a read-heavy steady state and lose during frequent churn, memory pressure, or cross-socket publication.

Model at least three phases:

• steady reads: lookup frequency, key skew, cache reuse, and per-request deadline;
• refresh: bytes allocated and copied, writer CPU, temporary peak footprint, publication synchronization, and NUMA node of first touch;
• retirement/recovery: lifetime of old generations, stalled readers, reclamation, restart warming, and failover placement.

An immutable generation with atomic publication can avoid reader locks and false sharing, but delayed reclamation can retain several generations. Sharding generations by owner can preserve NUMA locality, but cross-shard queries may become remote or require merging. An in-place structure can minimize refresh bytes while creating coherence and synchronization traffic. The decision belongs to the entire lifecycle, not the hottest read loop.

For a rollout, record baseline and candidate by phase. Canary on one topology, force a refresh under nominal load, then repeat during a bounded recovery backlog. Abort if correct goodput, memory headroom, refresh time, remote fraction, or p99 crosses its declared bound. A locality improvement that consumes recovery reserve is not a durable improvement.

A locality decision record

Before changing layout or placement, write a short causal claim. Name the user objective and normalize cycles or time to one correct unit of work; this establishes whether memory is material to the path at all. Then classify the suspected loss as dependent-access latency or bandwidth pressure, using the dependency shape, available concurrency, bytes transferred, and plateau behavior.

Name the boundary you intend to change: cache residency, page size and translation, CPU-to-page placement, or reclaim state. Record the correctness obligations that must survive it—ownership, updates, ordering, cancellation, and recovery—and the cost likely to move elsewhere, such as write amplification, queueing, interconnect traffic, complexity, or cold-start work. Finish with a falsifier: one controlled layout, page, or placement change and the matched result that would make you abandon the explanation.

Run the companion model:

node examples/performance-engineering-system-design-handbook/part-02/memory-locality/run.mjs
node examples/performance-engineering-system-design-handbook/part-02/memory-locality/verify.mjs

Then perform two drills. First, redesign the pointer layout while preserving stable lookup results and update semantics; explain whether you choose packing, separate hot/cold fields, an index, or batched traversal. Second, read the worker sweep and specify the one measurement that would distinguish DRAM bandwidth from a contended lock that happens to plateau at the same worker count. Your answer must name the useful-work denominator and one result that would reject your hypothesis.

The decision rule is conditional: treat data layout and placement as architecture when working-set size or access pattern materially dominates instruction cost. Change the smallest boundary that removes the measured movement or wait, then revalidate scheduler behavior, pressure, overload, and recovery. The other side of placement is runnable work: how it reaches cores and how concurrency runtimes disturb or preserve locality.

Sources and evidence scope

• Linux kernel NUMA memory policy documentation defines policy scopes, modes, inheritance, fallback, and page-placement behavior. Exact platform distance and migration costs remain machine-specific.
• Linux Transparent Hugepage documentation describes supported mappings, policies, and promotion/demotion controls. It does not imply that huge pages improve every workload.
• Linux physical-memory documentation describes the kernel’s node and zone abstractions; firmware topology and hardware paths remain platform evidence.
• The working-set, access-cycle, line-utilization, NUMA-fraction, and bandwidth numbers are modeled teaching evidence in examples/performance-engineering-system-design-handbook/part-02/memory-locality/, not processor measurements.