Wikipedia

Draft:WKdm

The WKdm algorithm is one of the first in the class of WK virtual memory compression techniques developed initially by Paul R. Wilson and Scott F. Kaplan et al. circa 1999.[1] The "dm" in the WKdm acronym stands for "direct mapped" and refers to the direct mapped hash method used to map uncompressed words in memory to the WKdm algorithm's dictionary.[1][2][3][4][5]

Motivation

edit

The key insight on which the WKdm algorithm is built is the realization that most high-level programming languages compile to output whose data section(s) have certain very strong data regularities with regard to integers and pointers.[1][2][3] Firstly, a large amount of integers and pointers are word-aligned within records, where "word" here will henceforth refer to 32 bits.[1][2][3] Additionally, most integers usually contain small values relative to their maximum ranges.[1][2][3] For pointers, most proximal in memory to each other reference addresses that are close to each other in memory.[1][2][3] Finally, certain data patterns, particularly words of all zeroes, frequently occur and this is exploited by the algorithm.[1][2][3]

To make use of the above data regularities, one need only realize that, frequently, words will share many of their high-order bits either because they aren't large enough to require a full-word bit width, or, said words are pointers whose values reference addresses close in memory to those referenced by nearby pointers.[1][2][3] Also, words of all zeroes, which occur frequently, can be easily compressed.[1][2][3]

Algorithm

edit

Compression

edit

The WKdm algorithm reads one word at a time from an address range, usually a page or pages, and uses a 16-entry direct mapped dictionary of words to produce compressed output which is segregated into four arrays or "segments" which contain, respectively, "tags" ( 2-bit values indicating the type of (non)match ), dictionary indices, unmatched words and the lower 10 bits of partially matched words.[1][4] The tag, index and partial match values are initially output into bytes or words in their respective segments, before being “packed” after the number of words in the addresses range to be compressed is exhausted.[1][4]

For each word read, the word is mapped to the dictionary using a direct-mapped hash, and then the type of (non)match is determined.[1][4][2] If a full 32-bit word match is found in the dictionary, then a 2-bit "tag" value indicating a full-word match is written to the tags segment and the 4-bit index of the match within the dictionary is written to the indices segment.[1][4] If only the high-order 22 bits match, then a different tag is written to the tags segment, the dictionary index of the partial match is output to the indices segment and the differing 10 lower-order bits are recorded in the partial match segment.[1][4] If no match is found then the new value is added to the dictionary, as well as being emitted to the unmatched-words segment, and another tag signaling this is written to the tags segment.[1][4] If the read word is all zeroes, then only one tag indicating this is output to the tags segment.[1][4]

After all the words in the address range to be compressed have been read, the tags, indices and 10-bit partial match values, which are stored in bytes or words in their segments, are "packed" within their respective segments ( e.g. their bits are made contiguous if their particular segment is taken to be one large bit vector. Additional steps may be taken — the exact details are implementation specific ) using bitwise operations to further reduce the compressed size of the data.[1][4]

Decompression

edit

Decompression is quite straightforward. The tags segment is processed one 2-bit tag at a time and action is taken depending on the value of the tag.[1][5] If the value indicates a full-word match, then the corresponding dictionary index within the indices segment is referenced and the value referenced by the index in the dictionary is output.[1][5] If a partial match is indicated, then the corresponding entry in the indices segment is consulted to look up the value that matches the high-order 22 bits and then the partial match segment is read to reconstruct the full 32-bit word, which is written to the uncompressed output.[1][5] If the current tag indicates that there was no match, then the corresponding 32-bit word in the unmatched words segment is referenced and added to the dictionary as well as being emitted as part of the uncompressed output.[1][5] If the tag indicates that a word was read that was all zeroes, then a 32-bit zero value is sent to the output.[1][5]

Performance

edit

Tests and real world performance data show[1][2][3][6] that WKdm compression achieves a compression ratio comparable or superior to LZ-based dictionary compressors.[7][8] The WKdm algorithm also has much less overhead than an LZ-class compressor as it only uses a dictionary that is 64 bytes in size as compared to eg. 64 kilobytes.[1][2][3] Furthermore, because of the simplicity of the algorithm, compression and decompression is usually much faster than traditional LZ-based compressors.[1][2][3]

Variants

edit

The original authors of the WKdm algorithm also developed the so-called "WK4x4" algorithm.[1][3] This variation on the algorithm uses a 4-way set associative cache instead of a direct mapped hash for the dictionary.[1][3] The performance, though, was shown to be the same or worse than WKdm in most cases.[1][3]

