11 ms·

Do people really look for the best possible general-purpose cache eviction approach? It appears evident that there is no single approach that will work for all

Do people really look for the best possible general-purpose cache eviction approach? It appears evident that there is no single approach that will work for all workloads (i.e. combinations of access patterns, read/write ratios, scans, processor/cache parameters, etc.). Perhaps I am wrong, and there's a holy grail out there, but... If there is no single approach, shouldn't the focus be on matching algorithms to workloads? Better selection approaches would seem to yield far more value than yet another boutique algorithm.

jandrewrogers 3y ago
The optimal algorithm is not computable. Approximately optimal algorithms are computationally intractable for all practical systems. This is why practical real-world algorithms are all narrowly optimized, it is required to make the algorithm usefully tractable. It can also work relatively well if you can very narrowly define the workload characteristics you need to optimize for. 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.
- dist-epoch 3y ago
  What if you kept statistics of what access patterns you encounter every day. A lot of workloads do the same thing day in day out. Some workloads almost never scan, others only scan, it would be a quick win to automatically optimize these cases.
  - willcipriano 3y ago
    The JVM feels like it could do that sort of thing.
    - shermantanktop 3y ago
      That's pretty much what the self-tuning elements of JVM GCs are doing. I think we might label the overall problem as "non-computable" but we have real-world systems doing it all day long.
  - jayd16 3y ago
    Not necessarily if it takes time to collect, ingest and update the data structure. Many algorithms will rebalance based on usage but that also has a cost.
- jedberg 3y ago
  > 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
Having a strong default starting point is nothing to scoff at. You wouldn't want a standard library to use insertion sort because "no singular approach works optimally in all cases, so why bother trying for good general case?"

jandrewrogers 3y ago

The optimal algorithm is not computable. Approximately optimal algorithms are computationally intractable for all practical systems. This is why practical real-world algorithms are all narrowly optimized, it is required to make the algorithm usefully tractable. It can also work relatively well if you can very narrowly define the workload characteristics you need to optimize for. 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.

dist-epoch 3y ago
What if you kept statistics of what access patterns you encounter every day. A lot of workloads do the same thing day in day out. Some workloads almost never scan, others only scan, it would be a quick win to automatically optimize these cases.
- willcipriano 3y ago
  The JVM feels like it could do that sort of thing.
  - shermantanktop 3y ago
    That's pretty much what the self-tuning elements of JVM GCs are doing. I think we might label the overall problem as "non-computable" but we have real-world systems doing it all day long.
- jayd16 3y ago
  Not necessarily if it takes time to collect, ingest and update the data structure. Many algorithms will rebalance based on usage but that also has a cost.
jedberg 3y ago
> 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

Having a strong default starting point is nothing to scoff at. You wouldn't want a standard library to use insertion sort because "no singular approach works optimally in all cases, so why bother trying for good general case?"