Compression ratio of 09 (was: Reference set in HPACK)

[Kazu Yamamoto ( 山本和彦 ) <[e-mail]>]

Hi,

I have implemented HPACK 09 and re-calculated compression ratio:

            08    09
Naive     1.10  1.10
Naive-H   0.86  0.85
Static    0.84  0.83
Static-H  0.66  0.66
Linear    0.39  0.39
Linear-H  0.31  0.31
Diff      0.39   N/A
Diff-H    0.31   N/A

As you can see, they are almost the same as those of HPACK 08.

Just FYI.

--Kazu

> Hi,
> 
> As you may remember, I implemented several HPACK *encoding* algorithms
> and calculated compression ratio. I tried it again based on HPACK
> 08. I have 8 algorithms.
> 
> - Naive    -- No compression
> - Naive-H  -- Using Huffman only
> - Static   -- Using static table only
> - Static-H -- Using static table and Huffman
> - Linear   -- Using header table
> - Linear-H -- Using header table and Huffman
> - Diff     -- Using header table and reference set
> - Diff-H   -- Using header table, reference set and Huffman
> 
> The implementations above pass all test cases in
> https://github.com/http2jp/hpack-test-case/.  Using this test cases as
> input, I calculated compression ratio again. The ratio is calculated
> by dividing the number of bytes after compression by that before
> compression.
> 
> Here is results:
> 
> Naive     1.10
> Naive-H   0.86
> Static    0.84
> Static-H  0.66
> Linear    0.39 
> Linear-H  0.31
> Diff      0.39
> Diff-H    0.31
> 
> Linear-H and Diff-H results in almost the same. To my calculation,
> Diff-H is only 1.6 byte shorter than Linear-H in average. This means
> that reference set does NOT much contribute to compress headers
> although it is very difficult to implement.
> 
> I have NOT seen any header examples for which reference set work
> effectively so far.
> 
> So, if the authors of HPACK want to retain reference set, I would like
> to see evidence that there are some cases in which reference set
> contributes the compression ratio. HPACK 08 says "Updated Huffman
> table, using data set provided by Google". So, I guess that the
> authors can calculate the compression ratio based on this data.
> 
> If there is not such an evidence, I would like to strongly recommend
> to remove reference set from HPACK. This makes HPACK much simpler, so
> implementations gets bug less and inter-operability is improved. Plus,
> the order of headers is reserved always.
> 
> Regards,
> 
> --Kazu