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

Nitin Gupta nitingupta910 at gmail.com
Mon Apr 14 05:53:18 EDT 2008


I will go through you algorithm soon but I was considering using this
for dynamic resizing:

http://linuxcompressed.sourceforge.net/linux24-cc/files/docs/paper.pdf

- Nitin


On Mon, Apr 14, 2008 at 2:49 PM, John McCabe-Dansted <gmatht at gmail.com> wrote:
> 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
>


More information about the linux-mm-cc mailing list