# Bélády's Anomaly Doesn't Happen Often

DevFeed: [Bélády's Anomaly Doesn't Happen Often](<https://devfeed.tech/articles/belady-s-anomaly-doesn-t-happen-often-12540.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2023/06/23/belady.html>)

Author: Marc Brooker

Published: 2023-06-23T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [Caching](<https://devfeed.tech/topics/caching.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [systems](<https://devfeed.tech/topics/systems.md>), [benchmarking](<https://devfeed.tech/topics/benchmarking.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [cache](<https://devfeed.tech/tags/cache.md>), [performance](<https://devfeed.tech/tags/performance.md>), [simulation](<https://devfeed.tech/tags/simulation.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

The article examines Bélády's anomaly, in which increasing the size of a FIFO cache can reduce performance. It explains the phenomenon, contrasts FIFO with LRU, and reports simulations suggesting that the anomaly is uncommon in randomly generated access patterns, appearing in fewer than 0.175% of uniform patterns.

## Source excerpt

Bélády's Anomaly Doesn't Happen Often Anomaly is a really fun word. Try saying it ten times. It was 1969. The Summer of Love wasn't raging4, Hendrix was playing the anthem, and Forest Gump was running rampant. In New York, IBM researchers Bélády, Nelson, and Schedler were hot on the trail of something strange. They had a paging machine, a computer which kept its memory in pages, and sometimes moved those pages to storage. Weird1. It wasn't only the machine that was weird, it was their performance results. Sometimes, giving the machine more memory made it slower. Without modern spook-hunting conveniences like Scooby Doo and Bill Murray, they had to hunt the ghost themselves. What Bélády and team found is something now called Bélády's anomaly. In their 1969 paper3, they describe it like this: Running on a paging machine and using the FIFO replacement algorithm, there are instances when the program runs faster if one reduces the storage space allotted to it. More generally, this can happen with any FIFO cache: growing the cache can lead to worse results. This could, in theory, be a big problem for any tuning system or process which makes the assumption that growing the cache leads to better performance2. This doesn't happen with LRU. Just with FIFO, and with algorithms like LFU. Some point to Bélády's anomaly as a good reason for avoiding FIFO caches, even in systems where the reduced read-time coordination and space overhead would be a big win. But how frequent is Bélády's anomaly really? Do we, as system builders, really need to avoid FIFO caches because of it? One way to answer that question is how often we're likely to come across Bélády's anomaly purely by chance. It turns out that it doesn't happen very often at all. Starting with access patterns selected randomly with a uniform distribution of keys: and with a Zipf distribution of keys: In each simulation here, we're comparing caches of size N and N+1, and counting the cases where the smaller cache has a superio