📘 Memory Hierarchy and Caches

A CPU can do several operations per nanosecond, but fetching a value from main memory takes about 100 nanoseconds. Caches bridge that gap, and for most performance-sensitive code memory access patterns matter more than instruction counts. This page explains how caches work and how to write code that uses them well.

Table of Contents

1. The Hierarchy
2. Latency Numbers
3. Locality
4. Cache Lines and Organization
5. Address Breakdown Example
6. Replacement and Write Policies
7. Types of Misses
8. Average Memory Access Time
9. Multi-Core Caches and Coherence
10. False Sharing
11. Cache-Friendly Code
12. Main Memory and Beyond
13. Questions

1. The Hierarchy

Moving down: bigger, cheaper per byte, slower. Each level caches the one below it. The hierarchy works because programs have locality: most accesses hit the small fast levels.

Sizes vary widely: Apple silicon cores have large L1 caches (192 KB instruction, 128 KB data on performance cores), and AMD's 3D V-Cache stacks extra L3 on top of the die for 96 MB or more per chip.

2. Latency Numbers

Approximate values for a modern server, popularized by Jeff Dean and Peter Norvig and updated for current hardware.

Takeaways:

• A main memory miss costs as much as hundreds of simple instructions.
• Sequential access is dramatically faster than random at every level.
• Network round trips inside a data center are now comparable to or slower than an SSD read, so "just call another service" is not free.

3. Locality

Caches exploit temporal locality by keeping recent data and spatial locality by fetching whole cache lines instead of single bytes.

4. Cache Lines and Organization

Caches move data in fixed-size lines (blocks), almost always 64 bytes on x86 and most ARM chips (Apple silicon uses 128 bytes). Reading one int pulls in its 15 neighbors for free.

Each cache entry holds: valid bit, tag (which memory block this is), dirty bit (for write-back caches), and the data.

Real L1 caches are typically 8 to 12 way associative, and L3 caches 12 to 16 way or more.

5. Address Breakdown Example

A 32 KB, 8-way set-associative cache with 64-byte lines and 32-bit addresses.

1. Number of lines = 32 KB / 64 B = 512.
2. Number of sets = 512 / 8 = 64.
3. Offset bits = log2(64 B) = 6 (which byte within the line).
4. Index bits = log2(64 sets) = 6 (which set).
5. Tag bits = 32 - 6 - 6 = 20.

| tag (20 bits) | index (6 bits) | offset (6 bits) |

A lookup uses the index to pick the set, compares the tag against all 8 lines in the set in parallel, and on a hit uses the offset to pick the bytes.

If the same cache were direct-mapped: 512 sets, so 9 index bits and 17 tag bits. If fully associative: 0 index bits and 26 tag bits.

A useful consequence: addresses that differ by a multiple of (sets x line size) = 64 x 64 = 4 KB map to the same set. Striding through memory by exactly 4 KB (for example, walking a column of a matrix whose rows are 4 KB) uses only one set, and 9 such addresses already start evicting each other.

6. Replacement and Write Policies

Replacement (which line in a full set to evict):

Write policies:

Inclusive vs exclusive: an inclusive L3 contains copies of everything in L1 and L2 (simpler coherence); an exclusive one does not duplicate (more total capacity).

7. Types of Misses

The 3 Cs (plus a fourth for multi-core):

8. Average Memory Access Time

AMAT = hit time + miss rate x miss penalty

One level: hit time 1 ns, miss rate 5 percent, miss penalty 100 ns. AMAT = 1 + 0.05 x 100 = 6 ns. Halving the miss rate to 2.5 percent gives 3.5 ns; a small miss rate change matters a lot.

Two levels: L1 hit 1 ns with 10 percent miss rate; L2 hit 4 ns with 20 percent local miss rate; memory 80 ns.

L2 AMAT   = 4 + 0.2 x 80 = 20 ns
Total AMAT = 1 + 0.1 x 20 = 3 ns

Without the L2, AMAT would be 1 + 0.1 x 80 = 9 ns, three times worse.

Local miss rate is misses at a level divided by accesses to that level; global miss rate divides by all CPU accesses (here L2's global miss rate is 0.1 x 0.2 = 2 percent).

9. Multi-Core Caches and Coherence

Each core has private L1 and L2 caches, so two cores could hold different values for the same address. Cache coherence protocols keep them consistent.

MESI states for each cache line:

Variants: MOESI (AMD, adds Owned) and MESIF (Intel, adds Forward). Protocols are implemented with snooping (every cache watches a shared bus, fine for a few cores) or directories (a table tracks which caches hold each line, needed for many cores and multi-socket systems).

Coherence keeps caches consistent for a single address, but it does not order operations across different addresses; that is the job of the memory model and barriers (see Synchronization and Deadlocks).

10. False Sharing

Two threads write different variables that happen to sit in the same cache line. Every write invalidates the other core's copy, so the line bounces between cores, even though the threads share no data logically.

struct Counters {
    long a;   // written by thread 1
    long b;   // written by thread 2, same 64-byte line as a
};
// Fix: pad or align each counter to its own line
struct PaddedCounter { alignas(64) long value; };

Symptoms: a multi-threaded program that gets slower with more threads, and high cache coherence traffic in perf c2c. Per-thread counters that are merged at the end avoid the problem entirely.

11. Cache-Friendly Code

Traversal order

C, C++, Java, and most languages store 2D arrays row-major: a[i][j] and a[i][j+1] are adjacent.

// Fast: walks memory sequentially
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];

// Slow for large N: jumps a full row on every access
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];

For large matrices the column-order loop can be several times slower with identical instruction counts. Fortran, MATLAB, R, and Julia are column-major, so the rule flips there.

Techniques

This is why std::vector beats std::list, Java ArrayList beats LinkedList in almost every benchmark, open-addressing hash tables beat chained ones, and B-trees beat binary trees even in memory.

Data-oriented design, columnar databases, and ECS game engines are all applications of these ideas.

12. Main Memory and Beyond

Bandwidth vs latency: DRAM latency has barely improved in 20 years (still about 100 ns), while bandwidth has grown many times over. Programs that stream sequentially benefit from bandwidth; programs that chase pointers are stuck with latency.

13. Questions

Next: Compilers and Program Execution.