Memorycache linegranularityfalse sharingpaddinglocality

Memory Moves in Lines, Not Variables

The cache has no concept of your variables. It moves fixed-size blocks — typically 64 bytes today — so reading one byte fetches the 63 around it. Almost every practical memory optimisation, and one notorious concurrency bug, follows directly from that one fact.

▶ Run the labFollow the mechanism

Software view, hardware view

The gap between what you wrote and what the machine does is where this whole domain lives.

The question
What is the actual unit of transfer between memory and cache, and what follows from it being larger than my variable?
What you wrote
You read a four-byte integer. It seems obvious that four bytes were moved — the language gave you a value of that size, and nothing suggests otherwise.
What the hardware does
A whole aligned block containing that integer was fetched — on most current machines 64 bytes. The other 60 arrived whether they were wanted or not, and now occupy cache capacity.
This single fact explains why arrays beat linked lists at equal complexity, why adding a field to a struct can slow an unrelated loop, why padding a variable can double multithreaded throughput, and why "I only read one byte" is never the whole cost. If you internalise one mechanism from this domain, make it this one.
Source→Compiler→Instructions→Front End→Execution→Registers→Caches→Memory→I/O→Behavior

One byte asked for, a whole line delivered

Caches are organised in fixed-size blocks called lines. A load for any address inside a line brings the entire line in. This is not overhead the designers failed to eliminate — it is deliberate, because tags cost space and time, and tracking memory at byte granularity would need vastly more of both. Coarse blocks also exploit adjacency for free, which is the bet described in What a Cache Actually Is.

The consequence is that the true cost of an access is not the size of your variable but the size of the line, divided by how many useful bytes in it you eventually use. Read every byte of a line and you paid one fetch for 64 bytes of work. Read four bytes and skip to the next line and you paid the same fetch for 6% utilisation.

The picture below shows the case that surprises people: a single four-byte counter in a 64-byte line. Nothing in the source hints that 60 bytes moved; the profiler will not attribute them to you either. It just shows up as a memory-bound loop nobody can explain.

A four-byte counter in a 64-byte line: what one read actually transfers
usedfetched, never readSIMPLIFIED
counterfetched but unused — 94% of the transfer
line 0
64 bytes total1 cache line touched60 bytes fetched and never read

The 60 bytes are not free: they consumed bandwidth and they occupy cache capacity that something else could have used.

Everything downstream of this fact

Once the line is the unit, a family of otherwise unrelated phenomena collapses into one explanation. An array wins over a linked list not because pointers are slow but because array elements share lines while heap nodes usually do not (Both Are O(n). One Is Far Slower.). Struct-of-arrays beats array-of-structs for column-wise work because it makes lines dense in the field you are reading (Array of Structs, or Struct of Arrays?). Padding a hot counter helps under threading because it stops two cores contending for one line (False Sharing: Independent Data, Shared Line).

The same fact explains a change that looks impossible: adding a rarely-used field to a struct slows down a loop that never touches it. The struct grew, so fewer of them fit per line, so the loop that walks them fetches more lines for the same number of elements. Nothing about the loop changed. Everything about its memory traffic did.

It also sets the sizing rule behind cache-conscious data structures generally: pick node and block sizes so that the useful payload fills whole lines. That is the reasoning behind B-tree node sizing and behind Matrix Tiling: Same Arithmetic, Ten Times Faster block choices — both are line-and-page arithmetic wearing an algorithms costume.

Sixteen bytes of payload spread across a 64-byte struct
1struct Entity {
2    float x, y, z, w;      // 16 B — the hot fields
3    char  name[32];        // 32 B — cold, touched rarely
4    int   flags, id, tag, pad;  // 16 B — cold
5}                          // 64 B total: one entity per line
6 
7for (e in entities) sum += e.x;
8// One line fetched per entity. 4 useful bytes of 64.
Hot field extracted into its own array
1float xs[N];              // hot: 16 floats per 64-byte line
2struct EntityCold { ... } cold[N];   // everything else
3 
4for (i in 0..N) sum += xs[i];
5// One line fetched per 16 entities. 64 useful bytes of 64.

