Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

QOI – The “Quite OK Image Format” for fast, lossless image compression

github.com

Post reply on HN
Print view View original

61–70 of 105 posts

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#61

Post by rndgermandude »

FullyFunctional wrote: post #35
stathibus wrote: post #32

Earlier quoted context omitted.

Who cares that it's not set up for simd? Seriously, who? This project is interesting because of how well it does compared to other systems of much higher complexity and without optimizing the implementation to high heaven. We can all learn something from that.

Good question. The answer is all the poor souls that N years later find themselves stuck with a data in a legacy format that they have to struggle to decode faster. Of all the artifacts in our industry, few things live longer than formats. Eg. we are still unpacking tar files (Tape ARchieve), transmitted over IPv4, decoded by machines running x86 processors (and others, sure). All of these formats couldn't possible a…

Those poor souls N years later will either have to decode a very few images, which is still fast enough, or decode a lot of images, which can be parallelized and run concurrently on a per-image level. In the very worst case, decode an extremely large single image, you're a bit out of luck, but that case would be rare, and you're still pretty fast at decoding anyway.

Creating formats and specs that are "future proof" is a noble goal. Criticizing QOI for not being able to be well parallelized inside the decode function, that seems more like a demand for a premature optimization to me...

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#62

Post by Dylan16807 »

FullyFunctional wrote: post #46
nynx wrote: post #37

Earlier quoted context omitted.

Unrelated to the rest of your comment, but risc-v does not have variable-length instructions. It has compressed instructions, but they're designed in such a way to be easily and efficiently integrated into the decoder for normal instructions, which are all 32 bits.

My day job for 6+ years is implementing high perf RISC-V cores and my name is in many of the RISC-V specs. Variable length ISAs are characterized by not being able to tell the beginning of an instruction without knowing the entrypoint. This applies to RISC-V with compressed instructions. Finding the boundaries is akin to a prefix scan and has a cost roughly linear in the scan length, but IMO the biggest loss is that…

> IMO the biggest loss is that you can’t begin predecode at I$ fill time.

That helps enough to overcome the increased code size?

I really wouldn't say they learned nothing from x86, though. You only have to look at 2 bits, and if you can get your users to put in the slightest effort then compilers can be told not to use C.

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#63

Post by FullyFunctional »

Dylan16807 wrote: post #62
FullyFunctional wrote: post #46

Earlier quoted context omitted.

My day job for 6+ years is implementing high perf RISC-V cores and my name is in many of the RISC-V specs. Variable length ISAs are characterized by not being able to tell the beginning of an instruction without knowing the entrypoint. This applies to RISC-V with compressed instructions. Finding the boundaries is akin to a prefix scan and has a cost roughly linear in the scan length, but IMO the biggest loss is that…

> IMO the biggest loss is that you can’t begin predecode at I$ fill time. That helps enough to overcome the increased code size? I really wouldn't say they learned nothing from x86, though. You only have to look at 2 bits, and if you can get your users to put in the slightest effort then compilers can be told not to use C.

That's a false strawman. There are infinitely many ways to achieve the same or better density without the drawback. Allowing instruction to span cache line, or even pages, is a mistake that we'll pay for forever.

The simplest possible mitigation would have been to disallow an instruction from spanning a 64-byte boundary. It would have almost no impact on instruction density, but it would have saved a lot of headaches for implementations.

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#64

Post by gautamcgoel »

FullyFunctional wrote: post #46
nynx wrote: post #37

Earlier quoted context omitted.

Unrelated to the rest of your comment, but risc-v does not have variable-length instructions. It has compressed instructions, but they're designed in such a way to be easily and efficiently integrated into the decoder for normal instructions, which are all 32 bits.

My day job for 6+ years is implementing high perf RISC-V cores and my name is in many of the RISC-V specs. Variable length ISAs are characterized by not being able to tell the beginning of an instruction without knowing the entrypoint. This applies to RISC-V with compressed instructions. Finding the boundaries is akin to a prefix scan and has a cost roughly linear in the scan length, but IMO the biggest loss is that…

It sounds like you regret the decision to make RISC-V variable length. Is that correct?

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#65

Post by TylerE »

zigzag312 wrote: post #23
artiii wrote: post #16

Earlier quoted context omitted.

check WavPack (32pcm, floats etc) but it's slower(not much) than flac, offering slighty beter compresion.

WavPack seems a bit too slow already. 3x slower decode compared to FLAC in this test https://stsaz.github.io/fmedia/audio-formats/

Wavpack on a modern CPU, from your own link, decodes at approx. 250x realtime. How fast is 'fast enough' if that isn't?

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#66

Post by edflsafoiewq »

ErikCorry wrote: post #52
jws wrote: post #21

Earlier quoted context omitted.

I find it interesting that QOI avoids any kind of Huffman style coding. Huffman encoding lets you store frequently used values in fewer bits than rarely occurring values, but the cost of a naïve implementation is a branch on every encoded bit. You can mitigate this by making a state machine keyed by "accumulated prefix bits" and as many bits as you want to process in a whack, these tables will blow out your L1 data c…

