 | This articlemay rely excessively on sourcestoo closely associated with the subject, potentially preventing the article from beingverifiable andneutral. Please helpimprove it by replacing them with more appropriatecitations toreliable, independent sources.(October 2021) (Learn how and when to remove this message) |
842,8-4-2, orEFT is adata compression algorithm. It is a variation onLempel–Ziv compression with a limited dictionary length. With typical data, 842 gives 80 to 90 percent of the compression of LZ77 with much faster throughput and less memory use.[1] Hardware implementations also provide minimal use of energy and minimal chip area.
842 compression can be used forvirtual memory compression, for databases — especiallycolumn-oriented stores, and when streaming input-output — for example to dobackups or to write tolog files.
The algorithm operates on blocks of 8 bytes with sub-phrases of 8, 4 and 2 bytes. A hash of each phrase is used to look up a hash table with offsets to a sliding window buffer of past encoded data. Matches can be replaced by the offset, so the result for each block can be some mixture of matched data and new literal data.[2][1][3]
IBM added hardware accelerators and instructions for 842 compression to theirPower processors fromPOWER7+ onward.[4] In addition,POWER9 andPower10 added hardware acceleration for theRFC 1951Deflate algorithm, which is used byzlib andgzip.[5]
Adevice driver for hardware-assisted 842 compression on a POWER processor was added to theLinux kernel in 2011.[6] More recently, Linux can fallback to a software implementation, which of course is much slower.[7]zram, aLinux kernel module for compressedRAM drives, can be configured to use 842.
Researchers have implemented 842 usinggraphics processing units and found about 30x faster decompression using dedicated GPUs.[8] An open source library provides 842 forCUDA andOpenCL.[9] AnFPGA implementation of 842 demonstrated 13 times better throughput than a software implementation.[10]