14 ms·

Smaller and faster data compression with Zstandard

819 points by jamesgpearce 10y ago

Grishnakh 10y ago
Looks very interesting, however I'm not impressed by the name. "Zstandard"??? With ".zstd" as the extension? I don't like it. They should have named it letter-zip, along the lines of gzip, bzip, and xzip, with the extension letterz. "fz" would have been a good one since they work at Facebook.
- levbrie 10y ago
  Agreed. How did they not call it "Pied Piper"?
  - ryeguy_24 10y ago
    I was waiting for that reference.
- VanillaCafe 10y ago
  https://en.wiktionary.org/wiki/bikeshedding https://en.wiktionary.org/wiki/bikeshedding
  - Grishnakh 10y ago
    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 suggest better ones. The people who name cars aren't the same people who design the engine-control algorithms for them. If you disagree, what do you think of naming your kid "Adolph Hitler [lastname]"? Most people agree that a name like that will cause great harm to a child growing up because of the constant ridicule and ostracization he'd inevitably face. That's an extreme example, but names are important. Note that I don't think this project's name is horrible, but I don't think it's very good either, and could be a lot better.
    - Blaisorblade0 10y ago
      https://en.wikipedia.org/wiki/Godwin%27s_law https://en.wikipedia.org/wiki/Godwin%27s_law ? :-D
- niftich 10y ago
  It used to be called just 'zstd' but I guess that wasn't very pronounceable.
  - wvenable 10y ago
    Zesty!
    - caf 10y ago
      Zed-Stud
- rspeer 10y ago
  ...yeah, why didn't they claim part of a namespace that only has room for 26 (or 36) things? Everyone else is doing it!
  - Grishnakh 10y ago
    I don't see the problem: only 3 members of that namespace are currently claimed (4 out of the 36-member namespace: 7z), so we have room for 23 (or 32) more compression standards before running out. We've been using gzip for, what, 20 years now? Only recently have we gotten xz. At this rate, we won't run out of compression standards using this scheme for roughly 153 years. And after that, we could always start using capital Zs, like the old "compress" standard that used the .Z extension. Or we could go to a 3-letter extension ending in z, such as ".fbz", which gives you 676 more options, and 4507 years. Considering that general-purpose data compression really hasn't moved that much since the DEFLATE algorithm took over, and only recently had any real change with the advent of LZMA (used in p7zip and xz), and perhaps this new zstd (too soon to tell), my time estimates here are probably too short.
    - twic 10y ago
      Perhaps we should require the less common algorithms to have a longer prefix.
      - Grishnakh 10y ago
        There's no way to know what's going to be a common algorithm in the future unless you have a time machine. When DEFLATE was first invented, it wasn't common either, it was brand-new. Now it's everywhere. This new algorithm might become just as ubiquitous in 10 years, or it might turn into the next bzip2, or worse, the next ZOO.
        twic 10y ago
        You're right, of course. So we should base it on how common the algorithm was in the compressions we've done so far. (I am not sure if i need to clarify that my original comment was meant to be a joke about Huffman coding)
ktta 10y ago
Some more benchmarks on this[0] page Also, I actually discovered something very interesting (to me at least). At the bottom of the link mentioned below, the link attached says https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd but then redirects to https://github.com/facebook/zstd https://github.com/facebook/zstd . Anyone know why? [0]: http://facebook.github.io/zstd/ http://facebook.github.io/zstd/ EDIT: After a little bit of sleuthing, it looks like the author of zstd (github.com/Cyan4973) is now contributing[1] to github.com/facebook/zstd And the page layout for lz4[2] looks the same as zstd[0] Anyone know if Yann Collet works for/with facebook on things other than zstd? EDIT 2: In the time it took me to google a couple things, looks like the children comments have already answered my questions. Also, previous discussions on zstd (not that its completely relevant) -https://news.ycombinator.com/item?id=8941955 https://news.ycombinator.com/item?id=8941955 https://www.reddit.com/r/programming/comments/2tibrh/zstd_a_new_compression_algorithm/ https://www.reddit.com/r/programming/comments/2tibrh/zstd_a_... [1]:https://github.com/facebook/zstd/pull/312 https://github.com/facebook/zstd/pull/312 [2]: http://cyan4973.github.io/lz4/ http://cyan4973.github.io/lz4/
- jakozaur 10y ago
  Cyan4973 is hired by Facebook. He is famous author of LZ4. Likely they decided to move their sponsor project to their organization most likely for PR.
- 0xmohit 10y ago
  It hasn't been long that I fetched zstd from https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd Upon looking further, it turns out that the author Yann Collet [0] works with Facebook now; the repo would have been thus transferred to Facebook. Author's blog [1]. [0] https://twitter.com/Cyan4973 https://twitter.com/Cyan4973 [1] http://fastcompression.blogspot.in/ http://fastcompression.blogspot.in/
  - ktta 10y ago
    >It hasn't been long that I fetched zstd from https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd Yep, and Google too https://www.google.co.in/search?q=zstd https://www.google.co.in/search?q=zstd > it turns out that the author Yann Collet [0] works with Facebook now yep https://www.facebook.com/yann.collet.73 https://www.facebook.com/yann.collet.73 On another note, wonder what happens when personal and professional lives can interfere. The profile of Yann Collet in the blog post is the above link and I can't help but think, why am I on faceook looking at a baby's picture on someone's profile instead of Github or at least LinkedIn? Seems like something he might want to keep private (and yes, I'm totally assuming here, I don't know his preferences) Now, I know you can restrict the stuff you post to friends only instead of public like he did, but it is still something people(and facebook for its employees) should consider if they want their facebook profile to become their professional contact page.
