Multigenerational LRU Code Updated For Enhancing Linux Kernel Performance

Written by Michael Larabel in Linux Kernel on 13 April 2021 at 08:44 AM EDT. 4 Comments
LINUX KERNEL
Last month Google engineers proposed multi-generational LRU for Linux to enhance the kernel performance and today the work has advanced to a second version.

Google's Yu Zhao announced the "v2" of the multigenerational LRU framework today for the Linux kernel. The key takeaway from this work remains: "The current page reclaim is too expensive in terms of CPU usage and often making poor choices about what to evict. We would like to offer an alternative framework that is performant, versatile and straightforward."

As noted in the original article on the matter, the multi-generational LRU code in its preliminary form was found to yield ~18% fewer low-memory kills on Android, reducing cold starts by 16%, on Chrome OS there were ~96% fewwer low-memory tab discards and 59% fewer out-of-memory kills on fully-utilized devices. Google's testing found a "significant reduction" in CPU usage with this proposed multi-generational LRU (Least Recently Used) framework.

With today's v2 patches the noted changes include addressing a buffered I/O regression and benchmarking there to now show a 14% improvement in IOPS when randomly accessing a SSD in the buffered I/O mode. The v2 patches introduce the notions of tiers:
This version includes the support of tiers, which represent levels of usage from file descriptors only. Pages accessed N times via file descriptors belong to tier order_base_2(N). Each generation contains at most MAX_NR_TIERS tiers, and they require additional MAX_NR_TIERS-2 bits in page->flags. In contrast to moving across generations which requires the lru lock, moving across tiers only involves an atomic operation on page->flags and therefore has a negligible cost. A feedback loop modeled after the well-known PID controller monitors the refault rates across all tiers and decides when to activate pages from which tiers, on the reclaim path.

Given the timing of the latest patches and the work still appearing to be tested and reviewed by upstream developers, multi-generational LRU will presumably not make it into the upcoming Linux 5.13 cycle but we'll continue monitoring this exciting work as well as delivering our own benchmarks when it looks like the code churn has settled down.
Related News
About The Author
Michael Larabel

Michael Larabel is the principal author of Phoronix.com and founded the site in 2004 with a focus on enriching the Linux hardware experience. Michael has written more than 20,000 articles covering the state of Linux hardware support, Linux performance, graphics drivers, and other topics. Michael is also the lead developer of the Phoronix Test Suite, Phoromatic, and OpenBenchmarking.org automated benchmarking software. He can be followed via Twitter, LinkedIn, or contacted via MichaelLarabel.com.

Popular News This Week