Aggressive prefetching (swap readahead and readbehind) is generally
a good idea given the horrible imbalance between seek times and
transfer times for VM pages.
However, it's important to realize that there are two different costs
to aggressive prefetching: increased transfer times and cache pollution.
If the transfer time is small relative to the latency, as it will
be for any small number of pages, you can mostly ignore the transfer
time issue. For some programs, though, the cache pollution is important;
if a program has bad spatial locality, aggressive prefetching may just
push the active pages out of the memory that much faster.
In the worst case, prefetching 16 pages at a time will effectively cut
your memory size by a factor of 16. Something like this worst case can
actually occur in practice, for example with very large hash tables that
are probed randomly but with a definite bias in the probe key distribution.
(I know of some programs that do this sort of thing, but I don't know
how common they are.)
To avoid the massive cache pollution in the bad cases, you want to
preferentially evict pages that are prefetched but go untouched for
some time. Most prefetches pay off relatively soon---a successfully
prefetched block is often touched almost immediately. If you limit
the memory devoted to prefetched-but-untouched pages, you can put
a bound on the damage done by cache pollution. For example, if you
never use more than 20% of your memory to hold prefetched-but-not-yet-touched
pages, then the pollution will only cut your effective memory size by
20% in the worst case. (In the good cases, they'll take up almost zero
percent of your memory, because you'll actually touch them and make
them normal pages.)
You do want to allow prefetched pages to use some significant *percentage*
of your memory, however, because prefetched pages may be touched "soon"
after they're prefetched, but not immediately. (The maximum memory used for
prefetching shouldn't be a fixed number of blocks---it should be proportional
to the memory size.) We see this behavior fairly commonly in locality
analyses of various programs.
A better policy (but slightly more complicated) would be adaptive, and
would notice whether keeping prefetched pages around for a given amount
of "time" is paying off, or would pay off, and would adjust the priority
of normal pages vs. prefetched pages dynamically. The key idea here
is to keep an LRU list of prefetched pages, or pages you *would* have
prefetched, and see how often you touch pages at various distances
down that list. If you touch very few pages past the beginning of
that list, you can reduce the amount of memory allocated to prefetched
pages, because it's a waste of space. If you touch lots of pages
far down the list, you can increase the amount of memory allocated to
prefetched pages, so that those will be hits. (This assumes that near-future
behavior of the workload will be similar to recent-past behavior; it
usually is.)
This could easily be generalized to keep more detailed stats on whether
prefetching n pages would pay off, for several values of n, and adjust
actual prefetching accordingly.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/