deleted 10y ago
[deleted]
AceJohnny2 10y ago
Note: this is from the same guy who created the popular lz4 compressor, Yann Collet: http://cyan4973.github.io/lz4/ http://cyan4973.github.io/lz4/ https://twitter.com/Cyan4973 https://twitter.com/Cyan4973
markonen 10y ago
The goals sound similar to Apple's LZFSE (see https://github.com/lzfse/lzfse https://github.com/lzfse/lzfse for more). Any comparison out there?
- Jerry2 10y ago
  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.
  - mark-r 10y ago
    I'd love to see that too. Remember that if the processor uses 2x the power but gets done 3x faster, it's still 1.5x more efficient overall.
    - tmd83 10y ago
      Thats what I was thinking. I haven't found any validation or even the rationale behind lzfse's supposed lower power usage. I can think of two things. 1. Apple tried to write a fast and reasonably compressible version of LZ4 thus improving power usage by creating LZFSE since none existed but beaten out handsomely by Zstandard. 2. Following a parent comment, Zstandard might some of the things that are dependent on a highly OoO cpu with lots of caches, extremely good branch predictor that could be significantly slower on an ARM even the apple one despite how good they are. Or they could still be slower but on ARM the gap might not be as big and the decision not as cut and dry as it seems now. Would love to know what the actual case is from someone involved in LZFSE.
  - MichaelGG 10y ago
    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.)
levbrie 10y ago
There 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 with it or is planning to put it into production right away I'd love to hear about it.
- tmd83 10y ago
  I think you should look at the author's blog [0]. There is lots of in depth explanation of not just what he is doing but how he got there, the failed steps, the intermediate steps. [0] http://fastcompression.blogspot.in/ http://fastcompression.blogspot.in/
- joseraul 10y ago
  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 https://dl.dropboxusercontent.com/u/12405967/ANSsem.pdf Not sure exactly when repcodes were invented. Igor Pavlov has already used them in 7zip.
  - DannyBee 10y ago
    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).
cbr 10y ago
The 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_944159239044397_638267599_n.jpg 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't mentioned at all.) (Disclaimer: I work at Google, which made Brotli)
- justinsaccount 10y ago
  The README at https://github.com/facebook/zstd https://github.com/facebook/zstd mentions brotli
- jithesh 10y ago
  Brotli is available in this graph - https://github.com/facebook/zstd/blob/master/images/DCspeed5.png https://github.com/facebook/zstd/blob/master/images/DCspeed5... This seems to be slightly old doc - from April.
- bryanlarsen 10y ago
  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...
  - niftich 10y ago
    'tuned' for the brotli dictionary is a bit generous [1], but yes, it contains a smattering of strings [2] you'd find in plain text and web documents. Because of its seemingly haphazard dictionary, I wouldn't rule out zstd outperforming brotli, if trained on a good dataset. [1] https://news.ycombinator.com/item?id=12010313 https://news.ycombinator.com/item?id=12010313 [2] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e
nemo1618 10y ago
How 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.
- ctur 10y ago
  The format itself is documented (https://github.com/facebook/zstd/blob/master/zstd_compression_format.md https://github.com/facebook/zstd/blob/master/zstd_compressio...) with the intention of other implementations and language bindings being readily available. We also have a zlib-compatible API for easier porting to applications already using Zlib. Our hope is that Zstandard is both easy to use and easy to contribute to.
- tmd83 10y ago
  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.
deleted 10y ago
[deleted]
ctur 10y ago
Yann 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.
- tmd83 10y ago
  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 both together? Also the post says its both OoO friendly and multi-core friendly but the speed benchmarks are those in a single core context or multi-core? Does only the format/algorithm multi-core friendly or the standard cli can run multi-threaded.
  - ctur 10y ago
    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.
  - twitch_checksum 10y ago
    Video is now available here : https://atscaleconference.com/videos/real-time-data-compression-at-scale/ https://atscaleconference.com/videos/real-time-data-compress...
- deleted 10y ago
  [deleted]
- socmag 10y ago
  Hey quick question, and sounds awesome. If I wanted to use this in the pipeline of my servers Journaling system, is there any requirement that I restart the stream periodically. That is to say, should I use it per journal entry (probably not a good idea for short messages), for the entire uptime of the writer, or with periodic restarts? Obviously can measure and find out for myself, but wondered if you had any thoughts. Thanks!
tmd83 10y ago
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 implementation blazes past zlib huffman though compresses less than FSE [0]. I also like reading his blog posts. While a lot of them goes over my head I can generally make a sense of what he is trying and why something's working despite the complexity. [0] https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy
- jerven 10y ago
  I agree, I just started using Zstd for uniprot.org (dev branch) and it looks like it is a lot faster in decoding than deflate or zlib and even smaller on disk. It is one of those things where the improvement really matters for us and gives us faster results for our users. i.e. download speed is up to 20% faster with Zstd as compression algo for backing store compared to Deflate. Assuming bandwidth is available ;)
- rektide 10y ago
  Cyan4973/Yann also is well known for xxhash[1], which is one of the faster hashers[2] out there. Post a new hasher and people will probably ask about xxhash (ex: metrohash[3]). Guy is an absolute machine. If you search Google for 'zstd' right now, you'll find him, not Facebook, namely: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd . Glad his work is being supported by someone now! Immensely well deserved, after so many years of helping make everyone fast. PS - I didn't know a lot of the terms you used, but the Finite State Entropy (FSE) link you provided does a good job intro'ing some of them, and the linked paper Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding [4] (ANS) seems interesting. [1] https://github.com/Cyan4973/xxHash https://github.com/Cyan4973/xxHash [2] https://github.com/rurban/smhasher https://github.com/rurban/smhasher [3] https://news.ycombinator.com/item?id=9613098 https://news.ycombinator.com/item?id=9613098 [4] http://arxiv.org/abs/1311.2540 http://arxiv.org/abs/1311.2540
