News for hackers. Stuff that matters.
Re:Linux Kernel: The multi-generational LRU by quelsolaar on Monday April 19, 2021 @02:03PM (#26866037)
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.

Re:Linux Kernel: The multi-generational LRU by dr_zoidberg on Monday April 19, 2021 @04:34PM (#26867664)
But 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.
Re:Linux Kernel: The multi-generational LRU by matheusmoreira on Monday April 19, 2021 @04:10PM (#26867404)
This is the point of the madvise system call.

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

Re:Linux Kernel: The multi-generational LRU by quelsolaar on Monday April 19, 2021 @06:29PM (#26868602)
Thanks!
Re:Linux Kernel: The multi-generational LRU by NovaX on Monday April 19, 2021 @03:36PM (#26867033)
That 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.