How Does CPU Cache Work? Hit Rate, Lines and Locality

In everyday life

The spec sheet of a PC processor lists numbers like "L2 cache 16 MB" and "L3 cache 64 MB." These are the figures for the Ryzen 9 9950X, which AMD released in 2024. Meanwhile, a web browser's settings have a button that says "Clear cache."

Both follow the same idea: keep a copy of what you use often close to where you use it. This article focuses on the CPU cache. At the end, it also looks at caches outside the CPU.

The CPU spends time "waiting" for memory

A CPU works by reading a program's instructions and data from main memory (just "memory" below). Memory is built from a type of chip called DRAM. The problem is that reading from memory is very slow compared with the speed of the CPU.

After the CPU asks memory for data, the data takes from several tens of nanoseconds to about 100 nanoseconds to arrive, depending on the product. A nanosecond is a billionth of a second. A CPU running at 4 GHz gets a "go" signal, called the clock, every 0.25 nanoseconds. So while it waits 100 nanoseconds for memory, 400 clock ticks go by.

A CPU can move several instructions forward on each tick, so this is a long stall. On top of that, for many years, memory delays have not shrunk as fast as CPUs have sped up.

So the CPU keeps copies of memory data in a small, fast storage area right next to it. This is cache memory. Today's caches sit on the same chip as the CPU. The closest level can be read in about 1 nanosecond.

Caches are built from a type of circuit called SRAM. Most SRAM stores 1 bit with 6 transistors and can be read faster than DRAM. In exchange, it takes up more space, so it cannot be made very large (see "DRAM vs SRAM").

Why a small cache is enough: locality

Memory is hundreds of times larger than the cache, or more. It still helps because programs use data in a predictable pattern. This pattern is called "locality," and it comes in two kinds.

The first kind: data that was just used is likely to be used again soon. This is called temporal locality. For example, a loop uses the same counter variable and the same instructions over and over.

The second kind: when one piece of data is used, the data next to it is likely to be used soon. This is called spatial locality. A program's instructions sit in memory in order and usually run in order. It is like reading a book: after one page, you usually read the next.

Moving 64 bytes at a time: the cache line