deleted 10y ago
[deleted]
AceJohnny2 10y ago
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. This is a tuning recommendation, though, not a compression format limitation." 8MB for the smallest preset? Back in the mid-2000s, I was attending a Jabber/XMPP discussion, about the viability of using libz for compressing the stream. It turned out that even just a 32kb window is huge when your connection server is handling thousands of connections at a time, and they were investigating the effect of using a modified libz with an even smaller window (it was hard-coded, back then). I know Moore's law is in ZStandard's favor w.r.t. memory usage (what's 8MB when your server's got 64GB or more?), but I think it's useful to note that this is squarely aimed at web traffic backed by beefy servers.
- joseraul 10y ago
  > what's 8MB when your server's got 64GB Note that 8Mb is the size of the L3 cache on some modern Intel chips. You want fast lookups in the window area, where you constantly do random-access reads.
- Scaevolus 10y ago
  You can get pretty far with "amnesiac" zlib for networking, too. You collect up writes in your out-buffer, and use zlib to compress it before transmission. The trick is that you don't retain context or find matches between chunks, so there's no memory overhead between sends.
- tmd83 10y ago
  Not sure I agree. The 8 MB is the recommended upper limit so I don't think anyone is planning to use it for the web traffic. I think its designed to be faster and have better compression even at lower window size though not sure how low. It most likely perform better than zlib even at 32KB at least faster I would assume. Now if you are a jabber/chat server opening thousands of long running connection there it can be an issue. You already said how even standard zlib doesn't work there.
deleted 10y ago
[deleted]
f137 10y ago
Probably nictpicking but "Smaller data compression" makes no sense really
mozumder 10y ago
Is this being pushed as being standard as part of the HTTP spec, seeing that it comes from Facebook?
- mrmrben 10y ago
  Just about anything is better than brotli.
mrmrben 10y ago
Really nice work compared to what I consider to be the quite bad Brotli -- an incredibly slow compression standard that only ended up in browsers because it was created by Google.
- tessela 10y ago
  except for the PATENTS file =/
  - ac29 10y ago
    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.
    - amluto 10y ago
      On a cursory glance, the VP9 patent license is much nicer: it only gets voided if you sue about VP9. That being said: has anyone actually given any indication that there are any relevant patents in the first place?
    - foepys 10y ago
      But doesn't that mean that Facebook can use any of your patents and you cannot sue them unless you don't use zstd?
    - gcp 10y ago
      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.
      - prirun 10y ago
        If Facebook wanted zstd in the browsers, which would make sense for them to be able to reduce bandwidth and improve performance, the patent grant seems to make that impossible: Google would never put zstd in Chrome with such a clause.
ohitsdom 10y ago
I'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 browser vendors would follow?
- wongarsu 10y ago
  >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 meaning the server is free to send a response compressed with either gzip, deflate or brotli. Or the server can choose to send the data uncompressed. 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.
  - ohitsdom 10y ago
    Nice, so really browsers and servers can implement it independently. Seems elegant, I like that browsers can advertise multiple compression formats. Thanks for the info!
    - riboflava 10y ago
      It's also possible to implement a decompressor in javascript to support browsers which don't do it natively. The performance would likely suck but if you're truly bandwidth constrained and don't mind users having a bit of a lag, it's an option...
      - hueving 10y ago
        Assuming the size of the decompressor isn't larger than the savings you gained from using this compression algo over another...
yread 10y ago
If anyone wants to try it on windows there is a 7-zip install with support for ZSTD https://mcmilk.de/projects/7-Zip-zstd/ https://mcmilk.de/projects/7-Zip-zstd/
tambourine_man 10y ago
Isn't it a bit presumptuous to call your own thing "standard"?
- partycoder 10y ago
  Like these guys: https://github.com/feross/standard https://github.com/feross/standard, which is permissive to the point it's completely pointless. You can follow it to the letter and still end up with vomit code.
esaym 10y ago
>> "It is written in highly portable C, making it suitable for practically every platform used today" I love C, it is not the enemy everyone makes it out to be. It's already in debian: https://packages.debian.org/stretch/zstd https://packages.debian.org/stretch/zstd and judging by the small requirements,it is portable indeed.
lasryaric 10y ago
Whats their weissman score?
- brickmort 10y ago
  I bet it doesn't even touch pied piper's.
ilostmykeys 10y ago
How does this compete with PiedPiper?
- bbcbasic 10y ago
  This is general purpose whereas Pied Piper, Hooli et al. focussed on video.
espadrine 10y ago
The following link points to a fairly good benchmark / tool that showcases the tradeoffs in real life: since (de)compression takes time, what is the fastest way to transmit data at a given transfer speed? https://quixdb.github.io/squash-benchmark/unstable/#transfer-plus-processing https://quixdb.github.io/squash-benchmark/unstable/#transfer... Spoilers: zstd wins at ethernet and wifi (and is among the best in 4G), lz4 wins at hard drive encryption… both were designed by the same author.
- jacobolus 10y ago
  Charles Bloom’s Oodle new codecs handily beat them across the scale: http://cbloomrants.blogspot.com http://cbloomrants.blogspot.com http://www.cbloom.com/oodle_arm_report/ http://www.cbloom.com/oodle_arm_report/ http://www.cbloom.com/rants.html http://www.cbloom.com/rants.html Caveat: proprietary commercial product.
