Cache replacement algorithms are in the family of universal sequence prediction problems. These problems are unfortunately related to the problem of generally optimal AI/learning algorithms, which gives you a sense of why the task is so difficult.
Cache replacement algorithms are in the family of universal sequence prediction problems. These problems are unfortunately related to the problem of generally optimal AI/learning algorithms, which gives you a sense of why the task is so difficult.
No but it's easily findable. If you have a group of say 10 cache machines, you can set each one to a different eviction algorithm, and then track misses, hits, and eviction rates. You can even use a one-arm bandit algo for the algos if you want to be really thorough.
But the main question would be why? In 99.9% of cases, the cache eviction algorithm is not going to be your bottleneck. So might as well just use LRU and move on to more important problems.
It really isn't. This has been known for things like silicon design since at least the 1980s, and there are a few different seemingly basic properties that make an otherwise simple data model have intrinsically poor cache characteristics. One of the best known is the use of high-dimensionality access methods (e.g. graphics, spatial, graph, etc processing).
The traditional solution to cache replacement intractability is latency hiding architectures (e.g. GPUs, barrel processors, etc) for applications that are mostly about throughput. In fact, this is a reasonable working definition of the difference between latency-oriented and throughput-oriented design (caching versus latency hiding).
> In 99.9% of cases, the cache eviction algorithm is not going to be your bottleneck.
What types of cases are we talking about here? For data intensive applications like database engines, using a naive algorithm like LRU will definitely show up in the profiler unless the rest of your code is similarly naive. You don't notice it for high-throughput workhorse systems because someone else has already spent a lot of time tweaking and optimizing this, using some combination of caching and latency hiding.
Or if you're implementing a feature in the standard library of a widely used language, the effects of your choice may be enormous.
Sure, and that would be the 0.1% of the time where it make sense.
> if you're implementing a feature in the standard library of a widely used language
I would contend that unless your library is very opinionated on exactly how data will be accessed, you can't possibly optimize cache access in a way that makes sense for every user.
Insertion sort is heuristically good in many practical circumstances. You wouldn't call it optimal, nor choose to use it as your general-purpose sorting algorithm.