News for hackers. Stuff that matters.
Re:Improving compression at scale with Zstandard by josephg on Wednesday December 19, 2018 @04:57PM (#18720126)
How does zstd compare with brotli? Would it be a better compression standard for http responses?
Re:Improving compression at scale with Zstandard by spatulon on Wednesday December 19, 2018 @05:46PM (#18720615)
For what it's worth from my not-particularly-scientific tests at work, they both compressed significantly better than gzip, but zstd compressed better and faster than brotli for our typical file sizes (text files around 5-20kb). Mind you, this was all at lower/faster compression levels; by default brotli compresses at the highest/slowest level, so perhaps it's been designed primarily for a different use case.

Unfortunately, we have a strict requirement that the decompression be done in pure Java (and ideally providing an InputStream interface). The official Brotli repo includes a pure Java decompression library that took about three lines of code to drop in next to our gzip support, while zstd had nothing suitable (a JNI wrapper is not an option, and the Java decompressor at [1] does not provide an streaming interface). Writing my own Java decompressor for zstd sounded like a fun project, but that would have been too much like yak shaving; brotli is good enough.

[1] https://github.com/airlift/aircompressor/tree/master/src/mai...

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @06:40PM (#18721090)
zstd vs. brotli -- there are loooots of badly conducted experiments. Even the zstd folks themselves fell into the trap of comparing brotli and zstd with different window sizes.

I never was able to locate a file that compresses better with zstd than with brotli, if you use the same window size in both.

The car analogy in using different window sizes is to drive on 1st gear with one car and drive on 5th gear with other, i.e., meaningless comparisons. One needs to use the same window size with both algos to be able to understand the performance potential in them. When one does that, brotli always wins in density and most of the time on compression speed to a given density. Zstd wins in decompression speed, but neither of them is slow (think 600 MB/s vs. 900 MB/s).

https://github.com/google/brotli/issues/642 is relatively well conducted, but covers the slow+dense and large window compression only.

Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @05:06PM (#18720216)
They compare pretty closely. The squash benchmark is a nice interactive comparison tool that usually agrees with my own benchmarks. See for example [1]. (Note that you should experiment with different input texts to get a sense for the variability in relative performance.)

I am working on that very question! Zstd's support for creating and using custom dictionaries opens the door to significant efficiencies. As described in the post though, dictionaries make compression a more complicated thing to use, and so there are lots of questions about how to apply that to the public internet in a way that's cross-compatible and secure. In short: it's something we're actively exploring.

[1] http://quixdb.github.io/squash-benchmark/unstable/?dataset=e...

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @06:36PM (#18721053)
Brotli added custom dictionaries in 2014 or 2015 (before zstd format was even frozen). We are currently working on a new more efficient custom dictionary that uses context and transforms to ramp up the impact of the custom dictionary (by about 20%).
Re:Improving compression at scale with Zstandard by pmarreck on Wednesday December 19, 2018 @05:40PM (#18720554)
Browsers could cache dictionaries per MIME type per domain which are provided by the server. Would be super cool, if a bit more complicated.
Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @06:03PM (#18720776)
Yep, that's in the vicinity of the solutions we're thinking about. There are a few proposals out there, and prior art like SDCH [1].

The hard part is that compression is already an attack vector for the web (e.g., CRIME [2], BREACH [3], et al.). We want to make sure that we're not eroding or unduly complicating that situation [4].

[1] https://tools.ietf.org/html/draft-lee-sdch-spec-00 [2] https://en.wikipedia.org/wiki/CRIME [3] https://en.wikipedia.org/wiki/BREACH [4] https://tools.ietf.org/html/draft-kucherawy-httpbis-dict-sec...

Re:Improving compression at scale with Zstandard by stochastic_monk on Wednesday December 19, 2018 @05:06PM (#18720213)
Both brotli and zstd support user-provided dictionaries, which helps with compressing files which contain items from the dictionary. This is particularly helpful for small files. Zstd is both faster and more effective at compressing.
Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @06:32PM (#18721014)
Actually brotli compresses some more, often around 5 % more density. If you compress to same density, brotli tends to be significantly faster. Zstd decompresses faster.

Brotli is naturally limited to 16 MB of memory use whereas ZStd makes less attempts to reduce memory use. If you want to use more memory with Brotli, you need to use another flag '--large_window' instead of '--window', to indicate that you really want it, whereas zstd uses a lot of memory more silently.

When you compare compression levels, you should compare with same memory consumption -- and if you do that, brotli tends to win by 5 %.

When in doubt in benchmarking, run brotli with --large_window 30

https://encode.ru/threads/2947-large-window-brotli-results-a... is a summary of a recent large-scale experiment of a large variety of compressors, including brotli, zstd and LZMA.

Re:Improving compression at scale with Zstandard by twitch_checksum on Wednesday December 19, 2018 @07:33PM (#18721433)
> ZStd makes less attempts to reduce memory use

Ever heard of flag `--ultra` ? Without it, zstd memory usage will be limited to 8 MB. It has been there since, forever.

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @08:06PM (#18721642)
-22 doesn't imply 128 MB window silently?
Re:Improving compression at scale with Zstandard by terrelln on Wednesday December 19, 2018 @08:20PM (#18721718)
Levels above 19, which has a 8 MB window size, may only be used with the --ultra flag, whose documentation says "requires more memory".
Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Wednesday December 19, 2018 @09:36PM (#18722047)
cool, just that most zstd benchmarking against other algos that I ever saw was with -22, i.e., disregarding memory use and multi-processing performance

would be wonderful to see benchmarking with real data and with realistic (and same from one algorithm to the next) window sizes

Re:Improving compression at scale with Zstandard by terrelln on Thursday December 20, 2018 @12:09AM (#18722647)
Looking at the brotli API, I believe I spotted the source of our disagreements. Brotli separates out the window size from the quality, but in zstd the level implies the window size, unless you use advanced parameters. For example, level 3 has a 1 MB window size.

When you are comparing brotli and zstd, are you focusing on the highest quality/compression level, but varying the window size?

For us, lower compression levels (1-3) are our primary focus. We care about the highest levels for benchmarks, but it isn't our focus. When we are benchmarking zstd we focus on the lower levels, since they are the most important to us. When we think about a smaller window size, we generally think about faster compression.

When we comparing against brotli, the question we're asking is, how does brotli compare to level 3. When you're benchmarking zstd, I suspect you're asking the question, how does the highest zstd level compare to the highest brotli quality for the same window size, is that right?

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Thursday December 20, 2018 @04:30PM (#18729322)
In my thinking window size is something that is optimized for the decoding resources -- whereas the encoding effort is optimized for how expensive the transfer is in relation to encoding cost.

For example, a mobile client might prefer to have no more than 512 kB sliding window due to design of its memory system or for multi-processing reasons. There, a static resource can still be encoded to the smallest size with extremely slow encoding (quality 9-11) -- but for one-use we'd still prefer a faster encoding (quality 6 or so).

Thank you for explaining your focus. Did you arrive to that by doing economic calculations or was it to have minimal changes to situation with no compression?

Re:Improving compression at scale with Zstandard by terrelln on Thursday December 20, 2018 @09:29PM (#18731035)
A lot of compression ends up being compress once, decompress one to a few times, so the faster end of the spectrum fits well. Additionally, compression has to fit into the existing system, and existing systems already have tight constraints, so it is an easier sell to say "hey, we can compress faster AND stronger" than what you have right now. For our larger services, we will tune the compression level more carefully, and end up at different places for different services, but still normally around the faster levels.

That said, we still see users of the stronger compression levels.

Re:Improving compression at scale with Zstandard by JyrkiAlakuijala on Friday December 21, 2018 @09:46PM (#18738608)
Yes, plenty of use cases -- that's what makes compression so interesting!

In my back-of-the-envelope financial analysis, the highest economic impact is when I can reduce people's need to wait for data to arrive. There we often use relatively slow compression even when it is for one use only. Computers are quite a lot (~1000x) cheaper than people's time.

Re:Improving compression at scale with Zstandard by felixhandte on Wednesday December 19, 2018 @05:08PM (#18720235)
At the moment, Brotli doesn't accept a user-provided dictionary. I know they're working to re-introduce that functionality, but it's not currently present.