Category: Performance

LiteSpeed’s HPACK Huffman Encoder has been optimized: it now runs twice as fast as before. In this article, we present the Fast Huffman Encoder, share a few optimization tricks and pitfalls, and benchmark several Huffman encoder implementations.

Introduction

Huffman encoder is used both in HTTP/2 and HTTP/3 stacks (HPACK and QPACK compression, respectively). Speeding up this component thus leads to a double win.

In our previous blog post, we discussed how we sped up our Huffman decoder. The main idea was that we can process the input two, rather than one, bytes at a time. The same approach can be used to speed up the Huffman encoder.

Unlike the decoder, the encoder implementations by LiteSpeed, nginx, h2o, and nghttp2 do not share a common ancestor. For that reason, we will benchmark all of them.

Starting Line

Before optimization, the main encoder loop in our implementation looks like this:

    while (src != src_end)
    {
        cur_enc_code = encode_table[*src++];
        if (bits_used + cur_enc_code.bits < sizeof(bits) * 8)
        {
            bits <<= cur_enc_code.bits;
            bits |= cur_enc_code.code;
            bits_used += cur_enc_code.bits;
            continue;
        }
        else if (p_dst + sizeof(bits) <= dst_end)
        {
            bits <<= sizeof(bits) * 8 - bits_used;
            bits_used = cur_enc_code.bits - (sizeof(bits) * 8 - bits_used);
            bits |= cur_enc_code.code >> bits_used;
#if UINTPTR_MAX == 18446744073709551615ull
            *p_dst++ = bits >> 56;
            *p_dst++ = bits >> 48;
            *p_dst++ = bits >> 40;
            *p_dst++ = bits >> 32;
#endif
            *p_dst++ = bits >> 24;
            *p_dst++ = bits >> 16;
            *p_dst++ = bits >> 8;
            *p_dst++ = bits;
            bits = cur_enc_code.code;   /* OK not to clear high bits */
        }
        else
            return -1;
    }

Where an element of encode_table is as follows:

struct encode_el
{
    uint32_t code;
    int  	bits;
};

Each byte of input is used as an index into encode_table. The associated encoded bit string is added to the accumulator buffer bits, which is an 8-byte or 4-byte integer, depending on the platform. When bits is full, its bytes are written out and the accumulator is reset.

We want to reduce the number of branches. A useful metric is “number of conditionals per byte of input.” In this loop, we check whether

1. we’ve run out of input (for every input byte);
2. the accumulator buffer is full (for every input byte); and
3. we’ve run out of output (every 8 output bytes).

Estimating average compression ratio of 0.75, this translates to 2.1 branches per byte of input. Can we do better?

Big Table

Since there is no obvious way to reduce the number of conditionals in the processing loop, the next thing to do is to reduce the number of input units: that is, process two bytes at a time instead of one.

struct henc {
    unsigned lens;
    uint32_t code;
} hencs[] = {
    [0x0000] = { 26, 0x3FF1FF8 },
    [0x0001] = { 64, 0 },
    /* --- 8< -- snip --- 8< --- */
    [0x6161] = { 10, 0x63 },
    /* --- 8< -- snip --- 8< --- */
    [0xFFFF] = { 64, 0 },
};

This table has 64K entries. Each element contains the bit string code that represents the Huffman encoding of the two input bytes and its length, lens. Because code is 32 bits wide, some two-byte encodings cannot be represented. They are marked by lens having value 64. In this case, the encoder has to fall back to processing input byte by byte.

New Loop

The new loop is broken up into three parts below to place explanation next to the code. You can view the loop in its entirety on GitHub.

