How CPU Caches Work: Lines, Associativity, and False Sharing

A load that misses DRAM can cost hundreds of cycles. A load that hits L1 often costs a handful. That gap is why two programs with the same big-O complexity can differ by an order of magnitude on the same machine. The hardware unit that creates the gap is the CPU cache: a small, fast SRAM store that keeps recently used blocks of memory close to the cores that use them.

This article is about that hardware contract: cache lines, set associativity, write-back versus write-through, the MESI coherence states that keep multiple cores honest, and the software failure mode called false sharing. It is not a second tour of HTTP caches, the kernel page cache, Redis, or virtual-memory page tables. Those reuse the word cache for a different layer. See how virtual memory works, how mmap works, and how application caching works for those layers.

The search intent here is one question: how does a modern CPU cache decide what to keep, where to put it, and how cores share it?

The contract

Main memory is large and slow. On-chip SRAM is small and fast. The cache is a hardware map from physical addresses to a limited number of SRAM slots. On every load or store the core asks:

• Is the block that contains this address already in a nearby cache?
• If yes, use that copy.
• If no, fetch a whole block from a lower level and install it, evicting something else if the set is full.

The unit of transfer is not a byte and not a 4 KiB virtual-memory page. It is a cache line, almost always 64 bytes on current x86-64 and many ARM server cores. Touching one integer can therefore pull 64 bytes into L1. That is spatial locality: nearby addresses ride along. It is also why two hot counters that sit 8 bytes apart can fight each other.

Typical latency shapes, not vendor promises for a specific SKU:

• L1 data cache: a few cycles, tens of KiB per core, private.
• L2: low tens of cycles, a few hundred KiB to a couple of MiB per core, usually private.
• Last-level cache (often L3): tens of cycles, many MiB shared by a cluster of cores.
• DRAM: hundreds of cycles plus contention on the memory controllers.

A miss at one level becomes a request to the next. An L1 miss that hits L2 is cheap compared with an LLC miss that walks to DRAM. Prefetchers try to hide some of that delay when the access pattern is regular. They do not cancel the line-sized transfer.

How an address is looked up

Split a physical address into three fields, from low bits to high:

• Offset inside the line. For a 64-byte line that is 6 bits.
• Index that names a set in this cache.
• Tag that must match one of the lines stored in that set.

A direct-mapped cache has one line per set. Address A always competes with every other address that shares the same index. Two hot arrays that stride through the same set will thrash even if the cache as a whole is half empty. That is a conflict miss, not a capacity miss.

An N-way set-associative cache stores N candidate lines per set. The index still selects the set. The tag is compared against all N ways, usually in parallel. Replacement inside the set is typically an approximation of LRU or a pseudo-random policy. Common L1 designs are 8-way. Last-level caches often use higher associativity because more cores dump more conflicting addresses into the same shared structure.

A fully associative cache is one set with as many ways as lines. It removes conflict misses and makes lookup expensive. TLBs sometimes use high associativity. Large data caches almost never go fully associative.

Misses are usefully split the way textbooks do:

• Compulsory (cold): the line has never been seen.
• Capacity: the working set does not fit.
• Conflict: the working set would fit, but too many lines hash to the same set.
• Coherence: another core invalidated a line this core still wanted.

Software can change the last three. Blocking a matrix multiply so each tile fits in L1 reduces capacity misses. Padding a per-thread counter to 64 bytes reduces coherence misses caused by false sharing. Aligning a hot structure so it does not straddle two lines reduces extra fills.

Write policy

On a store, the cache must decide when DRAM (or the next level) learns about the new bytes.

Write-through updates the next level on every store. Simple, and it keeps lower levels closer to the latest value. It also burns bandwidth. Few modern L1 data caches are write-through toward DRAM.

Write-back marks the line dirty and updates only the local copy. The dirty line is written downward when it is evicted, or when a coherence request demands a current copy. That is the usual design. It means a store that hits in L1 may never touch DRAM if the line dies in cache after later overwrites.

A write miss can allocate a line (write-allocate) or send the store downward without installing it. Write-allocate plus write-back is the common pairing: the first store to a line fetches the rest of the 64 bytes, then subsequent stores hit.

Store buffers and fill buffers sit in front of this machinery. A core can retire a store into a buffer before the line arrives. Visibility to other cores is a separate question, answered by the memory model and by the coherence protocol, not by the existence of the buffer.

Coherence: MESI in practice

Each core has private L1 (and usually L2) copies. Those copies must not silently disagree. Cache coherence is the protocol that keeps that promise for a single address: at any moment, all cores that hold a line agree on its value, and a write becomes visible according to the architecture's memory model.

MESI is the four-state protocol most explanations start from. Each cached line is in one of:

• Modified: this cache has the only copy, and it is dirty. Memory is stale. A later reader must obtain the line from this cache (or after a write-back).
• Exclusive: this cache has the only copy, and it matches memory. A store can move E to M without talking to other caches. That silent upgrade is why Exclusive exists; MSI without E would need a bus transaction for a private read-then-write.
• Shared: one or more caches hold a clean copy. A store must invalidate the others before the line can become Modified.
• Invalid: this slot does not hold a usable copy.

