Zstandard Compression

[sudoBash418]

I imagine I'm not the first one to look into this, but I haven't seen another post about this yet so I may as well throw the idea onto the playing field. Apologizes if this is the wrong place for this :sweat_smile:

On screenshots, I got anywhere from 15% to sometimes 50% on zstd levels 1-3, generally outperforming even fairly well-optimized PNGs in compression ratio. For other image types it seems to be around 10-15%.

Here's a more thorough comparison of the en.wikipedia.org.png screenshot from the original "test bench":

Compression	Size	Ratio
original file	1,316,655	1.000
oxipng -D -o3	1,046,134	0.794
qoi	1,498,761	1.138
qoi + zstd -1	955,221	0.725
qoi + zstd -3	809,694	0.615

Tested with the master branch of QOI (2ee2169), zstd v1.5.0, and oxipng 5.0.1.

Haven't done a complete comparison across the entire test bench yet; if there's interest I might get around to it though.

[chocolate42]

It's interesting that qoi is a pure pixel engine especially as it only touches input once so can be easily streamed. Being modular allows for all the niceties of the existing ecosystem like being wrapped in a tarball for archival or compressed with whatever generic streaming compressor you like (compare that to PNG which chose a fixed compressor, a mediocre one even at the time).

When all is said and done I think it would be ideal if .qoi rivalled libpng on filesize with much faster encode/decode, .qoi.zstd (with some fast setting) rivalled optimised PNG's for filesize, and .qoi.xz (with some slow setting) rivalled JpegXL for lossless filesize. Zstd fast is important to bench when optimising for access times (amusingly, compressing with zstd fast may be quicker than a raw qoi file depending on storage medium), xz slow is important when optimising for archival.

