4 ms·

The design of S3-FIFO seems to imply it should handle all loops less than 90% of the cache size pretty well, perhaps even up to 100%. Did you figure out why it

The design of S3-FIFO seems to imply it should handle all loops less than 90% of the cache size pretty well, perhaps even up to 100%. Did you figure out why it did not pass the test? Was there a bug in the implementation, perhaps? Also, where can I find the benchmark you speak of? My web search did not find anything.

falsandtru 3y ago
My implementation is reviewed and linked from the official S3-FIFO page. https://s3fifo.com https://s3fifo.com A benchmark is as follows. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency I can't deal with you any longer. Over.
- NovaX 3y ago
  /u/someplaceguy, Those LIRS traces, along with many others, are available at this page [1]. I did a cursory review using their traces with Caffeine's and the author's simulators to avoid bias or a mistaken implementation. In their target workloads Caffeine was on par or better [2]. I have not seen anything novel in this or their previous works and find their claims to be easily disproven, so I have not implement this policy in Caffeine’s simulator yet. [1]: https://github.com/ben-manes/caffeine/wiki/Simulator https://github.com/ben-manes/caffeine/wiki/Simulator [2]: https://github.com/1a1a11a/libCacheSim/discussions/20 https://github.com/1a1a11a/libCacheSim/discussions/20
  - falsandtru 3y ago
    I did a comparison on your data sets such as DS1, and S3-FIFO had very lower hit ratios than LRU in most cases. I think there are very limited situations where S3-FIFO is best.
    - 1a1a11a 3y ago
      You evaluated a single trace (from twenty years ago) and claimed that S3-FIFO is worse; why not show more traces? Most of the traces we used are open-source and can be found here. https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-file#open-source-cache-traces-and-the-people-behind-them https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-fi... Disclaimer: This is the author of S3-FIFO.
  - 1a1a11a 3y ago
    Hi Ben, "I have not seen anything novel in this or their previous works and find their claims to be easily disproven" is a big statement. We evaluated over 6000 workloads from 14 sources (Meta, Twitter, Microsoft, Wikipedia, VMWare, multiple CDNs, Tencent, Alibaba...), collected from 2007 to 2023. Most of the workloads we used are open-source and available to be verified [1]. If you want to claim that TinyLFU is better, you cannot just show it is better on one trace from 20 years ago. I wish this is not how you disprove a better algorithm. Disclaim: this is the author of S3-FIFO. We have never claimed that S3-FIFO is the best on every trace. We observed that quick demotion[2] is important to achieve a low miss ratio in modern cache workloads, and existing algorithms such as TinyLFU and LIRS have lower miss ratios because of the small 1% window they use. This motivated us to design S3-FIFO, which uses simple FIFO queues to achieve low miss ratios. It is true that compared to state-of-the-art, S3-FIFO does not use any fancy techniques, but this does not mean it has bad performance. In our large-scale evaluations, we found that the fancy techniques in LIRS, ARC, and TinyLFU can sometimes increase the miss ratio. But simple FIFO queues are more robust. However, *it is not true that S3-FIFO is better on every trace*. * Note that some of the S3-FIFO results in Otter's repo are not updated and have an implementation bug, and we are working with the owner to update them. [1] https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-file#open-source-cache-traces-and-the-people-behind-them https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-fi... [2] https://dl.acm.org/doi/10.1145/3593856.3595887 https://dl.acm.org/doi/10.1145/3593856.3595887
    - maypok86 3y ago
      Hmm, I'd like to know more about the bugs and not updated results. It seems that all the bugs that were there long ago have been fixed (and even with some improvements). And the results show the latest version's performance. Especially since S3-FIFO shows very good results, in fact, inferior only to the adaptive version of W-TinyLFU on S3 and DS1 traces. And about lock-free queues I don't agree, what they do with the implementation can be seen on the example of theine Reads 100% graph in the otter repository, if it wasn't there, it would be equal in speed to ristretto. And the BP-Wrapper technique actually has a huge engineering plus: it allows you to focus on optimizing different components of the system individually and easily make changes to the eviction policy that lock-free queues can't give to the developer.

