Subject: Speed concern related to bit order in Huffman (was: I-D Action: draft-ietf-httpbis-header-compression-10.txt)

From: Frédéric Kayser <[email-masked]>
Date: Tue, 2 Dec 2014 03:08:07 +0100

Hi,
I did not follow the list for nearly a year but this aspect as apparently not been discussed.
There’s something that puzzles me when I read the HPACK spec it seems to record the Huffman compressed data in a natural and naive way which is not what state of the art compressors do.
The problem here is not space saving but rather speed and especially decoding speed and it may not be apparent when using high level languages this is rather a fine tune for C and other bare metal (assembly like) implementation.

Bits-at-top is a different approach: Deflate has been doing this for more than two decades and Charles Bloom recently stated that it is still the fastest way to do bit level I/O (Charles Bloom is well respected in the data compression comunity).
http://cbloomrants.blogspot.fr/2014/02/02-18-14-ansfast-implementation-notes.html

If I take the sample given in HPACK 10:
http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#appendix-C.4
"example.com" is Huffman encoded this way: f1e3 c2e5 f23a 6ba0 ab90 f4ff

F1E3 C2E5 or 11110001 11100011 1100 0010 11100101 in binary and comes from:
‘w’ (119) 1111000
‘w’ (119) 1111000
‘w’ (119) 1111000
'.' (46)  010111
'e' (101) 00101

Notice that bits have been put into the bytes as they come: 1111000 <- 1111000 <- 1111000 <- 010111 <- 00101, dot used to show code boundary: 1111000.1 111000.11 1100 0.010 111.00101

Bits at top does work this way around:
xxxxxxxx xxxxxxxx xxxxxxxx x1111000
xxxxxxxx xxxxxxxx xx111100 01111000
-> emit 01111000
xxxxxxxx xxxxxxxx xxxxxxxx xx111100
xxxxxxxx xxxxxxxx xxx11110 00111100
-> emit 00111100
xxxxxxxx xxxxxxxx xxxxxxxx xxx11110
xxxxxxxx xxxxxxxx xxxxx010 11111110
-> emit 11111110
xxxxxxxx xxxxxxxx xxxxxxxx xxxxx010
xxxxxxxx xxxxxxxx xxxxxxxx 00101010
-> emit 00101010

gives 01111000 00111100 11111110 00101010 which is impossible to decode… silly me forget to reverse bit order at code level, which gives :
‘w’ (119) 1111000 -> 0001111
‘w’ (119) 1111000 -> 0001111
‘w’ (119) 1111000 -> 0001111
'.' (46)  010111 -> 111010
'e' (101) 00101 -> 10100

xxxxxxxx xxxxxxxx xxxxxxxx x0001111
xxxxxxxx xxxxxxxx xx000111 10001111
-> emit 10001111
xxxxxxxx xxxxxxxx xxxxxxxx xx000111
xxxxxxxx xxxxxxxx xxx00011 11000111
-> emit 11000111
xxxxxxxx xxxxxxxx xxxxxxxx xxx00011
xxxxxxxx xxxxxxxx xxxxx111 01000011
-> emit 01000011
xxxxxxxx xxxxxxxx xxxxxxxx xxxxx111
xxxxxxxx xxxxxxxx xxxxxxxx 10100111
-> emit 10100111

gives 10001111 11000111 01000011 10100111 or 8FC7 43A7, 

Bits-at-top looks a bit more complicated but is much closer to what CPUs are able to handle quickly, Deflate and now Brotli compression work this way and as I wrote before it’s still the way recommended by Charles Bloom for super fast implementation of bit level I/O.

I hope it’s not too late to stop press to evaluate the real impact it could have on HPACK.

Regards
Frédéric Kayser

---

From: Roberto Peon <[email-masked]>
Date: Mon, 1 Dec 2014 18:21:32 -0800

The best way to influence is to show the difference :)
I remember bemoaning that little-endian won, which requires such things for
speed for bitwise operations.

-=R

On Mon, Dec 1, 2014 at 6:08 PM, Frédéric Kayser <[email-masked]> wrote:

