Zstandard – Fast and efficient compression algorithm • Hacker News Board

Re: Zstandard – Fast and efficient compression algorithm

#21

Post by twotwotwo » Sun, Jan 25, 2015, 5:43 PM UTC

pdknsk wrote: post #16

I wonder how it compares to Intel's custom zlib implementation, and to a fast zlib compressor by IBM researchers. http://www.intel.com/content/dam/www/public/us/en/documents/... http://dx.doi.org/10.1109/DCC.2014.66

Zstandard beats the Intel zlib tweak (as does Google's Gipfeli, mentioned in another comment) -- Intel's zlib -6 could also be described as "faster than stock zlib with only a little compression loss", but (from the chart in the Intel paper) it's "only" 1.8x faster when Zstandard is closer to 10x.

The IBM implementation's abstract mentions "a factor of 2.6x or higher" so similar deal, unless the "or higher" language hides a 10x gain. Also, abstract says they did it by taking LZ4's matcher + Zlib's entropy encoder, so they can't be expected to outperform the LZ4 author's new work. :)

Of course, those are still some great backwards-compatible gains.

Could be that on modern processors, Huffman coding just isn't the best option to make your compressor scream. Gipfeli uses a simple non-Huffman entropy code, and Collet (author of Zstandard) has been working on a state-machine-based coding approach for a while. deflate is over 20 years old, so it would make sense for it to be designed for different realities.

Speaking of chipmakers and zlib, though, Intel sells "QuickAssist" dedicated compression hardware, and AMD promises a compression accelerator in their server ARM SoC. As with AES, performance in software might come to matter less if systems start doing it in hardware. I don't know the silicon-area requirements for a compression accelerator, though (whereas AES's design was hardware-optimized), and I haven't seen any suggestion that compression accelerators are on the roadmap to be in any consumer chips.

Re: Zstandard – Fast and efficient compression algorithm

#22

Post by aristidb » Sun, Jan 25, 2015, 6:08 PM UTC

Zstd and LZ4 look amazing. Here's another compressor I really like: http://mattmahoney.net/dc/zpaq.html

Re: Zstandard – Fast and efficient compression algorithm

#23

Post by david-given » Sun, Jan 25, 2015, 6:32 PM UTC

twotwotwo wrote: post #10

Neat. Google's Gipfeli ( https://github.com/google/gipfeli ) also aims for compression ratio and time to fall in between gzip -6 and the fastest algorithms. I've only glanced at code; think it includes a Snappy/LZO/LZ4-like repeat matcher using a hashtable, combined with simple-but-fast entropy coding where each literal input byte becomes 6, 8, or 10 bits. Super cool that Collet's working on still-pretty-fast-but-bet…

...I don't know anything about compression, but 'gipfeli' is Swiss German for 'croissant'.

Re: Zstandard – Fast and efficient compression algorithm

#24

Post by twotwotwo » Sun, Jan 25, 2015, 6:55 PM UTC

david-given wrote: post #23

twotwotwo wrote: post #10

Neat. Google's Gipfeli ( https://github.com/google/gipfeli ) also aims for compression ratio and time to fall in between gzip -6 and the fastest algorithms. I've only glanced at code; think it includes a Snappy/LZO/LZ4-like repeat matcher using a hashtable, combined with simple-but-fast entropy coding where each literal input byte becomes 6, 8, or 10 bits. Super cool that Collet's working on still-pretty-fast-but-bet…

...I don't know anything about compression, but 'gipfeli' is Swiss German for 'croissant'.

Yep.

Two of Google's other custom compression tools are Zopfli (much slower zlib implementation producing slightly smaller files, for things you compress once and serve many many times) and Brotli (high-compression algorithm used in the WOFF2 font format). The bread algorithms!

Re: Zstandard – Fast and efficient compression algorithm

#25

Post by acqq » Mon, Jan 26, 2015, 12:07 AM UTC

I dream about 7zip adding this algorithm, having the convenience of reliability of 7zip together with the speed which would allow me to never avoid compression because it would be always almost as fast as plain copying.

Re: Zstandard – Fast and efficient compression algorithm

#26

Post by nitverstan0 » Mon, Jan 26, 2015, 3:12 PM UTC

Q: I know, 'bytes' is a 'container'. maybe i have missed it, but i still don't understand that in a computer, '8 times zero' is 1, and not still 'zero' ? yes, a 'packer' solves that - and more, but can someone clean up my messed thinking here ?

Re: Zstandard – Fast and efficient compression algorithm

#27

Post by ac29 » Wed, Jan 28, 2015, 1:24 AM UTC

Looks like this would be an excellent candidate for transparent compression in newer filesystems like btrfs/ZFS. Ill never go back to non-compressed filesystems for my personal machines -- btrfs w/ LZO compression has been an excellent, efficient, fast FS for me (YMMV -- I dont know that I'd use it in an important production environment).