Subject: hpack huffman codes

From: "Martin Nilsson" <[email-masked]>
Date: Tue, 10 Jun 2014 16:44:55 +0200

Regarding the process to validate the current hpack huffman codes against  
a large set of real headers, I think there is a risk that we'll paint  
ourselves into a corner dictated by how HTTP/1 looks like. As pointed out,  
a lot of base64 or hex encoded headers greatly benefits from huffman  
encoding. However, if we can carry binary data there is no point in having  
the data encoded in the first place, and not something to train the code  
table for. These headers will change over time, because even if they are  
taken into consideration for the huffman table, it is still more space  
efficient to not encode them. The code lengths for the characters of the  
other headers might suffer though.

/Martin Nilsson

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

---

From: Martin Thomson <[email-masked]>
Date: Tue, 10 Jun 2014 08:08:12 -0700

It costs nothing to disable Huffman coding. Thus the table really isn't the
issue. The actual problem here is the grammar of the various header fields,
and the potential need to translate into HTTP/1.1.

---

From: Johnny Graettinger <[email-masked]>
Date: Tue, 10 Jun 2014 15:46:40 -0400

All,

As discussed during the interim, Chrome has been running a trial to
estimate an optimal HPACK Huffman code. Briefly, the methodology used is to
maintain an LRU of HPACK delta encoders for visited origins, to process all
request and response headers (including those delivered via HTTP/1) through
an origin-specific encoder, and to aggregate character counts of literals
emitted by those encoders. This roughly approximates the behavior of an
HPACK encoder if the origin had switched to long-lived HTTP/2 connections.
The implementation is available for inspection [1], and I'm happy to answer
questions.

Reviewing the last month of data, a Huffman code constructed for the count
PDF compresses that same PDF about 2.1% better than the current code table,
after adjusting the code to remove unique lengths (75.75% vs 77.87% of
uncompressed size). The observed PDF, constructed code, and comparison with
the current code are available at [2].

A caveat of the result is that this trial is running only on our Canary &
Dev channels. It's possible the distribution is somewhat biased due to
these populations. Ideally it would include Stable channel samples as well,
but that wasn't feasible in the time available. That said, this is still a
large population and having also looked at a couple of smaller windows, the
distribution does appear to have converged quickly and to be internally
consistent over time.

I'm personally on the fence as to whether the degree of improvement
warrants updating the current code, given the limitations of the trial. A
reasonable position is that this simply provides confirmation the current
code is near-optimal.

[1]
https://code.google.com/p/chromium/codesearch#chromium/src/net/spdy/hpack_huffman_aggregator.h&sq=package:chromium
[2]
https://docs.google.com/a/chromium.org/spreadsheet/ccc?key=0Ao3snhnDWuTvdGJNckVoWGpMN0tobTRERmVLdV8zRWc#gid=0

cheers,
-johnny

On Tue, Jun 10, 2014 at 11:08 AM, Martin Thomson <[email-masked]>
wrote:

> It costs nothing to disable Huffman coding. Thus the table really isn't
> the issue. The actual problem here is the grammar of the various header
> fields, and the potential need to translate into HTTP/1.1.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 10 Jun 2014 13:27:32 -0700

On 10 June 2014 12:46, Johnny Graettinger <[email-masked]> wrote:
> I'm personally on the fence as to whether the degree of improvement warrants
> updating the current code, given the limitations of the trial. A reasonable
> position is that this simply provides confirmation the current code is
> near-optimal.

Thanks for doing this Johnny.  This would seem to validate the
original table, though there are some interesting differences in
lengths.  It seems like the new numbers show less of a steep drop from
the high frequency 0/1/2 characters and a slightly more gradual roll
off in the mid range.

My little Monte Carlo estimation rig seems to produce better results
with common character set restrictions (ignore percentages):

~/code/bhpack master
$ node compare.js 1000000 40
1000000 random sequences of lengths:     40
Average sizes: min/ave/max (size compared against Base64+Huffman)
Raw Huffman coding (invalid):         62/95.944842/123 (203.71%)
Base 64 (no Huffman):             54/54/54 (114.65%)
Base 64 with Huffman:             41/47.099388/54 (100%)
bhpack cookie with Huffman:         40/46.334863/56 (98.38%)
bhpack URI safe with Huffman:         40/45.126209/52 (95.81%)
bhpack URI query with Huffman:         40/45.200022/53 (95.97%)