Same values, same arithmetic, one sixteenth of the line fetches. The layout did not make the CPU faster; it stopped wasting the transfers the CPU was already paying for. This is Array of Structs, or Struct of Arrays? and Data-Oriented Design, Without the Dogma in a single change.

Knowing the line size, and not assuming it

PLATFORM-SPECIFIC64-byte lines are typical on current x86-64 and much AArch64 hardware; some architectures and some levels use 128 bytes, and adjacent-line prefetch can make the effective granularity larger still

Sixty-four bytes is the common value on mainstream x86-64 and on many AArch64 parts today, which is why it appears in every example including the ones above. It is not a law. Some architectures use 128-byte lines; some parts fetch line pairs adjacently, which behaves like a larger effective granularity for streaming; and the size can differ between levels on the same chip.

So write code that reads the value rather than hard-coding it where it matters. C++ exposes std::hardware_destructive_interference_size for exactly the padding case; Linux publishes the value under /sys/devices/system/cpu/cpu0/cache/; and most languages have a platform query. Hard-coding 64 is acceptable in an illustration and a latent portability bug in a performance-critical struct.

The deeper §224 point: the *mechanism* — transfer happens in fixed blocks larger than your variable — is universal, and every consequence in this lesson follows from the mechanism, not from the number. Reason with the mechanism, look up the number.

Reading the real line size instead of assuming it (Linux)
$ getconf LEVEL1_DCACHE_LINESIZE
64

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64

# C++17 and later, for the padding case specifically:
#   std::hardware_destructive_interference_size   // avoid false sharing
#   std::hardware_constructive_interference_size  // promote true sharing

Key points

  • The unit of transfer is a fixed-size line — commonly 64 bytes today — not the size of the variable you named.
  • The real cost of an access is one line fetch amortised over how many useful bytes of that line you eventually use.
  • Array-versus-list, AoS-versus-SoA, padding against false sharing and cache-conscious node sizing are all consequences of this one fact.
  • Adding an unused field to a hot struct can slow a loop that never reads it, because it changed how many elements fit per line.
  • The mechanism is universal; the number is not — query the line size rather than hard-coding it in code that depends on it.

Progressive depth

Overview

Memory moves in fixed blocks, typically 64 bytes. Asking for one byte brings 64. So data you use together should sit together.

Practical

Estimate cost in lines touched, not bytes read. Group hot fields, separate cold ones, keep elements from straddling boundaries, and pad variables that separate threads write. Query the line size rather than assuming it.

Advanced

Line granularity interacts with alignment (a straddling object doubles fetches), with associativity (lines competing for the same set evict each other regardless of capacity — see Set-Associative Caches: The Compromise That Won), and with coherence (a write invalidates the whole line elsewhere, not the bytes you wrote).

Internals

Sectored caches track sub-line validity; adjacent-line prefetchers fetch a partner line, making effective granularity larger; write-combining buffers merge partial-line stores to avoid read-for-ownership; and the coherence unit is the line, which is why the destructive and constructive interference sizes exposed by C++ can legitimately differ from each other and from the raw line size.

Loop Order & Locality

Change an input and watch which number moves — and which one refuses to.

The same matrix, three traversal orders
SIMULATED
for i { for j { a[i][j] } }88%
for j { for i { a[i][j] } }0%
tiled 8×888%

Identical arithmetic, identical element count, identical complexity. Only the order changed. Column-major traversal of row-major storage touches a new line on essentially every access; tiling restores the reuse by keeping a block resident while it is used.

Follow the mechanism

The path through the machine, hop by hop — and the conclusions it invites that are wrong.

  1. 1
    Load → address decomposition: the address is split into a tag, a set index and a byte offset within the line (Tag, Index and Offset: How an Address Finds Its Line).
  2. 2
    Miss → line request: the cache requests the whole aligned line containing the address, never a partial fragment.
  3. 3
    Fill → installation: the full line is written into a slot at each level on the way back, displacing a victim.
  4. 4
    Neighbour access → hit: any subsequent access to any byte of that line is now a hit, which is where Spatial Locality pays.
  5. 5
    Store to the line → coherence: on a multicore machine, writing any byte invalidates the whole line in other cores' caches (False Sharing: Independent Data, Shared Line).