Read

    while (src + sizeof(bits) * 8 / 5 + sizeof(idx) < src_end
                                    && p_dst + sizeof(bits) <= dst_end)
    {
        memcpy(&idx, src, 2);
        henc = &hencs[idx];
        src += 2;
        while (bits_used + henc->lens < sizeof(bits) * 8)
        {
            bits <<= henc->lens;
            bits |= henc->code;
            bits_used += henc->lens;
            memcpy(&idx, src, 2);
            henc = &hencs[idx];
            src += 2;
        }

To avoid source and destination checks inside the loop, they are performed once. The body of the loop is executed if there are enough source bytes to fill the accumulator with shortest Huffman codes and read two more bytes (that translates to 64 / 5 + 2 = 14 bytes on 64-bit platforms) and enough space in the destination buffer to fit all bytes in the accumulator.

With that out of the way two bytes are read into idx and this value is used to point to the corresponding entry in the hencs table. memcpy is used to guarantee aligned access.

The loop condition of the inner while loop checks two things:

1. whether the accumulator will be filled by the current output bit string; and
2. output bit string validity.

The reason for making 64 the invalid value in the hencs table is to be able to combine the two checks above into a single expression. If 0 were the invalid value indicator, the condition would have to be more complicated:

henc->lens && bits_used + henc->lens < sizeof(bits) * 8

This optimization makes a noticeable difference by reducing the number of instructions in the inner loop.

Write

        if (henc->lens < 64)
        {
            bits <<= sizeof(bits) * 8 - bits_used;
            bits_used = henc->lens - (sizeof(bits) * 8 - bits_used);
            bits |= henc->code >> bits_used;
#if UINTPTR_MAX == 18446744073709551615ull
            *p_dst++ = bits >> 56;
            *p_dst++ = bits >> 48;
            *p_dst++ = bits >> 40;
            *p_dst++ = bits >> 32;
#endif
            *p_dst++ = bits >> 24;
            *p_dst++ = bits >> 16;
            *p_dst++ = bits >> 8;
            *p_dst++ = bits;
            bits = henc->code;   /* OK not to clear high bits */
        }

If the current henc entry is valid, the accumulated bytes are written to destination buffer. First, the accumulator bits is filled to the max by adding first part of the current output bit string henc->code.

Because the destination check has already been performed and we know the number of bytes to write, it is done in a series of shift, assignment, and increment statements.

henc->code is simply copied to the bits accumulator as is not necessary to clear any bits. The unused bits from henc->code will be processed based on the value of bits_used.

Note that it costs only one conditional to output a bits-ful of bytes.

Fallback

        else
        {
            src -= 2;
            break;
        }
    }

The fallback occurs when the current two-byte input sequence translates to an output bit string that is too long. The input pointer is backed up two bytes and the new loop is exited, with control proceeding naturally to the original byte-by-byte loop.

Count Branches

The loop checks:

1. source and destination bounds once per every 8 output bytes;
2. accumulator fill every two input bytes; and
3. code validity every 8 output bytes.

Again, assuming compression ratio to be 0.75, this translates to 1 / (8 / 0.75) + 1 / 2 + 1 / (8 / 0.75) = 0.69 branches per input byte. This is three times fewer branches than in the original loop.

Benchmarks

We compare the optimized Huffman encoder (litespeed) to the original (litespeed-orig), as well as to Huffman decoders from nginx, h2o, and nghttp2 projects. I extracted the relevant pieces of code from each project and placed them into separate C files in our Huffman encoder benchmark GitHub repo.

We will test using four different inputs:

1. litespeed.txt: This file contains the string “LiteSpeed”. It is used to test small inputs.
2. x-fb-debug.txt: This is a medium-size string taken from a real x-fb-debug header from the Facebook response QIF file. This is used to test medium-size input.
3. idle.huff: This file contains the first few paragraphs from The Idle Thoughts of an Idle Fellow by Jerome K. Jerome. It is used to test large input.
4. x-fb-backslash.huff: This is the same as (2), except with three backslashes inserted in the middle of the string. The backslash is encoded using a 19-bit code, and so the Fast Huffman Encoder will have to fall back to using the original byte-by-bytes loop.

The table below was generated by the helper program bench.pl. In addition to running the driver and calculating median values, it first calibrates each input file so that the fastest of the encoders runs for at least five seconds. Each encoder runs an input file five times and the median run time is taken. These are the numbers for each encoder in the table below. They are in seconds.

Results

As expected, there is no speedup for litespeed.txt, as that string is shorter than 14 bytes. For x-fb-debug.txt, x-fb-backslash.txt, and idle.txt, litespeed is 2.14, 1.75, and 1.70 times, respectively, faster than litespeed-orig. litespeed Huffman encoder beats nginx, h2o, and nghttp2 in all tests. This is how much faster:

