Types of Cache Misses: Capacity
What You'll Learn
You'll understand why caches sometimes fail to hold all the data your program needs, leading to capacity misses.
What Is a Capacity Miss?
A capacity miss occurs when the cache simply isn't large enough to hold all the data your program actively uses—its "working set." Even if the cache were fully associative (perfect placement), the working set is too big to fit.
Think of it like a desk with limited space. You're working on multiple books and papers simultaneously (your working set). If your desk can only hold 3 books but you need 5, you'll constantly have to swap books on and off the desk—even if you could place them anywhere you wanted. The desk's capacity is the bottleneck.
How Capacity Misses Happen
Unlike compulsory misses (first-time accesses you learned about), capacity misses occur when:
- Your program accesses data that was recently in the cache
- But got evicted because other data needed that space
- The total working set exceeds the cache size
For example, if you have a 32 KB L1 cache and your program loops through a 64 KB array, roughly half the data will always be missing—the cache can't hold the entire array at once, no matter how clever the organization.
The Working Set Problem
The working set is the collection of memory locations your program accesses frequently during a particular time window. When your working set exceeds cache capacity, you experience a stream of capacity misses, dramatically hurting performance.
Key Takeaway: Capacity misses happen when your cache is too small to hold all the data your program actively uses, forcing repeated evictions and reloads of still-needed data—the solution is either a larger cache or optimizing your program's working set size.