Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Smaller and faster data compression with Zstandard

code.facebook.com

Post reply on HN
Print view View original

121–130 of 166 posts

Re: Smaller and faster data compression with Zstandard

#121

Post by binarycrusader »

tmd83 wrote: post #118
binarycrusader wrote: post #116

Earlier quoted context omitted.

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey about the details, many strongly suspect their recently announced Kraken, etc. use ANS in some form and some of their previous products; see the discussion here: https://news.ycombinator.com/item?id=11583898 ...and here: http://encode.ru/threads/2492-Kraken-compress…

Yeah read about Kraken a while ago and found the encode.ru thread you pointed. Its unfortunate that we can't compare that side by side. Those guys seem another of those compression geniuses. Overall the world of compression is moving very fast and well these days. But even with that Yann might be the first. Yan's work on FSE is old [0] and if I'm reading this correctly his work on FSE is a mix of his own work and Jar…

Yeah, it's all very hazy, and since RAD is (understandably) proprietary, it's difficult to figure out exactly when who did what.

Re: Smaller and faster data compression with Zstandard

#122

Post by Twirrim »

From the bits of testing I've done today, it's phenomenally fast on x86. Much better than gzip (and pigz for that matter) in every metric I think I generally care about: CPU Usage, Compression Speed, Decompression Speed, Compression Ratio.

On other architecture the picture gets a bit murky, it seems to get handily beaten by pigz through what at first blush I'd guess is just sheer parallelism. It's got solid performance, and without a shadow of doubt faster than vanilla gzip. If/as/when I get time, it'll be interesting to dig into why performance is worse there.

Re: Smaller and faster data compression with Zstandard

#123

Post by illicium »

binarycrusader wrote: post #116
tmd83 wrote: post #27

I have been waiting for this to hit 1.0 and more importantly get popular so that I can use it everywhere. I am really a fan of Yann Collet's work. These are extremely impressive work specially when you consider that lz4 seems to be better than snappy (by google) and zstandard from LZFSE (from apple). I think he is the first one to write a practical fast arithmetic coder using ANS. And look at how his huffman implemen…

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey about the details, many strongly suspect their recently announced Kraken, etc. use ANS in some form and some of their previous products; see the discussion here: https://news.ycombinator.com/item?id=11583898 ...and here: http://encode.ru/threads/2492-Kraken-compress…

RAD use rANS for their compressors. See ryg's blog [0] for more details, and a bunch more interesting posts about compression and various low-level optimizations.

[0] https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/

Re: Smaller and faster data compression with Zstandard

#124

Post by gliptic »

binarycrusader wrote: post #116
tmd83 wrote: post #27

I have been waiting for this to hit 1.0 and more importantly get popular so that I can use it everywhere. I am really a fan of Yann Collet's work. These are extremely impressive work specially when you consider that lz4 seems to be better than snappy (by google) and zstandard from LZFSE (from apple). I think he is the first one to write a practical fast arithmetic coder using ANS. And look at how his huffman implemen…

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey about the details, many strongly suspect their recently announced Kraken, etc. use ANS in some form and some of their previous products; see the discussion here: https://news.ycombinator.com/item?id=11583898 ...and here: http://encode.ru/threads/2492-Kraken-compress…

There are now actually open source decompressors[0] for Oodle formats, and yes, many use rANS. Especially LZNA's clever use of SSE2 to decode and update 16 symbol models is interesting. FSE (which is tANS) is a different beast, though, and more suitable for rarely updated models.

[0] http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Sel...

Re: Smaller and faster data compression with Zstandard

#125

Post by lifthrasiir »

gliptic wrote: post #124
binarycrusader wrote: post #116

Earlier quoted context omitted.

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey about the details, many strongly suspect their recently announced Kraken, etc. use ANS in some form and some of their previous products; see the discussion here: https://news.ycombinator.com/item?id=11583898 ...and here: http://encode.ru/threads/2492-Kraken-compress…

There are now actually open source decompressors[0] for Oodle formats, and yes, many use rANS. Especially LZNA's clever use of SSE2 to decode and update 16 symbol models is interesting. FSE (which is tANS) is a different beast, though, and more suitable for rarely updated models. [0] http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Sel...

...and got DMCAed [1]. At the very least the discussion itself is interesting for the inside infos, though.

[1] https://github.com/github/dmca/blob/master/2016/2016-08-30-O...

Re: Smaller and faster data compression with Zstandard

#126

Post by MichaelGG »

bluedino wrote: post #97
MichaelGG wrote: post #52

Earlier quoted context omitted.

Is low energy significantly different from high performance code? I thought the general advice was make the code as fast as possible so the work can be finished and the CPU slow/power down again. Are there cases where an algorithm takes 10x the wall clock time to execute, but actually uses less energy on the same chip? (Memory use/access is the main thing I guess that could be different.)

>> Is low energy significantly different from high performance code? It can be. Certain operations are more power efficient than others - subtraction and then a check for negative value instead of comparison, certain vector operations, loop unrolling, using less memory/bus traffic... >> Are there cases where an algorithm takes 10x the wall clock time to execute, but actually uses less energy on the same chip? Slower…

Interesting. Do you know of any open source examples offhand?

I'd imagine this also requires very detailed knowledge of the chip, microcode, etc. Probably hard for x86 but I guess this kinda stuff would be on ARM where the programmer has deep vertical access (like as mentioned, Apple).

Re: Smaller and faster data compression with Zstandard

#127

Post by foepys »

ac29 wrote: post #103
tessela wrote: post #87

Earlier quoted context omitted.

except for the PATENTS file =/

Curious what your issue is with it -- it basically says "if you dont sue us, we wont sue you". Thats about as good as I can expect from a large tech company these days with regards to patents.

But doesn't that mean that Facebook can use any of your patents and you cannot sue them unless you don't use zstd?

Re: Smaller and faster data compression with Zstandard

#129

Post by acchow »

cooper12 wrote: post #104
hueving wrote: post #99

Earlier quoted context omitted.

Assuming the size of the decompressor isn't larger than the savings you gained from using this compression algo over another...

Well the decompressor would be cached by the browser so it would pay off for repeat visitors. And if it gets used enough, the user will already have downloaded the decompressor from another site.

And easily shared across sites if they all use a popular CDN'd version.
Post reply on HN