litespeed is about twice as fast (2.12 and 1.89) as nginx on normal input when the string is not tiny (and when it is tiny, its still faster).

h2o is an also-ran, while the nghttp2 encoder is the slowest of the bunch.

Conclusion

The Fast Huffman Encoder uses the same insight as the Fast Huffman Decoder: the subset of commonly used characters in HTTP headers is much smaller than the set of possible characters. For inputs of 12 characters or longer, the encoder virtually always uses the fast path, and the fallback is cheap. At the cost of 512KB of a read-only lookup table, we've doubled the Huffman encoding speed.

Portability

This is a bonus section for the dedicated. Welcome!

Table Compilation: Endianness

The initial description of the big table was a bit of a white lie. The table actually looks like this:

#if __BYTE_ORDER == __LITTLE_ENDIAN
#define I(i,j) ((j<<8)|i)
#else
#define I(i,j) ((i<<8)|j)
#endif
#if UINTPTR_MAX == 18446744073709551615ull
#define X32 32
#else
#define X32 64
#endif
struct henc {
    unsigned lens;
    uint32_t code;
} hencs[] = {
    [I(0,0)] = {26,0x3FF1FF8},
    [I(1,0)] = {64,0},
    /* --- 8< --- snip --- 8< --- */
    [I(97,97)] = {10,0x63},
    /* --- 8< --- snip --- 8< --- */
    [I(203,97)] = {X32,0xFFFFFBC3},
    /* --- 8< --- snip --- 8< --- */
    [I(255,255)] = {64,0},
};
#undef X32
#undef I

The I() macro is used to generate different indexes on little-endian and big-endian platforms.

Avoid Undefined Behavior

The X32 macro effectively disables 32-bit output sequences on 32-bit platforms. This is because of the left shift used when outputting encoded buffer in the big loop. The C standard says the following about bitwise shift operators:

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

This means that the result of the following statement may be undefined if we shift by 32:

bits <<= sizeof(bits) * 8 - bits_used;

To avoid bits_used from being 0 here, the longest code must be smaller than 32 on a 32-bit platform. We guarantee this with the inner while loop.

Aligned Access

We read encoder input as a sequence of two-byte integers by copying memory to a local variable:

memcpy(&idx, src, 2);
henc = &hencs[idx];

On Intel x86 and x64 architecture, data does not have to be aligned, so one could (or could one?) get away with writing code like this:

henc = &hencs[ * (uint16_t *) src];

But then this would not work on platforms with stricter alignment requirements, such as SPARC.

Fortunately, the compiler is smart enough to compile both of these code snippets to exactly the same -- fast -- code.

Summary

The LiteSpeed HPACK Huffman decoder is twice as fast as that used by nginx. This is one of the reasons LiteSpeed Web Server outperforms nginx in a variety of HTTP/2 benchmarks. This article describes how our Huffman decoder works and then tests its performance against that of nginx Huffman decoder. The benchmarked code is available in a public GitHub repository, making the results easy to verify.

Introduction

The latest major release of LiteSpeed Web Server includes several new features and optimizations. Our web server outperforms nginx by a factor of 2 to 12 in several readily reproducible benchmarks.

How do we do it? The truth is, when we are not adding new features, we are optimizing existing code. We 1) examine each module and submodule to find one we can speed up; 2) speed it up; and 3) go back to step 1. Sometimes we wake up because a way to elide a branch in the middle of a tight loop has appeared to us in a dream. Then we turn on the terminal and put down the nocturnal epiphany in code.

Why do we do it? HTTP/2 is on its way to become the dominant web protocol. HTTP/2 performance is crucial for any modern web server. And, of course, we want to be faster than everyone else.

This article describes one of the optimizations that made ours the fastest HTTP/2 implementation in the world.

History

Well-led software projects are not afraid to borrow good ideas, for the hubris of the not-invented-here syndrome often leads to suboptimal implementations. Such is the story of the HPACK Huffman decoder in today’s major web servers. Apache, LiteSpeed, and nginx have all, until recently, used the same Huffman decoder implementation.

HPACK is a specialized compression mechanism for HTTP headers, designed specifically for HTTP/2. Header compression is one of HTTP/2’s “killer features:” it reduces bandwidth necessary to transfer headers and thus improves throughput. Huffman coding is used to compress headers that are not in one of the HPACK tables.