Matthew Simpson et al. developed a variation on the original WKdm algorithm named "WKS" in which the compression is performed in-place without the need of any temporary arrays or "segments."[2] This cuts down on the temporary memory requirements. Also, the algorithm prevents compressed data expansion due to its ability to detect incompressible data.[2] Furthermore, WKS extends what is considered a partial match for a given word.[2]

Notable implementations

edit

WKdm compression has been used by Apple's OSX since version 10.9 Mavericks in 2013[9][10][11][12] and also in the shared source of the Darwin-XNU open source operating system / kernel.[13][4][5] WKdm compression has also been implemented in the OLPC Linux kernel.[14][15] A new implementation of the Linux virtual-memory manager, called "CCache", has also been demonstrated to work with the WKdm algorithm and its variants on a Nokia Internet Tablet N800 running on a TI OMAP processor.[3]

See also

edit

References

edit
  1. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab Wilson, Paul R.; Kaplan, Scott F.; Smaragdakis, Yannis (1999-06-06). The Case for Compressed Caching in Virtual Memory Systems (PDF). USENIX Annual Technical Conference. Monterey, California, USA. pp. 101–116.
  2. ^ a b c d e f g h i j k l m n o Simpson, Matthew; Barua, Rajeev; Biswas, Surupa (12 Aug 2023). "Analysis of Compression Algorithms for Program Data" (PDF). University of Maryland: 4–14. Retrieved 6 Jan 2024.
  3. ^ a b c d e f g h i j k l m n o Farias Briglia, Anderson; Bezerra, Allan; Moiseichuk, Leonid; Gupta, Nitin (2007). "Evaluating effects of cache memory compression on embedded systems" (PDF). 2007 Linux Symposium: 56–57. Retrieved 11 Jan 2024.
  4. ^ a b c d e f g h i j The explanation of the ARM64 implementation and of the general WKdm compression algorithm is contained in the second block comment. Also, similar explanations can be found in the OSFMK ARM32, x64 and x86 code. "WKdmCompress_4k.s". github.com. 28 Sep 2017. Retrieved 15 Jan 2024.
  5. ^ a b c d e f g The explanation of the ARM64 implementation and of the general WKdm decompression algorithm is contained in the second block comment. Also, similar explanations can be found in the OSFMK ARM32, x64 and x86 code. "WKdmDecompress_4k.s". github.com. 28 Sep 2017. Retrieved 15 Jan 2024.
  6. ^ Isaac, Sean; Anderson, Geronimo; Nordby, Jon (19 July 2019). "Cache and Memory Compression Techniques". github.com. Retrieved 3 Mar 2024.
  7. ^ Larabel, Michael (2 Jun 2017). "LZ4m: Taking LZ4 Compression To The Next Level". phoronix.com. Retrieved 3 Mar 2024. But LZ4m does come up short of the WKdm page compressor's compression ratio and compression speed.
  8. ^ Chihaia Tuduce, Irina; Gross, Thomas (2005). "Adaptive Main Memory Compression" (PDF). USENIX Annual Technical Conference: 237–250. Retrieved 5 Mar 2024. For all experiments, we use the WKdm compression algorithm as it shows superior performance over other algorithms
  9. ^ "OS X 10.9 Mavericks: The Ars Technica Review". 22 October 2013.
  10. ^ "OS X Mavericks Core Technologies Overview October 2013" (PDF). apple.com. Oct 2013. p. 7. Retrieved 9 Jan 2024.
  11. ^ "OS X El Capitan Core Technologies Overview September 2015" (PDF). apple.com. Sep 2015. p. 7. Retrieved 9 Jan 2024.
  12. ^ Kessler, Topher (10 Jun 2013). "Memory compression brings RAM Doubler to OS X Mavericks". cnet.com. Retrieved 3 March 2024.
  13. ^ G. Richard III, Golden; Case, Andrew (17 Jul 2014). "In lieu of swap: Analyzing compressed RAM in Mac OS X and Linux". Digital Investigation. 11: S7–S8. doi:10.1016/j.diin.2014.05.011. Retrieved 11 Jan 2024.
  14. ^ Beltran, Vicenc¸; Martorell, Xavier; Torres, Jordi; Ayguad´e, Eduard (2008). "Accelerating Software Memory Compression on the Cell/B.E." (PDF). First Workshop on Hardware Accelerators for High-Performance Computing: 2. Retrieved 11 Jan 2024.
  15. ^ Gupta, Nitin (7 Jul 2006). "[linux-mm-cc] Compression structure implementation". marc.info. Retrieved 9 Jan 2024.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Draft:WKdm&oldid=1231567241"