HTTP2: Huffman decoding implementation is inefficient

[geoffkizer]

We are currently implementing Huffman decoding by looping over a table with a list of encoded values for each length. (See Huffman.cs)

This doesn't seem particularly efficient.

Instead, we should implement Huffman decoding by doing table lookups, using keys of 8 bits or something along those lines.

Note that Huffman encoding from servers seems to be pretty common, so this may have real-world perf impact. (Or maybe not... as always, measuring is the best way to know.)

[jbhensley]

What were your thoughts regarding how this might work? I took a look at the code, but it wasn't immediately apparent that the current implementation could be improved much. Here are my observations:

• By definition, the most frequently used characters are encoded using the smallest number of bits, so the loop should terminate the majority of the time with a low iteration count given that the table is ordered by length.
• Each entry in the decoding table is a different bit length, so it's not possible to turn this into some kind of hash table. You probably could, but keying into it would require extracting the first 5 bits from the value you are decoding and then checking the table followed by extracting the first 6 bits and checking, etc. which is no different than the loop. Also, not all bit lengths exist (9, 16, 17, 18, 19 & 29) so you would want to skip trying to check for values using those, which the current loop does nicely since it uses a table of bit lengths.
• The other hash table option would be to generate a massive "rainbow table" like structure where all combinations of bits beyond the significant ones up to your key length are also hashed. In that case, a single 5 bit entry in the existing table would include hashed entries for every possible combination of extra bits out to, say, the max of 30. No more looping through bit lengths to key into the table, but the size would be enormous. Note that I'm assuming all combinations would be unique, but I haven't given this much thought since it's obviously a non-starter.

The only thing I saw in the code that I thought could be improved was the repeated calculation of codeMax even though that value is essentially a constant for each entry in the decoding table. Expanding the table to be a 3-tuple that included codeMax would avoid that, but the cost there is likely very insignificant.

Mind you, I'm new to the code so I could be way off base here. Looking to see if you could clarify this a bit.

[danmoseley]

@geoffkizer thoughts?

[4creators]

IMHO one of the best implementations of Huffman en/decoder is available here: https://github.com/Cyan4973/FiniteStateEntropy

Its written in C but it should be one of the best examples of Huffman implementations. It is in library together with Finite State Entropy en/decoder written using Asymmetric Numeral Systems (Huffman is special case of ASN). ASN is a separate story and I plan to submit API proposal to include zstd compression in .NET Core and will write more than..

[geoffkizer]

The other hash table option would be to generate a massive "rainbow table" like structure where all combinations of bits beyond the significant ones up to your key length are also hashed.

It doesn't need to be a single, massive hash table. It can be a multi-level table. Take the first 8 bits (or 10, or whatever) and use it as the key to the first-level table. This results in either a decoded value and a bit length, or a reference to a second-level table -- if so, take the next 8 bits and index into the second table, etc.

Choosing the best key size for each table involves a tradeoff -- smaller key sizes mean smaller tables but more lookups, and vice-versa. You can tune this as appropriate. With 8 bits, your main table is only 512 bytes (256 entries, 1 byte for decoded value, 1 byte for either bit length or next table id), and the most common values (including all alphanumerics) will be decoded in a single table lookup.

[jbhensley]

I explored that approach briefly as well, but it just seemed like we were back to looping again. A mock up to see if there is any real perf differential would be the way to go here. I might be able to take a crack at that next week.

[geoffkizer]

There's no looping if the value is encoded in 8 bits or less. (Or whatever key size you choose.) And this covers the most common values, including all alphanumerics and common punctuation.

[jbhensley]

Agreed, encoded values up to the chosen key size would be found immediately. Couple more questions:

• Is there a compiled list of common request headers you guys have that can be used for perf testing? If not, I can put together my own.
• What would be the preference for constructing the hash table in a production environment? Just use a collection initializer so the object is always ready or construct on first use? I assume we'd want to sync lock in the cause of COFU?

[geoffkizer]

Is there a compiled list of common request headers you guys have that can be used for perf testing? If not, I can put together my own.

Not really.

