[linux-mm-cc] kernel make benchmark on small x86 desktop

[John McCabe-Dansted]

On Mon, Apr 14, 2008 at 4:09 PM, Nai Xia <nai.xia at gmail.com> wrote:
>  >  In case (1), compcache should send all pages to physical device.
>
>  So this can be achieved by making bio requests to the block layer
>  without invading the kernel itself?
>  I'd like to have a try in the following days after I go through the
>  related kernel parts.

Yes, we just have to swap out stale pages to disk.

I don't know how Nitin Gupta is planning to do this, but here is a
design I have come up with. (Nitin: do you have any comments? Is this
useful?)

I was thinking of adding an age field for compcache's table of pages,
with age measured in units of #accesses divided by #pages. When the
pages reach a particular age we swap them out to disk or recompress
them with a  secondary compressor. The secondary compressor should
either give tighter compression (presumably as expense of speed) or
simply be different and thus be able to shrink some pages the primary
compressor to poorly suited to handle. Psuedo code follows below:

---

compressor[0] = lzo
compressor[1] = deflate
# It would be better to use a WK compressor
# rather than another LZ77 compressor like deflate,
# so we get strengths of both WK and LZ compressors.
# Deflate is currently in kernel, but we could distribute WK
# in third party package if important.
# compressor[1] = WK4x4
compressor[2] = swapfile


max_age[0]=4 # min age before we switch from lzo to deflate
max_age[1]=16 # min age before we write to swapfile

# may want to dynamically adjust max_age[1] to keep memory_usage reasonable.

page_iterator = iterator ( page_table )

BEGIN on_compcache_access(access_page,...)
if read
    handle_read()
else
    handle_write()
access_page.age=0

page=page_iterator.next()
page.age++
if page.age >= max_age[page.last_compressor]
    page.last_compressor++
    change page.actual_compressor to page.last_compressor IF this saves memory
fi
END # on_compcache_access

--

We could also dynamically adjust the max_age to keep compcache memory
usage under some % of memory, even for a very large ramzswap device
size.

This approach has a few advantages:

1) page.age could be a single byte, which could be easily accommodated
in existing structure. Now that the table is word aligned, we could
fit a 1-byte age field (0..255) and a 1-byte compressor bit-field
(0..15 for actual_compressor and last_compressor: 16 compressors
should be enough for anyone.) in compcaches table of pages without
increasing the amount of memory required. AFAICT a LRU list would
require a doubly linked list of ages, which would require 8 bytes per
4096-byte page. This is about 0.4% of the size of a compressed page,
so is not totally insignificant.

2) If we loop through memory, then the pages being looped through will
have an age of zero or one and thus will remain in compcache, while
the age of memory not accessed will increase until it is swapped out.
Thus for simple uniform access of the working set, this approach would
converge on optimum compcache size. With some tweaking, it might also
converge on a reasonable size in other cases. Unlike some other
compressed caching dynamic sizing policies, this approach does not
need any information about the use frequency graph for pages not
swapped out and thus not managed by compcache, information which might
be hard to get efficiently without inserting hooks in the kernel.

Also, if the system is running low on memory, the system will
typically begin to thrash the page cache. The increase in the number
of accesses to compcache will cause page.age to increase relatively
rapidly, causing compcache to reduce its memory usage by swapping out
and/or recompressing pages.

3) If t is the time required for the primary compressor, and s is the
time for the secondary compressor then if we set max_age[0] to be
greater than s/t then we know that we will spend less time in
compressor[1] than we do in compressor[0]. Hence it is easy to set
max_age[0] such that the addition of the slower compressor will never
significantly degrade performance compared to the original compcache,
while still ensuring that even if we do not have any physical swap
unused pages will eventually be recompressed and/or swapped out.

-- 
John C. McCabe-Dansted
PhD Student
University of Western Australia