kstrauser 10y ago
That's truly beautiful. Thanks, Facebook! I particularly love that you can pre-compute and reuse dictionaries, say if you're regularly compressing similar JSON objects.
DJ_Icebear 10y ago
Should've named it "Pied Piper"
DJ_Icebear 10y ago
They should've named it "Pied Piper".
erichocean 10y ago
For this to become anything like a standard, Facebook would have to remove its patent poison pill.
ryao 10y ago
This is an awesome blog post that is very well written, but the lack of incompressible performance analysis prevents It from providing a complete overview of zstd. Incompressible performance measurements are important for interactive/realtime workloads and the numbers are extremely interesting because they can differ dramatically from the average case measurements. LZ4 for instance has been measured at doing 10GB/sec on incompressible data on a single core of a modern Intel Xeon processor. At the other end of the spectrum is the worst case scenario for incompressible data where performance slows to a crawl. I do not recall any examples in this area, but the point is that it is possible for algorithms to have great average case performance and terrible worst case performance. Quick sort is probably the most famous example of that concept. I have no reason to suspect that zstd has bad incompressible performance, but the omission of incompressible performance numbers is unfortunate.
- Cyan4973 10y ago
  zstd goes at > 1 GB/s on uncompressible data. It has some fast heuristics for such cases too.
z3t4 10y ago
Tables should be in HTML.
cromwellian 10y ago
I think for typical JS/CSS/HTML sizes, and decompression times, probably maximum compression ratio, followed by decompression speed is what I'd look for. I don't care too much about compression speed, in the sense that if I have to spend 1 minute compressing JS to crunch it by 10%, but I serve that file a million times, then as long as decompression doesn't negate the gain in network time saved, it's a win. I guess the other factor for mobile is, besides memory and decompression speed, how do various compression schemes fare battery wise?
- nikkun 10y ago
  Regarding decompression times, I think it's much more important to save transferred network data than to prioritize quicker decompression. HTTP request times have a long tail; they can get really slow for the many, many people limited to slow connections. Decompression times are going to be much more consistent. Our aim here should be to improve the 10% slowest requests, and you do that by optimizing the actual transfer.
xrstf 10y ago
Quick benchmark on a 194MiB SQL dump: gzip -9: 27.574s, 48MiB output zstd -9: 14.182s, 41MiB output Thanks, I'll gladly use zstd as a drop-in replacement for my daily backups. :)
bananaoomarang 10y ago
Best middle-out in the game.
kaushalp88 10y ago
Should we start with the pied piper jokes now or later?
- bbcbasic 10y ago
  Not until I know the Weissman Score of Zstandard.
cristiandan 10y ago
Awesome
deleted 10y ago
[deleted]
faragon 10y ago
Beautiful.
partycoder 10y ago
Unless they integrate it into software like web servers and web browsers it will be hard to see it really flourish as a "standard". But at least within the perimeter of your own systems you can totally profit from this technology now.
morecoffee 10y ago
A recent compression discussion I saw involved how do compressors fare on uncompressible input? For example, suppose you wanted to add compression to all your outbound network traffic. What would happen if there was mixed compressible traffic along with the uncomressible kind? A common case would be sending HTML along with JPEG. Good compressors can't squeeze any more out of a JPEG, but they can back off fast and go faster. Snappy was designed to do this, and even implementations of gzip do it too. It greatly reduces the fear of CPU overhead to always on compression. I wonder how Zstd handles such cases? *Ignoring security altogether
- nimrody 10y ago
  Dropbox say they can losslessly compress JPEG files (~20% saving): https://blogs.dropbox.com/tech/2016/07/lepton-image-compression-saving-22-losslessly-from-images-at-15mbs/ https://blogs.dropbox.com/tech/2016/07/lepton-image-compress...
  - gcp 10y ago
    Known techniques. JPEG uses Huffman coding for entropy coding, you can replace that with arithmetic coding. This requires knowing the format details, though.
- Cyan4973 10y ago
  Zstd pass faster over incompressible data. Expect something > 1 GB/s
bnolsen 10y ago
turbohf claims to be 4x faster than zlib's huffman coding and 2x faster than FSE and is a generic cpu implementation. Even if claims are only partially true and turbohf is a clean dropin replacement for zlib and licensing were friendly the appeal of zstd drops substantially in my book. http://encode.ru/threads/2276-TurboHF-1GB-s-Huffman-Coding-Reincarnation http://encode.ru/threads/2276-TurboHF-1GB-s-Huffman-Coding-R... https://sites.google.com/site/powturbo/entropy-coder https://sites.google.com/site/powturbo/entropy-coder
Twirrim 10y ago
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.
- Twirrim 10y ago
  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 branches 89060880 branch-misses # 3.00% of all branches
  - Cyan4973 10y ago
    There is now a pzstd implementation, if you wish to compare it to pigz
    - Twirrim 10y ago
      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.
mana_12 10y ago
Zstandard is both a command line tool (zstd) and a library.
anjanb 10y ago
I was looking for a windows version of zstd. On the github page, I could only get the version 0.81 version of the windows tool. Can someone release the 1.0 version of zstd for windows ?
philplckthun 10y ago
I'd love HTTP content encoding to support this and see a comparison to Brotli. Looks like it might be yet another good alternative to gzip.
hasszhao 10y ago
Ok
- sctb 10y ago
  Please don't do this, comments on HN need to be substantive.
