News for hackers. Stuff that matters.
Re:Chrome feature: Compression dictionary transport with Sha... by jacobgorm on Friday September 22, 2023 @05:57AM (#37610049)
I never really understood with Google keeps pushing Brotli. LZ4 and ZStd both predate it by a couple of years, and seem to offer superior performance overall. Is it a Google-NIH thing?
Re:Chrome feature: Compression dictionary transport with Sha... by lifthrasiir on Friday September 22, 2023 @06:28AM (#37610255)
They were designed more or less independently from each other, and your statement that Zstandard predates Brotli is also wrong (both around 2015). They are both designed to be much more efficient than DEFLATE in both time and size axes, but otherwise have little similarities. Zstandard is notable in its use of ANS, while Brotli is probably the first mainstream format that uses a 2nd-order context model which was previously thought to be too slow. And Brotli is designed for web contents in mind, which made it excellent for small inputs with no prior. Zstandard has no such treatments but have a better performance when I/O can handle it, which makes it excellent for server jobs.
Re:Chrome feature: Compression dictionary transport with Sha... by jacobgorm on Friday September 22, 2023 @06:47AM (#37610372)
ZStd started out as ZHuff, which was first announced in 2008; see https://encode.su/threads/521-Zhuff-fast-compression and http://fastcompression.blogspot.com/p/zhuff.html

I've been using LZ4 in commercial software since 2011, so unless I am some kind of luminary Google's compression experts must have been aware of both LZ4 and ZHuff when they started working on Brotli.

Re:Chrome feature: Compression dictionary transport with Sha... by lifthrasiir on Friday September 22, 2023 @07:20AM (#37610552)
By that reckoning I can claim that the origin of Brotli also dates back to 2012 or earlier. :-) Indeed, Brotli authors were also reponsible for the VP8 Lossless codec (2012), Pik (2017) and eventually JPEG XL (2019, in part). The entropy coding scheme is substantially similar among those codecs for this reason.

But really, the large amount of differences between two formats rather suggest that they were designed for different uses in mind, which I believe relate to the maximum possible I/O. Formats designed for the web don't have to have an extremely fast decoder because I/O is the bottleneck: 100 MB/s should be enough, and the earned time can be invested to higher compression ratio which affects the decoder performance.

Re:Chrome feature: Compression dictionary transport with Sha... by adgjlsfhk1 on Friday September 22, 2023 @08:45AM (#37611279)
otoh, they achieve pretty similar compression ratios and faster decode saves battery life and will let you get on to running the JavaScript earlier
Re:Chrome feature: Compression dictionary transport with Sha... by miohtama on Friday September 22, 2023 @07:58AM (#37610827)
The performance depends on the data. I have found that for English text and source code Brotli overperforms Zstd. Not sure if this because of the static dictionary or some other tweaks, though. However none of this is static, as both technologies are actively developed.
Re:Chrome feature: Compression dictionary transport with Sha... by lifthrasiir on Friday September 22, 2023 @08:05AM (#37610892)
Better decoding time performance, I should have said. The use of 2nd-order context model indeed makes Brotli more efficient in compression ratio for many kinds of data.
Re:Chrome feature: Compression dictionary transport with Sha... by pmarreck on Friday September 22, 2023 @10:58AM (#37612915)
Yes, but hasn't "separate compression dictionary" been a core feature of Zstd since its inception, at least under that name?
Re:Chrome feature: Compression dictionary transport with Sha... by lifthrasiir on Friday September 22, 2023 @11:20AM (#37613211)
Not even close, zlib had one. (Search for "FDICT" from RFC 1950.) What Zstandard did was a CLI to automatically generate a good enough dictionary from sample inputs.
Re:Chrome feature: Compression dictionary transport with Sha... by pmarreck on Friday September 22, 2023 @11:35AM (#37613419)

      FDICT (Preset dictionary)
         If FDICT is set, a DICT dictionary identifier is present
         immediately after the FLG byte. The dictionary is a sequence of
         bytes which are initially fed to the compressor without
         producing any compressed output. DICT is the Adler-32 checksum
         of this sequence of bytes (see the definition of ADLER32
         below).  The decompressor can use this identifier to determine
         which dictionary has been used by the compressor.
Well, wow. I have to wonder why this wasn't more utilized, then. There are a ton of contexts (columnar data in databases, for example) where shared-dictionary-based compression might have helped a ton before now.
Re:Chrome feature: Compression dictionary transport with Sha... by __alexs on Friday September 22, 2023 @06:23AM (#37610218)
Zstd no longer comes with a patent grant which I guess makes it kind of hard to actually use for some people.
Re:Chrome feature: Compression dictionary transport with Sha... by jacobgorm on Friday September 22, 2023 @06:31AM (#37610273)
Zstd is already used in the Linux kernel, and I would assume that any patents covering Lempel-Ziv and Huffman coding would have expired long ago. The situation around ANS also seems to have been resolved, see https://en.wikipedia.org/wiki/Asymmetric_numeral_systems#Tab... .
Re:Chrome feature: Compression dictionary transport with Sha... by abdullahhhh on Friday September 22, 2023 @06:32AM (#37610280)
The requirements for IP authorisation can vary depending on the jurisdiction and the type of intellectual property you're dealing with. Generally, you wouldn't necessarily need a CCG (Collectible Card Game) to apply for IP authorisation. However, if your CCG contains elements that you want to protect (like artwork, game mechanics, or unique terms), then you might need to consider IP protection for those specific aspects. https://gokutoapk.top/
Re:Chrome feature: Compression dictionary transport with Sha... by __alexs on Friday September 22, 2023 @09:22AM (#37611705)
The Linux kernel is stuffed full of potentially patent encumbered code.
Re:Chrome feature: Compression dictionary transport with Sha... by secondcoming on Friday September 22, 2023 @06:45AM (#37610362)
huh, isn’t zstd the compression used for debian packages?
Re:Chrome feature: Compression dictionary transport with Sha... by oynqr on Friday September 22, 2023 @06:20AM (#37610197)
Brotli usually compresses plain text better than ZSTD.
Re:Chrome feature: Compression dictionary transport with Sha... by out_of_protocol on Friday September 22, 2023 @06:26AM (#37610243)
Both with dictionaries? Both without? Any links to benchmarks?
Re:Chrome feature: Compression dictionary transport with Sha... by oynqr on Saturday September 23, 2023 @05:54AM (#37621889)
Brotli comes with a dictionary by default, which is optimized for plaintext use cases. Once you give ZSTD a similar dictionary, its ratios are going to be similar/better.

I won't provide random links, because those can't replace testing on your own dataset.

Re:Chrome feature: Compression dictionary transport with Sha... by joelthelion on Friday September 22, 2023 @06:16AM (#37610171)
Patents, maybe?
Re:Chrome feature: Compression dictionary transport with Sha... by jauntywundrkind on Friday September 22, 2023 @10:11AM (#37612304)
Brotli has two major advantages. First it encodes to the same well known gzip format, so rolling it out didn't require new clients. Second, it didn't require dictionary support.

Where-as if you look at Mozilla's standards-positions for zstd, they defer because it requires a compression dictionary to encode & Moz didn't want to have to "standardize" one specific dictionary. https://github.com/mozilla/standards-positions/issues/105

Re:Chrome feature: Compression dictionary transport with Sha... by pmarreck on Friday September 22, 2023 @11:03AM (#37612993)
> Moz didn't want to have to "standardize" one specific dictionary

You could have multiple sources of dictionary identified by something like a hash, and cached in the browser. For example you could have a general-purpose HTML dictionary, a general-purpose CSS dictionary and a general-purpose JS dictionary, have canonical/official versions of these hosted somewhere (say, on Github) and distributed wherever, and update them on a semi regular basis (at the cost of re-compression of the associated data); and in turn these could be overrided on perhaps a site by site basis with site-specific versions of these. You could basically associate an overridable but defaulted dictionary specification by MIME type (or none at all in the case of already-compressed data).

Every file would have to be sent with the hash of the dictionary that was used to start compressing it, which would then be retrieved and cached somehow.

I could see this resulting in some fairly significant byte savings, especially for retrieval of many smaller files.

I bet this would also be useful potentially for email clients/servers.

Re:Chrome feature: Compression dictionary transport with Sha... by jauntywundrkind on Friday September 22, 2023 @05:33PM (#37618074)
> You could have multiple sources of dictionary identified by something like a hash, and cached in the browser.

The browser actually has a very advanced implementation of something like this! They're called urls. The work here is to make it possible to identify dictionaries & retrieve & cache them in the browsers.

Mozilla I think smartly avoided creating a spec that requires some variety of centralized governance of what dictionaries to use, like you describe. Whatever the intent of such a community, it creates biases & will have a hard time figuring out what sets of dictionaries are worth creating, for what intents or code bases, and adapting or not as it discovers underserved code bases.

Re:Chrome feature: Compression dictionary transport with Sha... by masklinn on Friday September 22, 2023 @11:27AM (#37613300)
> Brotli has two major advantages. First it encodes to the same well known gzip format

It does not. You’re thinking about zopfli. Brotli is an alternative to but not compatible with gzip.

Re:Chrome feature: Compression dictionary transport with Sha... by pmarreck on Friday September 22, 2023 @10:59AM (#37612929)
The Zstd guy is employed by Facebook, so I'd suspect it's at least in part a NIH thing.