4 ms·

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression s

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-reaches-final-format.html http://fastcompression.blogspot.com/2016/06/zstandard-reache... [2] https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd [3] https://github.com/Cyan4973/lz4 https://github.com/Cyan4973/lz4

AceJohnny2 10y ago
While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes. Right now, we're using LZSS because the decompressor code is tiny (hundreds of bytes), and scratch memory is in the single-digit kilobytes. Any suggestions? All benchmarks I can find online are focused on desktop usage (where comp/decomp memory use is either not mentioned or in the megabyte range) or web streaming usage (where total comp+decomp time is important. I don't care (within reason) about comp time)
- stijlist 10y ago
  https://github.com/atomicobject/heatshrink https://github.com/atomicobject/heatshrink, by @silentbicycle, sounds like it might be up your alley.
  - AceJohnny2 10y ago
    ...which is based on LZSS :|
- unwind 10y ago
  I've had good results with LZJB[1] (designed by Jeff Bonwick for ZFS) in embedded scenarios, perhaps at least worth testing for you? I even have some public code for it, there's Python module [2] that will adequately address your wish for mediocre offline-friendly performance (heh) and a streaming C decompression library [3]. The runtime memory usage for the decompressor are tiny (which is good, since from my perspective your system sounds huge!) so that should be fine at least. Very interested in any feedback you might have, of course. [1] https://en.wikipedia.org/wiki/LZJB https://en.wikipedia.org/wiki/LZJB [2] https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb [3] https://github.com/unwind/lzjb-stream https://github.com/unwind/lzjb-stream
JyrkiAlakuijala 10y ago
Brotli's fastest compression is slightly faster than zstd's. Zstd decompresses faster, but neither is slow. Zstd can use sliding window size longer than 16 MB, in brotli this is limited to 16 MB to have guarantees of the maximum resource use at decoding time. Zstd's longer sliding window helps with the longest files (16 MB+), and often benchmarking is done with 100 MB or even 1 GB files. Brotli compresses usually more, and quite a lot more on shorter files. Try with cp.html, sparc sum or xargs.1. Brotli compresses these 9-19 % more densely on the following benchmark: https://quixdb.github.io/squash-benchmark/unstable/ https://quixdb.github.io/squash-benchmark/unstable/ Note, that on this benchmark brotli is always limited to the 4 MB sliding window. Other algorithms are run with wider windows, too. This will make brotli seem worse on large files (4+ MB).
- AceJohnny2 10y ago
  Thanks for the clarification! I was going to include the squash-benchmark link, but they don't include zstd yet. I guess I jumped the gun :\ And especially thanks for the clarification on performance relative to input file size and sliding window size.
- blank_state 10y ago
  > Brotli's fastest compression is slightly faster than zstd's. Come on, this is not serious. Brotli's fastest compression algorithm is still significantly slower than zstd. And more importantly, it compresses _much worse_. For a 3rd party evaluation, one can try [TurboBench](https://github.com/powturbo/TurboBench https://github.com/powturbo/TurboBench) or even [lzbench](https://github.com/inikep/lzbench https://github.com/inikep/lzbench) which are open-sourced. Squash introduces a wrapper layer with distortions which makes it less reliable, and more complex to use and install, quite a pity given the graphical presentation is very good. I'm interested in speed, and in this area, all benchmarks point in the same direction : for a given speed budget, Zstandard offers better ratio (and decompresses much faster).
  - emn13 10y ago
    The two benchmarks you mention aren't very useful for comparing brotli and zstd, because they deal with large datasets. Per-call overhead matters a lot for small files, and I imagine (particularly brotli) is aimed at small files. Zstd (usefully!) calls out dictionary compression, which hints that small files matter for it too, but I'm not positive there's any specific use case for zstd in mind. In any case, neither the compression ratios nor the speed of large-file compression necessarily say much about small file performance. There's just much more context to search in a 100MB file than there is in a 10KB file. Having said that, there's no reason to assume brotli is better for small files; there's just no way to tell given the links you provide. I'm not affiliated with nor use neither zstd nor brotli.
jacobolus 10y ago
Take a look at Oodle Kraken, by Charles Bloom. http://www.cbloom.com/rants.html http://www.cbloom.com/rants.html (this is his blog, you’ll have to skim back through the last year of posts). But e.g. check out this very recent one http://cbloomrants.blogspot.com/2016/05/ps4-battle-miniz-vs-zlib-ng-vs-zstd-vs.html http://cbloomrants.blogspot.com/2016/05/ps4-battle-miniz-vs-... http://www.radgametools.com/oodle.htm http://www.radgametools.com/oodle.htm http://www.radgametools.com/oodlewhatsnew.htm http://www.radgametools.com/oodlewhatsnew.htm HN thread https://news.ycombinator.com/item?id=11583898 https://news.ycombinator.com/item?id=11583898

