Is this being pushed as being standard as part of the HTTP spec, seeing that it comes from Facebook?
Just about anything is better than brotli.
Smaller and faster data compression with Zstandard
51–60 of 166 posts
Re: Smaller and faster data compression with Zstandard
#52The goals sound similar to Apple's LZFSE (see https://github.com/lzfse/lzfse for more). Any comparison out there?
Apple's goals were also to have a low-energy de/compressor suitable for mobile. I'd love to see some comparisons of the two of them running on ARM.
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.)
Re: Smaller and faster data compression with Zstandard
#53The plot of compression ratio against speed for the various compression levels is pretty helpful for understanding its performance: https://scontent.fsnc1-3.fna.fbcdn.net/t39.2365-6/14146892_9... "The x-axis is a decreasing logarithmic scale in megabytes per second; the y-axis is the compression ratio achieved." I'd love to see a version of this chart that also included Brotli. (And I'm somewhat surprised Brotli isn'…
I thought that brotli was tuned for typical web workloads, that it contained a dictionary tuned for web workloads. Our internal testing shows that it performs very poorly for binary 3D vector data. So a test between zstd and brotli would show brotli in a poor light if it used a mixed corpus, but a test between zstd and brotli on a web corpus would give an advantage to brotli...
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 words and phrases that I'd associate with Wikipedia's "house style".
Re: Smaller and faster data compression with Zstandard
#54The goals sound similar to Apple's LZFSE (see https://github.com/lzfse/lzfse for more). Any comparison out there?
That was my first thought, too. I installed and ran both against a tar'd set of PDF files totaling 435MB in size. My timings: lzfse 45 MB/s encode, 229 MB/s decode, 1.12 comp ratio zstd 181 MB/s encode, 713 MB/s decode, 1.13 comp ratio The numbers are so dramatically different that I ran several different tests, but those results showed the same rough results. I used default command-line options for both tools, and b…
I use "fastest to complete == least power usage" as a rule of thumb because of "race to sleep". I suppose that might be thrown off by power usage characteristics varying based on number of cores working? How does one even begin to write code that prioritizes power-efficiency over performance?
Re: Smaller and faster data compression with Zstandard
#55How difficult is this new standard going to be to implement in another language? It seems highly sophisticated -- which is great, of course -- but the cost of that is relying on giants like Facebook to maintain their One True Implementation. For software this is (usually) fine; for a nee standard, it's a problem.
The majority of the work was done by a single person though. I think by the time facebook joined the majority design was done. Granted he doesn't seem to be like a normal person so doesn't matter that way.
But for compression isn't majority of the language would actually use bindings rather than implementing it natively for performance to make this moot.
I would assume the road to finding the optimal solution and understanding why it worked is much more complicated than the actual code. And a quick look doesn't seem to suggest its a very big code base for the library itself.
Re: Smaller and faster data compression with Zstandard
#56The goals sound similar to Apple's LZFSE (see https://github.com/lzfse/lzfse for more). Any comparison out there?
That was my first thought, too. I installed and ran both against a tar'd set of PDF files totaling 435MB in size. My timings: lzfse 45 MB/s encode, 229 MB/s decode, 1.12 comp ratio zstd 181 MB/s encode, 713 MB/s decode, 1.13 comp ratio The numbers are so dramatically different that I ran several different tests, but those results showed the same rough results. I used default command-line options for both tools, and b…
"Note that LZFSE has a somewhat different goal, however: it's designed to be the most power-efficient compression algorithm out there, in other words on mobile devices LZFSE optimizes for bytes-per-watt rather than bytes-per-second."
Sure, but is that even relevant? I mean, is there any way that lzfse could possibly be more power-efficient per byte than zstd when zstd is 3-4 times faster for the same compression ratio? According to the docs zstd doesn't have any support for multiple threads right now, so it should be a fair comparison.
Re: Smaller and faster data compression with Zstandard
#57I'm a complete dunce when it comes to compression and how it fits in the industry, so help me out here. Say that everyone accepts that Zstandard is amazing and we should start using it. What would the adoption process look like? I understand individual programs could implement it since they would handle both compression and decompression, but what about the web? Would HTTP servers first have to add support, then brow…
>what about the web
The browser sends the server a request header indicating which compression methods it understands. Current Firefox for example sends
Accept-Encoding: gzip, deflate, br
This means the adoption path for the web would be an implemtation in at least one major browser, which advertises this capability with the Accept-Encoding header. Then any server can start using Zstandard for clients accepting it.
Re: Smaller and faster data compression with Zstandard
#58There is just so much awesome stuff in this article. Finite State Entropy and Asymmetric Numeral System are completely new concepts to me (I've got 7 open tabs just from references FB supplied in the article), as is repcode modeling. I love that they've already built in granular control over the compression tradeoffs you can make, and I can't wait to look into Huff0. If anyone outside of Facebook has started playing…
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" that can be decoded back into the message (IE a fraction like 0.53817213781271231 ....)
range coding is similar, it just uses integers instead of floating point. You get one number that can be decoded back into the message (IE a number like 12312381219129123123).
Note that in both of these, you have not changed the number system at all. The number of even numbers and odd numbers still has the same density.
Another way to look at the above is based on what a bit selects.
In huffman, a single bit is generally not enough to select something, the prefixes are long. So you need to walk a bunch of bits to figure out what you've got.
In arithmetic or range coding, a single bit selects a very large range. They change the proportions of those ranges, but at some point, something has to describe that range. This is because it's a range. Knowing you have gotten to the 8 in 0.538 doesn't tell you anything on it's own, you need to know "the subrange for symbol a is 0.530 ... 0.539", so it's a. So you have to transmit that range.
ANS is a different trick. Instead of encoding things using the existing number system, it changes the number system. That is, it redefines the number system so that our even and odd numbers are still uniformly distributed but have different densities. If you do this in the right way, you end up with a number system that lets you only require one number to determine the state, instead of two (like in a range).
Re: Smaller and faster data compression with Zstandard
#59Yann will be giving a talk on Zstandard at today's @Scale 2016 conference, and the video will be posted. He can answer the most technical questions about Zstandard, but I may be able to answer some as well; we both work on compression at Facebook.
I am really looking forward to this. I usually like to read more than vidoes but for complicated topic with a good presenter it can actually be a comprehensive starting point. Would the video also be posted today or we will have to wait? One thing I haven't figured out from either today's post or Yann's blog is whether Zstandard is switching between huff0 and FSE depending on compression level or is it somehow using…
I'm not sure when videos will be posted -- hopefully soon.
All benchmarks today are single threaded. The algorithm itself is single threaded, but can be parallelized across cores. We will soon release a pzstd command line utility to demonstrate this, similar to pigz, which accelerates both compression and decompression.
Zstandard uses both huff0 and FSE together when it compresses -- it doesn't switch between them based on the input.
Re: Smaller and faster data compression with Zstandard
#60If anyone wants to try it on windows there is a 7-zip install with support for ZSTD