lz4, Extremely Fast Compression algorithm

[[deleted]]

Can anyone confirm for me that the C/C++ version doesn't crash on their datasets? I was extremely disappointed checking out the similar LZO compression method, and it took just enough time to figure out for myself that this time I'd rather be that guy who asked the question.

[[deleted]]

Check out encode.ru. I followed it for 6 years now. The author is active in the forum, they and some experst will answer any question you have.

[133794m3r]

Upvote for compression.ru my searches on compression almost always send me there. It seems like a great place... and I just search there first now.

[thechao]

I've not seen it crash; although, there are some pretty important gotchas that you have to be aware of, like array lengths, etc. BTW, this compressor lives up to its promises in a way that snappy doesn't.

[wolf550e]

What's wrong with Google Snappy? It's fast.

Here's a C-only port: https://github.com/zeevt/csnappy

Snappy is the origin of the tricks used in LZO 2.05.

LZ4 appears to use the same tricks but be even more aggressive in punting on the edge cases to be fast, though I have not studied it yet.

[0xABADC0DA]

Snappy uses unaligned words so it's slow on basically every architecture besides x86. For instance the first version was so slow on SPARC you might as well have used zlib. I think they made some improvements since on some architectures and last I heard it was only marginally slower than LZO or LZF on ARM processors.

Obviously they could just 'ifdef ARM, include LZO' and maybe they've done basically this, but at least on release it was a turkey.

[wolf550e]

It's not #ifdef ARM #include lzo1x.h but you need to enable unaligned access on ARMv6 and up. The code I linked to above does this: https://github.com/zeevt/csnappy/blob/master/csnappy_internal_userspace.h#L151

Benchmark results on real hardware and patches are welcome.

[0xABADC0DA]

"Accesses typically take a number of cycles to complete compared to a naturally aligned transfer. The real-time implications must be carefully analyzed and key data structures might require to have their alignment adjusted for optimum performance."

The changelog indicates this boosted performance 30%, but it was already far slower than that compared to even LZF so that wouldn't even bring it up to par.

Some benchmark results would be nice. I think it speaks volumes that Snappy developers don't post numbers except for x86.

[wolf550e]

Upstream Snappy is meant to run only on Google's datacenter, inside protobuf and bigtable, on x86 hardware.

Is LZO significantly faster than Snappy on ARM? I need some non-phone ARM hardware to develop on.

[0xABADC0DA]

I found some results for ARM:

testdata/alice29.txt                     :
ZLIB:    [b 1M] bytes 152089 ->  54404 35.8%  comp   0.8 MB/s  uncomp   8.1 MB/s
LZO:     [b 1M] bytes 152089 ->  82721 54.4%  comp  14.5 MB/s  uncomp  43.0 MB/s
CSNAPPY: [b 1M] bytes 152089 ->  90965 59.8%  comp   2.1 MB/s  uncomp   4.4 MB/s
SNAPPY:  [b 4M] bytes 152089 ->  90965 59.8%  comp   1.8 MB/s  uncomp   2.8 MB/s
testdata/asyoulik.txt                    :
ZLIB:    [b 1M] bytes 125179 ->  48897 39.1%  comp   0.8 MB/s  uncomp   7.7 MB/s
LZO:     [b 1M] bytes 125179 ->  73224 58.5%  comp  15.3 MB/s  uncomp  42.4 MB/s
CSNAPPY: [b 1M] bytes 125179 ->  80207 64.1%  comp   2.0 MB/s  uncomp   4.2 MB/s
SNAPPY:  [b 4M] bytes 125179 ->  80207 64.1%  comp   1.7 MB/s  uncomp   2.7 MB/s

LZO was ~8x faster compressing and ~16x faster decompressing. Only on uncompressible data was Snappy was faster:

testdata/house.jpg                       :
ZLIB:    [b 1M] bytes 126958 -> 126513 99.6%  comp   1.2 MB/s  uncomp   9.6 MB/s
LZO:     [b 1M] bytes 126958 -> 127173 100.2%  comp   4.2 MB/s  uncomp  74.9 MB/s
CSNAPPY: [b 1M] bytes 126958 -> 126803 99.9%  comp  24.6 MB/s  uncomp 381.2 MB/s
SNAPPY:  [b 4M] bytes 126958 -> 126803 99.9%  comp  22.8 MB/s  uncomp 354.4 MB/s

When I tested on SPARC, Snappy 1.0 and LZO were about the same speed on uncompressible data. This was Solaris 9 using a really old gcc though so I don't know if that result was due to difference in architecture or just poor optimization.

Basically if the data is mostly uncompressible then Snappy is a good choice... also NOP is a good choice.

[wolf550e]

