5 ms·

So why did you say S3-FIFO has no loop resistance (or loop tolerance)?

falsandtru 3y ago
There is an established benchmark for testing loop resistance (GLI, Loop). S3-FIFO has not passed this test. And I have already confirmed that S3-FIFO does not pass the test.
- someplaceguy 3y ago
  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

There is an established benchmark for testing loop resistance (GLI, Loop). S3-FIFO has not passed this test. And I have already confirmed that S3-FIFO does not pass the test.

someplaceguy 3y ago
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