I think a collection initializer is fine. If necessary, it's easy to switch this to a Lazy<T> later.

[grant-d]

The codeMax optimization THAT @jbhensley suggested has an immediate ~10% benefit in micro benchmark testing:

 Method |     Mean |    Error |   StdDev | Scaled | ScaledSD |
------- |---------:|---------:|---------:|-------:|---------:|
    New | 86.32 ns | 1.864 ns | 1.915 ns |   0.89 |     0.05 |
   Core | 97.49 ns | 1.950 ns | 5.069 ns |   1.00 |     0.00 |

Here's the core change, note the manually-computed additional deltaLength member:

private static readonly (int codeLength, int deltaLength, int[] codes)[] s_decodingTable = new[]
{
    (05, 0, new[] { 48, 49, 50, 97, 99, 101, 105, 111, 115, 116 }), // deltaLength must be 0 for related optimizations to work
    (06, 1, new[] { 32, 37, 45, 46, 47, 51, 52, 53, 54, 55, 56, 57, 61, 65, 95, 98, 100, 102, 103, 104, 108, 109, 110, 112, 114, 117 }),
    (07, 1, new[] { 58, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 106, 107, 113, 118, 119, 120, 121, 122 }),
    (08, 1, new[] { 38, 42, 44, 59, 88, 90 }),
    (10, 2, new[] { 33, 34, 40, 41, 63 }),
    (11, 1, new[] { 39, 43, 124 }),
    (12, 1, new[] { 35, 62 }),
    (13, 1, new[] { 0, 36, 64, 91, 93, 126 }),
    (14, 1, new[] { 94, 125 }),
    (15, 1, new[] { 60, 96, 123 }),
    (19, 4, new[] { 92, 195, 208 }),
    (20, 1, new[] { 128, 130, 131, 162, 184, 194, 224, 226 }),
    (21, 1, new[] { 153, 161, 167, 172, 176, 177, 179, 209, 216, 217, 227, 229, 230 }),
    (22, 1, new[] { 129, 132, 133, 134, 136, 146, 154, 156, 160, 163, 164, 169, 170, 173, 178, 181, 185, 186, 187, 189, 190, 196, 198, 228, 232, 233 }),
    (23, 1, new[] { 1, 135, 137, 138, 139, 140, 141, 143, 147, 149, 150, 151, 152, 155, 157, 158, 165, 166, 168, 174, 175, 180, 182, 183, 188, 191, 197, 231, 239 }),
    (24, 1, new[] { 9, 142, 144, 145, 148, 159, 171, 206, 215, 225, 236, 237 }),
    (25, 1, new[] { 199, 207, 234, 235 }),
    (26, 1, new[] { 192, 193, 200, 201, 202, 205, 210, 213, 218, 219, 238, 240, 242, 243, 255 }),
    (27, 1, new[] { 203, 204, 211, 212, 214, 221, 222, 223, 241, 244, 245, 246, 247, 248, 250, 251, 252, 253, 254 }),
    (28, 1, new[] { 2, 3, 4, 5, 6, 7, 8, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 127, 220, 249 }),
    (30, 2, new[] { 10, 13, 22, 256 })
};

[geoffkizer]

@grant-d What code are you using to test this?

[grant-d]

Code optimization, without changing the algorithm, gets us to ~23% improvement in the micro-bench.
(This needs real-world testing to get a measure of any true improvement)

    Method |     Mean |     Error |    StdDev | Scaled | ScaledSD | Allocated |
---------- |---------:|----------:|----------:|-------:|---------:|----------:|
 Optimized | 71.61 ns | 0.8184 ns | 0.7656 ns |   0.77 |     0.02 |       0 B |
    Legacy | 93.17 ns | 1.7961 ns | 2.3977 ns |   1.00 |     0.00 |       0 B |

