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

151–160 of 166 posts

Re: Smaller and faster data compression with Zstandard

#151

Post by duskwuff »

legulere wrote: post #143
duskwuff wrote: post #53

Earlier quoted context omitted.

Not just tuned for web workloads in general, but for specific web workloads. The Brotli dictionary is mostly composed of English words and phrases, and fragments of HTML, CSS, and Javascript. It would perform poorly on non-English text. I have a feeling that the dictionary was designed with the specific goal of performing well on a specific corpus similar to the Large Text Compression Benchmark[1]. It has quite a few…

The dictionary also contains lots of Chinese, Russian and Arabic

By the numbers:

- 9216 phrases total

- 5857 (63.5%) pure ASCII phrases, mostly English with a few Spanish words thrown in

- 1372 (14.8%) code fragments -- mostly HTML, CSS, and Javascript

- 1027 (11.1%) CJK (Chinese, Japanese, and Korean, and mostly the first two) phrases -- it's very hard to tell Chinese and Japanese apart in this context; I didn't try

- 158 (1.7%) phrases containing extended Latin-1 characters (nearly all Spanish words)

- 303 (3.3%) Cyrillic script (probably Russian) phrases

- 322 (3.5%) Arabic phrases

- 172 (1.9%) Devanagari script (Hindi) phrases

Plus a few miscellaneous other scripts and generally unclassifiable content.

Re: Smaller and faster data compression with Zstandard

#152

Post by Cyan4973 »

caf wrote: post #109
AceJohnny2 wrote: post #36

The modern trend of compressors is to use more memory to achieve speed. This is good if you're using big-iron cloud computers... "Zstandard has no inherent limit and can address terabytes of memory (although it rarely does). For example, the lower of the 22 levels use 1 MB or less. For compatibility with a broad range of receiving systems, where memory may be limited, it is recommended to limit memory usage to 8 MB.…

