Re: prefetching issues

Paul R. Wilson (wilson@cs.utexas.edu)
Sat, 19 Dec 1998 16:14:06 -0600


>From sct@redhat.com Sat Dec 19 07:18:21 1998
>Date: Sat, 19 Dec 1998 13:18:17 GMT
>From: "Stephen C. Tweedie" <sct@redhat.com>
>Subject: Re: prefetching issues
>
>Hi,
>
>On Fri, 18 Dec 1998 23:25:26 -0600, "Paul R. Wilson"
><wilson@cs.utexas.edu> said:
>
>> Here are some comments and some questions about prefetching. (It's
>> not clear to me yet what the new swap prefetching patches actually do.)
>
>They prefetch an aligned chunk (64k by default on machines with 32MB of
>memory or more) at once from disk.
>
> [...]
>
>> 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.)
>
>No, this won't happen, because...
>
>> 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.
>
>... we do this. Prefetches are deliberately NOT prefaulted, for
>precisely this reason. The prefetch remains in the page/swap cache, but
>does not get mapped into processes' page tables. As a result, the
>normal VM page recycling mechanism --- which already preferentially
>reaps cache pages before mapped pages --- will recycle these prefetched
>pages before it starts to throw out anything useful from process virtual
>address space.

Thanks for clarifying this. I'm having a rather hard time figuring
out what the VM code actually does. (There's not a lot of obvious
mechanism/policy separation, and the replacment algorithm seems
to be distributed among several components.)

What is the motivation for systematically preferring to evict mapped
pages rather than swapped pages? Is this based on tests that show
that it works better that way? My intuition would be that a simple
global replacement policy would work better, and the VM system could
be made simpler and easier to enhance. (Also, tags on pages could
be used to modify the replacement policy further back in the
pipeline, in a more modular way---pages would carry with them info
that could be used for prioritization.) I don't know what expertise has
one into the current design, though, and often researchers like me are
unaware of basic facts that implementors know about. (More's the pity.)

Since the system can handle eviction of mmapped pages, I'm wondering
if most of the swap space management code could be removed, and the
mapped file code could be used to handle normal swap duties. (Is
the separate-but-coordinated handling of file buffers, mmapped pages,
and plain swap pages intentional, or an artifact of evolutionary
development?) For my purposes, messing with the replacement policy
is very daunting because there's a lot of interacting code, much
of which I don't quite understand. (Especially with respect to
concurrency and the prioritization of different kinds of buffers.)
I'm wondering if I could simplify it somewhat with a *simple* hack to
bypass some of it; that might not actually make it better, but might
make it easier to experiment with.

-
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/