ARC, anyone?
ARC, anyone?
Posted Mar 6, 2026 13:42 UTC (Fri) by PeeWee (subscriber, #175777)In reply to: ARC, anyone? by intelfx
Parent article: Reconsidering the multi-generational LRU
IIUC, we sort of already do have, or had(?), an approximation of that with "classic" LRU. The active/inactive lists track frequency/recency respectively, kind of. And there is also refault distance tracking, though it seems to be limited to file pages, which should make no difference for a comparison to ARC.
Thus Linux already has ARC-but-not-ARC. File pages start life on the inactive list, after being initially faulted in. That's almost identical to what happens in ZFS ARC [PDF] (p. 13f); total misses - the page wasn't even on one of the ghost lists - are put at the head of the LRU list, Linux's inactive list being the equivalent. Only after being accessed again will they be promoted to the active list, hence they get promoted due to frequent access, otherwise they'd already be evicted again, possible still in some shadow entry. But a promotion to the active list implies a minor/soft page fault - inactive pages get unmapped but not evicted -, so it's not exactly the same as in ARC, where pages are simply promoted to the LFU list, no fault having happened, so slight advantage for ARC, maybe, depending on the LFU list overhead, see below. Arguably, that makes Linux's active list an LFU list in disguise, sans the access counter. The only way to eviction is by being less frequently accessed than other active pages; and to get on the active list, file pages need to be accessed a second time. And that's where the equivalency breaks, because in ARC it would be evicted but placed at the head of the ghost LFU list, whereas in Linux it gets unmapped and placed at the head of the inactive list for being the most recent visitor in purgatory. Reiterating, in Linux mm terms, file pages age out of the active list because they are not accessed frequently (enough) onto the inactive list and then onto the shadow "list" (entries in the radix tree, according to above article), after being evicted for not being accessed recently. If they get refauted in and there is still a shadow entry, one page gets demoted from the active list right next to the refaulted one, thus shortening the active list and lengthening the inactive list by one, respectively, if the refault distance (how many page faults were handled in its absence) is less than the length of the active list. There is no mention of what happens when refault distance is equal or greater than the length of the active list, so I am assuming no additional action takes place in that case. Also, since all of the above is in context of file-backed pages, I just want to add that anon pages only differ in that they are immediately placed on the active list after faulting them in, which might have implications regarding their exact refault behavior and which list to adjust, but I don't even know if it even applies there; couldn't find anything on anon refault distance tracking. There may also be other reasons for not having an ARC clone in Linux. As that presentation above states, LFU lists are of O(log(n)) complexity. Maybe that implies, it only makes sense for file pages, the overhead being small enough compared to the cost of a major fault, hitting spinning rust I/O. But it might be too much for tracking in-memory pages for frequency, if all that buys us is avoiding a minor fault - still considering the active list as LFU. Just assuming that active pages are frequently accessed might be the cheaper option, since aging out does not mean eviction, only demotion to a lower "tier", with tolerable (soft) refault cost. It's also hard to tell if it is ("remotely") competitive with ARC, at least for me. ZFS (ARC) has great tools and stats, but I wouldn't know where to find their equivalents in Linux, e.g. hit and miss rates on said active/inactive/shadow lists. Plus, ZFS ARC can optionally store compressed blocks, which need to be decompressed on access, just to name one more variable; I am almost sure that the compressed version stays in ARC and the decompressed one lives in the page cache, at least in ZFS on Linux (ZoL). That, if true, may have interesting effects, because really hot read-only pages, i.e. always clean (not dirtied, which would invalidate the ARC cache entry), never to be evicted from the page cache, their compressed siblings may get evicted from ARC, because, for all it knows, they are cold; I'd call that a temperature paradox, for lack of a better term, if there isn't already a name for it. But maybe I am totally misunderstanding how ZoL integrates with vanilla Linux. One more question just popped into my head; if ARC is so superior, then why was it only implemented for ZFS and not also in the swap path of Solaris? Did Sun Microsystems simply not think of that, or the Illumos developers, for that matter? Maybe that does speak to the relative cost compared to simpler solutions.