For example, changed this:

            for (var i = 0; i < s_decodingTable.Length && s_decodingTable[i].codeLength <= validBits; i++)
            {
                (var codeLength, var codes) = s_decodingTable[i];

                if (i > 0)
                {
                    codeMax <<= codeLength - s_decodingTable[i - 1].codeLength;
                }

                codeMax += codes.Length;

To this:

            for (var i = 0; i < s_decodingTable.Length; i++)
            {
                // deltaLength is precomputed codeMax delta
                var (codeLength, deltaLength, codes) = s_decodingTable[i];

                // Move check out of for-loop to leverage cached value for codeLength
                if (codeLength > validBits)
                    break;

                // Mitigate the if (i > 0) branch by ensuring s_decodingTable[0].deltaLength==0
                codeMax = (codeMax << deltaLength) + codes.Length;

[grant-d]

@geoffkizer see HuffmanBench.cs and related units in this PR

[grant-d]

Another example.
This:

                var next = (uint)(src[i] << 24 + lastDecodedBits);
                next |= (i + 1 < src.Length ? (uint)(src[i + 1] << 16 + lastDecodedBits) : 0);
                next |= (i + 2 < src.Length ? (uint)(src[i + 2] << 8 + lastDecodedBits) : 0);
                next |= (i + 3 < src.Length ? (uint)(src[i + 3] << lastDecodedBits) : 0)

Can be optimized as follows, since if the first src.Length branch is false, then there's no way the 2nd & 3rd branches can be true:

                var next = (uint)(src[i] << 24 + lastDecodedBits);
                if (i + 1 < src.Length)
                {
                    next |= (uint)(src[i + 1] << 16 + lastDecodedBits);

                    if (i + 2 < src.Length)
                    {
                        next |= (uint)(src[i + 2] << 8 + lastDecodedBits);

                        if (i + 3 < src.Length)
                            next |= (uint)(src[i + 3] << lastDecodedBits);
                    }
                }

[jbhensley]

I have code for using the multi-level table and am currently working on cleaning it up a bit and testing. Decoding becomes simple:

public static int Decode(uint data, int validBits, out int decodedBits)
{
	int byteNumber = 3;                      // grab the most significant byte
	uint virtualDictionaryMask = 0;          // used to key into different "virtual" dictionaries
	DecodingTableEntry entry;
	do
	{
		// extract the working byte
		uint workingByte = data >> (byteNumber * 8) & 0xFF;

		// apply virtual dictionary bitmask
		workingByte |= virtualDictionaryMask;

		// key into the dictionary
		if (!s_decodingDictionary.TryGetValue(workingByte, out entry))
			break;  // we should either get an entry or bitmask for the next virtual dictionary. if we get neither then
				// the bit pattern is not consistent with any entry we have

		// if we get a length back then we have found the decoded value
		if (entry.BitLength > 0)
		{   
			if (entry.BitLength > validBits)
				break;  // we only found a value by incorporating bits beyond the the valid remaining length of the data stream

			decodedBits = entry.BitLength;
			return (int)entry.DecodedValue;
		}
		// otherwise, we have found a mask that lets us key into the next virtual dictionary
		else
		{
			virtualDictionaryMask = entry.DecodedValue;
			byteNumber--;
		}

	} while (entry.BitLength == 0);

	// no luck. signal to caller that we could not decode
	decodedBits = 0;
	return -1;
}

Building the table is a bit ugly and will likely need to be done with a Lazy<T> that calls a method to construct it since the total size is 3840 entries. We could still use a collection initializer and surround it with a #region I suppose. Either way, I'm a little concerned about the memory footprint.

Since there would be 15 tables in total, I took the approach of using bitmasks on the key value of a single table to create several "virtual" ones within it. The "root" table has no mask, so you initially key in with the value you want to decode. If you get a bit length back then you have the decoded value. Otherwise, you have a bitmask to apply to your next byte when keying in again. The bitmask represents the next "vitual" table.

[geoffkizer]

You have more total entries (3840) than necessary.

The fourth-level tables only need 6 bits to index them (max encoded length is 30 bits). That by itself cuts the total number of entries in half, if my math is correct.

Additionally, at least some intermediate tables don't need all 8 bits either. For example, all encodings that start with 11111110 are exactly 10 bits in length, so the second level table here can be exactly 4 entries instead of the 256 you'd need if you indexed with a full 8 bits.

Dealing with all this will complicate the code and isn't necessary to get decent perf results.