For compressed page caching to be a win, you need to be able to compress
and decompress pages very quickly. We can compress and decompress a
4KB page in under a fifth of a millisecond on a fast machine (400 MHz
Pentium II). That's over 20 MB/sec compressed AND decompressed, which
matches the average *bandwidth* of a fast disk. We're getting about a
factor of two in compression, for a variety of C and C++ programs's
in-memory data, which our simulations indicate is enough to get tens of
percent speedup for most programs, most of the time, assuming a 2.5
millisecond average disk fetch cost for a 4 KB page.
Your mileage will vary, especially as your CPU speed and disk fetch
cost vary. (I noticed that Linux's disk fetch costs is varying a lot
over the last few days. Does anybody have actual measurements of
how much it costs, on average, to fetch a 4KB page with the
new prefetching scheme? Even very crude measurements would
be interesting---e.g., a count of faults vs. runtime for program
that is clearly paging-bound.)
For compressed paging to be a consistent win, though, you have to
compress and decompress several times faster than the average page
transfer cost to disk. This is because you're decreasing the size
of your uncompressed (normal) page cache as you allocate pages to
the compression cache. As you allocate more memory to the uncompressed
cache, the miss rate for the normal paging cache goes up more rapidly
than the disk fault rate goes down---that's because miss-rate curves
are usually concave upward.
An important part of making compressed caching a win is to turn it
off when you don't need it, and turn it up when it'll do the most
good. An example of the former case is a program whose working
set barely fits in memory, but fits. It doesn't need compression
to achieve a low fault rate, and having a large compression cache
will only incur cost. An example of the latter is a program whose
working set doesn't fit in memory, but would with a moderate-sized
compression cache. (Actually, it's more subtle than that, but not
a whole lot more subtle---not hard to hack if you know what to do.)
My group has developed an adaptive cache-sizing algorithm that works
well---it's self-tuning and (in simulation) does the right thing for
a variety of programs over a large range of memory sizes. (There are
some limitations to our simulations, however, because of limitations
in our tracing tool.) We're developing a variety of adaptive replacement
and prefetching algorithms that may be of interest.
I'd be happy to donate the compression and adaptive replacement algorithms
for use in Linux if somebody will help me get the right hooks into the
kernel. (I'll probably do it myself if necessary, but it may take
me some time since I'm not a kernel hacker.)
In the short term, I'm interested in gathering traces of paging traffic
for Linux systems, so that we can run them through our simulators and
see what will work best for Linux specifically. (I am currently looking
at special algorithms for detecting and compressing x86 machine code. Others
have done a good job of this in terms of compression ratios, but I want to
do a pretty good job *really*fast*, for compressed paging purposes.)
Does anybody have any recommendations as to how to capture traces of
the actual contents of pages that are fetched and evicted? I'm thinking
of a procfs trick or a loopback fs trick of some kind, but I'm not
sure what the easiest thing to do is.
I'm also interested in any measurements of the software overheads involved
in Linux paging and file access. E.g., if I implement compressed caching
in a file system and swap off of that, what will the page trap and
file system dispatching overheads be? (To get really good performance
for adaptive cache-sizing, it may be necessary to coordinate with the
swap cache.)
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wilson@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
-
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/