~/code/bhpack chromium-test
$ node compare.js 1000000 40
1000000 random sequences of lengths:     40
Average sizes: min/ave/max (size compared against Base64+Huffman)
Raw Huffman coding (invalid):         60/91.417749/123 (209.74%)
Base 64 (no Huffman):             54/54/54 (123.89%)
Base 64 with Huffman:             40/43.587016/47 (100%)
bhpack cookie with Huffman:         39/44.91345/56 (103.04%)
bhpack URI safe with Huffman:         40/43.424513/48 (99.63%)
bhpack URI query with Huffman:         39/43.268/49 (99.27%)

---

From: Mike Bishop <[email-masked]>
Date: Tue, 10 Jun 2014 20:40:08 +0000

Yes, thanks for this, Johnny!

Given that the difference is slight (less than 3% better), we would support accepting this as confirmation that the current code is good and leave things as they are, unless broader deployment shows that the Huffman table is further off-base for common headers than this indicates.

Martin, I'm going to throw out a hypothesis that probably can't be confirmed without changing the deployed code....  The original table was based on a sampling of HTTP headers, while this is based on a sample of *post-HPACK* literals.  That means headers which get optimized out by HPACK (header table, reference set) don't get counted every time in Johnny's model, where they probably did in the original analysis.  The less-steep highest-frequency characters (particularly 0/1) may be things that show up frequently but don't change from request to request over the lifetime of a connection.

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Tuesday, June 10, 2014 1:28 PM
To: Johnny Graettinger
Cc: Martin Nilsson; HTTP Working Group
Subject: Re: hpack huffman codes

On 10 June 2014 12:46, Johnny Graettinger <[email-masked]> wrote:
> warrants updating the current code, given the limitations of the 
> trial. A reasonable position is that this simply provides confirmation 
> the current code is near-optimal.

Thanks for doing this Johnny.  This would seem to validate the original table, though there are some interesting differences in lengths.  It seems like the new numbers show less of a steep drop from the high frequency 0/1/2 characters and a slightly more gradual roll off in the mid range.

My little Monte Carlo estimation rig seems to produce better results with common character set restrictions (ignore percentages):

~/code/bhpack master

---

From: Roberto Peon <[email-masked]>
Date: Tue, 10 Jun 2014 14:02:29 -0700

IIRC, when I created the code to generate the current table, it was done
using the same methodology as Johnny's-- a character is counted if it would
have been emitted in a literal, and not otherwise.
-=R

On Tue, Jun 10, 2014 at 1:40 PM, Mike Bishop <[email-masked]>
wrote:

> Given that the difference is slight (less than 3% better), we would
> support accepting this as confirmation that the current code is good and
> leave things as they are, unless broader deployment shows that the Huffman
> table is further off-base for common headers than this indicates.
>
> Martin, I'm going to throw out a hypothesis that probably can't be
> confirmed without changing the deployed code....  The original table was
> based on a sampling of HTTP headers, while this is based on a sample of
> *post-HPACK* literals.  That means headers which get optimized out by HPACK
> (header table, reference set) don't get counted every time in Johnny's
> model, where they probably did in the original analysis.  The less-steep
> highest-frequency characters (particularly 0/1) may be things that show up
> frequently but don't change from request to request over the lifetime of a
> connection.
>
> Thanks for doing this Johnny.  This would seem to validate the original
> table, though there are some interesting differences in lengths.  It seems
> like the new numbers show less of a steep drop from the high frequency
> 0/1/2 characters and a slightly more gradual roll off in the mid range.
>
> My little Monte Carlo estimation rig seems to produce better results with
> common character set restrictions (ignore percentages):
>
> ~/code/bhpack master

---

From: Martin Thomson <[email-masked]>
Date: Tue, 10 Jun 2014 14:20:18 -0700

> Given that the difference is slight (less than 3% better), we would support accepting this as confirmation that the current code is good and leave things as they are, unless broader deployment show…

The straight base64 tests I've run show a compound performance
increase of ~7.5%, which would seem to be fairly significant.

