A very fast algorithm for RAM compression

ABSTRACT

Compressed virtual memory systems have been suggested, and in some cases implemented, to improve the effectiveness of use of physical RAM. However, most proposals and/or implementations are based on adaptive compression algorithms which achieve good compression ratios, but are slow compared to a local disk. Hence, they can only give some advantage with very slow (e.g. network-mounted) swap devices. In this paper we show that in many cases memory pages contain highly compressible data, with a very large amount of zero-valued elements. This suggests the replacement of slow, adaptive compression algorithms with very fast ones based on static Huffman codes.We present one such algorithm which, paired with a careful layout of the data, is able to compress 4KB pages at 40MB/s even when implemented in software on an inexpensive Pentium 100 system. We also show that the algorithm can achieve interesting compression ratios despite its simplicity.Since the compression/decompression speed of our algorithms exceeds disk bandwidth, its use in a compressed VM system can lead to both memory savings and speed improvements in servicing page faults. In this paper we discuss some possible applications of the algorithm in a compressed VM system.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Management