CPUs read memory in cache lines, typically 64 bytes, and a cache miss costs far more than an arithmetic operation. Data layout that keeps accesses close together and repeated uses fast, while poor layout scatters accesses across memory and stalls the CPU.
Before you start
You should understand arrays, structs and basic memory layout. This article covers locality and false sharing.
Step-by-step walkthrough
Step 1: Exploit spatial and temporal locality
Spatial locality means accessing nearby addresses, so iterating an array in order uses each fetched cache line fully. Temporal locality means reusing recently accessed data, so a small hot set stays in cache. Contiguous data and predictable order maximize both.
Step 2: Avoid pointer chasing
A linked list or tree of separately allocated nodes forces a cache miss per hop, because each node is elsewhere in memory. A contiguous array often beats a pointer structure even with more comparisons, because it turns many misses into a few sequential reads.
Step 3: Watch for false sharing
Two threads writing different variables that share a cache line cause the line to bounce between cores, even though the variables are logically independent. This is false sharing, and padding hot variables to separate cache lines removes it. It is invisible in the source and shows up only in scaling.
Worked scenario
Contiguous iteration uses each cache line fully.
array of N ints, iterate in order:
fetch line (64 bytes = 16 ints), use all 16, fetch next
linked list of N nodes:
each node likely on a different line -> a miss per nodeWalk through the example
The array reads a cache line and then uses every element in it, so misses are rare. The linked list touches one value per line, so nearly every node is a miss. Same amount of data, very different cache behavior.
Common mistake
Choosing a pointer-heavy structure for data that is iterated often, or placing per-thread counters adjacent in an array so they share a line. Both look fine in the source and hurt only under real load.
Verify the behavior
Benchmark an array scan against a linked-list traversal with the same element count and compare time per element. For false sharing, run a multi-threaded counter array with and without padding and compare scaling.
Interview exercise
Why can a contiguous array outperform a linked list even when it does more work?
Answer and reasoning
Because the array’s sequential access uses each cache line fully and prefetches predictably, so the CPU rarely stalls on memory. A linked list follows pointers to scattered addresses, causing a cache miss per hop that can dominate the cost. The array trades comparisons for far fewer memory stalls, which usually wins.
Continue learning
Compare memory hierarchy in Page cache and allocation in Memory allocation. Read the What every programmer should know about memory and try the Operating systems interview questions.