mydeardiary 10y ago
If facebook hopes the new compression algorithm to be a standard, why doesn't it publish an IETF RFC draft? Will it follow OpenDNS way of dnscrypt by open-sourcing the reference implementation without publishing any IETF RFC draft?

819 points by jamesgpearce 10y ago

Looks very interesting, however I'm not impressed by the name. "Zstandard"??? With ".zstd" as the extension? I don't like it. They should have named it letter-zip, along the lines of gzip, bzip, and xzip, with the extension letterz. "fz" would have been a good one since they work at Facebook.

levbrie 10y ago
Agreed. How did they not call it "Pied Piper"?
- ryeguy_24 10y ago
  I was waiting for that reference.
VanillaCafe 10y ago
https://en.wiktionary.org/wiki/bikeshedding https://en.wiktionary.org/wiki/bikeshedding
- Grishnakh 10y ago
  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 suggest better ones. The people who name cars aren't the same people who design the engine-control algorithms for them. If you disagree, what do you think of naming your kid "Adolph Hitler [lastname]"? Most people agree that a name like that will cause great harm to a child growing up because of the constant ridicule and ostracization he'd inevitably face. That's an extreme example, but names are important. Note that I don't think this project's name is horrible, but I don't think it's very good either, and could be a lot better.
  - Blaisorblade0 10y ago
    https://en.wikipedia.org/wiki/Godwin%27s_law https://en.wikipedia.org/wiki/Godwin%27s_law ? :-D
niftich 10y ago
It used to be called just 'zstd' but I guess that wasn't very pronounceable.
- wvenable 10y ago
  Zesty!
  - caf 10y ago
    Zed-Stud
rspeer 10y ago
...yeah, why didn't they claim part of a namespace that only has room for 26 (or 36) things? Everyone else is doing it!
- Grishnakh 10y ago
  I don't see the problem: only 3 members of that namespace are currently claimed (4 out of the 36-member namespace: 7z), so we have room for 23 (or 32) more compression standards before running out. We've been using gzip for, what, 20 years now? Only recently have we gotten xz. At this rate, we won't run out of compression standards using this scheme for roughly 153 years. And after that, we could always start using capital Zs, like the old "compress" standard that used the .Z extension. Or we could go to a 3-letter extension ending in z, such as ".fbz", which gives you 676 more options, and 4507 years. Considering that general-purpose data compression really hasn't moved that much since the DEFLATE algorithm took over, and only recently had any real change with the advent of LZMA (used in p7zip and xz), and perhaps this new zstd (too soon to tell), my time estimates here are probably too short.
  - twic 10y ago
    Perhaps we should require the less common algorithms to have a longer prefix.
    - Grishnakh 10y ago
      There's no way to know what's going to be a common algorithm in the future unless you have a time machine. When DEFLATE was first invented, it wasn't common either, it was brand-new. Now it's everywhere. This new algorithm might become just as ubiquitous in 10 years, or it might turn into the next bzip2, or worse, the next ZOO.
      - twic 10y ago
        You're right, of course. So we should base it on how common the algorithm was in the compressions we've done so far. (I am not sure if i need to clarify that my original comment was meant to be a joke about Huffman coding)

ktta 10y ago

Some more benchmarks on this[0] page Also, I actually discovered something very interesting (to me at least). At the bottom of the link mentioned below, the link attached says https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd but then redirects to https://github.com/facebook/zstd https://github.com/facebook/zstd . Anyone know why? [0]: http://facebook.github.io/zstd/ http://facebook.github.io/zstd/ EDIT: After a little bit of sleuthing, it looks like the author of zstd (github.com/Cyan4973) is now contributing[1] to github.com/facebook/zstd And the page layout for lz4[2] looks the same as zstd[0] Anyone know if Yann Collet works for/with facebook on things other than zstd? EDIT 2: In the time it took me to google a couple things, looks like the children comments have already answered my questions. Also, previous discussions on zstd (not that its completely relevant) -https://news.ycombinator.com/item?id=8941955 https://news.ycombinator.com/item?id=8941955 https://www.reddit.com/r/programming/comments/2tibrh/zstd_a_new_compression_algorithm/ https://www.reddit.com/r/programming/comments/2tibrh/zstd_a_... [1]:https://github.com/facebook/zstd/pull/312 https://github.com/facebook/zstd/pull/312 [2]: http://cyan4973.github.io/lz4/ http://cyan4973.github.io/lz4/

jakozaur 10y ago
Cyan4973 is hired by Facebook. He is famous author of LZ4. Likely they decided to move their sponsor project to their organization most likely for PR.
0xmohit 10y ago
It hasn't been long that I fetched zstd from https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd Upon looking further, it turns out that the author Yann Collet [0] works with Facebook now; the repo would have been thus transferred to Facebook. Author's blog [1]. [0] https://twitter.com/Cyan4973 https://twitter.com/Cyan4973 [1] http://fastcompression.blogspot.in/ http://fastcompression.blogspot.in/
- ktta 10y ago
  >It hasn't been long that I fetched zstd from https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd Yep, and Google too https://www.google.co.in/search?q=zstd https://www.google.co.in/search?q=zstd > it turns out that the author Yann Collet [0] works with Facebook now yep https://www.facebook.com/yann.collet.73 https://www.facebook.com/yann.collet.73 On another note, wonder what happens when personal and professional lives can interfere. The profile of Yann Collet in the blog post is the above link and I can't help but think, why am I on faceook looking at a baby's picture on someone's profile instead of Github or at least LinkedIn? Seems like something he might want to keep private (and yes, I'm totally assuming here, I don't know his preferences) Now, I know you can restrict the stuff you post to friends only instead of public like he did, but it is still something people(and facebook for its employees) should consider if they want their facebook profile to become their professional contact page.

deleted 10y ago

[deleted]

AceJohnny2 10y ago

Note: this is from the same guy who created the popular lz4 compressor, Yann Collet: http://cyan4973.github.io/lz4/ http://cyan4973.github.io/lz4/ https://twitter.com/Cyan4973 https://twitter.com/Cyan4973

markonen 10y ago

The goals sound similar to Apple's LZFSE (see https://github.com/lzfse/lzfse https://github.com/lzfse/lzfse for more). Any comparison out there?

Jerry2 10y ago
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.
- mark-r 10y ago
  I'd love to see that too. Remember that if the processor uses 2x the power but gets done 3x faster, it's still 1.5x more efficient overall.
  - tmd83 10y ago
    Thats what I was thinking. I haven't found any validation or even the rationale behind lzfse's supposed lower power usage. I can think of two things. 1. Apple tried to write a fast and reasonably compressible version of LZ4 thus improving power usage by creating LZFSE since none existed but beaten out handsomely by Zstandard. 2. Following a parent comment, Zstandard might some of the things that are dependent on a highly OoO cpu with lots of caches, extremely good branch predictor that could be significantly slower on an ARM even the apple one despite how good they are. Or they could still be slower but on ARM the gap might not be as big and the decision not as cut and dry as it seems now. Would love to know what the actual case is from someone involved in LZFSE.
- MichaelGG 10y ago
  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.)

levbrie 10y ago

There 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 with it or is planning to put it into production right away I'd love to hear about it.

tmd83 10y ago
I think you should look at the author's blog [0]. There is lots of in depth explanation of not just what he is doing but how he got there, the failed steps, the intermediate steps. [0] http://fastcompression.blogspot.in/ http://fastcompression.blogspot.in/
joseraul 10y ago
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 https://dl.dropboxusercontent.com/u/12405967/ANSsem.pdf Not sure exactly when repcodes were invented. Igor Pavlov has already used them in 7zip.
- DannyBee 10y ago
  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).

cbr 10y ago

The 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_944159239044397_638267599_n.jpg 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't mentioned at all.) (Disclaimer: I work at Google, which made Brotli)

justinsaccount 10y ago
The README at https://github.com/facebook/zstd https://github.com/facebook/zstd mentions brotli
jithesh 10y ago
Brotli is available in this graph - https://github.com/facebook/zstd/blob/master/images/DCspeed5.png https://github.com/facebook/zstd/blob/master/images/DCspeed5... This seems to be slightly old doc - from April.
bryanlarsen 10y ago
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...
- niftich 10y ago
  'tuned' for the brotli dictionary is a bit generous [1], but yes, it contains a smattering of strings [2] you'd find in plain text and web documents. Because of its seemingly haphazard dictionary, I wouldn't rule out zstd outperforming brotli, if trained on a good dataset. [1] https://news.ycombinator.com/item?id=12010313 https://news.ycombinator.com/item?id=12010313 [2] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e

nemo1618 10y ago

How 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.

ctur 10y ago
The format itself is documented (https://github.com/facebook/zstd/blob/master/zstd_compression_format.md https://github.com/facebook/zstd/blob/master/zstd_compressio...) with the intention of other implementations and language bindings being readily available. We also have a zlib-compatible API for easier porting to applications already using Zlib. Our hope is that Zstandard is both easy to use and easy to contribute to.
tmd83 10y ago
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.

deleted 10y ago

[deleted]

ctur 10y ago

Yann 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.

tmd83 10y ago
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 both together? Also the post says its both OoO friendly and multi-core friendly but the speed benchmarks are those in a single core context or multi-core? Does only the format/algorithm multi-core friendly or the standard cli can run multi-threaded.
- ctur 10y ago
  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.
- twitch_checksum 10y ago
  Video is now available here : https://atscaleconference.com/videos/real-time-data-compression-at-scale/ https://atscaleconference.com/videos/real-time-data-compress...
deleted 10y ago
[deleted]
socmag 10y ago
Hey quick question, and sounds awesome. If I wanted to use this in the pipeline of my servers Journaling system, is there any requirement that I restart the stream periodically. That is to say, should I use it per journal entry (probably not a good idea for short messages), for the entire uptime of the writer, or with periodic restarts? Obviously can measure and find out for myself, but wondered if you had any thoughts. Thanks!

tmd83 10y ago

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 implementation blazes past zlib huffman though compresses less than FSE [0]. I also like reading his blog posts. While a lot of them goes over my head I can generally make a sense of what he is trying and why something's working despite the complexity. [0] https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy

jerven 10y ago
I agree, I just started using Zstd for uniprot.org (dev branch) and it looks like it is a lot faster in decoding than deflate or zlib and even smaller on disk. It is one of those things where the improvement really matters for us and gives us faster results for our users. i.e. download speed is up to 20% faster with Zstd as compression algo for backing store compared to Deflate. Assuming bandwidth is available ;)
rektide 10y ago
Cyan4973/Yann also is well known for xxhash[1], which is one of the faster hashers[2] out there. Post a new hasher and people will probably ask about xxhash (ex: metrohash[3]). Guy is an absolute machine. If you search Google for 'zstd' right now, you'll find him, not Facebook, namely: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd . Glad his work is being supported by someone now! Immensely well deserved, after so many years of helping make everyone fast. PS - I didn't know a lot of the terms you used, but the Finite State Entropy (FSE) link you provided does a good job intro'ing some of them, and the linked paper Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding [4] (ANS) seems interesting. [1] https://github.com/Cyan4973/xxHash https://github.com/Cyan4973/xxHash [2] https://github.com/rurban/smhasher https://github.com/rurban/smhasher [3] https://news.ycombinator.com/item?id=9613098 https://news.ycombinator.com/item?id=9613098 [4] http://arxiv.org/abs/1311.2540 http://arxiv.org/abs/1311.2540

