Alternative compression algorithms

[daniel-dewa]

GZip is not exactly the latest or greatest at compressing sparse data.

When working with big status lists (~1-2 MB), which have few bits flipped, GZip performance severely degrades compared to newer algorithms.

Algorithm	Bits flipped	Uncompressed size	Compressed size	Compression ratio
GZip	0bits	1.1 MB	1.4 KB	~/790
GZip	60 bits	1.3 MB	1.8 KB	~1/724
GZip	180 bits	4.0 MB	5.4 KB	~/740
Brotli	0 bits	1.1 MB	20 B	~1/55,000
Brotli	60 bits	1.3 MB	200 B	~1/6,493
Brotli	180 bits	4.0 MB	532 B	~1/7,520

Currently GZip is hardcoded into the standard, could it be possible to have a prefix or something that specifies which algorithm the data is compressed with?

[adeinega]

Just out of curiosity... what are you thoughts about ZLIB?

[dlongley]

@daniel-dewa,

Currently GZip is hardcoded into the standard, could it be possible to have a prefix or something that specifies which algorithm the data is compressed with?

Yes, however, that adds interoperability complexity -- which has to be justifiable (and maybe it is!).

What we're looking for here when making a decision for a global standard (as opposed to a specific application or limited ecosystem choice) prioritizes existing implementations, implementater burden, and interoperability over, say, "best possible compression". This is similar to global standard choices made around hash functions, where, for example, something like SHAKE-256 may outperform SHA-256, but not sufficiently so to override these other priorities.

If a particular compression algorithm (or hash algorithm, or any other algorithm...) is essentially ubiquitous (like gzip is), and it does "well enough", then it's often considered a "better" choice for a global standard even if something else outperforms it -- and even if it's a considerable improvement. Another way of putting it is that a massive improvement over "good enough" doesn't change the decision on its own, these other factors have to be considered.

Regarding any alternative compression algorithm (e.g., "Brotli") -- additional analysis is required to determine how common it is, how easily it can be implemented, what royalty-free / open source and performant implementations are available in various programming languages, whether a sufficient number of implementers would use it, whether it can be easily referenced in a stable spec (e.g., ideally from W3C / IETF), etc. I know Brotli in particular would do well in at least some of these categories (e.g., it is defined by RFC 7932).

This also suggests that we might also want a more rigorous discussion and quantification in the spec for what "good enough" compression is here -- given existing use cases and whatever extrapolation we can do for future unknown / innovative ones.

[dlongley]

@adeinega,

Just out of curiosity... what are you thoughts about ZLIB?

GZIP, the standard's current choice, is more or less just ZLIB (deflate algorithm) with a different header. It was chosen because the compression ratio was "good enough" (per willing implementers), it is essentially ubiquitously used on the Web today, and ticks various other standards/interop boxes. IIRC, zlib was used a few years back as the first choice during incubation (prior to standardization) -- and this was switched to GZIP based on implementer feedback because it was even more common.