Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
> When Are Randomized Algorithms Better Than LRU?<p>When the access pattern is random: recently used items are <i>not</i> more likely to be accessed than other items.<p>Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items.<p>This is undergraduate stuff I once had to know for exams in machine architectures and operating systems.<p>The choice of LRU replacement is favorable when there exists "locality of reference"; that's what it's predicated upon.<p>All of the replacement policy choices are only substitutes for a "magic oracle": a replacement strategy which can peer into the future and know which items will be accessed soonest. With a magic oracle, we can not only retain those items in the cache in preference to other items, to great advantage, but we can automatically prefetch the correct items that are not yet in the cache but are about to be accessed.<p>In general, randomized algorithms provide a defense against situations in which things don't work out according to the best case assumptions. For instance, they help defend against tickling worst cases in algorithms (e.g. sorting) that have good average-case behavior.