In January of 2014, over a year before the HPACK RFC was published, Tatsuhiro Tsujikawa rewrote Huffman decoder in nghttp2’s implementation of HPACK. (nghttp2 is used by Apache to provide HTTP/2 functionality.) The new code used the method described eleven years earlier by Renato Pajarola in his paper Fast Prefix Code Processing. It is significantly faster than prior methods. The idea is to process compressed data several bits — instead of one bit — at a time. Tatsuhiro chose 4 bits as input length. 4 is a good number. Conveniently, it is exactly half the length of a byte. A shorter sequence would not have sped up the code as much, while a longer sequence would grow the transition table.

Because HPACK Huffman codes do not change, the transition table is generated once — at compile time. The static table is then used by a simple, robust, and fast decoder function. This was a good idea and a good piece of code, so LiteSpeed, nginx, and others copied (with slight alterations) the code, and moved on.

Fast or Slow?

Our own version of the Huffman decoder looks like this (see litespeed.c):

int
lshpack_dec_huff_decode_full (const unsigned char *src, int src_len,
                                            unsigned char *dst, int dst_len)
{
    const unsigned char *p_src = src;
    const unsigned char *const src_end = src + src_len;
    unsigned char *p_dst = dst;
    unsigned char *dst_end = dst + dst_len;
    struct decode_status status = { 0, 1 };

    while (p_src != src_end)
    {
        if (p_dst == dst_end)
            return -2;
        if ((p_dst = hdec_huff_dec4bits(*p_src >> 4, p_dst, &status))
                == NULL)
            return -1;
        if (p_dst == dst_end)
            return -2;
        if ((p_dst = hdec_huff_dec4bits(*p_src & 0xf, p_dst, &status))
                == NULL)
            return -1;
        ++p_src;
    }

    if (!status.eos)
        return -1;

    return p_dst - dst;
}

Even though 4 bits at a time is faster than one bit at a time, the code is still pretty expensive. One way to look at this is to count the number of branches for each byte of input. Inside the while loop above, there are four if statements. This is in addition to conditionals in hdec_huff_dec4bits function (there are two) and in addition to the while loop conditional that checks for end of input. That is seven branches for each byte of input. Can we do better?

Common Case

HPACK defines 257 Huffman codes: one for each of the 256 possible bytes and one for the special end-of-stream (EOS) symbol. The codes range from 5 to 30 bits in length: the more likely the value, the shorter its code. What is important to realize is that two thirds of the Huffman codes are virtually never used in HTTP headers. Most of the time, only shorter codes are used. For example, no codes longer than 13 bits are used in the QIF corpus. In this restricted domain, there are more possibilities for optimization.

Big Table!

The idea is to generate a large table that can be indexed by the longest of the common Huffman codes. For example, a table with 64K entries can be indexed by a 16-bit value, representing a sequence of 16 input bits. In the common case, a 16-bit sequence is wide enough to contain Huffman codes for one or more output symbols (the average number is 2.14 output symbols per 16 bits).

Encountering a code longer than 16 bits would require falling back to the original, full Huffman decoder that processes the input 4 bits at a time.

Fast Huffman Decoder Details

(To keep the blog post manageable, only the most important snippets of code are included here. For your convenience, the table and the Fast Huffman Decoder function are available in their entirety here: litespeed.c, litespeed-table.h.)

The Table

As mentioned above, the table contains 64K entries, for the full range of values that fits into a 16-bit integer, from 0 to 65,535. Each entry contains three things:

1. Sum of lengths of Huffman codes consumed from the input stream, in bits. This value has a valid range from 5, which is the length of the shortest HPACK Huffman code, to 16, which is the number of bits available for input. Remember, the input bits here are in the index value.
2. Number of output bytes. The smallest value is 1, while the largest is 3. 3 is how many 5-bit codes can fit into 16 bits.
3. Output bytes themselves.

