Course contentsShow
← Computer Science
Lesson 1143 of 2,87226. Memory Hierarchy and CachingFree lesson

Types of Cache Misses: Capacity

Analyze capacity misses that occur when the cache is too small to hold the working set.

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:

  1. Your program accesses data that was recently in the cache
  2. But got evicted because other data needed that space
  3. 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.