The short answer
Quick answer: A CPU can execute instructions far faster than main memory can deliver data. To bridge the gap, processors keep small, extremely fast memories called caches (L1, L2 and L3) that hold copies of recently used data. If the data a program needs is in the cache (a hit), it arrives in about a nanosecond. If not (a miss), the CPU waits around a hundred times longer for RAM. Code that reads memory in a compact, predictable order gets mostly hits and can run many times faster than code doing the same work in a scattered order.
Why caches exist
A modern core can perform several simple operations per nanosecond. A trip to main memory takes roughly 100 nanoseconds. Without caches, the processor would spend almost all its time waiting.
The fix is a hierarchy of memories, each level larger and slower than the one before:
| Level | Typical size | Typical access time | Shared? |
|---|---|---|---|
| L1 | Tens of KB per core | About 1 ns | Per core |
| L2 | Hundreds of KB to a few MB per core | A few ns | Usually per core |
| L3 | Several MB to tens of MB | 10 to 20 ns or more | Shared across cores |
| Main memory (RAM) | Gigabytes | Around 100 ns | Whole system |
The figures vary by processor, but the ratios are what matter. The well-known latency numbers list and Ulrich Drepper's What every programmer should know about memory explain the hardware reasons in depth.
Why caching works: locality
Caches rely on two patterns that almost all programs show:
- Temporal locality. If you used something recently, you will probably use it again soon, such as a loop counter.
- Spatial locality. If you used something, you will probably use its neighbours soon, such as the next element of an array.
To exploit spatial locality, the cache never loads a single byte. It loads a whole cache line, typically 64 bytes. Touch one element of an array and its neighbours come along for free.
The CPU also has a prefetcher that spots simple patterns, such as walking forward through memory, and loads upcoming lines before you ask for them.
The classic demonstration
Summing a large two-dimensional array can be written two ways:
// Row by row: walks memory in order
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += grid[i][j];
// Column by column: jumps N elements each step
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += grid[i][j];
Both do exactly the same additions. But in C, rows are stored one after another, so the first version reads memory sequentially and the second jumps to a different cache line on almost every access. For a large array, the second version can be several times slower. Same algorithm, same big-O, very different speed.
Data structures and the cache
This is why the "best" data structure in theory is not always the fastest in practice.
- Arrays store elements side by side. Iterating is ideal for the cache and the prefetcher.
- Linked lists store each node wherever the allocator put it. Following each pointer is a likely cache miss, so walking a list can be much slower than walking an array of the same length.
- Hash tables vary. Designs that keep entries in one flat array ("open addressing") tend to be more cache-friendly than those that chain nodes through pointers. See how hash maps work.
- Trees with many keys per node, such as B-trees, need fewer jumps than binary trees. That is one reason databases favour them; see how database indexes work.
Where data lives matters too. Values on the stack or packed in an array are contiguous; many small separately allocated heap objects are scattered. See stack vs heap.
How to write cache-friendly code
- Prefer contiguous storage. Use arrays or vectors unless you have a measured reason not to.
- Access memory sequentially. Loop in the order the data is laid out.
- Keep hot data small. If a loop only needs two fields of a large object, the other fields waste cache space. Storing each field in its own array ("struct of arrays") can help in hot loops.
- Avoid pointer chasing in performance-critical paths.
- Process in blocks. For big matrices, working on cache-sized tiles keeps data in the cache while you use it.
- Measure. Use a profiler; on Linux,
perf stat -e cache-misses ./programreports misses directly.
False sharing: a multi-threading trap
Caches work on whole lines, which creates a subtle problem with threads. Suppose two threads each update their own counter, and the two counters happen to sit in the same 64-byte cache line. Each write by one core forces the other core's copy of the line to be invalidated. The line bounces between cores, and the program runs far slower than expected, even though the threads never touch the same variable.
This is false sharing. The fix is to place heavily written per-thread data on separate cache lines, usually by adding padding or alignment. For more on threads sharing memory, see processes vs threads.
Not to be confused with other caches
"Cache" appears everywhere in computing: the browser cache, CDN caches, the operating system's file cache, Redis. They all share one idea, keeping a fast copy of something slow to fetch, but the CPU cache is hardware inside the processor and is managed automatically. You cannot control it directly; you can only arrange your data so it works well. The same layered idea applies to the whole machine, as described in why we need both RAM and storage.
Frequently asked questions
What is a cache miss?
It happens when the CPU needs data that is not in the cache and must fetch it from a slower level or from RAM. The processor stalls while it waits.
Is a bigger cache always better?
Larger caches hold more but are slower to search, which is why there are several levels: a tiny, very fast L1 backed by larger, slower L2 and L3.
Does this matter in high-level languages like Python or JavaScript?
Yes, though interpreter overhead usually dominates. Libraries such as NumPy are fast largely because they store numbers in contiguous arrays and process them in tight native loops.
What is a cache line?
The unit the cache works in, usually 64 bytes. Loading any byte loads the whole line containing it.
Conclusion
On modern hardware, memory access patterns often matter more than instruction counts. The cache rewards code that keeps related data together and reads it in order, and punishes code that hops around memory. Choose contiguous data structures, loop in layout order, and measure cache misses before reaching for cleverer algorithms.
Related articles
- How Virtual Memory Tricks Every Program Into Thinking It Owns the RAM
- Why Do We Need Both RAM and Storage?
- How Hash Maps Achieve O(1) Lookups
- Stack vs Heap: Where Your Variables Actually Live
Sources and further reading