I would think that you could use a hybrid approach where you have a table that is perhaps 9 or 10 bits wide and covers many of the more common codes, which will by definition be more common. Should be small enough to fit in the cache. Then do something slower for the very long codes. This way you avoid difficult branches most of the time.

Exactly. Normally you use second-level tables for the long codes. In the first table, if code doesn't reach a leaf, tbl[code] holds a pointer to the next table to use.

For example, here's JPEG XL's Huffman decoder: https://github.com/libjxl/libjxl/blob/1c67f4eff0464e6241f365.... The branch uses a second table if the code was too long.

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#67

Post by Dylan16807 »

FullyFunctional wrote: post #63
Dylan16807 wrote: post #62

Earlier quoted context omitted.

> IMO the biggest loss is that you can’t begin predecode at I$ fill time. That helps enough to overcome the increased code size? I really wouldn't say they learned nothing from x86, though. You only have to look at 2 bits, and if you can get your users to put in the slightest effort then compilers can be told not to use C.

That's a false strawman. There are infinitely many ways to achieve the same or better density without the drawback. Allowing instruction to span cache line, or even pages, is a mistake that we'll pay for forever. The simplest possible mitigation would have been to disallow an instruction from spanning a 64-byte boundary. It would have almost no impact on instruction density, but it would have saved a lot of headaches…

Strawman? I wasn't even trying to characterize anyone else's point, I was just trying to list some significant improvements over x86.

> The simplest possible mitigation would have been to disallow an instruction from spanning a 64-byte boundary.

Sure, that sounds good. But before this you hadn't even mentioned any problems with split instructions that need to be mitigated.

(You did mention decoding without a known entry point, but a rule like that doesn't guarantee you can find the start of an instruction. And if it would help to know that a block of 64 bytes probably starts with an aligned instruction, that seems like something you could work out with compiler writers even without a spec.)

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#68

Post by FullyFunctional »

gautamcgoel wrote: post #64
FullyFunctional wrote: post #46

Earlier quoted context omitted.

My day job for 6+ years is implementing high perf RISC-V cores and my name is in many of the RISC-V specs. Variable length ISAs are characterized by not being able to tell the beginning of an instruction without knowing the entrypoint. This applies to RISC-V with compressed instructions. Finding the boundaries is akin to a prefix scan and has a cost roughly linear in the scan length, but IMO the biggest loss is that…

It sounds like you regret the decision to make RISC-V variable length. Is that correct?

I fought against making the _current_ way to do compressed instructions a mandated part of the Unix profile, but RISC-V was (at least at the time) dominated by microcontroller people and there was a lack of appreciation of the damage it incurred. A lot of people far more senior than me couldn't believe what happened.

Interesting to contrast with Arm which upon defining Aarch64 did _away_ with variable length instructions and thus also page crossing ones. Maybe they knew something.

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#69

Post by FullyFunctional »

Dylan16807 wrote: post #67
FullyFunctional wrote: post #63

Earlier quoted context omitted.

That's a false strawman. There are infinitely many ways to achieve the same or better density without the drawback. Allowing instruction to span cache line, or even pages, is a mistake that we'll pay for forever. The simplest possible mitigation would have been to disallow an instruction from spanning a 64-byte boundary. It would have almost no impact on instruction density, but it would have saved a lot of headaches…

Strawman? I wasn't even trying to characterize anyone else's point, I was just trying to list some significant improvements over x86. > The simplest possible mitigation would have been to disallow an instruction from spanning a 64-byte boundary. Sure, that sounds good. But before this you hadn't even mentioned any problems with split instructions that need to be mitigated. (You did mention decoding without a known en…

I did forget to mention the requirement that you can't branch into the middle of an instruction. If you have both of these constraints then you can unambiguously determine the location of all instructions in any aligned 64-byte block, including at I$ fill time.

Implementing this would require instruction fetch to take an exception on line-crossing instructions (which must be illegal) and a change to the assembler to insert a 16-bit padding nop or expand a compressed instruction to maintain the alignment. There is nothing needed from the compiler (or linker AFAICT). JITs will have to be aware though.

Re: QOI – The “Quite OK Image Format” for fast, lossless image compression

#70

Post by seoaeu »

rndgermandude wrote: post #61
FullyFunctional wrote: post #35

Earlier quoted context omitted.

Good question. The answer is all the poor souls that N years later find themselves stuck with a data in a legacy format that they have to struggle to decode faster. Of all the artifacts in our industry, few things live longer than formats. Eg. we are still unpacking tar files (Tape ARchieve), transmitted over IPv4, decoded by machines running x86 processors (and others, sure). All of these formats couldn't possible a…

Those poor souls N years later will either have to decode a very few images, which is still fast enough, or decode a lot of images, which can be parallelized and run concurrently on a per-image level. In the very worst case, decode an extremely large single image, you're a bit out of luck, but that case would be rare, and you're still pretty fast at decoding anyway. Creating formats and specs that are "future proof"…

> Criticizing QOI for not being able to be well parallelized inside the decode function, that seems more like a demand for a premature optimization to me

What? Faster encoding and decoding is one of the primary reasons for the format. Yet, QOI decoders are currently an order of magnitude slower than SSDs available today and even worse compared to DRAM! Now seems like the perfect time to look at possible optimizations to close that gap.

Post reply on HN