What people conclude from this — wrongly
  • • Assuming a small read is a small transfer, and building a bandwidth estimate from variable sizes rather than line counts.
  • • Hard-coding 64 in a padding constant and shipping a struct that silently under-pads on a 128-byte-line machine.
  • • Concluding that "the struct is only 40 bytes so it fits fine", without checking whether elements straddle line boundaries.
  • • Treating false sharing as a locking bug and adding synchronisation, which makes it slower still (False Sharing: Independent Data, Shared Line).

Consequences, controls and cost

What it causes
  • • Sequential traversal is dramatically cheaper per element than strided or random traversal at the same instruction count.
  • • Struct size changes alter the performance of loops that do not touch the added fields.
  • • Two threads writing different variables can contend badly if those variables share a line.
  • • Reading one field of a large object costs the same transfer as reading the whole line it sits in.
What you can do
  • • Put the fields you iterate over together, and separate them from fields you rarely touch ([[aos-vs-soa]]).
  • • Size hot structures so an integer number fit per line, avoiding elements that straddle two lines ([[alignment]]).
  • • Pad or align variables that different threads write, so they land in different lines ([[false-sharing]]).
  • • Prefer contiguous containers over node-based ones when you iterate more than you insert ([[array-vs-linked-list]]).
  • • Query the platform line size rather than hard-coding it anywhere it affects correctness of the optimisation.
How to see it
  • • Read the coherency line size from the platform and confirm your assumptions against it before tuning.
  • • Compute the ratio of bytes actually used to lines fetched for a hot loop; low utilisation is the signature this lesson predicts.
  • • Add a padding field to a hot struct and re-measure; a change in an untouched loop confirms line density is the mechanism.
  • • For threaded code, watch coherence or invalidation counters while varying padding — see [[false-sharing]] for the pattern.
What it costs
  • • Padding wastes memory deliberately, which costs capacity and can push a working set past a cache level to fix a contention problem.
  • • Splitting hot and cold fields breaks a natural object model and can make the code meaningfully harder to maintain.
  • • Line-size-aware structures are tuned to a platform and need re-checking when targeting a different one.

Scope

§224 — what these claims are specific to.

What these claims are specific to
  • PLATFORM-SPECIFIC64-byte lines are typical on current x86-64 and much AArch64; 128-byte lines exist, and levels on one chip can differ
  • GENERALThat transfer happens in fixed blocks larger than a scalar variable is universal to cached architectures, and every consequence in this lesson follows from that rather than from the specific size

Misconceptions

Claim
“Reading one byte costs one byte of memory traffic.”
Reality
It costs a full line — typically 64 bytes. This is why bandwidth estimates built from variable sizes are wrong, often by more than an order of magnitude for sparse access patterns.
Claim
“Cache lines only matter for concurrent code.”
Reality
False sharing is the most famous consequence, but line granularity governs single-threaded performance far more often: it is the reason for array-versus-list, AoS-versus-SoA, struct packing and every cache-conscious data structure. Concurrency just adds a spectacular failure mode on top.
Claim
“A 64-byte struct is optimal because it exactly fills a line.”
Reality
Only if it is also 64-byte *aligned*. An unaligned 64-byte object straddles two lines, so every access touches both and you have doubled your fetches while believing you optimised. Size and alignment are separate properties — see Alignment: Why Addresses Are Not Arbitrary.

Apply it

🔍 One Field of Sixteen, and All of the Bandwidth🔍 Adding Threads Made It Slower

Where the rest of this lives

Concurrency & Parallelism
False sharing as a scaling failure

The correctness-and-interleaving view of two threads sharing a line — why your speedup never arrived — belongs there; the coherence mechanism that causes it is MESI and Its Relatives here.

← What a Cache Actually IsSpatial Locality →