falsandtru 3y ago

My implementation is reviewed and linked from the official S3-FIFO page. https://s3fifo.com https://s3fifo.com A benchmark is as follows. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency I can't deal with you any longer. Over.

NovaX 3y ago
/u/someplaceguy, Those LIRS traces, along with many others, are available at this page [1]. I did a cursory review using their traces with Caffeine's and the author's simulators to avoid bias or a mistaken implementation. In their target workloads Caffeine was on par or better [2]. I have not seen anything novel in this or their previous works and find their claims to be easily disproven, so I have not implement this policy in Caffeine’s simulator yet. [1]: https://github.com/ben-manes/caffeine/wiki/Simulator https://github.com/ben-manes/caffeine/wiki/Simulator [2]: https://github.com/1a1a11a/libCacheSim/discussions/20 https://github.com/1a1a11a/libCacheSim/discussions/20
- falsandtru 3y ago
  I did a comparison on your data sets such as DS1, and S3-FIFO had very lower hit ratios than LRU in most cases. I think there are very limited situations where S3-FIFO is best.
  - 1a1a11a 3y ago
    You evaluated a single trace (from twenty years ago) and claimed that S3-FIFO is worse; why not show more traces? Most of the traces we used are open-source and can be found here. https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-file#open-source-cache-traces-and-the-people-behind-them https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-fi... Disclaimer: This is the author of S3-FIFO.
- 1a1a11a 3y ago
  Hi Ben, "I have not seen anything novel in this or their previous works and find their claims to be easily disproven" is a big statement. We evaluated over 6000 workloads from 14 sources (Meta, Twitter, Microsoft, Wikipedia, VMWare, multiple CDNs, Tencent, Alibaba...), collected from 2007 to 2023. Most of the workloads we used are open-source and available to be verified [1]. If you want to claim that TinyLFU is better, you cannot just show it is better on one trace from 20 years ago. I wish this is not how you disprove a better algorithm. Disclaim: this is the author of S3-FIFO. We have never claimed that S3-FIFO is the best on every trace. We observed that quick demotion[2] is important to achieve a low miss ratio in modern cache workloads, and existing algorithms such as TinyLFU and LIRS have lower miss ratios because of the small 1% window they use. This motivated us to design S3-FIFO, which uses simple FIFO queues to achieve low miss ratios. It is true that compared to state-of-the-art, S3-FIFO does not use any fancy techniques, but this does not mean it has bad performance. In our large-scale evaluations, we found that the fancy techniques in LIRS, ARC, and TinyLFU can sometimes increase the miss ratio. But simple FIFO queues are more robust. However, *it is not true that S3-FIFO is better on every trace*. * Note that some of the S3-FIFO results in Otter's repo are not updated and have an implementation bug, and we are working with the owner to update them. [1] https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-file#open-source-cache-traces-and-the-people-behind-them https://github.com/Thesys-lab/sosp23-s3fifo?tab=readme-ov-fi... [2] https://dl.acm.org/doi/10.1145/3593856.3595887 https://dl.acm.org/doi/10.1145/3593856.3595887
  - maypok86 3y ago
    Hmm, I'd like to know more about the bugs and not updated results. It seems that all the bugs that were there long ago have been fixed (and even with some improvements). And the results show the latest version's performance. Especially since S3-FIFO shows very good results, in fact, inferior only to the adaptive version of W-TinyLFU on S3 and DS1 traces. And about lock-free queues I don't agree, what they do with the implementation can be seen on the example of theine Reads 100% graph in the otter repository, if it wasn't there, it would be equal in speed to ristretto. And the BP-Wrapper technique actually has a huge engineering plus: it allows you to focus on optimizing different components of the system individually and easily make changes to the eviction policy that lock-free queues can't give to the developer.