How computers decide which data to discard when their memory is completely full

How computers decide which data to discard when their memory is completely full
Image: Intellect (generated)

In short: When a computer cache reaches capacity, it must instantly decide which information to sacrifice to make room for new data. This choice is a high-stakes compromise between speed and accuracy, as the wrong decision can trigger a performance-killing cascade of delays known as cache pollution or thrashing.

At the heart of cache management lies a fundamental trade-off between latency and hit ratio. Latency measures the time required to retrieve a requested item, while the hit ratio tracks how often the system successfully finds that item in the cache. Because predicting the future is impossible, the ideal strategy—Bélády’s optimal algorithm, which discards the data needed furthest in the future—remains a theoretical benchmark rather than a practical tool.

Engineers instead rely on various heuristics. Simple approaches like First-In-First-Out (FIFO) or Last-In-First-Out (LIFO) treat the cache like a queue or stack, ignoring usage frequency entirely. More sophisticated methods attempt to track access patterns. Least Recently Used (LRU) discards the oldest items, but it becomes prohibitively expensive to implement in hardware as cache associativity grows. Consequently, designers often use approximations like Pseudo-LRU (PLRU), which uses binary tree pointers to identify candidates for eviction with minimal overhead.

Modern workloads have forced further innovation. Streaming data, which is often read only once, can easily overwhelm traditional caches, leading to the development of scan-resistant policies. For instance, Intel’s Re-Reference Interval Prediction (RRIP) assigns prediction values to cache lines, prioritizing the eviction of data that is unlikely to be reused. Other specialized algorithms like SIEVE or S3-FIFO use multi-queue structures to filter out one-hit-wonders, ensuring that only truly valuable, frequently accessed data occupies the limited, high-speed memory space.

The choice of algorithm is rarely universal. A policy that excels in a distributed network, such as Time-Aware Least Recently Used (TLRU), might be useless for a CPU cache. By balancing the cost of tracking usage history against the performance gains of higher hit rates, these algorithms ensure that modern computing systems remain responsive even when handling massive, complex datasets.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-cache-replacement-policies.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…