A read miss typically obtains the line in E if no other cache has it, or in S if someone else does. A write to an S line sends invalidations, waits until the other copies are gone, then becomes M. Two cores that ping-pong a lock word spend their time on those invalidations, not on the compare-and-swap itself.

Snooping works on a small interconnect: every cache watches a shared broadcast. Large chips use directories. The last-level cache or a home agent records which cores may hold a line and forwards requests point to point. Inclusive LLCs make that directory easier: if the line is absent from an inclusive L3, it is absent from the private caches above it, so the agent does not have to snoop every L1. Exclusive or non-inclusive LLCs save capacity by not duplicating L1/L2 contents, at the cost of more probing.

MOESI and MESIF add extra states (Owned, Forward) so one cache can supply a dirty or clean copy without always writing back to DRAM first. The programmer-visible rule stays the same: do not assume two cores can write adjacent fields cheaply if they share a line.

False sharing

True sharing is two cores that actually need the same bytes: a lock, a mailbox, an atomic counter everyone increments. False sharing is two cores that need different bytes that happen to live in the same 64-byte line.

struct Counters {
    uint64_t a;  /* core 0 increments this */
    uint64_t b;  /* core 1 increments this */
};

Those two fields are 8 bytes each and sit next to each other. Hardware coherence does not track fields. It tracks lines. Every increment of a invalidates core 1's copy of the line that also holds b. Core 1 then misses, pulls the line, increments b, and invalidates core 0. Throughput collapses toward the interconnect's invalidate rate.

The usual fix is to give each hot per-core field its own line:

struct Counters {
    alignas(64) uint64_t a;
    alignas(64) uint64_t b;
};

or to keep per-thread counters in thread-local storage and combine them later. Java's @Contended, some C++ allocator pads, and many ring-buffer designs exist for this reason. The extra 56 bytes of padding look wasteful until you measure the coherency traffic.

False sharing is not a data race. Both fields can be correctly atomic. The program is still slow because the unit of coherence is larger than the unit of the algorithm.

Worked cost picture

Walk a 32 MiB array with a 64-byte stride and you touch every line once. Walk it with an 8-byte stride and you reuse each line eight times after the first miss. The second loop does more loads but often finishes faster because L1 absorbs seven of every eight accesses. That is the entire reason structure-of-arrays layouts, blocked linear algebra, and sequential scans beat pointer-chasing graphs on cache-sensitive hardware.

A linked list of separately allocated nodes is the opposite pattern. Each node may sit on its own line, possibly on its own DRAM page. The next pointer is not known until the current node arrives, so prefetchers guess poorly. The CPU spends time on misses, not on the comparison in the loop body.

Hardware prefetchers help sequential and strided streams. They can also pollute a small L1 if the stream is huge and the useful working set is a different array. Software prefetch intrinsics exist; they are a hint, and a wrong hint occupies a fill buffer that a demand miss needed.

Where this sits next to other machinery

Virtual memory translates a user address to a physical address before (or in parallel with) the data-cache lookup. The TLB caches that translation. A TLB miss is not a cache-line miss, though both stall the core. Huge pages reduce TLB pressure; they do not change the 64-byte line size.

The kernel page cache stores file bytes in DRAM pages so read and mmap can avoid disk. Those pages are ordinary memory as far as the CPU cache is concerned. Once a file page is mapped and touched, the same L1/L2/L3 machinery applies. mmap's "zero-copy" benefit is about avoiding a user-buffer copy, not about skipping hardware caches.

Language runtimes that bump-allocate in an arena get spatial locality for free. Collectors that compact also restore locality. A heap that sprays small objects across pages turns every pointer chase into a potential LLC miss. That is one reason compacting collectors and region allocators show up in performance-sensitive systems.

Misconceptions

• "L3 is just a bigger L1." It is shared, higher latency, and often inclusive. A line in L1 may already exist in L3. Evicting from L3 can force invalidation of private copies.
• "If it fits in RAM it is fast." RAM is the miss path. Working sets that fit in L2 and working sets that only fit in DRAM are different machines.
• "Atomics are expensive because of the LOCK prefix." On a line already in Modified state in this core, an aligned atomic may be cheap. The expensive case is the line bouncing between cores.
• "Padding always helps." Padding a cold structure wastes bandwidth and capacity. Pad only the fields that neighboring cores write.
• "Cache is the same as the page cache." One is SRAM next to the core. The other is DRAM managed by the kernel for files.

Takeaways

• CPU caches move 64-byte lines, not individual variables. Layout is part of the algorithm.
• Set associativity limits where a line may live. Conflict misses are real even when capacity remains.
• Write-back plus MESI (or a close relative) is how private caches stay coherent. Exclusive state exists so a private read-modify-write does not broadcast.
• False sharing is coherence traffic on bytes you did not mean to share. Align and pad hot per-thread writes.
• Measure misses and coherency counters when a parallel loop is slower than the serial version for no algorithmic reason.

Related reading on this site: How Virtual Memory Works, How mmap Works, How System Calls Work, How Caching Works.