7 ms·
Okay, the decoder is less than a kilobyte. But where is that an advantage over a 50KB PNG decoder, when the compression ratio suffers so much?
by Dylan16807 4y ago
Okay, the decoder is less than a kilobyte. But where is that an advantage over a 50KB PNG decoder, when the compression ratio suffers so much?
- whateveracct 4y agogolf
- Dylan16807 4y agoGolf of what sort? It's hard to beat RLE or RLE+palette for minimal code size. I'd expect either one of those to be a tenth the size of a QOI decoder.
- adgjlsfhk1 4y agothese do well on synthetic images but really poorly with noise. QOI manages pretty good performance even with noise.
- Dylan16807 4y agoThat doesn't really explain the code golf answer.
- eps 4y agoQOI is in the same ballpark as RLE simplicty-wise but performs much better in a larger number of common cases. That's very much "golf".
- Dylan16807 4y agoI don't know about that. My estimate would be that QOI is ten times as complex as RLE and ten times less complex than DEFLATE-style compression. It could (barely) share a ballpark with either one.
- jitl 4y agoI came away from reading the article wondering what context I was missing. What use-case is the author targeting? It feels like I need to read more about this author to understand the article.
- dmix 4y agoIt reminds me of that Steve Jobs insult thread, it’s a technology looking for an audience. The pitch as I can tell is that the specification is simple. So the guy who spends a lot of time writing code based on specifications likes it? I guess that’s the niche audience. Maybe a better pitch would be “image format specifications should be more like QOI”.
- bscphil 4y agoI think it's in the title: assets. The example case is replacing the BMP assets used by a game with QOI with a resulting 10x size reduction: https://github.com/skeeto/chess/commit/5c123b3 https://github.com/skeeto/chess/commit/5c123b3 I think this functions as a test case. For a game as simple as a chess UI, PNG would probably be fine unless you're code-golfing on the final output binary size or refusing to use common dependencies. But for some programs (e.g. large video games), preloading all your assets is very common and decoding speed can be crucial. Maybe the assets could even be left in compressed form in memory in order to reduce the system requirements? I'm not sure if this is common or not. Side note: video game assets are often enormous in size because developers refuse to implement even very basic compression because of the supposed performance impact. Getting the decompression speed up can result in tremendous reduction in disk usage because it allows doing compression without losing performance.
- duskwuff 4y ago> But for some programs (e.g. large video games), preloading all your assets is very common and decoding speed can be crucial. Those games typically don't need lossless image compression. There are much better (and faster) algorithms for lossy texture compression, many of which can even be decoded directly by the GPU. The S3TC family is one popular example. One interesting commercial product in this space is Oodle Texture: http://www.radgametools.com/oodletexture.htm http://www.radgametools.com/oodletexture.htm
- adgjlsfhk1 4y agoif you throw lz4 or zstd on top of it, of it, it actually can beat png
- oefrha 4y agoSo, if you throw another >100KB decoder on top of the 1KB decoder, you can beat png (haven’t verified). What’s the point.
- adgjlsfhk1 4y agolz4 is also pretty small https://nigeltao.github.io/blog/2022/qoir.html https://nigeltao.github.io/blog/2022/qoir.html is an implementation of QOI with some tweaks+lz4 and it's still pretty tiny
- masklinn 4y agoAlso I could see it with zstd (which is a lot more than 100k, though very fast indeed) but I’m a bit doubtful about lz4, it’s generally worse than deflate (which png uses) at compression and qoi lacks filtering.
- duskwuff 4y agoQOI's QOI_OP_DIFF and QOI_OP_LUMA opcodes can act like horizontal filtering once the results are fed into a stream compressor. There's nothing to provide vertical filtering, though, which is a pretty huge limitation. I wonder if you'd get better compression using a zigzag scan?
- adgjlsfhk1 4y agothere was some work done to find better scan arrangements. unfortunately, is pretty hard to do so without storing the previous row in memory which has a pretty large effect on speed
- robinsonb5 4y agoI once ported an LZ4 decoder from 68k to my own toy CPU design - the lz4_depack routine weighs in at a whopping 72 bytes. https://github.com/robinsonb5/EightThirtyTwoDemos/blob/master/LZ4/Firmware/lz4.asm https://github.com/robinsonb5/EightThirtyTwoDemos/blob/maste...
- masklinn 4y agoGiven the context, simplicity and control. I assume part of the inefficiency can be reclaimed by compressing the assets separately, although the lack of filtering would hurt. Encoding and decoding speed as well, because qoi is much simpler (simplistic even) it decodes at 3x libpng (which I’d assume is more relevant than the 20x compression for OP, though then encode might be more relevant for other applications but then IO trade offs rear their ugly heads).
- makapuf 4y agoIts a tradeoff. Decoder is real fast and can be used in embedded contexts (or ported to languages simply). Encoder is also really fast which can be useful for game textures by example.
- ardwindo 4y agoSome people consider implementation simplicity as a virtue. It's nice to be able to understand large parts of your stack at a source code level. I'd like to see more minimal viable X.
- spullara 4y agoYeah, but that doesn't make any sense at all. So, don't listen to them. If any photo saves 50kb from compression you can easily see that thinking this is a mistake.
- csande17 4y agoJavaScript developers tell me that disk space and network bandwidth are cheap these days. While they're mostly saying that to try and justify extremely bad architectural decisions (what's a couple thousand NPM dependencies between friends?), maybe we can apply that logic here. Maybe it's worth making every image file twice as big, if we can use a much simpler decoder implementation that's not a constant source of bugs and security vulnerabilities.
- Dylan16807 4y agoBy using a bespoke decompressor? No thanks. Take a standard format and make sure all array bounds are checked. Data-oriented compression formats tend not to be very complicated and can be implemented with few instances of simple data structures.
- hnlmorg 4y agoI’m not saying I agree with them but I do sympathise with the argument. Is old timers spent the first part of our career understand most, if not all, of the technology stack. It’s actually really empowering having that level insight. So I can see why people might still crave for those days of simplicity back. It’s not not a decision I’d personally follow but I do see the attraction in their decision.
- 4y ago
- jchw 4y agoThe QOI benchmarks shows it only lagging a small bit behind PNG in compression ratio, while performing much faster (multiples) in both encoding and decoding. Doesn't seem like an awful trade-off. Surely you'd expect a much larger, slower and more sophisticated encoder and decoder would at least net 25-50% improvements to compression ratio, but it seems to net much less. If you are artificially or truly constrained in either CPU usage, or maybe just static code size, it seems like it would have some appeal, even if niche.
- duskwuff 4y ago> The QOI benchmarks shows it only lagging a small bit behind PNG in compression ratio The benchmarks are misleading. By size, they mostly consist of photographs and other true-color images, which neither compressor handles well. This has the effect of hiding QOI's lackluster performance on synthetic images which PNG does compress well. In particular, QOI performs dramatically worse than PNG on synthetic images containing any sort of vertical pattern. As a worst-case example, an image consisting of a single line of noise repeated vertically will compress down to basically nothing in PNG, but QOI will fail to compress it at all.
- jchw 4y agoYes, but the point is that it's not really that far off. PNG will outperform in screenshots with a lot of empty space, so if you were dealing with that situation, obviously PNG is better. OTOH, QOI still performs relatively well: while the difference is multiples in some cases, to me it seems that those cases are mostly ones where PNG's compression ratio is obscenely good, and therefore QOI is actually still producing reasonably small image files, too. I can see that QOI performs well for what you might use as texture maps for 3D rasterization, for example. Definitely seems to have some applicability to me.
- mananaysiempre 4y ago> The QOI benchmarks shows it only lagging a small bit behind PNG in compression ratio, while performing much faster (multiples) in both encoding and decoding. Presumably that’s with stock libpng, which uses zlib. I wonder if anyone tried patching it to use the substantially faster (on x86) libdeflate[1] instead? It doesn’t do streaming, but you shouldn’t really need that for PNG textures. [1] https://github.com/ebiggers/libdeflate https://github.com/ebiggers/libdeflate
- AceJohnny2 4y agoEmbedded. We're currently fighting to gain 10-20kB in our binary.
- masklinn 4y agoAh but will you trade that for 5MB in assets?
- AceJohnny2 4y agoEh, the assets can be streamed. The decoder resides in .text
- audunw 4y agoEmbedded can mean many different things, so it's still not clear what the challenge is.. But it sounds to me like you're trying to reduce the amount of code on the NVM of an MCU, where space is very limited, but you have slower off-chip (QSPI, SDC, ..) memory where you can store images?