> There’s something that puzzles me when I read the HPACK spec it seems to
> record the Huffman compressed data in a natural and naive way which is not
> what state of the art compressors do.
> The problem here is not space saving but rather speed and especially
> decoding speed and it may not be apparent when using high level languages
> this is rather a fine tune for C and other bare metal (assembly like)
> implementation.
>
> Bits-at-top is a different approach: Deflate has been doing this for more
> than two decades and Charles Bloom recently stated that it is still the
> fastest way to do bit level I/O (Charles Bloom is well respected in the
> data compression comunity).
>
> Notice that bits have been put into the bytes as they come: 1111000 <-
> 1111000 <- 1111000 <- 010111 <- 00101, dot used to show code boundary:
> 1111000.1 111000.11 1100 0.010 111.00101
>
> gives 01111000 00111100 11111110 00101010 which is impossible to decode…
> silly me forget to reverse bit order at code level, which gives :
> Bits-at-top looks a bit more complicated but is much closer to what CPUs
> are able to handle quickly, Deflate and now Brotli compression work this
> way and as I wrote before it’s still the way recommended by Charles Bloom
> for super fast implementation of bit level I/O.
>

---

From: Frédéric Kayser <[email-masked]>
Date: Wed, 3 Dec 2014 01:10:57 +0100

I’ve started the work to benchmark both bit ordering, but now I find that this EOS thing is a bit too complicated.

"A Huffman encoded string literal containing the EOS symbol MUST be treated as a decoding error."

If you don’t want it to appear in the compressed stream just get rid of it and free its code (this will make another symbol one bit shorter)
Basically you want to be sure that the unset bits of the last octet cannot be mismatched with one of the shortest codes (those between 5 and 7 bits) padding it with bits set to 1 is sufficient, successful decoding is achieved when either there are no leftover bits or they are all set to 1 and there's on need to check if EOS has been accidentally decoded since it does not exist anymore. The size of the compressed stream already holds a lot of information there’s no need for a full featured EOS in this case, just get rid of it.

Regards

Le 2 déc. 2014 à 03:21, Roberto Peon <[email-masked]> a écrit :

> I remember bemoaning that little-endian won, which requires such things for speed for bitwise operations.
> 
> -=R
>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Dec 2014 16:27:36 -0800

I'd suggest ignoring it for the purpose of your speed tests :)
-=R

On Tue, Dec 2, 2014 at 4:10 PM, Frédéric Kayser <[email-masked]> wrote:

> If you don’t want it to appear in the compressed stream just get rid of it
> and free its code (this will make another symbol one bit shorter)
> Basically you want to be sure that the unset bits of the last octet cannot
> be mismatched with one of the shortest codes (those between 5 and 7 bits)
> padding it with bits set to 1 is sufficient, successful decoding is
> achieved when either there are no leftover bits or they are all set to 1
> and there's on need to check if EOS has been accidentally decoded since it
> does not exist anymore. The size of the compressed stream already holds a
> lot of information there’s no need for a full featured EOS in this case,
> just get rid of it.
>
> Regards
>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 5 Dec 2014 10:55:59 +0000

I gave a look at your proposal and I think it should provide some speed-up to HPACK encoding when using Huffman codes.
Unfortunately, we are now late in the process and I don't think this optimization introduces enough benefits to be included in HPACK. We might consider it again if we had other changes to make to HPACK.

Regards,

Hervé.

> -----Original Message-----
> From: Frédéric Kayser [mailto:[email-masked]]
> Sent: mardi 2 décembre 2014 03:08
> To: [email-masked]
> Subject: Speed concern related to bit order in Huffman (was: I-D Action: draft-
> ietf-httpbis-header-compression-10.txt)
> 
> Hi,
> There's something that puzzles me when I read the HPACK spec it seems to
> The problem here is not space saving but rather speed and especially decoding
> speed and it may not be apparent when using high level languages this is rather
> a fine tune for C and other bare metal (assembly like) implementation.
> 
> Bits-at-top is a different approach: Deflate has been doing this for more than
> two decades and Charles Bloom recently stated that it is still the fastest way to
> do bit level I/O (Charles Bloom is well respected in the data compression
> comunity).
> 'w' (119) 1111000
> 'w' (119) 1111000
> 'w' (119) 1111000
> Notice that bits have been put into the bytes as they come: 1111000 <- 1111000
> <- 1111000 <- 010111 <- 00101, dot used to show code boundary: 1111000.1
> 111000.11 1100 0.010 111.00101
> 
> gives 01111000 00111100 11111110 00101010 which is impossible to decode.
> 'w' (119) 1111000 -> 0001111
> 'w' (119) 1111000 -> 0001111
> 'w' (119) 1111000 -> 0001111
> Bits-at-top looks a bit more complicated but is much closer to what CPUs are
> able to handle quickly, Deflate and now Brotli compression work this way and
> as I wrote before it's still the way recommended by Charles Bloom for super
> fast implementation of bit level I/O.
> 
> I hope it's not too late to stop press to evaluate the real impact it could have on
> HPACK.
> 
> Regards
> Frédéric Kayser
>

