Data Compression Nerds Hate This One Trick [video](media.ccc.de)
media.ccc.de
Data Compression Nerds Hate This One Trick [video]
https://media.ccc.de/v/eh22-8-more-than-just-quite-ok-data-compression-nerds-hate-this-one-trick
45 comments
Reminds me of one of my most exhilerating old-timer stories. I once took 15 seconds off of the boot time of a smartphone - halving the startup time! - by replacing the MNG (think PNG but multi-frame animation; no surprise it never took off) startup animation with a custom encode-runs-of-pixel-offsets that nicely captured the way the logo swirled. Then encoded this as static data in a dll which the phone had a built-in system for compressing which worked well for this data, so doubly faster. This made me a complete legend for a while, although that phone model ended up never shipping.
Similar but different old-time story about a scroll wheel on a smartphone not working. I had unfortunately been flown to a foreign country to solve a FW issue where scrolling had been made unreliable with a development team I could barely communicate with, and build times measured in fractional days.
Of course it turned out that ID had decided they wanted a longer bleep-boop every time you spun the wheel, and the real-time screen position update was dependent on the sound completing. Click-ticks were completely unacceptable, but adding a scroll buffer and detecting it's state while filling an audio buffer with tiny fractional bleeps allowed reasonable latency scrolling. Of course buffer cleanup and beep-slice management was the most annoying. Sadly, the phone shipped.
Of course it turned out that ID had decided they wanted a longer bleep-boop every time you spun the wheel, and the real-time screen position update was dependent on the sound completing. Click-ticks were completely unacceptable, but adding a scroll buffer and detecting it's state while filling an audio buffer with tiny fractional bleeps allowed reasonable latency scrolling. Of course buffer cleanup and beep-slice management was the most annoying. Sadly, the phone shipped.
> and the real-time screen position update was dependent on the sound completing.
Over the years I saw tons of software in windows that made mistakes like this. Some stupid animations or sounds that were synced with the actual logic of the application holding everything up.
Years ago there was some app our team installed that just took forever to install around 500MB of data, like 30 minutes. When we monitored it there was nothing going on most of the time. We ended up just batching out all the files, registry keys, and dll registrations to install in less than 5 minutes.
Over the years I saw tons of software in windows that made mistakes like this. Some stupid animations or sounds that were synced with the actual logic of the application holding everything up.
Years ago there was some app our team installed that just took forever to install around 500MB of data, like 30 minutes. When we monitored it there was nothing going on most of the time. We ended up just batching out all the files, registry keys, and dll registrations to install in less than 5 minutes.
Every day I learn something that makes me wanna start building and repairing Z80 based computers running FORTH and patiently wait for the the modern computer ecosystem to collapse under its own weight.
MNG was unfortunately designed so badly that Mozilla had to create APNG to replace it. In retrospect, MNG was only capable to do about 10% of what SVG 1.0 can do on top of an incomprensible binary format. (One may argue that SVG is also badly designed for this reason.)
yeah I remember no joy working with implementations of it. The whole thing smelt like a standards body mess when really they should have got one good engineer to just make something workable in a weekend. Its possibly worse than the OpenGLES mess.
It's rare that I see such a fractally wrong comment. I guess APNG did come from Mozilla, which I think is the only true subpart of the above?
Okay, I admit the "badly designed" part is my claim, but I'm very confident in that claim and can explain why.
The original impetus that led to MNG was animated GIF. While GIF was also designed as extensible, GIF practically only had a handful number of extensions and wasn't that complex. MNG in comparison was essentially a binary version of SVG as I have described, except that it had no vector graphics and can more accurately be described as a binary slideshow format [1]. No one asked for this! The PNG development group forgot its goal and made a much bloated specification. As a result libmng, while working, was a quite big library to be incorporated into Gecko and ultimately rejected in favor of APNG which only required a small patch to libpng. It is amusing that the original PNG specification had chunks corresponding to GIF extensions including animation one; those chunks might have been widespread in the alternate universe!
If the group's goal was indeed a slideshow format, it should have been two separate formats, one for multi-part images and one for animations and object transformations. The former is necessary because one aspect of GIF was that a difference from the previous frame can be encoded, so this "Delta-PNG" format should have been made into the mainline PNG specification as an option. (These additional images could have been used as previews, for example.) And anything else should be a simple textual format that refers to external files. MNG instead had chunks for JPEG images---came with its standalone sister format called JNG---, which is absurd when you think about it---why should there be JNG when JFIF and Exif already exist? The modern SVG happens to be perfectly usable as this second format, and it is fine being textual.
[1] If you can't believe what I've said, see the table of contents of the actual specification: http://www.libpng.org/pub/mng/spec/
The original impetus that led to MNG was animated GIF. While GIF was also designed as extensible, GIF practically only had a handful number of extensions and wasn't that complex. MNG in comparison was essentially a binary version of SVG as I have described, except that it had no vector graphics and can more accurately be described as a binary slideshow format [1]. No one asked for this! The PNG development group forgot its goal and made a much bloated specification. As a result libmng, while working, was a quite big library to be incorporated into Gecko and ultimately rejected in favor of APNG which only required a small patch to libpng. It is amusing that the original PNG specification had chunks corresponding to GIF extensions including animation one; those chunks might have been widespread in the alternate universe!
If the group's goal was indeed a slideshow format, it should have been two separate formats, one for multi-part images and one for animations and object transformations. The former is necessary because one aspect of GIF was that a difference from the previous frame can be encoded, so this "Delta-PNG" format should have been made into the mainline PNG specification as an option. (These additional images could have been used as previews, for example.) And anything else should be a simple textual format that refers to external files. MNG instead had chunks for JPEG images---came with its standalone sister format called JNG---, which is absurd when you think about it---why should there be JNG when JFIF and Exif already exist? The modern SVG happens to be perfectly usable as this second format, and it is fine being textual.
[1] If you can't believe what I've said, see the table of contents of the actual specification: http://www.libpng.org/pub/mng/spec/
Link [1] doesn't seem to mention svg or vector graphics at all.
I think the point was that like SVG, MNG has the ability to transform existing objects in order to compose an image.
See this example[1] for illustration.
[1]: http://www.libpng.org/pub/mng/spec/#example4
See this example[1] for illustration.
[1]: http://www.libpng.org/pub/mng/spec/#example4
> Link [1] doesn't seem to mention svg or vector graphics at all.
They specifically called out that it doesn't support vector graphics, so the latter shouldn't be a surprise.
And if you want to check if it's like SVG but worse, you need to compare that spec with the SVG spec, not look for the word SVG.
They specifically called out that it doesn't support vector graphics, so the latter shouldn't be a surprise.
And if you want to check if it's like SVG but worse, you need to compare that spec with the SVG spec, not look for the word SVG.
Slides: https://filmroellchen.eu/talks/QOI%20EH25/#/0/1
As that data compression nerd, QOI is both a refresher and an annoyance. It serves as a good example that input modelling is very important, so much that QOI almost beats PNG in spite of very suboptimal coding. But QOI also represents a missed opportunity because, well, we can do much better if we are willing to use something like QOI instead of standard formats! Weirdly enough people seem to value only the simplicity when it comes to QOI, which is not the main takeaway I believe. Maybe QOIR [1] might result in a better balanced format in the future though...
[1] https://github.com/nigeltao/qoir/
As that data compression nerd, QOI is both a refresher and an annoyance. It serves as a good example that input modelling is very important, so much that QOI almost beats PNG in spite of very suboptimal coding. But QOI also represents a missed opportunity because, well, we can do much better if we are willing to use something like QOI instead of standard formats! Weirdly enough people seem to value only the simplicity when it comes to QOI, which is not the main takeaway I believe. Maybe QOIR [1] might result in a better balanced format in the future though...
[1] https://github.com/nigeltao/qoir/
[deleted]
Let's say you had a lossless image format that's 20% smaller (on average for pictures people send over networks) than PNG. Let's say it takes 10% more computing power than PNG. Do you stand to make money? What would it be used for?
I can't imagine people will start storing their family pictures in a new format they've never heard of which is not supported by any software they use for "just" 20% better compression. Do they even want lossless compression in the first place (if you don't ask them directly and call it that)?
I can't imagine people will start storing their family pictures in a new format they've never heard of which is not supported by any software they use for "just" 20% better compression. Do they even want lossless compression in the first place (if you don't ask them directly and call it that)?
That's the portability bit the presenter mentions, and is a very important concern in practice. But how about recompression? For example many PNG files are suboptimally compressed partly because PNG is an old format and also because many softwares have been too dumb to produce a well-optimized PNG. In that case we may benefit from a transparent recompression, which may be done either by using a better library like libdeflate or by internally using a separate format that can be quickly transformed from and back to PNG. In fact Dropbox did so for JPEG files [1]. When I'm saying "so much better" I was thinking about such opportunities that benefit end users.
[1] https://github.com/dropbox/lepton
[1] https://github.com/dropbox/lepton
Dropbox apparently abandoned the project. Do you know what their takeaways were from trying to improve the JPEG storage?
For example, was it worth it in the end? Did they announce anything? Did they switch to another method or give up on the idea, or do we not know?
For example, was it worth it in the end? Did they announce anything? Did they switch to another method or give up on the idea, or do we not know?
Dropbox apparently still uses Lepton or any successor internally, but the open source version is abandoned because it posed larger maintenance burden than internal projects.
Has Dropbox said this anywhere? Or are you assuming it based on something like "this kind of project is very easy to maintain internally so there's no reason why they would have stopped using it"?
At least at the time of abandonment, Dropbox did say (emphasis mine):
> While we did ensure that the reported vulnerabilities don’t affect our internal use of Lepton, we unfortunately don’t have the capacity to properly fix these and future issues in this public repo.
As far as I know this is indeed the last known public mention of its use, but given that Lepton was already in use and dropping it would substantially increase its traffic, it is reasonable to assume that its use somehow continues to this day.
> While we did ensure that the reported vulnerabilities don’t affect our internal use of Lepton, we unfortunately don’t have the capacity to properly fix these and future issues in this public repo.
As far as I know this is indeed the last known public mention of its use, but given that Lepton was already in use and dropping it would substantially increase its traffic, it is reasonable to assume that its use somehow continues to this day.
That's pretty strange. If they're using it in a meaningful way, then they're applying it to arbitrary files, so they'd generally need fixes for almost all the bugs. So what resources would be lacking so badly that they give up on releasing?
It could just be a lame excuse. Open sourcing with zero support would be better than not doing it. But I imagine that this seems valuable enough to keep secret, or at least not to pay money to polish up for external use.
QOI is just a simple filter. It cannot do full compression. In fact, in certain cases it can increase the size instead of compressing. It is unnecessarily overrated, of course, mostly because it is open source. The rest is irrelevant.
There is another codec that is as fast as QOI (or even faster and multi-core) but with a much higher compression ratio. HALIC (High Availability Lossless Image Compression). But because it's closed source, it definitely didn't get the attention and respect it should have gotten. And that's why I think it stopped developing.
https://github.com/Hakan-Abbas/HALIC-High-Availability-Lossl...
https://github.com/Hakan-Abbas/HALIC-High-Availability-Lossl...
>>> In fact, in certain cases it can increase the size instead of compressing.
Fwiw, all (lossless) compression algorithms will increase the size of some inputs.
Fwiw, all (lossless) compression algorithms will increase the size of some inputs.
> Fwiw, all (lossless) compression algorithms will increase the size of some inputs.
They rarely meaningfully increase the size though. Typical compression algorithms, when faced with hard to compress sections, can add a handful of bits to wrap them up. Total overhead a fraction of a percent.
When QOI encounters noisy pixels, it has to spend an extra byte per pixel, inflating the file by 33%.
They rarely meaningfully increase the size though. Typical compression algorithms, when faced with hard to compress sections, can add a handful of bits to wrap them up. Total overhead a fraction of a percent.
When QOI encounters noisy pixels, it has to spend an extra byte per pixel, inflating the file by 33%.
one pretty simple qoi improvement would be a tag to say to store the next n pixels uncompressed. I think there's room in the tags for adding it
I wanted to use HALIC but ended up using SQZ instead.
QOI is overrated but QOIR and my own QOIX are a bit more interesting, albeit ultimately stupid.
A simple filter may still do wonder if it is carefully chosen ;-)
The apparent death of HALIC was indeed unfortunate, I've heard that its decoder was less than 1K lines of code so it must have had a carefully designed and optimized context model in its heart. But there are so many other formats that are F/OSS but weren't highlighted enough anyway...
The apparent death of HALIC was indeed unfortunate, I've heard that its decoder was less than 1K lines of code so it must have had a carefully designed and optimized context model in its heart. But there are so many other formats that are F/OSS but weren't highlighted enough anyway...
For a format to proliferate as a standard, it has to be open source. Nobody cares about 5% smaller images if not everyone can view them.
Historically speaking, that’s not true; WMV and FLV were extremely popular for over a decade in the early 2000s. Closed source formats can, and have, become de facto standards if they solve a pressing need that open standards don’t (or provide a stepwise increase in functionality or performance) and if there’s sufficient market demand.
This is the website of the presented project for those who prefer text:
https://qoiformat.org/
An interesting and somewhat inspiring bit of trivia from the video: the creator barely understands modern image compression techniques (from their own words), but this hasn't stopped them from coming up with that impressive result.
https://qoiformat.org/
An interesting and somewhat inspiring bit of trivia from the video: the creator barely understands modern image compression techniques (from their own words), but this hasn't stopped them from coming up with that impressive result.
Here's an interesting negative result.
After watching this video, my first thought was whether recent results from columnar compression (e.g. https://docs.vortex.dev/references#id1) applied "naively" like QOI would have good results.
I started with a 1.79MiB sprite file for a 2D game I've been hacking on, and here are the results:
So, there's magic to being Quite OK that is more than just applying compression techniques than elsewhere :)
After watching this video, my first thought was whether recent results from columnar compression (e.g. https://docs.vortex.dev/references#id1) applied "naively" like QOI would have good results.
I started with a 1.79MiB sprite file for a 2D game I've been hacking on, and here are the results:
PNG: 1.79 MiB
QOI: 2.18 MiB
BtrBlocks: 3.69 MiB
So, there's magic to being Quite OK that is more than just applying compression techniques than elsewhere :)
Even ironic clickbait is irritating.
Going off of the description, since I currently can't watch videos or anything with audio:
> How one guy in his bedroom (kind of) beat all of PNG's combined multi-decade effort in one year, and why that's strange.
PNG is a 30 year old format and hasn't changed much over the years (as far as I am aware). PNG at it's core is still just some basic filters with DEFLATE on top. The decades of work would mostly be spend on optimizing the encoding speed and finding better heuristics for selecting filters. There is a lot more impressive codecs nowadays.
Apart from that I am still a big fan of QOI. It has amazing results for how simple the format is.
> How one guy in his bedroom (kind of) beat all of PNG's combined multi-decade effort in one year, and why that's strange.
PNG is a 30 year old format and hasn't changed much over the years (as far as I am aware). PNG at it's core is still just some basic filters with DEFLATE on top. The decades of work would mostly be spend on optimizing the encoding speed and finding better heuristics for selecting filters. There is a lot more impressive codecs nowadays.
Apart from that I am still a big fan of QOI. It has amazing results for how simple the format is.
QOI is just a simple filter. It cannot do full compression. In fact, in certain cases it can increase the size instead of compressing. It is unnecessarily overrated, of course, mostly because it is open source. The rest is irrelevant. There are another codecs that is as fast as QOI (or even faster and multi-core) but with a much higher compression ratio.
In this day and age, storage is not as important as IO, so I hate it when I see benchmarks with compression ratios + CPU times. That's not helpful.
What I want to see is the total IO + CPU time across libraries for my specific IO and CPU constraints.
Sure, it makes benchmarks more involved to display, as scalars are not enough anymore, you need multiple curves, but that's meaningful at least.
To illustrate, if I have very fast IO, then I probably don't care of the compression ratio, it will be faster to download the raw payload and have 0 decompression cost.
On the other end of the spectrum, if I have very slow IO, I would gladly have a much slower decompression algorithm but higher compression ratio for a faster overall timing.
This is especially important because cloud storage for instance are rather cheap, but slow. Caches/CDNs are very fast, but storage is expensive. Etc
What I want to see is the total IO + CPU time across libraries for my specific IO and CPU constraints.
Sure, it makes benchmarks more involved to display, as scalars are not enough anymore, you need multiple curves, but that's meaningful at least.
To illustrate, if I have very fast IO, then I probably don't care of the compression ratio, it will be faster to download the raw payload and have 0 decompression cost.
On the other end of the spectrum, if I have very slow IO, I would gladly have a much slower decompression algorithm but higher compression ratio for a faster overall timing.
This is especially important because cloud storage for instance are rather cheap, but slow. Caches/CDNs are very fast, but storage is expensive. Etc
> What I want to see is the total IO + CPU time across libraries for my specific IO and CPU constraints.
This knob is typically called as a (compression) level, even though it isn't advertised as such because it is hard to translate level into your metric. Some libraries like zstd support IO-adaptive operations as a simpler alternative too.
This knob is typically called as a (compression) level, even though it isn't advertised as such because it is hard to translate level into your metric. Some libraries like zstd support IO-adaptive operations as a simpler alternative too.
Read and write time are cpu_time/your_cpu_performance + data_size/your_bandwidth.
The benchmark doesn't know what your CPU performance and bandwidth are (or will be on some future device). You should be able to multiply these costs out yourself.
The benchmark doesn't know what your CPU performance and bandwidth are (or will be on some future device). You should be able to multiply these costs out yourself.
In the specific examples mentioned, it almost doesn’t matter. It achieves nearly identical sizes (within 10-20%) that the transfer size of the image given typical sizes is nearly irrelevant unless you’re downloading on dial-up.
You're assuming that IO and CPU are equal.
CPU speed is getting faster at a much higher rate than IO. It makes sense, one is infrastructure, the other is the silicon in your pocket.
That's why you're getting downvoted, and why algos always push more and more to the CPU. Statistically, the correct posture is to expect the CPU to consistently get faster. I mean, if you make an image format now, you want it to work with CPUs in 30 years. Will IO speed gains overtake CPU improvements in 30 years? Most certainly not.
CPU speed is getting faster at a much higher rate than IO. It makes sense, one is infrastructure, the other is the silicon in your pocket.
That's why you're getting downvoted, and why algos always push more and more to the CPU. Statistically, the correct posture is to expect the CPU to consistently get faster. I mean, if you make an image format now, you want it to work with CPUs in 30 years. Will IO speed gains overtake CPU improvements in 30 years? Most certainly not.
Data compression nerds really hate it when someone claims to be able to compress any string of m bits to n < m bits, without loss.
_ZeD_(1)