What I think is interesting is that LRU can substantially outperform random eviction (so well, in fact, that improvements over LRU offer quickly diminishing returns on many workloads), but you can approximate LRU quite well with a random algorithm. This appears to be true for many algorithms. The real world isn’t perfect, so perfect algorithms struggle to outperform alternatives.
What I think is interesting is that LRU can substantially outperform random eviction (so well, in fact, that improvements over LRU offer quickly diminishing returns on many workloads), but you can approximate LRU quite well with a random algorithm. This appears to be true for many algorithms. The real world isn’t perfect, so perfect algorithms struggle to outperform alternatives.