Skip to content
KinPilot™Learn & Explore
Menu
← TopicsReading path →

Grades 9–12 · Computing

When does a cache reduce read cost?

A cache keeps copies of some objects in limited storage so repeated reads may avoid a more expensive read from the backing store: the larger source holding the objects. A hit occurs when the requested object is already cached. A miss requires a backing read and brings the object into the cache. The benefit depends on which objects are requested again before they are removed.

D08 visual explanationThe empty cache holds 2 equal-size objects. Read requests: A, B, A, C, A, B. A hit costs 1 tick total; a miss costs 6 ticks total (1 lookup plus 5 backing-store ticks) and loads the object. Every access makes that object most recent; a full cache evicts the least recently used. Results: miss, miss, hit, miss, hit, miss, 2 hits, 4 misses, 26 ticks. Final least-to-most-recent order: A, B. Direct backing reads without a cache cost 5 ticks each, 30 total. These invented costs omit real CPU behavior, writes, transfer blocks and policy overhead.A cache trades storage for read latency2 slots · initially empty · least recent evictedHit = 1 tick total; miss = 6 ticks totalReadResultCache: least → most recentTicks1: AmissA62: BmissA → B63: AhitB → A14: CmissA → C65: AhitC → A16: BmissA → B62 hits · 4 misses · 26 ticks totalNo-cache baseline: six reads × 5 ticks = 30 ticks.

In the diagramA cache trades storage for read latency2 slots · initially empty · least recent evictedHit = 1 tick total; miss = 6 ticks totalReadResultCache: least → most recentTicks1: AmissA62: BA → B3: AhitB → A14: CA → C5: AC → A6: B2 hits · 4 misses · 26 ticks totalNo-cache baseline: six reads × 5 ticks = 30 ticks.

The two-slot LRU cache has two hits and four misses for A, B, A, C, A, B. Under the invented cost rules, that totals 26 ticks versus 30 without the cache.

This model begins with an empty two-slot cache and reads A, B, A, C, A, B. It uses least recently used replacement, or LRU. Every access makes its object the most recent, including a hit. When a new object needs a full cache, the object unused for the longest time is evicted.

The first A and B requests miss. The next A hits, making B least recent. Loading C therefore removes B. The following A hits again, but the final B misses and replaces C. The trace has two hits and four misses; its final least-to-most-recent order is A, B.

The invented costs are one tick total for a hit and six for a miss, including lookup and backing access. The trace costs 2 × 1 + 4 × 6 = 26 ticks. Direct backing reads without a cache cost five each, or 30 ticks for the same six requests.

A cache is not automatically faster for every workload. A repeating sequence that evicts each next-needed object can produce repeated misses, while lookup still costs something. Capacity, access pattern and cost rules all matter; these toy ticks are not hardware benchmark results.

About this explanation

Starting knowledge: Follow an ordered sequence, maintain a short list of recent items and sum integer costs.

Sources

  • Carnegie Mellon University, 15-213 — Introduction to Computer Systems: Cache Memories
  • Carnegie Mellon University, CSD PhD Blog — FIFO is Better than LRU: Cache eviction and recency context
← Grades 9–12 topics