Optimizations for reading multiple literals at once

[Shnatsel]

fdeflate uses 12-bit indices to get multiple literals from a single table lookup, improving performance. The technique is described here: image-rs/image#1852 (comment)

I'm curious if this optimization is applicable to zune-inflate. If not already done and not conflicting with other parts of the library, this could serve as a further optimization.

[etemesi254]

Aa the good old multiple literals technique, love it.

But it's not used.

Here are the disadvantages.

1. It's complicated to set up the tables to use multiple literals.

2. Adds an extra unpredictable path in the decoder, to answer the question, are we in a single literal or mult-literal pass.

3. Table sizes.

[Shnatsel]

Alright. Good to know that you've considered it!

[etemesi254]

Elaborating on above

1. Table building time is important for small/medium sizes.

2. Branch predictions hurt decoders, and the more code you run, the slower it is. The reason LZ4 is really fast is beause you can write the inner loop in so few lines of code, so the general rule of thumb is that if you write decompressor code, keep it as small as possible/ add edge cases away from the hot path.

3. Table sizes is the interesting part though.

there are two types of table based Huffman decoders,

1. Fast path for short codes, spend more cycles resolving the longer codes, using loops

I'm gonna use STB , so here's the fast path, https://github.com/nothings/stb/blob/5736b15f7ea0ffb08dd38af21067c314d6a3aae9/stb_image.h#L4249-L4255

And the slow path

https://github.com/nothings/stb/blob/5736b15f7ea0ffb08dd38af21067c314d6a3aae9/stb_image.h#L4221-L4238

Now this can have apply the optimization for multiple literals, in the fast path. It's possible to fill the fastpath tables with 2 literals if both literals consume less than TABLE_LEN bits, it's assumed that the table can hold 1<<TABLE_LEN entries.

Longer codes will take time, bit it's compression, we expect more shorter codes than longer ones, otherwise it won't work.

2. Subtables-(what we use)
   Huffman codes have a unique prefix to them, so for us when we meet a long code, we add a flag to our table entry indicating this code is too big, to complete it load this value again from the main table and combine it with the short table.

So the main table has sub-tables, and we allocate and partition it into sub tables.

Long codes get two table lookups and short codes only get one, but this doesn't allow us to have space for multi-entries, since the whole space is used.

Here is where we use it,

zune-image/zune-inflate/src/decoder.rs

Lines 1132 to 1140 in 83c11db

	if (entry & HUFFDEC_EXCEPTIONAL) != 0
	{
	// offset requires a subtable
	self.stream.drop_bits(OFFSET_TABLEBITS as u8);
	let extra = self.stream.peek_var_bits(((entry >> 8) & 0x3F) as usize);
	entry = offset_decode_table[((entry >> 16) as usize + extra) & 511];
	}

PS this may be information overload, it was for me, so here are some links that helped me https://cbloomrants.blogspot.com/search?q=huffman+codes

Feel free to ask for any clarifications

[fintelia]

I now have more precise data. When decoding the QOI Bench corpus of PNGs, two byte entries are used 65.9% of the time when looking up a literal. That includes 12.4% of lookups which specify both two data bytes and 1-10 additional zero bytes. The full table:

1: 34.135%
2: 53.424%
3: 7.654%
4: 3.386%
5: 1.270%
6: 0.067%
7: 0.0096%
8: 0.0076%
9: 0.0049%
10: 0.0065%
11: 0.0023%
12: 0.030%

[etemesi254]

That's is then one solid optimization.

Would such things be translated to something like a full inflate implementation?

[fintelia]

I'm actually in the process of turning fdeflate into a full inflate implementation (deflate would still remain constrained). The measurements above are for the corpus of PNGs with their original compression settings including backreferences and non-zero RLE. Some of them were encoded with questionable compression settings, but hopefully that's just a representation of real-world PNGs.

In the sample, approximately 5% of literal/length codes in the deflate streams were lengths (about 8% after merging consecutive short literals).

[etemesi254]

Does this mean it would have two special paths for decoding? One where you detect if file has the special details you have and use the set shortcuts and one where you have the normal deflate path?

And curious if the double literal optimization would make it. Would love to tear it down in some tests, I suspect the reason it works soo well for png is due to the filtering separation before, but would love to see it on random normal gzip files.

[fintelia]

I still need to do more experimentation. The special details are mostly intended to improve encoding performance, so I don't think having a different mode for it would help when decoding. My guess is that the same decoding logic would work, it would just "happen" to never hit the slow paths for handling symbols longer than 12 bits, or for handling non-rle back references.

And yes, filtered PNG image data is very different than random gzip files so the optimization tradeoffs are probably not the same