To make use of spatial locality, the cache fetches more than the requested data. It also brings in the data around it. This unit of transfer is called a cache line ("line" below). On x86 CPUs and many Arm CPUs, one line is 64 bytes. (On Apple's M-series chips, macOS reports 128 bytes.)

For example, suppose 8-byte numbers sit in a long row in memory. One line holds 8 of these numbers. When the CPU asks for the first number, the cache does not have it yet, so it goes to memory. At that moment, the 7 numbers next to it are copied too.

Finding the wanted data in the cache is called a "hit." Not finding it is called a "miss." If you read the 8 numbers in order, only the first read misses, and the other 7 hit. Even for data read for the first time, 7 out of 8 reads, or 87.5%, are hits.

Real CPUs also try to load the lines they will probably need next, before they are asked for. This is called prefetching, and we leave it out here.

Hit rate and average access time

The share of reads that hit is called the "hit rate." If 95 out of 100 reads hit, the hit rate is 95%. The other 5% is the "miss rate."

We judge a cache by the average time one read takes. Multiply the time for a hit and the time for a miss by how often each happens, then add them. The effective access time formula used in many IT certification exams works this way:

Effective access time = hit rate × cache time + (1 − hit rate) × memory time

Let's calculate

Suppose a cache read takes 1 nanosecond, a memory read takes 100 nanoseconds, and the hit rate is 95%.

• Hits: 0.95 × 1 ns = 0.95 ns
• Misses: 0.05 × 100 ns = 5 ns
• Average: 0.95 + 5 = 5.95 ns

Without a cache, every read takes 100 nanoseconds, so the average is about 17 times shorter. But note that 5 of the 5.95 nanoseconds come from just 5% of reads: the misses.

Textbooks also use another form, called average memory access time (AMAT). It is "hit time + miss rate × extra time per miss." Here, a miss costs the 1 nanosecond spent checking the cache, plus 100 nanoseconds for memory. In the example above, that gives 1 + 0.05 × 100 = 6 nanoseconds.

The 0.05 nanosecond gap comes from one thing: whether the miss time includes the cache check. In an exam, use the formula and assumptions that the question gives. To try other numbers, use the "cache and AMAT calculator."

L1, L2 and L3: levels by speed and size

A bigger cache raises the hit rate. But the bigger a storage area is, the longer it takes to find and fetch the data you want.

So caches are split into several levels. The smallest, fastest level, closest to the circuits that compute, is the "L1 cache." Next comes L2, then L3. The higher the number, the larger and slower the level. The CPU checks L1 first, then each level in turn. If no level has the data, it goes to memory.

Here are typical sizes, using high-end PC processors released in 2024. How the levels are split and named differs from product to product.

The 9950X's L1 figure is the spec-sheet total of 1,280 KB divided by its 16 cores. "L1 vs L2 vs L3 cache" sums up the differences between the levels in a table.

Where data goes: direct-mapped and set-associative

Because the cache is small, the CPU needs a rule for which slot in the cache each memory line goes into.

The simplest rule fixes one slot for each line, based on its memory address. For example, in a cache with 4 slots, the slot is the line number's remainder after dividing by 4. This is called a direct-mapped cache. The CPU only has to check one slot, so it is fast, and the circuit is simple.

The weakness: two lines assigned to the same slot push each other out when used in turn. Lines 0 and 4 in the figure below are an example. Misses keep happening even while other slots are empty.

So most of today's CPUs group the slots into "sets." The address picks only the set, and the line can go in any of the few slots in that set. This is called a set-associative cache. The slots in a set are checked at the same time, so finding data takes little extra time.

There is also a design where a line can go anywhere (fully associative). But the circuit that checks every slot at once becomes large. "Direct-mapped vs set-associative vs fully associative cache" compares the three designs.

When the cache is full: choosing a line to evict

If a set is full, one line must be pushed out ("evicted") to make room for a new one. A common rule evicts the line that has gone unused the longest. This is called LRU (least recently used). By temporal locality, data unused for a while is unlikely to be needed soon. Tracking the exact order is hard, so real CPUs often use simpler rules that come close to LRU.

An OS uses the same idea when it moves memory contents out to storage (see "What Is an Operating System?").

When writing: write-through and write-back

As long as the CPU only reads, the copy in the cache matches the original in memory. But when the CPU changes data, the copy and the original no longer match. There are two main ways to decide when memory gets updated.

The first writes to memory at the same time as it writes to the cache. This is called write-through. Memory is always up to date, so the design is simple. In exchange, every write has to talk to slow memory.

The second updates only the cache for now, and is called "write-back." The changed line gets a mark, and it is written back to memory when it is evicted. Even if the same place is changed many times, memory is written only once, at eviction. In exchange, memory holds old data for a while, so keeping track is more complex.

Write-back is the norm for the data caches of today's PC processors. "Write-through vs write-back cache" sums up the differences in a table.

Why programs that read in order are faster

Once you know how lines work, you can see why the same calculation can run at different speeds depending on how it is written. As an example, take a table (a 2D array) of 10,000 rows by 10,000 columns, and add up every number. Each number is 8 bytes.

Some languages, such as C, store a table row by row. Row 1 is laid out from left to right, then row 2, and so on. One row is 80,000 bytes, and the whole table is 800 MB, far larger than any cache.

If you add along each row from left to right, you read memory in the order it is laid out. Each line brings in 8 numbers, so only 1 read in 8 misses.

If you add down each column from top to bottom, each read jumps 80,000 bytes ahead and lands in a different line every time. In L1, the smallest cache, almost every read misses. By the time the next column needs the other 7 numbers in a line, that line has left L1. The number of additions and the answer are the same, but the time taken is very different.

This example is simplified. The real gap depends on the CPU and the size of the table. Still, "read in the order data sits in memory" is a basic rule for fast programs. The same property matters in "Array vs linked list."

When there are several cores

Today's CPUs have several cores, and each has its own L1 and L2. So two cores can hold copies of the same data. If one changes it, the other's copy goes out of date. The CPU's circuits handle this automatically, for example by telling other cores to throw away their copies. This mechanism, which makes every core see the same value, is called cache coherency.

Caches outside the CPU

The idea of keeping a copy of what you use often close by is also used outside the CPU. For example, a browser saves images and other parts of pages it has loaded on your device. Next time, it uses the local copy instead of fetching it from a distant server. This is the browser cache.

DNS, which looks up IP addresses from names, also uses caches that remember answers for a while (see "How Does DNS Work?"). Services that deliver videos and images keep copies on servers around the world and serve users from a nearby one. This is called a CDN (content delivery network).

Copies going out of date is a shared problem. What differs is how it is handled, and how fast. In a CPU, circuits keep copies in step within nanoseconds. Browsers and CDNs use software to set how long a copy may be used. They save network waits measured in milliseconds (thousandths of a second).

Common misconceptions

By the numbers

During one wait for memory, the clock ticks hundreds of times. A cache is a way to shrink most of those waits to a few ticks.

Learn more

• Compare in a table: Write-allocate vs no-write-allocate (what happens on a write miss), MSI vs MESI vs MOESI (how cores keep their copies in step)
• Terms for the next step: miss penalty, conflict miss and capacity miss (kinds of misses), false sharing (cores fighting over one line), TLB (a cache for address translation)
• How memory speed limits AI computing: "Why Are GPUs Used for AI?"