Re:Zstandard – Real-time data compression algorithm
by vanderZwan on Sunday September 04, 2022 @04:56PM
(#32717640)
Well, the entropy coding step is. Which is just one of multiple parts of the data compression. But entropy coding typically is the bottleneck in encoding/decoding speed, yes, and Duda's work is impressive (also because he took on Google when the latter didn't appear to keep their no-software-patents promise that they. made when they first started collaborating. The man stands up for his principles)
Re:Zstandard – Real-time data compression algorithm
by _0ffh on Monday September 05, 2022 @06:24AM
(#32722656)
Also look at the time line! The dude started three 4-year masters courses (c.s., theo.math., theo.phys.) in a one-year stagger, so during 2001-2004 he was doing all three in parallel. The man seems to be quite the beast, even if he was probably able to reuse quite a bit of that math!
Re:Zstandard – Real-time data compression algorithm
by Svetlitski on Sunday September 04, 2022 @03:29PM
(#32716799)
Zstandard really is incredible. Anywhere I would’ve previously compressed things with gzip I now universally prefer to use Zstandard instead. It’s a shame it’s not supported as a HTTP Content-Encoding in web browsers.
Re:Zstandard – Real-time data compression algorithm
by cyann on Monday September 05, 2022 @03:11AM
(#32721416)
Yes, sort of: "Zstd offers a training mode, which can be used to tune the algorithm for a selected type of data. Training Zstandard is achieved by providing it with a few samples (one file per sample). The result of this training is stored in a file called "dictionary", which must be loaded before compression and decompression. Using this dictionary, the compression ratio achievable on small data improves dramatically."
Re:Zstandard – Real-time data compression algorithm
by wongarsu on Monday September 05, 2022 @07:45AM
(#32723240)
But surely anyone could publish dictionaries? Like let's say Mozilla could publish a dictionary trained on HTTP headers, HTML and Javascript, and then accept traffic compressed with it under a "Accept-Encoding: zstd/mozilla" header
Re:Zstandard – Real-time data compression algorithm
by SergeAx on Monday September 05, 2022 @06:32PM
(#32730281)
Brotli is super slow and thus suitable only for static content.
zStd also supports pre-trained dictionaries, it is particularly good for specific small JSON, for example. It won't be that helpful for relatively large HTML files.
Re:Zstandard – Real-time data compression algorithm
by thayne on Sunday September 04, 2022 @11:28PM
(#32720196)
The problem is brotli compression is pretty expensive/slow to encrypt. Which isn't really a problem for static content that can be compressed ahead of time. But doesn't work very well for just in time compression.
Perhaps, this common misunderstanding is due to the fact the slowest level (-11) is the default one in the brotli command line utility?
It's also faster than gzip, and gzip was used for "just in time" compression on the web for ages, so I don't see how brotli can be a problem for this use case. (I assume by "encrypt" you mean "compress".)
Re:Zstandard – Real-time data compression algorithm
by thayne on Monday September 05, 2022 @01:53AM
(#32721007)
On a project I worked on, we tried switching from gzip to brotli for on the fly compression, and it significantly increased CPU usage. That was years ago though so it's possible things are better now, or maybe the library we used just didn't support a compression ratio as low as what we were using with gzip.
Re:Zstandard – Real-time data compression algorithm
by anotherevan on Sunday September 04, 2022 @07:01PM
(#32718576)
Just did some quick research and it looks like you can serve pre-compressed static resources in Brotil. See the precompressed option of the file_server directive[1].
The thinking seems to be due to how CPU intensive it is, Brotil is not favoured for on-the-fly compression[2].
If you're really desperate for it though, you could try [this extension][3].
Re:Zstandard – Real-time data compression algorithm
by BackBlast on Sunday September 04, 2022 @06:39PM
(#32718434)
Caddy 2 supports brotli static compression out of the box, I ran a test on it just last week with this exact configuration. Dynamic, I'm not sure. That use case doesn't interest me as much.
Re:Zstandard – Real-time data compression algorithm
by morelisp on Sunday September 04, 2022 @04:43PM
(#32717516)
Yeah, this is definitely a real advantage and not a broke-ass feedback loop of SEO and confirmation bias. It's great that we have to ship our compressors with massive English-biased static dictionaries now.
Re:Zstandard – Real-time data compression algorithm
by BackBlast on Sunday September 04, 2022 @06:45PM
(#32718466)
Technically it is available, but it's just not widely supported. Though it's really unnecessary. Brotli is, in many ways, very comparable or a near equivalent to zstd.
Re:Zstandard – Real-time data compression algorithm
by dvhh on Sunday September 04, 2022 @07:17PM
(#32718715)
last time I looked Brotli format do not clearly define its frame format, such as there is a good chance that a random stream of data would be decoded as valid brotli compressed data.
Re:Zstandard – Real-time data compression algorithm
by Too on Monday September 05, 2022 @11:26AM
(#32725343)
Its not so much about suddenly starting to decode something. It’s more when your stream for some reason gets misaligned or corrupted and whatever is still streamed is happily consumed with no possible way to detect the error.
Common reason being someone forgot to check how many bytes read() actually returned and just assume it filled the buffer.
Robust data formats have double protection against this class of bugs with unambiguous SOF and EOF boundaries that the consumer can assert. I guess a sanity-byte once every X Megabytes wouldn’t hurt either.
Re:Zstandard – Real-time data compression algorithm
by BackBlast on Tuesday September 06, 2022 @12:04PM
(#32739031)
I use brotli as a web distribution format and as an internal compression format on web stacks for various projects and for production systems without issue.
I still don't understand the use case limitation, or exactly where this is a potential issue. Why is the data being interrupted? Is this some kind of raw UDP stream use case?
3% larger size for a nearly 2x decompression speed is a no brainer for lots of uses.
Anecdotally I have also gotten much better decomp speed on snappy on previous generations of CPUs staying within ~10% compression ratio, though I had not benchmarked/tuned extensively nor reconfirmed in the past ~2 years. (Probably this can also vary a lot by implementation, which you're often stuck with based on some other library choice.)
Re:Zstandard – Real-time data compression algorithm
by josephg on Sunday September 04, 2022 @10:47PM
(#32719955)
The lz4 algorithm is also tiny code-wise. Pulling in a lz4 compressor / decompressor library into my wasm project only added 11kb to the bundled size. Zstd is many times larger.
For my use case, any extra benefits of zstd are far outweighed by the extra cost of downloading zstd itself in the browser.
Re:Zstandard – Real-time data compression algorithm
by adgjlsfhk1 on Sunday September 04, 2022 @06:30PM
(#32718358)
this can be a bit misleading because you only get the 2x decompression speed if you aren't bandwidth limited. this means that zstd will almost always be faster over a network.
Re:Zstandard – Real-time data compression algorithm
by rincebrain on Sunday September 04, 2022 @09:50PM
(#32719659)
Recent versions of zstd definitely don't obsolete LZ4, or else I don't think the author would still be contributing to both...
zstd also seems to be optimizing much more, recently, for the large stream of data use cases, versus the fixed-size or smaller records you might get in, say, databases, or filesystems, so I think it's actually becoming less generally useful over time of late.
And if you're going to play with Snappy, you might find S2, which was linked on HN relatively recently, interesting. [1]
Re:Zstandard – Real-time data compression algorithm
by Cyberdog on Sunday September 04, 2022 @06:16PM
(#32718258)
I don't really know anything about compression algos, but something that struck me as interesting with this one when it came up on KF before is the ability to create a custom dictionary - not sure if that's really common among other compression algos or not. But since I often work with compressed MySQL dumps with a lot of repetitive data from my client's site that come out to almost 50MB when compressed with xz, I wonder if I could make a dictionary with all the MySQL keywords you'd see in dumps, plus other repetitive strings unique to that site (for example, something like two-thirds of all user email addresses end with "@gmail.com") and get those dump sizes even smaller.
I imagine that xz might be good enough at making its own dictionary that what it ends up with wouldn't be much different from what I'd make manually, so I could see a decent chance that the improvements would be minimal at best. Has anyone done any experimentation along these lines?
Re:Zstandard – Real-time data compression algorithm
by killingtime74 on Sunday September 04, 2022 @10:30PM
(#32719857)
The dictionaries mentioned here speed up for small files where the dictionary would be bigger than the raw source. You don't need that for a Mysql dump. Its many times bigger than the dictionary. You could theoretically save space for large files by sharing a dictionary but the saving is probably negligible.
Re:Zstandard – Real-time data compression algorithm
by johannes1234321 on Monday September 05, 2022 @06:50AM
(#32722861)
Sorry for the little hijacking: An alternative to using "regular" dumps might be MySQL Shells dump utility. Contrary to mysqldump etc. it doesn't save data in SQL but some CSV-like format. This won't solve the "@gmail.com" case but avoid the repetitive "INSERT INTO tablename VALUES (" for each record and what isn't there doesn't have to be compressed to begin with. (And then is paralizable etc., downside might be that it is not using a single file, but a number of files)
https://dev.mysql.com/doc/mysql-shell/8.0/en/mysql-shell-uti...
Depending on your needs you could also look at the MySQL clone plugin, which gives you a simple way to clone the data dictionary as physical backup, avoiding the textual representation, but has its restriction.
https://dev.mysql.com/doc/refman/8.0/en/clone-plugin.html
Disclaimer: I work at the MySQL development team at Oracle
Re:Zstandard – Real-time data compression algorithm
by unsigner on Monday September 05, 2022 @04:17AM
(#32721760)
Zstd achieves considerably higher compression on some kinds of data with little to no preprocessing. LZ4 hits a compression ratio ceiling at some point - algorithmically, it's "half of Zstd" (only LZ match/literal encoding, no entropy encoding at all).
Read the LZ4 format, it's very simple and educational, I'd say beautiful. It fits in half a screen of text.
Re:Zstandard – Real-time data compression algorithm
by SergeAx on Monday September 05, 2022 @06:42PM
(#32730358)
At my previous job I noted that analytics events were passed to dwh as plain JSON. I said immediately that it should be compressed and proposed zStd as a codec. The actual implementation took less than a week including testing and gradual rollout, and cut incoming traffic to our data-center by 70%, while not at all affecting CPU on client or server.
Re:Zstandard – Real-time data compression algorithm
by tgsovlerkhgsel on Sunday September 04, 2022 @04:37PM
(#32717473)
Is this comparing the same number of cores, or is zlib single-threaded and zstd multi-threaded?
For some applications it matters how fast one operation completes, but for others, it's much more relevant how much CPU time it consumes, so if zstd needs 1 second on 8 cores for something gzip does in 8 seconds on 1 core, it would be no benefit at all.
Re:Zstandard – Real-time data compression algorithm
by JoshTriplett on Sunday September 04, 2022 @04:24PM
(#32717322)
We're interested. I'd love to see this happen. But it does require several different things to change, and rustup wouldn't be the starting place (apart from needing to have support for it).
Re:Zstandard – Real-time data compression algorithm
by staticassertion on Sunday September 04, 2022 @04:11PM
(#32717211)
They seem very interested. There's lots of benchmarks and discussion. It just looks like zstd would take more space than xz - it wasn't a universally better solution. The concerns noted are totally reasonable and are based on real world issues that the teams that maintain this infra have. What's obvious, however, is that there was a lot of interest.
Re:Zstandard – Real-time data compression algorithm
by asveikau on Sunday September 04, 2022 @08:23PM
(#32719131)
That thread doesn't appear to be uninterested people. They're asking about rationale, saying they may be asking the wrong people, brainstorming other things that would help, and asking for data.
Re:Zstandard – Real-time data compression algorithm
by remram on Monday September 05, 2022 @04:42PM
(#32729190)
Is the latency of the Rust installation process important?
I can see why you would want it to be efficient, economical in bandwidth, and fast enough in all scenarios. But why does it need to be faster in situations where it is already quite fast?
some cool references:
https://www.youtube.com/watch?v=uXtmN9fE01k
https://th.if.uj.edu.pl/~dudaj/
https://demonstrations.wolfram.com/DataCompressionUsingAsymm...
https://encode.su/threads/2078-List-of-Asymmetric-Numeral-Sy...
well, impressive
https://github.com/facebook/zstd#the-case-for-small-data-com...
zStd also supports pre-trained dictionaries, it is particularly good for specific small JSON, for example. It won't be that helpful for relatively large HTML files.
https://quixdb.github.io/squash-benchmark/unstable/?dataset=...
Perhaps, this common misunderstanding is due to the fact the slowest level (-11) is the default one in the brotli command line utility?
It's also faster than gzip, and gzip was used for "just in time" compression on the web for ages, so I don't see how brotli can be a problem for this use case. (I assume by "encrypt" you mean "compress".)
The thinking seems to be due to how CPU intensive it is, Brotil is not favoured for on-the-fly compression[2].
If you're really desperate for it though, you could try [this extension][3].
[1] https://caddyserver.com/docs/caddyfile/directives/file_serve...
[2] https://caddy.community/t/caddy-v2-brotli/8805
[3] https://github.com/ueffel/caddy-brotli
Other webservers support it, mainly Nginx. But since Caddy is written in go, they need a native go port which doesn't exist yet.
Yeah, hence my "really desperate" qualifier. I probably should have been more explicit.
Common reason being someone forgot to check how many bytes read() actually returned and just assume it filled the buffer.
Robust data formats have double protection against this class of bugs with unambiguous SOF and EOF boundaries that the consumer can assert. I guess a sanity-byte once every X Megabytes wouldn’t hurt either.
I still don't understand the use case limitation, or exactly where this is a potential issue. Why is the data being interrupted? Is this some kind of raw UDP stream use case?
https://www.rfc-editor.org/rfc/rfc8478
Anecdotally I have also gotten much better decomp speed on snappy on previous generations of CPUs staying within ~10% compression ratio, though I had not benchmarked/tuned extensively nor reconfirmed in the past ~2 years. (Probably this can also vary a lot by implementation, which you're often stuck with based on some other library choice.)
For my use case, any extra benefits of zstd are far outweighed by the extra cost of downloading zstd itself in the browser.
LZ4 is smaller, faster and much more simple.
zstd also seems to be optimizing much more, recently, for the large stream of data use cases, versus the fixed-size or smaller records you might get in, say, databases, or filesystems, so I think it's actually becoming less generally useful over time of late.
And if you're going to play with Snappy, you might find S2, which was linked on HN relatively recently, interesting. [1]
[1] - https://github.com/klauspost/compress/tree/master/s2
I imagine that xz might be good enough at making its own dictionary that what it ends up with wouldn't be much different from what I'd make manually, so I could see a decent chance that the improvements would be minimal at best. Has anyone done any experimentation along these lines?
Depending on your needs you could also look at the MySQL clone plugin, which gives you a simple way to clone the data dictionary as physical backup, avoiding the textual representation, but has its restriction. https://dev.mysql.com/doc/refman/8.0/en/clone-plugin.html
Disclaimer: I work at the MySQL development team at Oracle
zstd 1.4.5 --fast=5 2.178 700 MB/s 2420 MB/s
lz4 1.9.2 2.101 740 MB/s 4530 MB/s
Read the LZ4 format, it's very simple and educational, I'd say beautiful. It fits in half a screen of text.
(see, e.g., https://news.ycombinator.com/item?id=32529412#32531734)
For some applications it matters how fast one operation completes, but for others, it's much more relevant how much CPU time it consumes, so if zstd needs 1 second on 8 cores for something gzip does in 8 seconds on 1 core, it would be no benefit at all.
https://github.com/rust-lang/rustup/issues/1858
I can see why you would want it to be efficient, economical in bandwidth, and fast enough in all scenarios. But why does it need to be faster in situations where it is already quite fast?