static const struct hdec {
    uint8_t lens;
    uint8_t out[3];
} hdecs[] = {
    /* 0 */ {(15<<2)|3,{48,48,48}},
    /* 1 */ {(15<<2)|3,{48,48,48}},
    /* 2 */ {(15<<2)|3,{48,48,49}},
    /* 3 */ {(15<<2)|3,{48,48,49}},
    /* --- 8< --- many rows skipped --- 8< --- */
    /* 65532 */ {(15<<2)|1,{123,0,0}},
    /* 65533 */ {(15<<2)|1,{123,0,0}},
    /* 65534 */ {0,{0,0,0,}},
    /* 65535 */ {0,{0,0,0,}},
};

To keep each element to 4 bytes, Huffman codes lengths and number of output bytes are combined into a single struct member lens. The 3-byte array out holds the output bytes themselves. For example, element 2 above consumes 15 bits of input and outputs 3 bytes: 0, 0, 1. Element 65533 consumes 15 bits of input and outputs 1 byte: {.

The last two elements of the table have lens equal zero. This indicates that there is no matching Huffman code that fits into 16 bits. The HPACK Huffman code table shows that, indeed, all codes longer than 16 bits begin with either 11111111 11111110 (65534) or 11111111 11111111 (65535) bit sequence. When this code is encountered, the Fast Huffman Decoder has to use the fallback mechanism.

Main Loop

The main loop can be described in this high-level pseudocode:

while (have input)
{
    fill buf;
    drain buf;
}

Several input bytes are copied into an intermediate representation. This batch of input bits is then processed: an element in hdecs table is looked up and output is written, until the number of available bits (avail_bits) falls under 16. At this point, buf is refilled.

Input Batching

The input bytes are copied into an integer buffer buf, which is the size of a pointer (8 bytes on 64-bit platforms). avail_bits holds the number of input bits available in buf. avail_bits must be at least 16 to be able to use the large table.

if (src + sizeof(buf) <= src_end)
    /* --- 8< --- omitted for brevity, refer to litespeed.c --- 8< --- */
    ;
else if (src < src_end)
    do
    {
        buf <<= 8;
        buf |= (uintptr_t) *src++;
        avail_bits += 8;
    }
    while (src < src_end && avail_bits <= sizeof(buf) * 8 - 8);
else
    break;  /* Normal case terminating condition: out of input */

Filling buf is optimized. If the number of remaining input bytes is at least the size of buf, we can use a switch statement. Otherwise, bytes are added to buf using a while loop.

Batch Processing

The batch of input bits in buf is used to look up elements in hdecs. If the output buffer has enough room to fit the maximum number of bytes that could possibly be encoded in buf (64 / 5 = 12 bytes on 64-bit platform), the processing loop can skip destination check.

if (dst_end - dst >= (ptrdiff_t) (8 * sizeof(buf) / SHORTEST_CODE)
                                                	&& avail_bits >= 16)
{
    /* Fast path: don't check destination bounds */
    do
    {
        idx = buf >> (avail_bits - 16);
        hdec = hdecs[idx];
    	dst[0] = hdec.out[0];
    	dst[1] = hdec.out[1];
    	dst[2] = hdec.out[2];
    	dst += hdec.lens & 3;
    	avail_bits -= hdec.lens >> 2;
    }
    while (avail_bits >= 16 && hdec.lens);
    if (avail_bits < 16)
        continue;
    goto slow_path;
}

The do/while loop above is the main reason the Fast Huffman Decoder is fast. The only conditional is the terminating condition, which checks both the number of available bits and hdec validity at the same time. The average number of consumed bits in hdecs table is 12.76. This translates to 0.63 branches per input byte. Far cry from seven! Of course, there are branch penalties elsewhere — filling the batch, error checking — but this loop’s speed makes up for them in spades.

The next 16-bit input sequence to use is in the most significant bits of buf. Since idx is uint16_t, there is no need to mask out the low 16 bits of buf: assignment to uint16_t takes care of that.

All three bytes of the hdec.out array are written to the destination buffer. This saves a conditional at a cost of an unnecessary write. 15% of hdecs entries output 3 bytes, while 84% output 2 bytes. On average, then, 5 times out of 6 an extra byte is written to dst. This is cheaper than a branch.

As described above, invalid entries have lens equal to zero. In this case, the values of dst and avail_bits are not changed inside the loop. The if statement after the loop is used to differentiate whether we ran out of bits (the common case) or found an invalid code. The latter forces us to fall back to the full Huffman decoder.

A slower while loop is utilized when there is not much room left in the destination buffer.

Fallback

When a long (or invalid) Huffman code is encountered, we have to use the full (original) Huffman decoder to process the rest of the string.

/* Find previous byte boundary and finish decoding thence. */
while ((avail_bits & 7) && dst > orig_dst)
    avail_bits += encode_table[ *--dst ].bits;
src -= avail_bits >> 3;
r = lshpack_dec_huff_decode_full(src, src_end - src, dst, dst_end - dst);
if (r >= 0)
    return dst - orig_dst + r;
else
    return r;

We cannot start processing from the current input position if the Huffman code is not on the byte boundary. We need to rewind the input pointer toward the beginning, looking for the byte boundary. To do that, we use the bytes we already output and the Huffman encoder table. We back up until avail_bits is a multiple of 8. In the worst case, we will stop at the beginning of the input, but that usually does not happen for an input of any appreciable length.

Benchmarks

We will compare the Fast Huffman Decoder with Huffman decoder from nginx. To do that, I extracted Huffman decoder functions from ls-hpack and nginx and wrote a small driver program that runs the decoder. See our Huffman decoder GitHub repo. The specific versions of the decoder are here (LiteSpeed) and here (nginx). The latter has been adapted from nginx 1.16.1. You should be able easily to clone this repository and replicate our results.

The driver is a simple program that reads Huffman-encoder string from a file and decodes it a number of times. The less time a decoder takes to decode the input, the faster the decoder.

For example:

sh$ time -p ./comp-dec idle.huff 1000000 litespeed
real 8.35
user 8.33
sys 0.00
sh$ time -p ./comp-dec idle.huff 1000000 nginx
real 16.20
user 16.16
sys 0.00

It took Fast Huffman Decoder 8.35 seconds to decode Huffman-encoded string in idle.huff one million times, while the nginx Huffman decoder took 16.20 seconds.

We will test using four different inputs:

1. litespeed.huff. This is a Huffman-encoded string “LiteSpeed”. It is used to test small inputs.
2. x-fb-debug.huff. This is a medium-size string taken from a real x-fb-debug header from the Facebook response QIF file. This is used to test medium-size input.
3. idle.huff. This file contains the first few paragraphs from The Idle Thoughts of an Idle Fellow by Jerome K. Jerome. It is used to test large input.
4. x-fb-backslash.huff. This is the same as (2), except with a backslash inserted in the middle of the string. The backslash is encoded using a 19-bit code, and so the Fast Huffman Decoder will have to backtrack and fall back to the full decoder. This is used to test how well (or poorly) the Fast Huffman Decoder performs in this case.

We’ll run each input file five times for each decoder, LiteSpeed and nginx. Then we will compare median average run times. (See the complete numbers at the bottom of this article.)

Results

Presented with normal input, the LiteSpeed Fast Huffman Decoder almost doubles the speed of the nginx Huffman decoder. Even when the Fast Huffman Decoder has to backtrack due to uncommon input, it still performs significantly better than the alternative.

Conclusion

The LiteSpeed Fast HPACK Huffman Decoder leverages its knowledge of the expected input to optimize for the common case. The fast code path uses two to three times fewer conditionals than the original decoder, making it twice as fast as the original Huffman decoder for all but the most unusual inputs. This is one of the many optimizations we performed — and continue to perform — to make ours the fastest web server, period.

We also use the Fast Huffman Decoder in our QPACK library, speeding up our HTTP/3 stack. We intend to maintain performance leadership with next-generation HTTP version as well.

Post Scriptum

While writing this article, I found two more optimizations that would make the Fast Huffman Decoder even faster. Stay tuned!

Raw Numbers

litespeed.huff

Needed to set number of iterations to 100,000,000 to get into the seconds.

x-fb-debug.huff

Number of iterations is set to 10,000,000

idle.huff

Number of iterations set to 1,000,000

x-fb-backslash.huff

Number of iterations set to 10,000,000

It is curious that this input differs only by one character from x-fb-debug.huff, yet nginx decoder processes it markedly faster. I haven’t been able — using a limited amount of time — to figure out why.