Which is a rambling way of saying yes I am very interested in compressed benchmarks. You might want to hold off on doing so until the format has been finalised (or create the benchmark in such a way that it's easy to run again if the spec changes).

[nigeltao]

https://github.com/phoboslab/qoi/issues/71#issuecomment-991884414 has some numbers on wrapping with LZ4 instead of Zstd, on the entire test suite. LZ4 seems closer in spirit to QOI (byte-aligned ops, relatively simple format, emphasize speed over compression ratios, etc).

[nigeltao]

Apologizes if this is the wrong place for this

This is the right place!

[sudoBash418]

phoboslab/qoi#71 (comment) has some numbers on wrapping with LZ4 instead of Zstd, on the entire test suite. LZ4 seems closer in spirit to QOI (byte-aligned ops, relatively simple format, emphasize speed over compression ratios, etc).

I tested LZ4 once or twice on a couple images but gave up because I thought that zstd had it beat no matter what speed/size you aim for, but I'll add it to my comparison. Looking at the numbers from zstd's own author, it seems that lz4 wins in at least decompression time, so its benefits likely will not be revealed by my script.

It's interesting that qoi is a pure pixel engine especially as it only touches input once so can be easily streamed. Being modular allows for all the niceties of the existing ecosystem like being wrapped in a tarball for archival or compressed with whatever generic streaming compressor you like (compare that to PNG which chose a fixed compressor, a mediocre one even at the time).

When all is said and done I think it would be ideal if .qoi rivalled libpng on filesize with much faster encode/decode, .qoi.zstd (with some fast setting) rivalled optimised PNG's for filesize, and .qoi.xz (with some slow setting) rivalled JpegXL for lossless filesize. Zstd fast is important to bench when optimising for access times (amusingly, compressing with zstd fast may be quicker than a raw qoi file depending on storage medium), xz slow is important when optimising for archival.

Yeah I agree, and that reminds me that I should add LZMA to the test as well, in one form or another.

Which is a rambling way of saying yes I am very interested in compressed benchmarks. You might want to hold off on doing so until the format has been finalised (or create the benchmark in such a way that it's easy to run again if the spec changes).

I'm going to try writing a shell script for testing all this; it'll be filesizes-only however because getting accurate numbers for speed is a much more difficult task.

[sudoBash418]

Here are my results, using qoiconv from phoboslab/qoi@2ee2169 (master). Compressors are sorted by total filesize, descending.

Compression Results (kB)

| | TOTAL | icon_512 | icon_64 | photo_kodak | photo_tecnick | photo_wikipedia | pngimg | screenshot_game | screenshot_web | textures_photo | textures_pk | textures_pk01 | textures_pk02 | textures_plants | |-------------|---------|----------|---------|-------------|---------------|-----------------|--------|-----------------|----------------|----------------|-------------|---------------|---------------|-----------------| | plain | 1351894 | 18658 | 1002 | 16502 | 258843 | 105507 | 274221 | 328421 | 37984 | 40590 | 77559 | 20646 | 115290 | 56671 | | lz4fast12 | 1312141 | 14902 | 990 | 16495 | 258744 | 105508 | 262631 | 308866 | 34795 | 40590 | 77163 | 20066 | 114830 | 56561 | | lz4fast5 | 1299434 | 13635 | 963 | 16487 | 258681 | 105508 | 260110 | 303348 | 33330 | 40572 | 76492 | 19828 | 114042 | 56438 | | lz4fast3 | 1292847 | 13043 | 946 | 16483 | 258654 | 105508 | 258928 | 300492 | 32586 | 40549 | 76084 | 19696 | 113524 | 56354 | | zstdfast5 | 1284166 | 12005 | 949 | 16500 | 258628 | 105496 | 257074 | 297238 | 31723 | 40591 | 74793 | 19458 | 113357 | 56354 | | lz4fast1 | 1283038 | 12346 | 917 | 16477 | 258613 | 105500 | 257277 | 296477 | 31586 | 40495 | 74993 | 19520 | 112615 | 56222 | | zstdfast3 | 1276492 | 11326 | 920 | 16498 | 258583 | 105489 | 255692 | 294090 | 30888 | 40591 | 73992 | 19303 | 112864 | 56256 | | lz4_1 | 1275580 | 11887 | 894 | 16471 | 258572 | 105481 | 256090 | 293549 | 30855 | 40426 | 73915 | 19397 | 111914 | 56129 | | zstdfast1 | 1266374 | 10649 | 880 | 16491 | 258521 | 105476 | 254095 | 290440 | 30077 | 40571 | 71979 | 19134 | 111975 | 56086 | | lz4_3 | 1205685 | 10281 | 873 | 15611 | 254795 | 103816 | 241933 | 271855 | 27532 | 36699 | 66498 | 18461 | 103959 | 53372 | | lz4_5 | 1202112 | 10178 | 872 | 15581 | 254577 | 103745 | 241258 | 270580 | 27399 | 36506 | 66157 | 18396 | 103599 | 53264 | | lz4_9 | 1201317 | 10143 | 871 | 15580 | 254552 | 103743 | 241145 | 270312 | 27373 | 36479 | 65936 | 18375 | 103560 | 53248 | | zstd1 | 1100532 | 10059 | 796 | 14216 | 225918 | 92452 | 220777 | 252941 | 26873 | 31394 | 65662 | 16869 | 94487 | 48088 | | zstd3 | 1074274 | 9473 | 763 | 14052 | 225600 | 92230 | 215909 | 243789 | 24851 | 31249 | 60772 | 16476 | 91715 | 47395 | | zstd9 | 1052353 | 8704 | 756 | 13848 | 224181 | 91546 | 210475 | 238618 | 23610 | 30531 | 58062 | 16134 | 89201 | 46687 | | xz1 | 1019691 | 8011 | 727 | 13270 | 220192 | 89650 | 202900 | 228139 | 22883 | 30471 | 56269 | 15524 | 86384 | 45271 | | zstd19 | 1017895 | 8225 | 740 | 13298 | 220685 | 89924 | 200601 | 229915 | 22427 | 29472 | 55717 | 15745 | 85869 | 45277 | | zstdultra22 | 1017813 | 8222 | 740 | 13298 | 220685 | 89924 | 200531 | 229908 | 22426 | 29472 | 55717 | 15745 | 85869 | 45276 | | xz3 | 1016294 | 7956 | 726 | 13265 | 219986 | 89605 | 201633 | 227615 | 22398 | 30325 | 55971 | 15496 | 86109 | 45209 | | 7z9 | 979018 | 7523 | 739 | 12911 | 213357 | 86717 | 193025 | 219147 | 21348 | 28969 | 54258 | 14976 | 82347 | 43701 | | xz6 | 978992 | 7502 | 718 | 12910 | 213359 | 86721 | 193193 | 219085 | 21347 | 28968 | 54190 | 14968 | 82333 | 43698 | | xz9 | 978811 | 7502 | 718 | 12910 | 213359 | 86721 | 193012 | 219085 | 21347 | 28968 | 54190 | 14968 | 82333 | 43698 |

Compression Results (%)

| | TOTAL | icon_512 | icon_64 | photo_kodak | photo_tecnick | photo_wikipedia | pngimg | screenshot_game | screenshot_web | textures_photo | textures_pk | textures_pk01 | textures_pk02 | textures_plants | |-------------:|-------|----------|---------|-------------|---------------|-----------------|--------|-----------------|----------------|----------------|-------------|---------------|---------------|-----------------| | plain | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | | lz4fast12 | 97.06 | 79.87 | 98.84 | 99.96 | 99.96 | 100.0 | 95.77 | 94.05 | 91.6 | 100.0 | 99.49 | 97.19 | 99.6 | 99.81 | | lz4fast5 | 96.12 | 73.08 | 96.15 | 99.91 | 99.94 | 100.0 | 94.85 | 92.37 | 87.75 | 99.96 | 98.62 | 96.03 | 98.92 | 99.59 | | lz4fast3 | 95.63 | 69.9 | 94.42 | 99.89 | 99.93 | 100.0 | 94.42 | 91.5 | 85.79 | 99.9 | 98.1 | 95.4 | 98.47 | 99.44 | | zstdfast5 | 94.99 | 64.34 | 94.77 | 99.99 | 99.92 | 99.99 | 93.75 | 90.51 | 83.52 | 100.0 | 96.43 | 94.25 | 98.32 | 99.44 | | lz4fast1 | 94.91 | 66.17 | 91.59 | 99.85 | 99.91 | 99.99 | 93.82 | 90.27 | 83.15 | 99.77 | 96.69 | 94.55 | 97.68 | 99.21 | | zstdfast3 | 94.42 | 60.7 | 91.89 | 99.98 | 99.9 | 99.98 | 93.24 | 89.55 | 81.32 | 100.0 | 95.4 | 93.5 | 97.9 | 99.27 | | lz4_1 | 94.36 | 63.71 | 89.24 | 99.82 | 99.9 | 99.98 | 93.39 | 89.38 | 81.23 | 99.6 | 95.3 | 93.95 | 97.07 | 99.04 | | zstdfast1 | 93.67 | 57.08 | 87.88 | 99.94 | 99.88 | 99.97 | 92.66 | 88.44 | 79.18 | 99.95 | 92.81 | 92.67 | 97.12 | 98.97 | | lz4_3 | 89.18 | 55.1 | 87.14 | 94.6 | 98.44 | 98.4 | 88.23 | 82.78 | 72.48 | 90.42 | 85.74 | 89.42 | 90.17 | 94.18 | | lz4_5 | 88.92 | 54.55 | 87.05 | 94.42 | 98.35 | 98.33 | 87.98 | 82.39 | 72.13 | 89.94 | 85.3 | 89.1 | 89.86 | 93.99 | | lz4_9 | 88.86 | 54.36 | 86.95 | 94.42 | 98.34 | 98.33 | 87.94 | 82.31 | 72.06 | 89.87 | 85.01 | 89.0 | 89.83 | 93.96 | | zstd1 | 81.41 | 53.91 | 79.48 | 86.15 | 87.28 | 87.63 | 80.51 | 77.02 | 70.75 | 77.34 | 84.66 | 81.7 | 81.96 | 84.86 | | zstd3 | 79.46 | 50.77 | 76.17 | 85.16 | 87.16 | 87.42 | 78.74 | 74.23 | 65.42 | 76.99 | 78.36 | 79.8 | 79.55 | 83.63 | | zstd9 | 77.84 | 46.65 | 75.46 | 83.92 | 86.61 | 86.77 | 76.75 | 72.66 | 62.16 | 75.22 | 74.86 | 78.15 | 77.37 | 82.38 | | xz1 | 75.43 | 42.94 | 72.6 | 80.42 | 85.07 | 84.97 | 73.99 | 69.47 | 60.24 | 75.07 | 72.55 | 75.19 | 74.93 | 79.88 | | zstd19 | 75.29 | 44.08 | 73.91 | 80.59 | 85.26 | 85.23 | 73.15 | 70.01 | 59.04 | 72.61 | 71.84 | 76.26 | 74.48 | 79.89 | | zstdultra22 | 75.29 | 44.07 | 73.91 | 80.59 | 85.26 | 85.23 | 73.13 | 70.0 | 59.04 | 72.61 | 71.84 | 76.26 | 74.48 | 79.89 | | xz3 | 75.18 | 42.64 | 72.52 | 80.39 | 84.99 | 84.93 | 73.53 | 69.31 | 58.97 | 74.71 | 72.17 | 75.05 | 74.69 | 79.77 | | 7z9 | 72.42 | 40.32 | 73.77 | 78.24 | 82.43 | 82.19 | 70.39 | 66.73 | 56.2 | 71.37 | 69.96 | 72.53 | 71.43 | 77.11 | | xz6 | 72.42 | 40.21 | 71.7 | 78.24 | 82.43 | 82.19 | 70.45 | 66.71 | 56.2 | 71.37 | 69.87 | 72.5 | 71.41 | 77.11 | | xz9 | 72.4 | 40.21 | 71.7 | 78.24 | 82.43 | 82.19 | 70.39 | 66.71 | 56.2 | 71.37 | 69.87 | 72.5 | 71.41 | 77.11 |

Commpressor Details

| Name | Command Line | |--|--| | zstdfast# | `zstd --fast=#` | | zstd# | `zstd -#` | | zstd19 | `zstd -19 -T0` | | zstdultra22 | `zstd -22 --ultra -T0` | | xz# | `xz -# -c -T0` | | 7z9 | `7z a -mx9` | #### Versions ``` zstd: v1.5.0 xz: (XZ Utils) 5.2.5 7z: p7zip Version 17.04 ```

---

Some quick notes:

• For photos, zstd --fast seems to be useless, zstd -1 is where compression starts to take effect
• 7z was worse than useless, probably due to overhead of the 7z format on small files
• zstd --ultra -22 is nearly equivalent to zstd -19
• Similarly, xz -9 is nearly equivalent to xz -6
• zstd -19 beats out xz -1 in filesize

[chocolate42]

I ran the test suite through zopflipng which appears to have better compression than oxipng (even oxipng -o 6 -Z, where Z is zopflipng). It took ~30 core hours with option -m, there are more exhaustive options but it would have taken an age for minimal gains. Sorry if you're in the process of crunching PNGs, I set it running overnight on a whim. kB=1000

zopflipng -m
images/icon_512:      8598
images/icon_64:            723
images/photo_kodak:  14715
images/photo_tecnick:   209470
images/photo_wikipedia:  87123
images/pngimg:          208908
images/screenshot_game: 227834
images/screenshot_web:   26516
images/textures_photo:   31315
images/textures_pk:  41078
images/textures_pk01:    14504
images/textures_pk02:    80261
images/textures_plants:  47995
totals:                 999046

So qoi + the top compressors already beat the top optimised PNGs. Arguably the PNGs could be crunched slightly further, but then so can qoi if we go off the deep end and start using experimental state of the art compressors like cmix.

@sudoBash418 Let me know if you're going to generate lossless JpegXL data. If not I can crunch those numbers.

LZ4 seems closer in spirit to QOI (byte-aligned ops, relatively simple format, emphasize speed over compression ratios, etc).

LZ4 is too quick IMO unless only dealing with in-memory operations (which is a category I hadn't considered). zstd -1 nearly saturates the bandwidth of a typical consumer SSD with a single (modern) CPU core, so it's a better fit for quickly loading assets for example. So rather than replacing zstd -1 with LZ4 it might be best to have three main data points: LZ4, zstd -1, xz -6.

[sudoBash418]

So qoi + the top compressors already beat the top optimised PNGs. Arguably the PNGs could be crunched slightly further, but then so can qoi if we go off the deep end and start using experimental state of the art compressors like cmix.

@sudoBash418 Let me know if you're going to generate lossless JpegXL data. If not I can crunch those numbers.

I wasn't planning on it; go for it. I might do a more quick-and-dirty test of "uncompressed PNG" compressed with zstd/xz just to see what happens.

LZ4 seems closer in spirit to QOI (byte-aligned ops, relatively simple format, emphasize speed over compression ratios, etc).

LZ4 is too quick IMO unless only dealing with in-memory operations (which is a category I hadn't considered). zstd -1 nearly saturates the bandwidth of a typical consumer SSD with a single (modern) CPU core, so it's a better fit for quickly loading assets for example. So rather than replacing zstd -1 with LZ4 it might be best to have three main data points: LZ4, zstd -1, xz -6.

I would be inclined to agree, but I haven't run the numbers yet so I'm not certain about what the performance would look like. One thing to note about zstd (and probably lz4, but I'm not certain) is that decompression speed and memory requirements generally stay the same even up to -19, which can be very useful in "compress once, decompress many" cases (such as game assets or static web files).

[chocolate42]

Great point about using -19 instead of -1, that makes a lot more sense for that use case.

[chocolate42]

JPEG XL encoder v0.7.0 335f8a8 [AVX2,SSE4,SSSE3,Scalar] cjxl -e 9 -q 100

kB=1000
images/icon_512:           4934
images/icon_64:             536
images/photo_kodak:       10169
images/photo_tecnick:    151300
images/photo_wikipedia:   65934
images/pngimg:           135264
images/screenshot_game:  163189
images/screenshot_web:    15254
images/textures_photo:    19797
images/textures_pk:       38466
images/textures_pk01:     12085
images/textures_pk02:     63698
images/textures_plants:   29439
totals:                  710071

Lossless JpegXL lives up to the hype.

[magnus-ISU]

While this is indeed very cool, would the specification actually require anything different?

EDIT: unless by writing a parser that does both at once, you can get more efficient code or something? I can definitely see that happening actually

[nigeltao]

Putting compression into the qoi2 format (and specifically leaving the magic identifier and the rest of the header uncompressed), instead of flinging around foo.qoi2.xz files around, makes it easier to tell (e.g. as part of the /usr/bin/file command) that a foo.dat file is an image (and specifically a qoi2 image of a certain width and height), instead of only knowing that it's "xz compressed data".

[chocolate42]

There is some benefit to integrating entropy coding but it's a fair bit of complexity to do it. Refactoring the encode/decode functions to allow streaming would let either method be just as efficient. As long as it's optional it's fine, the worst thing we could do is enforce a particular entropy-coder which doesn't suit all use cases and quickly dates the format. If integrated entropy coding exists I think it should accept these codecs which should cover most use cases with a "none" escape hatch: None, lz4, zstd, xz/lzma.

The zstd reference implementation appears to be able to output all three, haven't had a chance to try it out yet.

edit: It's the benchmark tool in the zstd repo that can handle all three not the implementation, which makes more sense. Looks about as easy as lz4 to integrate, zstd dev files are even in major Linux repo's so it should be as easy as lz4 at least on Linux.

[nigeltao]

I haven't fully digested it yet, but @richgel999 recently blogged about LZ_ADD / LZ_XOR compression which might inspire some ideas for interesting QOI2 experiments.

[wbd73]

What I don't like about compression is that something like a lz4 encoder might not be available for all programming languages.

[oscardssmith]

It exists for C, python, C#, Java, and javascript, Rust, and Go (and a ton more). Is there a specific language you're worried about?

[chocolate42]

... might not be available for all programming languages.

If something exists for C it can exist for pretty much anything through C bindings. LZ4 is such a fundamental and long-lived algorithm that it's definitely everywhere and has been for decades. Same goes for LZMA and even ZSTD (which is newer but already used in a lot of fundamental things like package managers and the Linux kernel).

[wbd73]

I should have read a bit more about it. Now I've read a bit more about it I see it's not really an issue.