---

From: Frédéric Kayser <[email-masked]>
Date: Fri, 12 Dec 2014 03:29:54 +0100

Here are some figures, I took an existing Huffman HPACK implementation:
https://github.com/http2/http2-spec/wiki/Implementations
It looks like nghttp2 and H2O share some code at this level especially the decoding table:
https://github.com/tatsuhiro-t/nghttp2/blob/master/lib/nghttp2_hd_huffman_data.c

I took H2O code and tweaked it to fit into FSE benchmark code.
Wrote a bits-on-top encoder loosely based on Zlib code and its decoder counterpart (damn slow for now since it doesn't use tables) and since a found that using a full-blown Huffman encoder/decoder was a bit overkill in this case I also made some trials with a dumber variable length encoder called Fastlane.

When it comes to measuring speed using small data samples the problem is that your en/decoding code as hardly reached cruise speed that it already stops… since headers are not supposed to hold megabytes of data the sample used here is relatively small (183 bytes) larger samples would produce higher figures (but the overall results stay inline just scaled).

hpackori is H2O code, hpacktop is my code (bits-on-top), since H2O uses precomputed tables for decoding it blows away my code for now but when it comes to encoding speed it’s a bit different: quite faster on Intel, slightly slower on ARM. Bits-on-top is supposed to offer more flexibility on the decoding side, and from what I have seen H2O code does basic I/O when encoding, therefore I would not draw conclusions at this point.
But what stroke me most was the Huffman codes themselves, actually a small subset of ASCII (about 96 code points) enjoy relatively small codes whereas the others quickly get very long codes, in fact if you encounter too many of those codes you’re not going to compress your data but rather expand it and you’re probably better off recording this field uncompressed which leads to the question: how were the underlying statistics gathered? I mean if a particular message is shorter when stored uncompressed it should not take part in the overall stats to foster a more precise picture for codes that will effectively be stored in a compressed way (2 stages mecanism).
I’m even wondering why bother with an universal encoder that is tuned only for a small subset of ASCII and here came the idea for Fastlane. Fastlane is a dumb but fast variable length encoder it only knows 3 code length: 5 bits, 7 bits and 8 bits and can encode only 97 code points (17 of length 5, 40 of length 7 and again 40 of length 8) since the remaining code points are not handled a message holding one of those would have to be recorded uncompressed (or they could be recorded using 16 bits by reducing the base code points to 96 and introducing an escape symbol). Since it is quite simpler than a full-blown Huffman encoder it also works a bit faster (no overly long code to handle, it is quite happy with 16-bits logic) and decoding is way easier, the decoding speed reported here is without a lookup table (after having read the 5 first bits the full length of the code is instantaneously known) a lookup table may still bring some speed gains but would a larger memory foot print and waste some L1 cache, the caveat being that it will not always compress as well as a full Huffman encoder, and at this point I'm curious to see the impact of having Huffman on or off in HTTP/2 on a server CPU load (bit I/O is slow by nature at lot of short bit I/O bursts does not bode well for me).

Intel C2D 1.6GHz (64-bits)

hpackori -z bromix
bromix           :       183 ->       140 (76.50%),   76.9 MB/s ,   61.8 MB/s

hpacktop -z bromix
bromix           :       183 ->       140 (76.50%),   92.5 MB/s ,   34.5 MB/s

fastlane -z bromix
bromix           :       183 ->       140 (76.50%),  102.8 MB/s ,   78.3 MB/s

ARM Cortex A8 800MHz

hpackori -z bromix
bromix           :       183 ->       140 (76.50%),   24.7 MB/s ,   22.8 MB/s
 
hpacktop -z bromix
bromix           :       183 ->       140 (76.50%),   23.2 MB/s ,   12.8 MB/s

fastlane -z bromix
bromix           :       183 ->       140 (76.50%),   40.2 MB/s ,   28.4 MB/s

Regards
Frédéric Kayser