CPU Cache Explorer

Simulate a set-associative CPU cache in your browser. Change size, block size, associativity and replacement policy, replay access patterns and see every hit and every compulsory, capacity and conflict miss.

How a cache decides: hit or miss

A cache is a small, fast memory that keeps copies of recently used data close to the processor. It never stores single bytes. It stores lines (also called blocks): aligned chunks of, say, 32 or 64 bytes. When the processor asks for one byte that isn’t cached, the whole line around it is loaded. That is a miss. If the line is already there, the request is a hit and never has to travel to main memory.

The explorer above simulates one level of data cache. Every access you enter, or that a pattern generates, is looked up, classified and logged, and you can step backwards and forwards through all of them.

Splitting an address: tag, set index and offset

To find a line quickly, the cache divides every address into three fields, shown in the bar at the top of the canvas:

• The offset picks a byte inside the line. A 32-byte line needs 5 offset bits.
• The set index picks which set the line must live in. A cache with 16 sets needs 4 index bits.
• The tag is everything left over. It is stored with the line so the cache can tell which of the many addresses that share a set is actually present.

Lookup is therefore cheap: use the index to go straight to one set, then compare the tag against each line in that set. The grid shows each set as a row and each line as a cell, with its tag, a V when it is valid and a D when it is dirty.

Associativity: how many places a line may go

The number of lines per set is the cache’s associativity, or number of ways.

• Direct-mapped (1 way): every address has exactly one possible slot. Lookup is fastest, but two busy addresses with the same index keep evicting each other.
• N-way set-associative: a line may go in any of N slots in its set. More ways means fewer collisions, at the cost of comparing more tags at once.
• Fully associative: one set holding every line, so there are no index bits at all. Any line can go anywhere.

When a set is full, a replacement policy chooses the victim. LRU evicts the line used least recently, FIFO evicts the line loaded longest ago, and random picks one using a seeded generator, so a shared link replays exactly the same choices.

Writes use write-back with write-allocate: a write miss loads the line first, the write marks it dirty, and the dirty line is written to memory only when it is evicted.

The 3C model: why did that miss happen?

Every miss in the explorer is classified with the classic “three Cs”:

• A compulsory miss is the first ever access to a line. No cache, however large, can avoid it.
• A capacity miss happens because the program’s working set is bigger than the cache. The explorer checks this by running a fully associative LRU cache of the same total size alongside yours: if that one would have missed too, the cache was simply too small.
• A conflict miss is one that the fully associative cache would have hit. The data would have fitted; it was evicted because too many lines mapped to the same set.

The distinction tells you what to change. Capacity misses call for a smaller working set or a bigger cache. Conflict misses call for more associativity or a different memory layout.

Locality, and why loop order matters

Caches pay off because real programs show locality. Temporal locality means reusing data you touched recently. Spatial locality means touching data next to what you just used, which is exactly what loading a whole line rewards.

A two-dimensional array in C is stored row by row. Reading it row by row walks through memory in order, so each 32-byte line serves eight 4-byte integers: one miss, then seven hits. Reading the same array column by column jumps a whole row ahead on every access. With 32 integers per row, consecutive accesses are 128 bytes apart, every access lands in a different line, and in the default cache those lines also crowd into just four of the sixteen sets. The arithmetic is identical; only the order changed.

Try it

1. 01

   Row-major matrix traversal

   Run the row-major traversal and step through the first ten accesses to the summary step. Why is the hit rate exactly 87.5%? Count how many 4-byte integers fit in one 32-byte line.

2. 02

   Column-major matrix traversal

   Now run the column-major traversal on the same cache. Every access misses. Look at the 3C breakdown: most misses are conflict misses, not capacity misses. Which sets in the grid ever get used?

3. 03

   Conflict misses, direct-mapped

   Two addresses, read alternately, in a direct-mapped cache. After two compulsory misses, every access is a conflict miss. Then raise the associativity to 2 ways: the explorer replays the same accesses, and the misses turn into hits.

4. 04

   Working set just exceeds capacity

   Loop over 17 lines in a 16-line LRU cache. LRU always evicts exactly the line you need next, so nothing ever hits. Switch the replacement policy to Random and run it again: random replacement is no longer perfectly wrong.

5. 05

   When FIFO beats LRU

   LRU is usually the better guess, but not always. Run this eight-access sequence with LRU, then switch to FIFO and compare the hit counts.

Each one opens the matching scenario in the explorer above.

Where this fits in the series

The explorer accompanies Computer Memory Hierarchy: Registers, Cache, RAM, and Virtual Memory, which introduces cache lines, locality, hits and misses, replacement and write-back in the context of the whole memory hierarchy. The next chapter, How a CPU Executes Instructions, follows instructions through the fetch-decode-execute cycle, which is where these loads and stores come from.

Real processors stack several cache levels, keep caches coherent between cores and prefetch lines before they are requested. The explorer leaves those out on purpose so that each decision a single cache makes stays visible.