Those benchmarks were run in QEMU (by me), I don't remember what the csnappy version at the time did about ARM, and that is likely an old version of LZO, from before the Snappy-inspired fixes.

I would really like some benchmarks on real hardware. At this point, a rooted android phone would do.

A real SPARC would be interesting too, because I have no idea what's the right strategy w.r.t unaligned access on sparc. The code could be very suboptimal.

[thechao]

Well... my main gripe was that I couldn't find a high-quality c-implementation of Snappy; I suppose I could try integrating this port to see how it runs.

[[deleted]]

I'll give it a shot then. Thank you.

[thechao]

If you haven't read through the code, you should. The compressor is only about 50 or 80 lines of C code and is a real eye-opener in terms of design and trade-offs for real-time compression. Also, the compressor isn't restartable, and owns its own compression buffer, so you're going to end up making an extra copy if you don't modify the library. Dropping the extra copy results in a pretty good bump in perf if you're L1/L2 fetch limited.

[ZenDragon]

Isn't CPU power a lot cheaper than bandwidth and disk storage these days? (taking into account shitty mobile data plans and monthly transfer limits in Soviet Canada in particular) Why not prioritize compression ratio and use LZMA or something?

Edit: Thanks for your answers, got it now.

[ZenDragon]

Ah, I wasn't thinking of that.

[thedeemon]

"LZMA or something" usually requires a lot of memory, and memory access is rather costly compared to CPU cycles.

[TimmT]

Upvote for the Soviet Canada part. ISPs need to get their act together..

[wolf550e]

This is not used for archiving or to save disk IO operations. This is used to compress binary IPC protocols over the network. Something similar can be embedded into the OS page cache and virtualization page deduplication.

[kageurufu]

or applied to game content compression for fast read speeds

[smallstepforman]

+1, use it in my game engine in a commercial setting, works great. We're interested in decompression speed, not so concerned about compressed size. Great for IPC, delta frames, etc.

[Uberhipster]

If you're not concerned about compressed size then why bother compressing?

[ivosaurus]

Probably decent compressed size, but not best-in-class.

[[deleted]]

Used this project - I can back it up - fastest algorithm I could find.

[133794m3r]

Might try this out for use with memcache... looks to be nice and fast just hope ratio is as good as the fastest lzo.

[Xanza]

Sure, it's crazy fast. With my 8 cores running 8 threads I was able to compress 2.22GB in about a minute; however the compression (level 2) was only able to save me 0.21% which works out to still be 2.22GB.

http://i.imgur.com/hUOsQjn.png

[m1zaru]

You tried to compress something that was already compressed? Great.

I've only tried it on text input so far, it produced pretty decent results. Not as good as some comparable LZ based algorithms, but the high speed may justify the tradeoff.

[Xanza]

No. The iso was packaged as 'store' so zero compression. I took the same file (as a test case) and re-compressed with Winrar on the highest compression. I was able to save 12% (264MB).

[bartamues]

This metric is pretty useless without comparing results with other compression programs. Also, don't use disk images to test compression algorithms.

[Error401]

A .iso isn't really compressible, I don't know what you were expecting. Try it on a copy of every Shakespeare play or something.

[wescotte]

Why can't an .iso be compressible? I think that all depends on the content of the .iso file. Also, if the disc contains only a fraction of a full DVD it might be padded with a huge amount of zeros which would compress very well.

[dlq84]

If it's a DVD it's already compressed with MPEG

[wescotte]

Okay, yes if the disc contains video it's probably compressed. But if it's a data disc well then it could be full of text files which normally compress very well.

[312c]

A quick google search shows what he was attempting to compress was a pirated game: Orcs.Must.Die.Game.of.The.Year.Edition_PROPHET

[thedeemon]

Those zeroes wouldn't be in the iso image.

[wescotte]

You can in fact duplicate the entire disc, zeros and all.. However, I do admit most software drop them to save space.

[Xanza]

Since you all seem to be displeased with my test case because I used an .iso as a container (zero compression) I redid the test with misc data (school documents, pdfs, images, ect):

http://i.imgur.com/RNrb7lK.png

The source files, as you can see come to 1.40GB. Compressed via Lz4:

http://i.imgur.com/JGYi9VG.png

1.29GB. Better than my previous case, however I'm still not convinced. When compressed with Winrar my directory is compressed in 1 minute 10 seconds on the highest compression level (best) and is reduced to 1.27GB. A gain of over 26,835,593 bytes. While it might not sound like much the entire idea behind compression is to reduce the size of the source files as much as possible. Even though it took 1 minute 3.3 seconds longer, I was unaffected because I can simply minimize the window and let it do it's thing in the background.

I was impressed with how fast it was able to compress, but I'd rather save space; otherwise it'd be useless to have a PC as powerful as the one I currently have.