Messages in this thread | | | From | "Paul R. Wilson" <> | Date | Fri, 18 Dec 1998 23:25:26 -0600 | Subject | prefetching issues |
| |
Here are some comments and some questions about prefetching. (It's not clear to me yet what the new swap prefetching patches actually do.)
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/
| |