CPU caches, locality, coherence and NUMA

Why it matters

Two loops with identical big-O can differ by an order of magnitude because one walks memory sequentially and the other jumps around. The same physics explains why adding threads to a counter-heavy service can make it slower, why two "independent" per-thread counters interfere, and why a large VM spanning two sockets behaves differently from a small one. If you have studied interference between co-located workloads, shared last-level cache and memory bandwidth are the mechanisms behind much of it. Low-level, AI-infrastructure and systems-research interviews probe this directly; backend interviews touch it through data layout and contention.

Core ideas

The hierarchy. Registers, per-core L1 and L2 caches, a shared last-level cache, then DRAM. As rough orders of magnitude, an L1 hit costs a few cycles, a last-level hit tens of cycles and a DRAM access around a hundred nanoseconds. Measure your own machine rather than memorizing figures, but keep the ratio in mind: missing every cache costs the time of hundreds of instructions.

Lines and locality. Caches move fixed-size lines, 64 bytes on most x86 and many ARM cores. Spatial locality means using the rest of a line you already paid for; temporal locality means reusing data while it is still cached. Hardware prefetchers recognize sequential and strided streams, so array scans run near bandwidth limits while pointer chasing, hash probing and random access pay full latency. Misses are compulsory (first touch), capacity (working set too big) or conflict (too many hot lines mapping to one set); coherence adds a fourth kind.

Layout is a design decision. Traversing a row-major matrix by columns touches a new line on every access. A struct-of-arrays layout lets a loop that reads one field stream through memory, while an array of structs drags unused fields along. Blocking (tiling) reorganizes a computation so each tile is reused while cached, the same idea that makes GPU kernels and FlashAttention fast.

Coherence, MESI intuition. Each cached line is Modified (only copy, dirty), Exclusive (only copy, clean), Shared (clean, possibly in several caches) or Invalid. Reads can share a line cheaply. A write needs exclusive ownership, so every other copy is invalidated and the next access from another core misses. A line written by several cores therefore bounces between them, and each transfer costs about as much as a cache miss.

False and true sharing. False sharing happens when independent variables written by different threads sit on the same line, such as per-thread counters packed into one array. Fix it with padding or alignment to line boundaries, or by accumulating locally and combining at the end. True sharing, many threads updating the same variable such as a global counter or a lock word, cannot be padded away; the scalable answer is sharding (per-core counters summed on read) or batching updates.

struct padded_counter { _Alignas(64) long value; }; /* one line per thread */
struct padded_counter per_thread[NTHREADS];

Coherence is not consistency. Coherence keeps the copies of one location in agreement. It provides neither atomic read-modify-write nor any order in which different locations become visible; that is the memory model, covered with synchronization primitives.

NUMA and bandwidth. On multi-socket machines and some large single-socket parts, each memory controller is closer to some cores than to others. Linux normally places a page on the node of the thread that first touches it, so one thread initializing a big array can strand all of it on one node. Streaming workloads saturate memory bandwidth long before the cores are busy, and adding threads then adds nothing. numactl and numa(7) expose the placement policies.

Common misconceptions

• "Asymptotic complexity decides performance." At realistic sizes, constant factors from misses often dominate; a linked list and an array have the same traversal complexity and very different speed.
• "Cache coherence makes concurrent code correct." It keeps one location's copies consistent; it gives neither atomic increments nor ordering across locations.
• "Atomics make a shared counter scale." An atomic increment still needs exclusive ownership of the line, so under contention every increment is a cross-core transfer.
• "False sharing only affects locks." Any frequently written data sharing a line with another thread's data suffers, including adjacent struct fields and arrays indexed by thread ID.
• "Prefetchers hide memory latency." Only for predictable patterns; dependent loads in linked structures and hash chains still wait for DRAM.
• "NUMA does not matter in the cloud." Large instances can span sockets, and placement and bandwidth effects appear there too.

How to approach it

Write two small experiments and measure them: sum a matrix by rows and by columns, and run per-thread counters packed together versus padded. Use perf stat with cycle and cache-miss events to see the difference, then perf c2c to locate the contended line (event availability varies by CPU and inside VMs). In interviews, explain answers in terms of lines, ownership and bandwidth rather than "the cache is faster", and propose a fix (layout change, padding, sharding) together with how you would verify it.