I don't know about the size of the data set that Roberto used
originally, nor do I know how good the distribution of both sets of
test data were (I might theorize that these are too WEIRD [1], or
maybe even too biased toward Google's workloads).

I'm somewhat inclined toward a change here, but mainly due to the
robustness of the data set.  Unless Roberto can produce evidence that
his input data was comparable in quality.  It took me less than five
minutes to make a change in my code, so that's not the issue.

[1] http://schott.blogs.nytimes.com/2010/07/14/weird/?_php=true&_type=blogs&_r=0

---

From: Roberto Peon <[email-masked]>
Date: Tue, 10 Jun 2014 14:27:51 -0700

I'd prefer to use the table from the larger corpus if folks accepted it,
and the bas64 improvement you quote is a fairly big deal.
I have nothing to assure us that my input data was anywhere near the same
quality (which would be why I convinced Johnny to do this experiment!
Thanks Johnny!!!), and every reason to doubt it.
-=R

On Tue, Jun 10, 2014 at 2:20 PM, Martin Thomson <[email-masked]>
wrote:

> http://schott.blogs.nytimes.com/2010/07/14/weird/?_php=true&_type=blogs&_r=0
>
>

---

From: David Krauss <[email-masked]>
Date: Wed, 11 Jun 2014 07:53:11 +0800

I did a little investigation about more efficient codings, but I wasn’t sure that anyone still cared about these incremental improvements.

This program produces encouraging results: http://ideone.com/e77b6S . The input is a corpus with one line per entry. It’s in C++11 so running it outside ideone.com will require a moderately recent C++ compiler, passing it the -std=c++11 flag.

What you see at the output line “ideal size = …”  is the projected size (in bytes) of the compressed corpus if each output symbol is given its own Huffman table, populated by the *conditional* probabilities for the next symbol.

The succeeding lines give the incremental cost in bytes of combining all those tables, i.e. treating the next-symbol predictions of the given characters as the same. It follows a simple greedy algorithm.

At the bottom, you get the projected size as if there were just one Huffman table, which should roughly match existing results. It doesn’t actually do the encoding but calculates an ideal information content, which corresponds more closely to arithmetic encoding.

The last few lines should show a large potential gain from having just 3-5 distinct static tables. Using ~1.5 MB of URLs from my browser history, the last few lines of output are:

7485 x (+-./;=[_|~ += ABCDEFGHIJKLMNOPQRSTUVWXYZbj
7999 x &?ir += aeou
19332 x &?aeioru += )*:]cdfghklmnpqstvwxyz
20017 x  !"#$%',0123456789<>@\^`{} += (+-./;=ABCDEFGHIJKLMNOPQRSTUVWXYZ[_bj|~
48991 x  !"#$%'(+,-./0123456789;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\^_`bj{|}~ += &)*:?]acdefghiklmnopqrstuvwxyz
single-table size = 989717 = 989718 vs 1425268

This means that for this corpus, there’s a savings of 88 KB or ~9% compound if separate tables are used for:
- Lowercase consonants
- Numbers
- Uppercase letters and most punctuation
- Lowercase vowels

I’m working on improving the algorithm, I think the scheme should do better if duplicates are allowed between tables. Also, the low-probability tails of the tables should be merged.

In principle, runs of Base64 text should be compressed at a constant 25% savings, because that’s the information content of Base64. It’s really not too much to ask. However, you guys have to be aware that Huffman codes are not magic; it’s just reflecting the frequency of the characters you put in. If you arbitrarily want Base64 to encode better, then just increase the frequency of the letters used by it. But remember that this will decrease the relative frequency/probability of all the other symbols, and the flatten the relative differences between the Base64 characters.

Let me know if there’s interest here. Otherwise I’ll just pursue this independently, because the idea works well enough. Huffman tables with conditional probability are still just Huffman tables; little generality is lost.

It would be very helpful if I could see the corpus you guys are working with. My URL history is simply too small and biased and as you can see from the above results, there are some artifacts that may result from that.

On 2014–06–11, at 5:27 AM, Roberto Peon <[email-masked]> wrote:

> I'd prefer to use the table from the larger corpus if folks accepted it, and the bas64 improvement you quote is a fairly big deal.
> I have nothing to assure us that my input data was anywhere near the same quality (which would be why I convinced Johnny to do this experiment! Thanks Johnny!!!), and every reason to doubt it.
> -=R
> 
> 
> On Tue, Jun 10, 2014 at 2:20 PM, Martin Thomson <[email-masked]> wrote: