Better Compression with Zstandard
gregoryszorc.com
gregoryszorc.com
However this worries me:
https://github.com/facebook/zstd/blob/dev/PATENTS
---
The license granted hereunder will terminate [...] if you [...] initiate [...] any Patent Assertion: (i) against Facebook or any of its subsidiaries or corporate affiliates, (ii) against any party if such Patent Assertion arises in whole or in part from any software, technology, product or service of Facebook or any of its subsidiaries or corporate affiliates, or (iii) against any party relating to the Software.
---
Not a lawyer, but I would guess that's makes it a non-starter for many situations. You sue them, now your customers' data, your code repository, or backups have to be decoded with a software for which don't have a license to use anymore. Am I crazy, and this is not a BigDeal(TM)? Or does anyone else have an issue with this?
1) BSD license covers copyright, and that patent file covers patent grants. Totally separate things. If you sue Facebook, you retain the BSD license and they can't sue you back for copyright infringement, but they can then come after you asserting you infringed their compression patents and demand royalties.
2) Because PATENTS file says "Additional Grant of Patent Rights Version 2" it could mean an extension of the BSD license. That is the termination would trigger the revocation of copyright license as well not just patent protection.
Does termination of the additional patent grant in the Facebook BSD+Patents license cause the copyright license to also terminate?
No.
I don't know what are the consequences of the Facebook patent clause, but I know the BSD license doesn't contradict it.
I'm not sure what the excitement is, Pied Piper has had faster and deeper compression for over two years.
> such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted.
Facebook's version applies if you sue Facebook for any patent assertion.
Say you have a startup in talks to being bought by Google. The are suing Facebook because Facebook stole their ad click fraud detection algorithm. Now they'd be an additional worry about that patent claim.
So an explicit patent grant, even if terminated if you sue Facebook for patent infringement, is much better than omitting the PATENTS file.
The very popular OSS Apache 2.0 license includes the same language to grant a patent license that is terminated if you start a patent lawsuit. Avoid suing Google about Android patents or Microsoft about .NET patents if you are using that software.
Overall I think it's a good thing, and if enough open-source projects adopt the same rule, then it could perhaps become a poison pill that stops everyone from enforcing software patents.
No, Apache-2.0's language around patents is more restricted, as others in this thread have noted.
Updating Our Open Source Patent Grant
https://news.ycombinator.com/item?id=9356508 (2 years ago)
I saw a similar grant for React js project [1]. The wording has had me look at alternatives for commercial use. The patent grant in React has been on HN several times in the past [2]
Facebook has an Open Source License FAQ where the explicitly do NOT mention the scenario you mention. [3]
[1] https://github.com/facebook/react/blob/master/PATENTS [2] https://news.ycombinator.com/item?id=12108158 [3] https://code.facebook.com/pages/850928938376556
So no, this is just another one where once or twice a year someone reads that license and tries to make it a "BugDeal".
FWIW, I'm using this Go library: https://github.com/DataDog/zstd
I've made some contributions and the DataDog team is very prompt at reviewing merge requests.
edit: time -> team, thanks JoshTriplett, DYAC.
(assuming you mean "legal team", not "legal time")
If it did, they almost certainly couldn't say.
Also, in my system all compressed data is marked with its compression type, so it's possible for me to later find zStandard-compressed data and recompress with a different algorithm if needed. It would be a lengthy process, but at least possible.
http://www.radgametools.com/oodle.htm
(not a employee or a financially related in any way to them, just a compression nerd following the field)
Only two input types: text logs and network traces. My conclusion was the same: Zstandard has the best space-time tradeoff.
The article goes into CPU usage (which seems awesome...) but I don't see anything about the buffer sizes for either. It just mentions them as knobs that can be twiddled.
http://fastcompression.blogspot.com/ see under "Custom window sizes" section
The table mapping compression levels to window sizes is at https://github.com/facebook/zstd/blob/15a7a99653c78a57d1ccbf.... The first element is the window size. I'm pretty sure you raise 2 to that power to get the window size. As you can see, level 1 is 2^18, which is 256KB - far larger than the minimum of 1KB. Lowering it will make compression faster at the expense of compression ratio.
For comparison, zlib's max window size is 32KB. That's one reason its compression ratio is so limited.
For example: brotli is designed with an existing dictionary optimized for HTTP. Based on this design decision, it seems like it wouldn't necessarily be a good idea to use it with ProtoBuf, especially for small ProtoBuf serialized plain-old-[whatever]-objects in a data access layer.
Poking around a bit so far, it seems http://blosc.org/blosc-in-depth.html may be the right choice, but I'm not so sure about adopting its serialization stuff since it isn't as widely xplat as ProtoBuf.
If your decision was obvious after reviewing multiple algorithms then you might save me some time by sharing your experience; thanks in advance!
11728 bytes - brotli 11
11941 bytes - brotli 10
12056 bytes - lzma
12219 bytes - zstd 22
12314 bytes - brotli 9
12512 bytes - brotli 5
12526 bytes - zstd 15
12809 bytes - zstd 12
12831 bytes - zstd 9
14753 bytes - zopfli
15110 bytes - gzip 9
Many times, lz4 level 1 isn't just 25% faster [0] in Compression vs. say zlib level 1 (as it appears visually), it's actually 6 times (6x, or 600%) faster in terms of MB/s (~600 MB/s vs. ~100 MB/s)!
And it's not just 5% or so faster than zstd in Decompression (visually) [1], it's about twice as fast (~2000 MB/s vs. ~1000 MB/s).
Yes. It does not compress as well. But ~3.2:1 compression ratio best case for lz4 (listed as ~3.2 in the chart) compresses almost as quickly as the 6:1 zstd [0] but will then decompress twice as fast as zstd at any level [1]. Having a high-compression is a case I could (almost) not care about. If you're youtube/google or facebook/instagram, you might care (streaming, photos, static assets all at enormous scales).
For me, however, the above results mean far less CPU burden on the client with a twice the burden on the network I/O. If you're concerned about battery, loading screens, or download dialogs, I'd still pick lz4. Just turn the AC up a half notch in my AWS DC.
[0] http://gregoryszorc.com/images/compression-bundle-common.png
[1] http://gregoryszorc.com/images/decompression-bundle-output.p...
Link - http://www.patrickcraig.co.uk/other/compression.php
Previous commentary - https://news.ycombinator.com/item?id=9163782
About the main reason I haven't pushed on using it for work is just concerns about maturity. gzip/pigz works well enough for our purposes, and isn't enough of a hindrance to justify using what is still new software without a proven history.
As much as I trust Yann, I probably wouldn't use Zstd for anything mission-critical yet.
To that end, every release (and pretty much every commit) undergoes significant testing. We also fuzz test heavily and have significant regression tests in place constantly looking at corner cases and verifying known prior bugs stay fixed. It's impossible to prove there are no issues, but so far we've put a lot of effort into being as reliable as possible and seen that play out well in our production environments. We trust it.
I just like to be careful with a mental "new tech" budget for a project/platform. The more new tech is involved, the more risk there is. The balancing point there being the value the new tech brings.
With the platform I'm working on at the moment, the gains are relatively minor: shaving a few seconds off here and there, when things are in the scale of minutes; and saving 20-30MB when things are in the scale of gigabytes, but also not lots of them. As the project grows, and as the new tech we've introduced proves itself, there's always scope to introduce other new tech like Zstandard and start gaining in the storage savings.
The biggest candidate for that is serving static assets to browsers which can natively decompress a zlib compressed response by checking the response Content-Encoding.
Until browsers catch up, you'd have to either serve uncompressed traffic to the end user or recompress it for transport (which kind of kills the whole point right?).
See the post by rdtsc above https://news.ycombinator.com/item?id=13814476
I think the problem lies in the perl library Compress::Zstandard, rather than in the zstd code itself. The C code has flags to enable 'legacy' support and they they are on by default. The perl library doesn't seem to be using them...
When I get the time, hopefully I can track this down further and submit a patch if this turns out to be the case.
So Zstandard is not the compression algorithm to end them all and definitely has its weak spots.
Using bzip2 is not a great idea because it's old, you can always beat it using newer methods. But bzip2 is widely installed, so that makes it somewhat useful.
The OP also shows zstd being very close to lzma for high compression ratio jobs. In my experience, for higher compression ratios lzma handily beats zstd (in the pareto-optimal sense of the word). But lzma is slow to decompress. If decompression speed matters a lot, zstd is awesome.
If you need to compress something like game assets (compression speed doesn't matter, compression ratio matters, decompression speed matters a lot) and can afford to use proprietary code then check out Oodle [1]. It beats zstd.
7z a -m0=PPMd demo.7z demo.txt
I recently did some benchmarking with lz4, gzip-6 and gzip-9 to look at using better compression for archival datasets. However, the overhead of gzip made the system largely unresponsive for days! An algorithm with better compression ratios but less CPU overhead would be a great addition.
Does it support efficient random access?