Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!purdue!tut.cis.ohio-state.edu!ucbvax!agate!saturn!wilson@carcoar.stanford.edu
From: wilson@carcoar.stanford.edu (Paul Wilson)
Newsgroups: comp.os.research
Subject: compress/decompress paging?  prepaging?
Message-ID: <7929@saturn.ucsc.edu>
Date: 13 Jun 89 00:21:30 GMT
Sender: usenet@saturn.ucsc.edu
Organization: Stanford University
Lines: 39
Approved: comp-os-research@jupiter.ucsc.edu



I'm looking for information on paging with compression.  Does anybody
do it?  (Has anybody threatened to, even?)

What I mean is compressing pages of main memory before they're swapped
out to disk, and uncompressing pages when they're faulted in.

There are two benefits to this, as I see it.  The obvious and not thrilling
benefit is that it saves you disk space (and/or interconnect bandwidth).

The more interesting possibility is to use a compressed-page cache as
a new layer of the memory hierarchy, intermediate in speed between
RAM and disk.  This is increasingly attractive as CPU speeds increase
faster than disk speeds.

(My particular scheme is for garbage collected languages, and uses a
little knowledge of the gc's copying algorithm to allow most pointers
to be encoded with zero (yes, zero) address bits.)

I'm also interested in references to prepaging algorithms.  My compression
scheme would allow you to win with a somewhat less effective prepaging
algorithm, because the space cost of a bad guess wouldn't be prohibitive.

So what are the classic references and the state of the art in prepaging?

[ I can see some scary problems here.  1) it has to be FAST.  2) now your ]
[ pages going to secondary store are not of fixed size.  --DL             ]


thanks prematurely,

   Paul


Paul R. Wilson                         
Human-Computer Interaction Laboratory     lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680