3 ms·

> The optimal algorithm is not computable No but it's easily findable. If you have a group of say 10 cache machines, you can set each one to a different evict

> The optimal algorithm is not computable 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.

onetoo 3y ago
Strictly speaking, that approach would help you find a heuristically good algorithm, but not necessarily the optimal one. Those are very different.
- jedberg 3y ago
  But does it matter to anyone other than an academic? In practice the heuristically good == optimal.
  - onetoo 3y ago
    We should use the right words for things. 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.
Jabbles 3y ago
If you have 1e4 machines and run a global video distribution network it might be worth an engineer's salary to look into it. Or if you're implementing a feature in the standard library of a widely used language, the effects of your choice may be enormous.
- jedberg 3y ago
  > If you have 1e4 machines and run a global video distribution network it might be worth an engineer's salary to look into it. 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.
  - onetoo 3y ago
    You can't possibly optimize sorting in a way that makes sense for every user. Let us use insertion sort in our standard library and call it a day. Why are you bothering to discuss general-case sorting algorithms?
deleted 3y ago
[deleted]
jandrewrogers 3y ago
> No but it's easily findable 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.

onetoo 3y ago

Strictly speaking, that approach would help you find a heuristically good algorithm, but not necessarily the optimal one. Those are very different.

jedberg 3y ago
But does it matter to anyone other than an academic? In practice the heuristically good == optimal.
- onetoo 3y ago
  We should use the right words for things. 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.

Jabbles 3y ago

If you have 1e4 machines and run a global video distribution network it might be worth an engineer's salary to look into it. Or if you're implementing a feature in the standard library of a widely used language, the effects of your choice may be enormous.

jedberg 3y ago
> If you have 1e4 machines and run a global video distribution network it might be worth an engineer's salary to look into it. 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.
- onetoo 3y ago
  You can't possibly optimize sorting in a way that makes sense for every user. Let us use insertion sort in our standard library and call it a day. Why are you bothering to discuss general-case sorting algorithms?

deleted 3y ago

[deleted]

jandrewrogers 3y ago

> No but it's easily findable 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.