Re: [PATCH] 2.2.17pre7 VM enhancement Re: I/O performance on

["Scott F. Kaplan" <sfkaplan@cs.amherst.edu>]

[Stephen C. Tweedie]
> > Having said that, LRU is certainly broken, but there are other ways to
> > fix it.
>
> Right.  LFU is just one way of fixing LRU.

I, too, am new to this mailing list, but since this comment was in
reference to the one made by Yannis, and I participated in the research
to which he mentioned, I'll chime in anyhow.

The problem is that LFU *doesn't* really fix LRU.  There are some cases
for which LRU performs as badly as possible.  (Imagine a 100 page memory
and a program that loops over 101 pages.)  In those cases, doing
*anything* that deviates from LRU will be an improvement; it's not much
of an accomplishment if LFU does well in this case, as RANDOM would be
an improvement as well.  Frequency isn't the right metric -- it just
allows for noise so that LFU can possibly do something different from
LRU.

There's lots of evidence that LFU can perform horribly, particularly
when the reference behavior changes (a.k.a. phase changes.)  Frequency
information doesn't reveal this change well, and the system can page
quite badly before the statistics come into line with the new behavior.

When LFU performs well, it's usually because of the skew in how often
recently used pages are re-used; that is, recently used pages *are* used
frequently.  It's when that association stops being true for a given set
of pages that a replacement policy must update its notion of the
program's behavior quickly.  LRU does so as quickly as the program can
touch some new pages.  LFU takes much longer.

LRU does the right thing in most cases.  With a little extra data, a
system can notice when LRU is doing the *wrong* thing, and only then
should non-LRU replacement be used.  At least, that's the basis of the
paper to which Yannis provided a reference.  I'll also throw out of a
reference to my dissertation, which has a more thorough (and, I hope,
better written!) discussion of recency, its uses, and the failings of
frequency information.  So, for anyone interested,
<http://www.cs.amherst.edu/~sfkaplan/papers/sfkaplan-dissertation.ps.gz>.

Scott Kaplan
sfkaplan@cs.amherst.edu
http://www.cs.amherst.edu/~sfkaplan
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/