3 ms·

There are two important differences between academic and real-world cache replacement designs that should be kept in mind: First, most competent real-world des

There are two important differences between academic and real-world cache replacement designs that should be kept in mind: First, most competent real-world designs are considerably more complex than the academic model whence they are derived. Support for or resistance to many common cache patterns can often be grafted onto simpler academic designs, making them considerably more robust and flexible than academic analysis may suggest. Consequently, benchmarking performance of an academic design with other academic designs is not all that indicative of how it would perform against a real-world implementation. In practice, thoroughly engineered real-world designs all have similar cache hit rate characteristics regardless of the algorithm starting point because it is relatively straightforward to take ideas from other algorithms and make something that works similarly for your algorithm, albeit a bit less elegantly. Second, one of the most important properties of cache replacement algorithms that is often overlooked in academic literature is real-world computational cost and operation latency. It is not unusual for a disk cache to be accessed 10s of millions of times per second. This cost can vary by orders of magnitude across algorithm implementations that have similar cache hit rates. Consequently, you often go with a design that has excellent memory locality, efficient concurrency, minimizes CPU cache thrashing etc because that is what keeps cache replacement out of the profiler. Given the first point above, there is a bit of a convergent evolution in real-world cache replacement designs because this has a larger engineering impact than the specific algorithm you use. Heavy optimization of the CPU throughput characteristics severely restricts the practical design space, which tends to push you toward the same couple algorithm starting points. It is not intuitive to most software engineers that this is often the property you most optimize for, not things like cache hit rate, when they first get into the space. It is a fun design problem with a very high dimensionality tradeoff space.

1a1a11a 3y ago
Good points. The first point is probably true for most research in computer systems. Different systems have different constraints that make a simple design very complex or not possible. Can you elaborate on the second point more? It feels to me that S3-FIFO is optimized for latency, throughput, and scalability than existing algorithms (e.g., with multiple LRU queues).
- jandrewrogers 3y ago
  On the second point, there are a few different aspects that designs typically navigate. Effective thread concurrency used to be one, but the strong trend toward thread-per-core architecture has mooted that to a significant extent. More common is how many cold cache lines a cache replacement hits and how amenable the algorithm is to the CPU’s preference for sequential access. You are probably familiar with this problem but it is trickier than many average software devs allow. Basic CLOCK-derived algorithms are an obvious choice for CPU efficiency, and easy to patch up for most weaknesses, but when cache metadata becomes large, which is common on modern servers, they have a tendency to thrash the CPU cache for some access patterns. This has some pretty negative performance effects. Not having to worry about multithreading (because thread-per-core) enabled some modifications that came about as close I’ve seen to ensuring that cache replacement lives in hot CPU cache lines. This largely involves ensuring that you can find an immediately evictable buffer with a short scan with very high probability, and if that fails (a rare case), the scan metadata is so compressed that it often easily fits within L1. And that metadata is often evaluated with massive parallelism in a handful of clock cycles using vector intrinsics. AFAIK, these variants are the strongest cache replacement designs in terms of CPU efficiency (not necessarily cache hit rate for some access patterns). Some of the core techniques above are things I learned from other database kernel designers who themselves learned it from someone else. The scan length reduction technique was so elegant and obvious in hindsight that I am surprised that it never occurred to me or most anyone else (though it does make the designs more subtle). Quite a lot of these practical details have never been written down a far as I can tell, it is passed along as lore and beer convos. I am as guilty of this as anyone else. I thought the SIEVE algorithm was great, by the way! This area of research deserves far more attention than it seems to receive, most people act like it is a fully solved problem. Caches are in the hot path of everything. That said, in recent years I have become a lot more interested in the theoretical limits of effective cache replacement, regardless of algorithm. There are modern workloads that are asymptotically approaching randomness for all cache replacement even when the cache is 10-20% of the working set. Being able to narrowly split and assign workload to things that are effectively cacheable and things that are not is becoming important. I routinely deal with workloads now where <1% of the working set fits in memory, and it is becoming more common. Caching is important but the impact on overall performance is diminishing.

1a1a11a 3y ago

Good points. The first point is probably true for most research in computer systems. Different systems have different constraints that make a simple design very complex or not possible. Can you elaborate on the second point more? It feels to me that S3-FIFO is optimized for latency, throughput, and scalability than existing algorithms (e.g., with multiple LRU queues).

jandrewrogers 3y ago
On the second point, there are a few different aspects that designs typically navigate. Effective thread concurrency used to be one, but the strong trend toward thread-per-core architecture has mooted that to a significant extent. More common is how many cold cache lines a cache replacement hits and how amenable the algorithm is to the CPU’s preference for sequential access. You are probably familiar with this problem but it is trickier than many average software devs allow. Basic CLOCK-derived algorithms are an obvious choice for CPU efficiency, and easy to patch up for most weaknesses, but when cache metadata becomes large, which is common on modern servers, they have a tendency to thrash the CPU cache for some access patterns. This has some pretty negative performance effects. Not having to worry about multithreading (because thread-per-core) enabled some modifications that came about as close I’ve seen to ensuring that cache replacement lives in hot CPU cache lines. This largely involves ensuring that you can find an immediately evictable buffer with a short scan with very high probability, and if that fails (a rare case), the scan metadata is so compressed that it often easily fits within L1. And that metadata is often evaluated with massive parallelism in a handful of clock cycles using vector intrinsics. AFAIK, these variants are the strongest cache replacement designs in terms of CPU efficiency (not necessarily cache hit rate for some access patterns). Some of the core techniques above are things I learned from other database kernel designers who themselves learned it from someone else. The scan length reduction technique was so elegant and obvious in hindsight that I am surprised that it never occurred to me or most anyone else (though it does make the designs more subtle). Quite a lot of these practical details have never been written down a far as I can tell, it is passed along as lore and beer convos. I am as guilty of this as anyone else. I thought the SIEVE algorithm was great, by the way! This area of research deserves far more attention than it seems to receive, most people act like it is a fully solved problem. Caches are in the hot path of everything. That said, in recent years I have become a lot more interested in the theoretical limits of effective cache replacement, regardless of algorithm. There are modern workloads that are asymptotically approaching randomness for all cache replacement even when the cache is 10-20% of the working set. Being able to narrowly split and assign workload to things that are effectively cacheable and things that are not is becoming important. I routinely deal with workloads now where <1% of the working set fits in memory, and it is becoming more common. Caching is important but the impact on overall performance is diminishing.