Cache hit and cache miss

When the CPU needs data, it first looks in the cache. If found, all is well—but what if it's not found?

This lecture helps you understand the core mechanics of how caches work, and the key principle that makes caches effective—Principle of locality。

Everyday analogy: the desk in a library

You're writing a paper in the library. At most 4 books can fit on your desk—this is yourCache, its capacity is small but within arm's reach.

When you need a book, first check whether it's on the desk:

• On the table (cache hit): just open and use it, zero waiting.
• Not on the table (cache miss): get up and look on the bookshelf, bring it back and put it on the desk. If the desk is full, you have to put the book that hasn't been touched for the longest time back on the shelf.

This simple rule is exactly the essence of a computer cache system—"Keep the recently used, evict the rarely used"。

Going further, you will find: when writing a paper, you don't randomly flip through unrelated books. Over a certain period of time, you repeatedly consult the same set of reference materials. Of the books on those thousands of shelves in the library, the ones you actually touched may only be twenty or thirty. This isPrinciple of localityAt work.

Core concept: cache hit and miss

Basic Terms

A simple example

, arr

2 hits out of 5 accesses, hit rate = 40%. Not high, but it already demonstrates the principle of caching.

Why caches work: the principle of locality

If a program accesses memory completely randomly, the cache is almost useless—data is loaded in only to be of no use right away.

But real programs don't behave randomly. They exhibit strongLocality, and this is precisely the fundamental reason why caches are effective.

... They are contiguous in memory.

If a piece of data is accessed, it is likely to be accessed again in the near future.

Typical scenario:

• Variables in a Loop：for i in range(1000000): total += i— VariableiandtotalAccessed 1 million times within a short period.
• Function Hot Code: 20% of a program's code accounts for 80% of its execution time; those instructions get frequently re-accessed.
• Frequently called function parameters: Local variables in a recursive function pile up on the stack with each call.

Spatial Locality

If a data item is accessed, nearby data is also likely to be accessed.

Typical scenario:

• Sequential Array Traversal：for i in range(len(arr)): sum += arr[i]—arr
• Struct/object fields: accessstudent.nameAfter [that], it is very likely that the next access will be...student.age, they are adjacent in memory.
• Sequentially Executed Instructions: After the CPU executes the instruction at address 100, the next instruction is likely at address 104.

Visualization of the two types of locality

时间局部性示意图：
  时间轴：   t1    t2    t3    t4    t5    t6    t7    t8
  访问地址：  A     B     A     C     A     D     B     A
             |_____|_____|_____|
              地址 A 在短时间内被多次访问——时间局部性

空间局部性示意图：
  内存地址： 100  104  108  112  116  120  124  128
  访问顺序：  *1   *2   *3   *4   *5
             |_____________________________|
              连续访问相邻地址——空间局部性

Modern CPUs exploit spatial locality to improve performance: when loading data from address 100 in memory, they also load addresses 100~164 (a full cache line, usually 64 bytes) into the cache. This way, when accessing address 104, it's already in the cache.

Cache replacement policy: what to do when it's full

Cache slots are limited; when the cache is full and new data needs to come in, it mustEvict an Old Data Item. The decision of "who gets evicted" is the cache replacement policy.

LRU performs best in practice because it directly exploits temporal locality—"If it hasn't been used recently, it probably won't be used for a while."

Real CPU caches usually use approximate variants of LRU (such as pseudo-LRU) to reduce hardware implementation complexity.

Interactive demo: LRU cache simulator

The following Python program fully simulates the working process of an LRU cache. You can modify the access sequence and cache capacity to observe changes in the hit rate.

Run this code and you will find:

• The larger the cache capacity, the higher the hit rate—but the improvement diminishes gradually (marginal effect)
• Access patterns with locality have much higher hit rates than random access—this is why caches are effective
• Under the LRU policy, repeatedly accessed addresses stay in the cache and are almost never evicted

Three types of cache misses

Not all "cache misses" are the same. Hardware engineers classify them into three types:

For ordinary programmers, dealing with the first two types is more common:

• Compulsory miss: unavoidable, but the longer your program runs, the smaller its impact.
• Capacity miss: Can be mitigated by optimizing data structure size and access patterns. For example, use more compact data types, process large arrays in blocks.

Understanding cache misses is key to writing high-performance code. A simple rule of thumb: make your data access patterns cache-friendly—traverse arrays in memory layout order, avoid jumpy access, and keep data that's often used together close in memory.

Programming practice: cache-friendly code

Here's a classic example: when traversing a 2D array, row-major vs column-major traversal makes a world of difference in performance.