W3C home > Mailing lists > Public > ietf-http-wg@w3.org > April to June 2014

Re: hpack huffman codes

From: Martin Thomson <martin.thomson@gmail.com>
Date: Tue, 10 Jun 2014 13:27:32 -0700
Message-ID: <CABkgnnW8+_=s3DYMB7PzMryZaOpZ=fLu=gbK+oBRb08GVhxeyw@mail.gmail.com>
To: Johnny Graettinger <jgraettinger@chromium.org>
Cc: Martin Nilsson <nilsson@opera.com>, HTTP Working Group <ietf-http-wg@w3.org>
On 10 June 2014 12:46, Johnny Graettinger <jgraettinger@chromium.org> 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%)
Received on Tuesday, 10 June 2014 20:27:59 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 17:14:31 UTC