Virtual memory compression: Difference between revisions

Revision as of 15:58, 31 December 2023

Revision as of 18:30, 1 January 2024

Line 12:

There are two general types of virtual memory compression : (1) sending compressed pages to a swap file in main memory, possibly with a backing store in auxiliary storage,<ref name ="CaseForCompressedCaching"/><ref name="zram_kernel_org">{{cite web |url=https://www.kernel.org/doc/html/next/admin-guide/blockdev/zram.html |title="zram: Compressed RAM-based block devices" |last="Gupta" |first="Nitin" |website=docs.kernel.org |publisher="The kernel development community" |access-date=2023-12-29 }}</ref><ref name="zswap_kernel_org">{{cite web |url=https://www.kernel.org/doc/html/v4.18/vm/zswap.html |title="zswap" |website=www.kernel.org |publisher="The kernel development community" |access-date=2023-12-29 }}</ref> and (2) storing compressed pages side-by-side with uncompressed pages.<ref name="CaseForCompressedCaching"/>

The first type (1) usually uses some sort of [[LZ77_and_LZ78|LZ]] class dictionary compression algorithm combined with [[entropy coding]], such as [[Lempel–Ziv–Oberhumer|LZO]] or [[LZ4_(compression_algorithm)|LZ4]], <ref name="zswap_kernel_org" /><ref name="zram_kernel_org" /> to compress the pages being swapped out. Once compressed, they are either stored in a swap file in main memory, or written to auxiliary storage, such as a hard disk.<ref name="zswap_kernel_org" /><ref name="zram_kernel_org" /> A two stage process can be used instead wherein there exists both a backing store in auxiliary storage and a swap file in main memory and pages that are evicted from the in-memory swap file are written to the backing store with a greatly decreased bandwidth need due to the compression. This last scheme leverages the benefits of both previous methods : fast in-memory data access with a great increase in the total amount of data that can be swapped out and a decreased bandwidth requirement for data written to auxiliary storage.<ref name="zswap_kernel_org" /><ref name="zram_kernel_org" /><ref name ="CaseForCompressedCaching"/>

One of the most used class of algorithms for the second type (2), the WK class of compression algorithms, takes advantage of in-memory data regularities present in pointers and integers.<ref name ="CaseForCompressedCaching"/> Specifically, in target code generated by most high-level programming languages, both integers and pointers are often present in records whose elements are word-aligned. Furthermore, the values stored in integers are usually small. Also pointers tend to point to nearby locations. Additionally, common data patterns such as a word of all zeroes can be encoded in the compressed output by a very small code. Using these data regularities, the WK class of algorithms use a very small dictionary ( 16 entries in the case of [[WKdm]] ) to achieve up to a 2:1 compression ratio while achieving much greater speeds and having less overhead than LZ class dictionary compression schemes.<ref name ="CaseForCompressedCaching"/>