Subject: delta compression I-D 01

From: Roberto Peon <[email-masked]>
Date: Wed, 13 Mar 2013 12:28:53 -0700

I posted an update to the delta header compression I-D yesterday (but
failed to put the tags on it that automatically marked it for HTTPbis.
*sigh*).

http://datatracker.ietf.org/doc/draft-rpeon-httpbis-header-compression/

I'm sure I've missed things and gotten some wrong, but I'm moderately happy
that it is mostly fleshed out.

-=R

---

From: James M Snell <[email-masked]>
Date: Wed, 13 Mar 2013 12:36:46 -0700

Excellent. The next step for me then is to update the java implementation
[1] based on this and get the new value encoding options tied in. I'll
review in detail later today but are there any major logic changes that
you've made in the process? It's been about two weeks since I last reviewed
your implementation.

- James

[1] https://github.com/jasnell/http2

On Wed, Mar 13, 2013 at 12:28 PM, Roberto Peon <[email-masked]> wrote:

> I'm sure I've missed things and gotten some wrong, but I'm moderately
> happy that it is mostly fleshed out.
>
> -=R
>

---

From: Roberto Peon <[email-masked]>
Date: Wed, 13 Mar 2013 12:39:42 -0700

No huge changes logically except that the implementation actually uses
canonical huffman codes, as spec'd.
I'm interested in seeing your variation on it with the alternate encoding
types!

---

From: James M Snell <[email-masked]>
Date: Wed, 13 Mar 2013 12:42:41 -0700

Give me about a week and it should be ready to go. I need to get the
huffman coding implemented stil and want to take another pass at optimizing
everything.

---

From: Fred Akalin <[email-masked]>
Date: Fri, 15 Mar 2013 17:47:55 -0400

For anyone interested, my test Javascript implementation is at
http://www.akalin.cx/http-2-header-compression . I also uploaded my repo to
https://github.com/akalin-chromium/httpbis-header-compression .

-- Fred

---

From: Fred Akalin <[email-masked]>
Date: Sat, 16 Mar 2013 21:09:35 -0400

Correction: I moved the test implementation to
http://akalin-chromium.github.com/httpbis-header-compression/ -- I might as
well let GitHub serve up the page since I uploaded the repository to it.

I'll remove it from my personal web space soon-ish.

On Fri, Mar 15, 2013 at 5:47 PM, Fred Akalin <[email-masked]> wrote:

> http://www.akalin.cx/http-2-header-compression . I also uploaded my repo
> to https://github.com/akalin-chromium/httpbis-header-compression .
>
> -- Fred
>
>

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 17 Mar 2013 08:17:44 +0100

Hi Roberto,

> http://datatracker.ietf.org/doc/draft-rpeon-httpbis-header-compression/

Great work, really !

I noticed this :
                  ('authorizations', ''),

I expect that you wanted to match the Authorization header instead, so
the trailing "s" should be removed.

I also have a few comments :

1) it's unclear to me how we can conserve key-value ordering in multiple
   key-value pairs. I mean, let's say we first have this :

   X-List: value1, value2, value3

Which is equivalent to :

   X-List: value1
   X-List: value2
   X-List: value3

It is then encoded as :

   [ ("X-List", "value1"),
     ("X-List", "value2"),
     ("X-List", "value3") ]

and stored as is on the recipient.

Then the list is changed to become :

   X-List: value4, value2, value3

So I guess the sender emits stoggl("X-List", "value1") then
skvsto("X-List", "value4"). But then I fear that X-List once
decoded will look like this :

   X-List: value2, value3, value4

which is different. Think about X-Forwarded-For across multiple
reverse-proxies where only the first value changes since it holds
the client's IP address. I think I'm missing something. Or perhaps
we should add opcodes to replace a specific key-value pair. 

2) I'm still seeing lots of zeroes in the output stream so I think
   we could compress it a bit better. From what I'm seeing in the
   pseudo-code, these two bytes are responsible for these "holes" :

       opcode = header_block.read_uint8()
       num_fields = header_block.read_uint8()

Thus I suggest that we could send a single byte with (opcode << 4) +
num_fields when numfields <  15 and that we only use the additional
byte for values 15 and above. It could then be done like this :

       byte       = header_block.read_uint8();
       opcode     = byte & 0xF;
       num_fields = byte >> 4;
       if (num_fields == 0xF)
           num_fields += header_block.read_uint8();
      
       byte       = header_block.read_uint8();
       opcode     = byte >> 4;
       num_fields = byte & 0xF;
       if (num_fields == 0xF)
           num_fields += header_block.read_uint8();

This way we would fall from two to one byte per opcode for most opcodes.

Last point, I like the static huffman table. It should allow most
decoders to automatically generate code to decode it without any
loop and produce an optimal branch prediction pattern for the CPU.

Cheers,
Willy