A modern CPU can do several arithmetic operations per nanosecond, but a load that has to go all the way to main memory takes on the order of 100 ns. Caches close that gap, and they work only as well as your access pattern lets them. Two programs that do exactly the same arithmetic can differ by a factor of 30 depending on the order they touch memory.
Interviewers bring this up in performance questions (“why is this loop slow?”) and in concurrency questions (“why does adding a thread make it slower?”). Both have the same root: the hardware moves memory in fixed-size lines, and keeps them coherent between cores, whether or not your code knows.
Lines, levels and the two kinds of locality
Caches don’t store individual bytes. They store lines. On the Apple M1 I used for the measurements below, sysctl hw.cachelinesize reports 128 bytes. Most x86 chips use 64. When you read one int, the whole line containing it is fetched, so the next 31 ints (on M1) are already in cache.
The same machine reports its cache sizes through sysctl: 128 KiB of L1 data cache per performance core, and a 12 MiB L2 shared by the performance cluster (hw.perflevel0.l1dcachesize and hw.perflevel0.l2cachesize). Anything bigger than that working set comes from DRAM.
Two properties of access patterns decide whether caches help:
- Spatial locality: after touching an address, you soon touch nearby addresses. Walking an array in order is the ideal case, because each fetched line is fully used, and the hardware prefetcher notices the pattern and fetches lines before you ask.
- Temporal locality: after touching an address, you soon touch it again. A small lookup table used in a hot loop stays in L1.
Programs get slow when they lack both: touching one value per line, in an order the prefetcher can’t predict, across a working set larger than the caches.
Traversal order: the 4096 × 4096 matrix
C stores two-dimensional arrays row by row, so m[i][j] and m[i][j+1] are adjacent while m[i][j] and m[i+1][j] are 16 KiB apart for a 4096-wide int32 matrix. Summing the same 64 MiB matrix in both orders, compiled with cc -O2:
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) sum += m[i][j]; /* row-major */
for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) sum += m[i][j]; /* column-major */matrix 4096x4096 int32 (64 MiB): row-major 2 ms, column-major 65 ms (sum 68702699520)A second run gave 7 ms and 84 ms, so treat the numbers as rough, but the ratio is consistently 10 to 30 times. In row order, every byte of each 128-byte line is used and the compiler can vectorise the loop. In column order, each access lands on a different line, and by the time the loop comes back to the next element of a line, that line has usually been evicted. Same data, same additions, an order of magnitude apart.
The fix in real code is usually just to swap the loops. When you can’t (matrix multiplication needs both a row of one matrix and a column of another), the standard technique is blocking or tiling: process the data in tiles small enough to stay in cache, so each line is reused several times before it’s evicted.
Pointer chasing
Linked structures hurt for a different reason. To find node n+1 you have to load node n and read its next pointer, so the CPU can’t start the next load until the current one returns. Each miss is paid in full, one after another.
I built a 2-million-node linked list (64-byte nodes, 128 MiB in total) twice: once with nodes linked in memory order, once with the same nodes linked in a shuffled order. Then I summed a plain array of the same length:
linked list, 2M nodes, sequential: 2.7 ms (1.3 ns/node, sum 1999999000000)
linked list, 2M nodes, shuffled: 194.8 ms (97.4 ns/node, sum 1999999000000)
plain array, 2M int64: 0.3 ms (0.17 ns/element, sum 1999999000000)The sequential list is fast because the nodes happen to sit in order, so the prefetcher keeps up and two nodes share each line. Shuffle the links and each step costs about 97 ns, close to the raw memory latency, because nothing about the next address is predictable. The array, which needs no pointers at all, is another order of magnitude faster than even the lucky list.
That’s why a list allocated node by node over a long-running program performs like the shuffled case: after enough allocations and frees, consecutive nodes live far apart. It’s also why hash tables with open addressing, B-trees with wide nodes, and “array of structs” to “struct of arrays” rewrites show up in performance work. They all pack the data you touch together into fewer lines.
Note
Garbage-collected languages have the same issue. In Java or JavaScript, an array of objects is an array of references; iterating it chases pointers to wherever each object was allocated. A typed array or a primitive array keeps values contiguous.
False sharing between threads
Each core has its own L1 cache, and the coherence protocol ensures that when one core writes a line, other cores’ copies of that line are invalidated. That’s correct behaviour, and it’s also a trap. If two threads write different variables that happen to share a line, every write by one thread invalidates the other’s copy, and the line bounces between cores.
Two threads, each incrementing its own volatile int64_t 100 million times. In the first layout the counters are adjacent; in the second they’re 128 bytes apart:
struct { volatile int64_t a, b; } packed;
struct { volatile int64_t a; char pad[120]; volatile int64_t b; } padded;two threads, 100M increments each: same cache line 153 ms, 128 bytes apart 32 msThe threads never touch each other’s counter, yet sharing a line made the work about four to five times slower. There’s no data race and no lock. The code is correct, just slow. You won’t find it by reading the logic, only by thinking about layout or by profiling cache-coherence events.
Where it shows up: per-thread statistics in an array (counters[threadId]++), a lock next to the data it protects when many threads spin on the lock, ring-buffer head and tail indices in the same struct. The fix is to pad or align hot per-thread fields to the line size, which C11 can express with alignas(128) and C++17 with std::hardware_destructive_interference_size. Java has @Contended for JDK-internal use; libraries like LMAX Disruptor pad fields by hand.
What interviewers listen for
A few misconceptions come up often. “Caches are the OS’s job” is wrong: caching here is done by the hardware; the operating system’s influence is indirect, through which core a thread runs on (moving a thread to another core leaves its warm cache behind) and through page placement. “Big-O decides performance” holds only when the constant factors are similar; a linear scan over an array often beats a tree lookup for a few thousand elements because of locality. And “more threads, more speed” fails when threads share lines they write to.
A good answer to any “why is this slow?” question asks about the access pattern first: what’s the working set, is it walked in order, and are threads writing near each other?
Exercise: the counter that didn’t scale
A service keeps request statistics in long stats[NUM_THREADS], each worker thread incrementing its own slot. On a 1-thread benchmark it handles 2 million requests per second. With 8 threads it manages only 3 million in total, though the threads share no locks. What’s happening, and how would you fix and confirm it?
Answer
The slots for different threads sit next to each other, so with 8-byte longs and 64- or 128-byte cache lines, eight or sixteen threads’ counters share each line. Every increment invalidates that line in the other cores’ caches, so the line ping-pongs and each increment waits for coherence traffic. That’s false sharing: no logical sharing, but physical sharing of a line. The fix is to give each thread’s counter its own line, either by padding (a struct with the counter and enough bytes to fill the line, aligned to the line size) or by keeping counters in thread-local storage and summing them when someone reads the statistics. To confirm, I’d benchmark padded against packed at 1, 2, 4 and 8 threads: the packed version should flatten or drop as threads are added while the padded one keeps scaling. On Linux, perf c2c reports exactly which cache lines are contended; on macOS, Instruments’ CPU counters can show the effect.