deleted 10y ago

[deleted]

AceJohnny2 10y ago

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. This is a tuning recommendation, though, not a compression format limitation." 8MB for the smallest preset? Back in the mid-2000s, I was attending a Jabber/XMPP discussion, about the viability of using libz for compressing the stream. It turned out that even just a 32kb window is huge when your connection server is handling thousands of connections at a time, and they were investigating the effect of using a modified libz with an even smaller window (it was hard-coded, back then). I know Moore's law is in ZStandard's favor w.r.t. memory usage (what's 8MB when your server's got 64GB or more?), but I think it's useful to note that this is squarely aimed at web traffic backed by beefy servers.

joseraul 10y ago
> what's 8MB when your server's got 64GB Note that 8Mb is the size of the L3 cache on some modern Intel chips. You want fast lookups in the window area, where you constantly do random-access reads.
Scaevolus 10y ago
You can get pretty far with "amnesiac" zlib for networking, too. You collect up writes in your out-buffer, and use zlib to compress it before transmission. The trick is that you don't retain context or find matches between chunks, so there's no memory overhead between sends.
tmd83 10y ago
Not sure I agree. The 8 MB is the recommended upper limit so I don't think anyone is planning to use it for the web traffic. I think its designed to be faster and have better compression even at lower window size though not sure how low. It most likely perform better than zlib even at 32KB at least faster I would assume. Now if you are a jabber/chat server opening thousands of long running connection there it can be an issue. You already said how even standard zlib doesn't work there.

deleted 10y ago

[deleted]

f137 10y ago

Probably nictpicking but "Smaller data compression" makes no sense really

mozumder 10y ago

Is this being pushed as being standard as part of the HTTP spec, seeing that it comes from Facebook?

mrmrben 10y ago
Just about anything is better than brotli.

mrmrben 10y ago

Really nice work compared to what I consider to be the quite bad Brotli -- an incredibly slow compression standard that only ended up in browsers because it was created by Google.

tessela 10y ago
except for the PATENTS file =/
- ac29 10y ago
  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.
  - amluto 10y ago
    On a cursory glance, the VP9 patent license is much nicer: it only gets voided if you sue about VP9. That being said: has anyone actually given any indication that there are any relevant patents in the first place?
  - foepys 10y ago
    But doesn't that mean that Facebook can use any of your patents and you cannot sue them unless you don't use zstd?
  - gcp 10y ago
    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.
    - prirun 10y ago
      If Facebook wanted zstd in the browsers, which would make sense for them to be able to reduce bandwidth and improve performance, the patent grant seems to make that impossible: Google would never put zstd in Chrome with such a clause.

ohitsdom 10y ago

I'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 browser vendors would follow?

wongarsu 10y ago
>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 meaning the server is free to send a response compressed with either gzip, deflate or brotli. Or the server can choose to send the data uncompressed. 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.
- ohitsdom 10y ago
  Nice, so really browsers and servers can implement it independently. Seems elegant, I like that browsers can advertise multiple compression formats. Thanks for the info!
  - riboflava 10y ago
    It's also possible to implement a decompressor in javascript to support browsers which don't do it natively. The performance would likely suck but if you're truly bandwidth constrained and don't mind users having a bit of a lag, it's an option...
    - hueving 10y ago
      Assuming the size of the decompressor isn't larger than the savings you gained from using this compression algo over another...

yread 10y ago

If anyone wants to try it on windows there is a 7-zip install with support for ZSTD https://mcmilk.de/projects/7-Zip-zstd/ https://mcmilk.de/projects/7-Zip-zstd/

tambourine_man 10y ago

Isn't it a bit presumptuous to call your own thing "standard"?

partycoder 10y ago
Like these guys: https://github.com/feross/standard https://github.com/feross/standard, which is permissive to the point it's completely pointless. You can follow it to the letter and still end up with vomit code.

esaym 10y ago

>> "It is written in highly portable C, making it suitable for practically every platform used today" I love C, it is not the enemy everyone makes it out to be. It's already in debian: https://packages.debian.org/stretch/zstd https://packages.debian.org/stretch/zstd and judging by the small requirements,it is portable indeed.

lasryaric 10y ago

Whats their weissman score?

brickmort 10y ago
I bet it doesn't even touch pied piper's.

ilostmykeys 10y ago

How does this compete with PiedPiper?

bbcbasic 10y ago
This is general purpose whereas Pied Piper, Hooli et al. focussed on video.

espadrine 10y ago

The following link points to a fairly good benchmark / tool that showcases the tradeoffs in real life: since (de)compression takes time, what is the fastest way to transmit data at a given transfer speed? https://quixdb.github.io/squash-benchmark/unstable/#transfer-plus-processing https://quixdb.github.io/squash-benchmark/unstable/#transfer... Spoilers: zstd wins at ethernet and wifi (and is among the best in 4G), lz4 wins at hard drive encryption… both were designed by the same author.

jacobolus 10y ago
Charles Bloom’s Oodle new codecs handily beat them across the scale: http://cbloomrants.blogspot.com http://cbloomrants.blogspot.com http://www.cbloom.com/oodle_arm_report/ http://www.cbloom.com/oodle_arm_report/ http://www.cbloom.com/rants.html http://www.cbloom.com/rants.html Caveat: proprietary commercial product.