I don't think 8MB is the smallest preset, the text you quoted says that the lower levels use "1 MB or less". The concern I have is that this makes it sound like the compressor can choose how much memory the decompressor will need to use. Does this mean that zstd can't be used in a potentially adversarial environment? (Eg. is there a denial-of-service vector here by forcing the server to use large amounts of memory to…

The decompressor can receive a parameter to refuse compressed frames requiring more than a selected amount of memory.

Re: Smaller and faster data compression with Zstandard

#153

Post by Cyan4973 »

Twirrim wrote: post #147
Twirrim wrote: post #122

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 performan…

Dug in a bit further. On the non-x86 architecture I use, it looks like it's really just straight core performance that explains it. pigz's only advantage there really seems to be the brute force parallelism. In particular note the huge difference in branches between gzip and zstd on decompress: 8959780663 branches # 143.024 M/sec 2969481781 branches # 64.454 M/sec and on misses: 542158823 branch-misses # 6.05% of all…

There is now a pzstd implementation, if you wish to compare it to pigz

Re: Smaller and faster data compression with Zstandard

#154

Post by vintermann »

gcp wrote: post #131
ac29 wrote: post #103

Earlier quoted context omitted.

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.

Compare it to the Opus patent license (also including a retaliation clause), which includes grants from Broadcom, Mozilla and Microsoft. Using zstd gives Facebook a free license on ALL your patents. Using Opus gives Facebook only a license on patents that apply to Opus. So no, large tech companies can and have given MUCH better grants for compression tech, than Facebook is doing.

Well, I suppose so, provided that you hold patents and want to use them offensively.

Because as far as I can see, Facebook has an exception saying that if they for some reason patent-sue you first, you would be allowed to countersue without losing your license to their patents.

That could be a misinterpretation, I suppose. But if it's right, then Facebook's license seems superior for those parties who wish to end software patents.

Re: Smaller and faster data compression with Zstandard

#155

Post by vintermann »

DannyBee wrote: post #58
joseraul wrote: post #30

Earlier quoted context omitted.

Indeed ANS is difficult: it is the biggest innovation in compression in the last 20 years. Its author has some nice but dense slides about it. https://dl.dropboxusercontent.com/u/12405967/ANSsem.pdf Not sure exactly when repcodes were invented. Igor Pavlov has already used them in 7zip.

The best TL;DR of ANS is something like this (without being too wrong). It's still too long: Huffman requires at least one bit to represent any symbol, because it finds unique prefix codes for every symbol by varying the leading bits. Arithmetic coding encodes symbols as fractional numbers of bits, by using binary fractions. It divides up the range to make this work. In the end, you get one fraction per "message" tha…

With regular arithmetic coding and Huffman coding you don't need to send over a dictionary. Instead, you can have an adaptive model that learns to compress the data as it goes (e.g. keeps running track of symbol frequencies), and it will still be reversible.

I thought this wasn't possible with ANS. Or has this changed?

Re: Smaller and faster data compression with Zstandard

#156

Post by gcp »

vintermann wrote: post #154
gcp wrote: post #131

Earlier quoted context omitted.

Compare it to the Opus patent license (also including a retaliation clause), which includes grants from Broadcom, Mozilla and Microsoft. Using zstd gives Facebook a free license on ALL your patents. Using Opus gives Facebook only a license on patents that apply to Opus. So no, large tech companies can and have given MUCH better grants for compression tech, than Facebook is doing.

Well, I suppose so, provided that you hold patents and want to use them offensively. Because as far as I can see, Facebook has an exception saying that if they for some reason patent-sue you first, you would be allowed to countersue without losing your license to their patents. That could be a misinterpretation, I suppose. But if it's right, then Facebook's license seems superior for those parties who wish to end sof…

Facebook's license seems superior for those parties who wish to end software patents

It's mostly superior for Facebook. If you're a party that wants to end software patents, but intends to use zstd in any place you might want to interface with a company that doesn't hold the same position, then you're screwed.

If you want to end software patents, and Facebook sues with one (not applying to zstd), you're also still screwed. This is relevant because even if you're against software patents, you can take them out defensively. But this license makes that useless.

Compare to GPL vs LGPL, or how the free software codecs all eventually moved to BSD.

Re: Smaller and faster data compression with Zstandard

#157

Post by gcp »

tmd83 wrote: post #149
gcp wrote: post #131

Earlier quoted context omitted.

Compare it to the Opus patent license (also including a retaliation clause), which includes grants from Broadcom, Mozilla and Microsoft. Using zstd gives Facebook a free license on ALL your patents. Using Opus gives Facebook only a license on patents that apply to Opus. So no, large tech companies can and have given MUCH better grants for compression tech, than Facebook is doing.

I don't understand these things well. But if true this would be really bad. LZ4 is everywhere because it was completely free and I think most of Zstandard's real work was pre-facebook by just Yann alone. Now to have its hand tied because of his job at facebook is the worst thing possible. I just read the Opus patent summary. It seems like if zstd followed the same license using it wouldn't give facebook any license b…

Now to have its hand tied because of his job at facebook is the worst thing possible.

If you accept the job you give up your work. It's not like there's no compensation.

Am I correct in that.

Yes, the retaliation (and hence, implicit license to Facebook) is only for the technology itself.

Re: Smaller and faster data compression with Zstandard

#158

Post by eln1 »

vintermann wrote: post #155
DannyBee wrote: post #58

Earlier quoted context omitted.

The best TL;DR of ANS is something like this (without being too wrong). It's still too long: Huffman requires at least one bit to represent any symbol, because it finds unique prefix codes for every symbol by varying the leading bits. Arithmetic coding encodes symbols as fractional numbers of bits, by using binary fractions. It divides up the range to make this work. In the end, you get one fraction per "message" tha…

With regular arithmetic coding and Huffman coding you don't need to send over a dictionary. Instead, you can have an adaptive model that learns to compress the data as it goes (e.g. keeps running track of symbol frequencies), and it will still be reversible. I thought this wasn't possible with ANS. Or has this changed?

It depends if you have static or adaptive coder.

Static is much cheaper, uses the same probabilities for the entire data block (e.g. 30 kB), probabilities are stored in the header - practically all Huffman and tANS compressors (however, there are considered exceptions: https://en.wikipedia.org/wiki/Adaptive_Huffman_coding ).

Adaptive can start with e.g. uniform probability (no need to store in header) and learns on the way - it is more costly but gives better compression, used with arithmetic coding or rANS. See https://fgiesen.wordpress.com/2015/05/26/models-for-adaptive... https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/

Re: Smaller and faster data compression with Zstandard

#159

Post by Blaisorblade0 »

Grishnakh wrote: post #64
VanillaCafe wrote: post #14

Earlier quoted context omitted.

https://en.wiktionary.org/wiki/bikeshedding

This isn't bikeshedding. Bikeshedding is about quibbling over unimportant details. Names are critically and absolutely important. Lots of great things have been hobbled or ruined by poorly-chosen names. A terrible name can cause something worthy to be ignored in favor of something inferior but with a better name. And you don't need to even be competent in the inner workings of a project to criticize its name or sugge…

https://en.wikipedia.org/wiki/Godwin%27s_law ? :-D

Re: Smaller and faster data compression with Zstandard

#160

Post by Twirrim »

Cyan4973 wrote: post #153
Twirrim wrote: post #147

Earlier quoted context omitted.

Dug in a bit further. On the non-x86 architecture I use, it looks like it's really just straight core performance that explains it. pigz's only advantage there really seems to be the brute force parallelism. In particular note the huge difference in branches between gzip and zstd on decompress: 8959780663 branches # 143.024 M/sec 2969481781 branches # 64.454 M/sec and on misses: 542158823 branch-misses # 6.05% of all…

There is now a pzstd implementation, if you wish to compare it to pigz

Had a shot. It's slightly buggy, but holy crap is it fast.

I'm not a C programmer, understanding what happened is a bit beyond me but: 1) to compile on linux it needs the -pthread flag passed to it, Makefile is missing that (compiles fine on OS X) 2) decompression over stdin appears to be effectively impossible, still demands in input file. Compression over stdin works fine.

Post reply on HN