Sunday, February 27, 2011

LZ4 on steroids : version 0.8

Back to playground. It's always nice to work with LZ4, since its layout is very easy to test new ideas.
In this case, i wanted to check the principle of selective sampling, but this time purely in order to improve speed. This is a bit different from Zhuff, which used this idea to improve compression.

As stated in an earlier post, increasing speed is achieved by decreasing the number of samples. However, since LZ4 is a pure LZ77 compressor (using offset to identify repeated patterns), it also means that reducing samples can only decrease compression. Therefore, this is a matter of trade-off.

The end result achieved with LZ4 version 0.8 seems really interesting. On average, we end up with a 0,05% compression loss, and achieve a more than 10% speed boost. This is almost an unfair trade-off.

Don't be fooled by this "10%" average value, since it hides some very vast differences. Effectively, some files will gain a lot, while others will not get any benefit. For instance, an almost incompressible file can get a speed improvement of more than 500%, while another file with no possibility to "discard" elements, such as enwik8, will not see any performance improvement. But this is still an interesting bet "on average".

While at it, i also modified the multi-threading code branch. The new behavior is now much closer to an I/O algorithm, which makes it more representative of real usage. It also results in a slightly faster operation.
And finally, there is a new checksum algorithm, which ensures compression results are correct.

The resulting binary is rightly available here, and can be tested on your system.

versionCompression RatioSpeed Decoding
LZ4 "Ultra Fast"0.72.062232 MB/s805 MB/s
LZ4 "Ultra Fast"0.82.061260 MB/s810 MB/s
LZ4 "Ultra Fast" - 2 threads0.72.062430 MB/s1510 MB/s
LZ4 "Ultra Fast" - 2 threads0.82.061500 MB/s1510 MB/s

No comments:

Post a Comment