kstrauser 10y ago

That's truly beautiful. Thanks, Facebook! I particularly love that you can pre-compute and reuse dictionaries, say if you're regularly compressing similar JSON objects.

DJ_Icebear 10y ago

Should've named it "Pied Piper"

DJ_Icebear 10y ago

They should've named it "Pied Piper".

erichocean 10y ago

For this to become anything like a standard, Facebook would have to remove its patent poison pill.

ryao 10y ago

This is an awesome blog post that is very well written, but the lack of incompressible performance analysis prevents It from providing a complete overview of zstd. Incompressible performance measurements are important for interactive/realtime workloads and the numbers are extremely interesting because they can differ dramatically from the average case measurements. LZ4 for instance has been measured at doing 10GB/sec on incompressible data on a single core of a modern Intel Xeon processor. At the other end of the spectrum is the worst case scenario for incompressible data where performance slows to a crawl. I do not recall any examples in this area, but the point is that it is possible for algorithms to have great average case performance and terrible worst case performance. Quick sort is probably the most famous example of that concept. I have no reason to suspect that zstd has bad incompressible performance, but the omission of incompressible performance numbers is unfortunate.

Cyan4973 10y ago
zstd goes at > 1 GB/s on uncompressible data. It has some fast heuristics for such cases too.

z3t4 10y ago

Tables should be in HTML.

cromwellian 10y ago

I think for typical JS/CSS/HTML sizes, and decompression times, probably maximum compression ratio, followed by decompression speed is what I'd look for. I don't care too much about compression speed, in the sense that if I have to spend 1 minute compressing JS to crunch it by 10%, but I serve that file a million times, then as long as decompression doesn't negate the gain in network time saved, it's a win. I guess the other factor for mobile is, besides memory and decompression speed, how do various compression schemes fare battery wise?

nikkun 10y ago
Regarding decompression times, I think it's much more important to save transferred network data than to prioritize quicker decompression. HTTP request times have a long tail; they can get really slow for the many, many people limited to slow connections. Decompression times are going to be much more consistent. Our aim here should be to improve the 10% slowest requests, and you do that by optimizing the actual transfer.

xrstf 10y ago

Quick benchmark on a 194MiB SQL dump: gzip -9: 27.574s, 48MiB output zstd -9: 14.182s, 41MiB output Thanks, I'll gladly use zstd as a drop-in replacement for my daily backups. :)

bananaoomarang 10y ago

Best middle-out in the game.

kaushalp88 10y ago

Should we start with the pied piper jokes now or later?

bbcbasic 10y ago
Not until I know the Weissman Score of Zstandard.

cristiandan 10y ago

Awesome

deleted 10y ago

[deleted]

faragon 10y ago

Beautiful.

partycoder 10y ago

Unless they integrate it into software like web servers and web browsers it will be hard to see it really flourish as a "standard". But at least within the perimeter of your own systems you can totally profit from this technology now.

morecoffee 10y ago

A recent compression discussion I saw involved how do compressors fare on uncompressible input? For example, suppose you wanted to add compression to all your outbound network traffic. What would happen if there was mixed compressible traffic along with the uncomressible kind? A common case would be sending HTML along with JPEG. Good compressors can't squeeze any more out of a JPEG, but they can back off fast and go faster. Snappy was designed to do this, and even implementations of gzip do it too. It greatly reduces the fear of CPU overhead to always on compression. I wonder how Zstd handles such cases? *Ignoring security altogether

nimrody 10y ago
Dropbox say they can losslessly compress JPEG files (~20% saving): https://blogs.dropbox.com/tech/2016/07/lepton-image-compression-saving-22-losslessly-from-images-at-15mbs/ https://blogs.dropbox.com/tech/2016/07/lepton-image-compress...
- gcp 10y ago
  Known techniques. JPEG uses Huffman coding for entropy coding, you can replace that with arithmetic coding. This requires knowing the format details, though.
Cyan4973 10y ago
Zstd pass faster over incompressible data. Expect something > 1 GB/s

bnolsen 10y ago

turbohf claims to be 4x faster than zlib's huffman coding and 2x faster than FSE and is a generic cpu implementation. Even if claims are only partially true and turbohf is a clean dropin replacement for zlib and licensing were friendly the appeal of zstd drops substantially in my book. http://encode.ru/threads/2276-TurboHF-1GB-s-Huffman-Coding-Reincarnation http://encode.ru/threads/2276-TurboHF-1GB-s-Huffman-Coding-R... https://sites.google.com/site/powturbo/entropy-coder https://sites.google.com/site/powturbo/entropy-coder

Twirrim 10y ago

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.

Twirrim 10y ago
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 branches 89060880 branch-misses # 3.00% of all branches
- Cyan4973 10y ago
  There is now a pzstd implementation, if you wish to compare it to pigz
  - Twirrim 10y ago
    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.

mana_12 10y ago

Zstandard is both a command line tool (zstd) and a library.

anjanb 10y ago

I was looking for a windows version of zstd. On the github page, I could only get the version 0.81 version of the windows tool. Can someone release the 1.0 version of zstd for windows ?

philplckthun 10y ago

I'd love HTTP content encoding to support this and see a comparison to Brotli. Looks like it might be yet another good alternative to gzip.

hasszhao 10y ago

sctb 10y ago
Please don't do this, comments on HN need to be substantive.

mydeardiary 10y ago

If facebook hopes the new compression algorithm to be a standard, why doesn't it publish an IETF RFC draft? Will it follow OpenDNS way of dnscrypt by open-sourcing the reference implementation without publishing any IETF RFC draft?