The one problem with LRU that I always remember is one John Carmack one wrote about with an LRU cache for items that were always accessed in the same order (obj

The one problem with LRU that I always remember is one John Carmack one wrote about with an LRU cache for items that were always accessed in the same order (objects to be rendered, in z-order?), which happened to be slightly bigger than the frequently-accessed set... until the day it wasn't. And performance suddenly dropped off a massive cliff. The problem, it turned out, was that iterating through the same frequently accessed set of items, 1...N, in the same order every time, with an LRU cache of size N-1, would put items 1...N-1 in the cache, and then on the very last step evict item 1 (because it was the oldest) to put in item N. The next time round, when item 1 was not in the cache, it would evict item 2 (the oldest) to make way for item 1. And then evict item 3 to make way for item 2, evict 4 for 3, etc..., until finally evicting item 1 (again) to make way for item N. And do the same on the next iteration. IIRC, he solved it by switching one of the cache slots as a "scratch" slot for the current iteration, so the last few items in the set would only overwrite each other, and items 1...C-1 would remain in the cache for the next iteration (where C is the size of the cache). It is an unusual use case, to be sure, and not a reason to avoid LRU caches in general. Most users are unlikely to hit it. But it's useful considering as an example of how edge cases can pop up in places you might not have been expecting. It also shows you don't necessarily need to completely switch algorithms if you hit a pathological case - just tweaking how the cache works slightly (LRU to LRU-plus-scratch-slot) can sometimes get you back to 95% of where you were, which might be good enough.