4 ms·
A FIFO cache of this kind can be very bad in some situations. Imagine if you have a cache of 8 entries and the application reads 9 entries in a loop from beginn
by quelsolaar 6y ago
A FIFO cache of this kind can be very bad in some situations. Imagine if you have a cache of 8 entries and the application reads 9 entries in a loop from beginning to end over and over. In this case the FIFO cache algorithm will always eject the next entry just before its needed. Ejecting even a random entry is much better.
Its an incredibly difficult problem to try to figure out what to keep in cache, so I find that the first thing one should allow is for the user to give hints.
It would be great if there was a way for applications to designate some memory allocations as "hot" or "cold" to indicate the usage pattern, or indicate that its reading something linearly, or that its about to need something.
- NovaX 6y agoThat assumes the developer can provide correct hints, which unfortunately is rarely true. In my experience it is better to invest in an algorithm that can detect these patterns, learn from the workload, and optimize accordingly. Modern cache policies are robustly near optimal, but developers don't bother to implement them.
- matheusmoreira 6y agoThis is the point of the madvise system call. https://www.man7.org/linux/man-pages/man2/madvise.2.html https://www.man7.org/linux/man-pages/man2/madvise.2.html > MADV_RANDOM > MADV_SEQUENTIAL > MADV_WILLNEED > MADV_DONTNEED > MADV_COLD > MADV_PAGEOUT > MADV_DONTDUMP > MADV_WIPEONFORK
- quelsolaar 6y agoThanks!
- dr_zoidberg 6y agoBut this algorithm isn't a FIFO: it's a multi-generational LRU cache. That means, LRU+some extra details (evry well explained in the post) to make it perform even better. There are some metrics in the post, and some in the comments here too.