AceJohnny2 10y ago

While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes. Right now, we're using LZSS because the decompressor code is tiny (hundreds of bytes), and scratch memory is in the single-digit kilobytes. Any suggestions? All benchmarks I can find online are focused on desktop usage (where comp/decomp memory use is either not mentioned or in the megabyte range) or web streaming usage (where total comp+decomp time is important. I don't care (within reason) about comp time)

stijlist 10y ago
https://github.com/atomicobject/heatshrink https://github.com/atomicobject/heatshrink, by @silentbicycle, sounds like it might be up your alley.
- AceJohnny2 10y ago
  ...which is based on LZSS :|
unwind 10y ago
I've had good results with LZJB[1] (designed by Jeff Bonwick for ZFS) in embedded scenarios, perhaps at least worth testing for you? I even have some public code for it, there's Python module [2] that will adequately address your wish for mediocre offline-friendly performance (heh) and a streaming C decompression library [3]. The runtime memory usage for the decompressor are tiny (which is good, since from my perspective your system sounds huge!) so that should be fine at least. Very interested in any feedback you might have, of course. [1] https://en.wikipedia.org/wiki/LZJB https://en.wikipedia.org/wiki/LZJB [2] https://github.com/unwind/python-lzjb https://github.com/unwind/python-lzjb [3] https://github.com/unwind/lzjb-stream https://github.com/unwind/lzjb-stream

JyrkiAlakuijala 10y ago

Brotli's fastest compression is slightly faster than zstd's. Zstd decompresses faster, but neither is slow. Zstd can use sliding window size longer than 16 MB, in brotli this is limited to 16 MB to have guarantees of the maximum resource use at decoding time. Zstd's longer sliding window helps with the longest files (16 MB+), and often benchmarking is done with 100 MB or even 1 GB files. Brotli compresses usually more, and quite a lot more on shorter files. Try with cp.html, sparc sum or xargs.1. Brotli compresses these 9-19 % more densely on the following benchmark: https://quixdb.github.io/squash-benchmark/unstable/ https://quixdb.github.io/squash-benchmark/unstable/ Note, that on this benchmark brotli is always limited to the 4 MB sliding window. Other algorithms are run with wider windows, too. This will make brotli seem worse on large files (4+ MB).

AceJohnny2 10y ago
Thanks for the clarification! I was going to include the squash-benchmark link, but they don't include zstd yet. I guess I jumped the gun :\ And especially thanks for the clarification on performance relative to input file size and sliding window size.
blank_state 10y ago
> Brotli's fastest compression is slightly faster than zstd's. Come on, this is not serious. Brotli's fastest compression algorithm is still significantly slower than zstd. And more importantly, it compresses _much worse_. For a 3rd party evaluation, one can try [TurboBench](https://github.com/powturbo/TurboBench https://github.com/powturbo/TurboBench) or even [lzbench](https://github.com/inikep/lzbench https://github.com/inikep/lzbench) which are open-sourced. Squash introduces a wrapper layer with distortions which makes it less reliable, and more complex to use and install, quite a pity given the graphical presentation is very good. I'm interested in speed, and in this area, all benchmarks point in the same direction : for a given speed budget, Zstandard offers better ratio (and decompresses much faster).
- emn13 10y ago
  The two benchmarks you mention aren't very useful for comparing brotli and zstd, because they deal with large datasets. Per-call overhead matters a lot for small files, and I imagine (particularly brotli) is aimed at small files. Zstd (usefully!) calls out dictionary compression, which hints that small files matter for it too, but I'm not positive there's any specific use case for zstd in mind. In any case, neither the compression ratios nor the speed of large-file compression necessarily say much about small file performance. There's just much more context to search in a 100MB file than there is in a 10KB file. Having said that, there's no reason to assume brotli is better for small files; there's just no way to tell given the links you provide. I'm not affiliated with nor use neither zstd nor brotli.

jacobolus 10y ago

Take a look at Oodle Kraken, by Charles Bloom. http://www.cbloom.com/rants.html http://www.cbloom.com/rants.html (this is his blog, you’ll have to skim back through the last year of posts). But e.g. check out this very recent one http://cbloomrants.blogspot.com/2016/05/ps4-battle-miniz-vs-zlib-ng-vs-zstd-vs.html http://cbloomrants.blogspot.com/2016/05/ps4-battle-miniz-vs-... http://www.radgametools.com/oodle.htm http://www.radgametools.com/oodle.htm http://www.radgametools.com/oodlewhatsnew.htm http://www.radgametools.com/oodlewhatsnew.htm HN thread https://news.ycombinator.com/item?id=11583898 https://news.ycombinator.com/item?id=11583898