Subject: JavaScript header compressor/decompressor updated to HPACK-03

From: Fred Akalin <[email-masked]>
Date: Fri, 13 Sep 2013 14:51:10 -0700

Hey all,

I updated
http://akalin-chromium.github.io/httpbis-header-compression/compressor_test.html
to
implement the HPACK-03 draft. In particular, I tried to make it a complete
an implementation as possible, and I added copious comments and references
to the spec to make it easy to validate and understand.

The only thing I didn't implement is UTF-8 validation for header values.
Hopefully, the need for that will go away.

Some thoughts:

- There aren't any tests. I wanted to see how correct I can make the
implementation without them (which will be measured when the compliance
suite comes out). I'm sure there are bugs.

- I didn't try very hard to make the encoder smart, but I did try to make
it exercise all the opcodes.

- I found it quite helpful that the encoding context was precisely defined
(as a header table plus the reference set). However, I ultimately found it
better to encode the reference set as part of the header table (by having a
bit per entry) instead of having a separate data structure, since it
eliminates a bunch of logic to keep the indices in the two in sync. This
may have been obvious to some people, but not to me. I wonder if it's in
the scope of the spec to suggest this.

- I also found it helpful to have a 'touch' flag per entry since
encoding/decoding requires processing of the untouched subset of the
reference set.

- For encoding I also needed to keep track of the number of touches
(representing the number of times the entry would be explicitly emitted),
and I needed to make a distinction between no touches and 0 touches
(representing an implicit emission). This is to support duplicate headers,
which was tricky to get right.

- It would be nice to have explicit bounds for encoded integers, string
lengths, header lengths, etc. I didn't try to make the encoder/decoder
streaming, since that would complicate the implementation, but it seems
difficult to guarantee memory bounds without the above explicit bounds.

- It would be nice to clarify the behavior when the max header table size
is reduced. I just implemented popping from the front until the new bound
is satisfied.

- I didn't find the need to encode index vs. index + 1 too confusing this
time around. I feel like making the header table start at 1 would simply
move the off-by-one bugs someplace else. I don't feel too strongly about
this, though.

Comments, pull requests, etc. welcome!

-- Fred

---

From: Roberto Peon <[email-masked]>
Date: Fri, 13 Sep 2013 15:16:36 -0700

Awesome!

The expiry mechanism should always be oldest item first.

-=R
On Sep 13, 2013 2:53 PM, "Fred Akalin" <[email-masked]> wrote:

> Hey all,
>
> I updated
> http://akalin-chromium.github.io/httpbis-header-compression/compressor_test.html to

---

From: Fred Akalin <[email-masked]>
Date: Wed, 18 Sep 2013 14:28:01 -0700

Just to clarify, is the oldest item the one with index 0, or some other
definition of oldest?

On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <[email-masked]> wrote:

>> - I found it quite helpful that the encoding context was precisely
>> defined (as a header table plus the reference set). However, I ultimately
>> found it better to encode the reference set as part of the header table (by
>> having a bit per entry) instead of having a separate data structure, since
>> it eliminates a bunch of logic to keep the indices in the two in sync. This

---

From: Roberto Peon <[email-masked]>
Date: Wed, 18 Sep 2013 14:33:34 -0700

If you added an item A at index 0, then B at 1, then substituted C in at 0,
then B is the oldest.

-=R
On Sep 18, 2013 2:28 PM, "Fred Akalin" <[email-masked]> wrote:

>>> - I didn't try very hard to make the encoder smart, but I did try to
>>> make it exercise all the opcodes.
>>>
>>> - It would be nice to clarify the behavior when the max header table
>>> size is reduced. I just implemented popping from the front until the new
>>> bound is satisfied.
>>>
>>> - I didn't find the need to encode index vs. index + 1 too confusing
>>> this time around. I feel like making the header table start at 1 would
>>> simply move the off-by-one bugs someplace else. I don't feel too strongly
>>> about this, though.
>>>

---

From: Mike Bishop <[email-masked]>
Date: Wed, 18 Sep 2013 21:54:55 +0000

In HPACK-03, section 3.2.4 says that "To achieve this [size within bounds], repeatedly, the first entry of the header table is removed, until enough space is available for the modification."  I don't see any references in the spec to "oldest" or entry age.

Or are we talking about different things?

From: Roberto Peon [mailto:[email-masked]]
Sent: Wednesday, September 18, 2013 2:34 PM
To: Fred Akalin
Cc: HTTP Working Group
Subject: Re: JavaScript header compressor/decompressor updated to HPACK-03

If you added an item A at index 0, then B at 1, then substituted C in at 0, then B is the oldest.

-=R
On Sep 18, 2013 2:28 PM, "Fred Akalin" <[email-masked]<mailto:[email-masked]>> wrote:
Just to clarify, is the oldest item the one with index 0, or some other definition of oldest?

On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <[email-masked]<mailto:[email-masked]>> wrote:

Awesome!

-=R
On Sep 13, 2013 2:53 PM, "Fred Akalin" <[email-masked]<mailto:[email-masked]>> wrote:
Hey all,

I updated http://akalin-chromium.github.io/httpbis-header-compression/compressor_test.html to implement the HPACK-03 draft. In particular, I tried to make it a complete an implementation as possible, and I added copious comments and references to the spec to make it easy to validate and understand.

The only thing I didn't implement is UTF-8 validation for header values. Hopefully, the need for that will go away.

Some thoughts:

- There aren't any tests. I wanted to see how correct I can make the implementation without them (which will be measured when the compliance suite comes out). I'm sure there are bugs.

- I didn't try very hard to make the encoder smart, but I did try to make it exercise all the opcodes.

- I found it quite helpful that the encoding context was precisely defined (as a header table plus the reference set). However, I ultimately found it better to encode the reference set as part of the header table (by having a bit per entry) instead of having a separate data structure, since it eliminates a bunch of logic to keep the indices in the two in sync. This may have been obvious to some people, but not to me. I wonder if it's in the scope of the spec to suggest this.

- I also found it helpful to have a 'touch' flag per entry since encoding/decoding requires processing of the untouched subset of the reference set.

- For encoding I also needed to keep track of the number of touches (representing the number of times the entry would be explicitly emitted), and I needed to make a distinction between no touches and 0 touches (representing an implicit emission). This is to support duplicate headers, which was tricky to get right.

- It would be nice to have explicit bounds for encoded integers, string lengths, header lengths, etc. I didn't try to make the encoder/decoder streaming, since that would complicate the implementation, but it seems difficult to guarantee memory bounds without the above explicit bounds.

- It would be nice to clarify the behavior when the max header table size is reduced. I just implemented popping from the front until the new bound is satisfied.

- I didn't find the need to encode index vs. index + 1 too confusing this time around. I feel like making the header table start at 1 would simply move the off-by-one bugs someplace else. I don't feel too strongly about this, though.

-- Fred

---

From: Roberto Peon <[email-masked]>
Date: Wed, 18 Sep 2013 15:58:07 -0700

Well, it is the way Herve and I designed it. The ordering of the header
table is not necessarily in index order. :/

I'd be perfectly happy to not have substitution, and not have the potential
confusion, but I'm fairly sure Herve would object :)

-=R

On Wed, Sep 18, 2013 at 2:54 PM, Mike Bishop
<[email-masked]>wrote:

>  In HPACK-03, section 3.2.4 says that “To achieve this [size within
> bounds], repeatedly, the first entry of the header table is removed, until
> enough space is available for the modification.”  I don’t see any
> references in the spec to “oldest” or entry age.****
>
> ** **
>
> Or are we talking about different things?****
>
> ** **
>
> *From:* Roberto Peon [mailto:[email-masked]]
> *Sent:* Wednesday, September 18, 2013 2:34 PM
> *To:* Fred Akalin
> *Cc:* HTTP Working Group
> *Subject:* Re: JavaScript header compressor/decompressor updated to
> HPACK-03****
>
> ** **
>
> If you added an item A at index 0, then B at 1, then substituted C in at
> 0, then B is the oldest.****
>
> -=R****
>
> On Sep 18, 2013 2:28 PM, "Fred Akalin" <[email-masked]> wrote:****
>
> definition of oldest?****
>
> ** **
>
> On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <[email-masked]> wrote:***
> *
>
> Awesome!****
>
> The expiry mechanism should always be oldest item first.****
>
> -=R****
>
> On Sep 13, 2013 2:53 PM, "Fred Akalin" <[email-masked]> wrote:****
>
>  Hey all,****
>
> ** **
>
> I updated
> to the spec to make it easy to validate and understand.****
>
> ** **
>
> Hopefully, the need for that will go away.****
>
> ** **
>
> Some thoughts:****
>
> ** **
>
> suite comes out). I'm sure there are bugs.****
>
> ** **
>
> it exercise all the opcodes.****
>
> ** **
>
> the scope of the spec to suggest this.****
>
> ** **
>
> reference set.****
> ** **
> which was tricky to get right.****
>
> ** **
>
> difficult to guarantee memory bounds without the above explicit bounds.***
> *
>
> ** **
>
> is satisfied.****
> ** **
> this, though.****
> ** **
> Comments, pull requests, etc. welcome!****
>
> ** **
>
> -- Fred****
>
>    ** **
>
>

---

From: Fred Akalin <[email-masked]>
Date: Wed, 18 Sep 2013 15:59:41 -0700

I thought that section refers only to eviction when appending/replacing
(which is definitely lowest index first) as opposed to eviction when
changing the max size (which isn't really treated in the spec).

On Wed, Sep 18, 2013 at 3:58 PM, Roberto Peon <[email-masked]> wrote:

> I'd be perfectly happy to not have substitution, and not have the
> potential confusion, but I'm fairly sure Herve would object :)
>
> -=R
>
>
> On Wed, Sep 18, 2013 at 2:54 PM, Mike Bishop <[email-masked]
> > wrote:
>
>> On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <[email-masked]> wrote:**
>> **
>>
>> Awesome!****
>>
>> difficult to guarantee memory bounds without the above explicit bounds.**
>> **
>>
>> ** **
>>

---

From: Roberto Peon <[email-masked]>
Date: Wed, 18 Sep 2013 16:10:40 -0700

Welp, it sounds like it is all a mess.
Expiring from the top or bottom all have their disadvantages as compared to
expiring the oldest.
LRU is arguably the best or next best, but nothing really plays nice with
indexing.

On Wed, Sep 18, 2013 at 3:59 PM, Fred Akalin <[email-masked]> wrote:

>> On Wed, Sep 18, 2013 at 2:54 PM, Mike Bishop <
>> [email-masked]> wrote:
>>
>>>  Just to clarify, is the oldest item the one with index 0, or some
>>> other definition of oldest?****
>>>
>>> ** **
>>>
>>> On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <[email-masked]> wrote:*
>>> ***
>>>
>>> Awesome!****
>>>
>>> make it exercise all the opcodes.****
>>>
>>> ** **
>>>
>>> difficult to guarantee memory bounds without the above explicit bounds.*
>>> ***
>>>
>>> ** **
>>>
>>> bound is satisfied.****
>>> about this, though.****

---

From: Fred Akalin <[email-masked]>
Date: Wed, 18 Sep 2013 16:21:36 -0700

I think we should have a consistent expiry policy for
append/replace/size-adjust. I guess we can discuss this at the next interim?

I'll hold off on implementing expire-oldest-first until we figure it out. :)

On Wed, Sep 18, 2013 at 4:10 PM, Roberto Peon <[email-masked]> wrote:

> Expiring from the top or bottom all have their disadvantages as compared
> to expiring the oldest.
>>>> If you added an item A at index 0, then B at 1, then substituted C in
>>>> at 0, then B is the oldest.****
>>>>
>>>> -=R****
>>>>
>>>> ****
>>>> The only thing I didn't implement is UTF-8 validation for header
>>>> values. Hopefully, the need for that will go away.****
>>>>
>>>> ** **
>>>>
>>>> Some thoughts:****
>>>>
>>>> ** **
>>>>
>>>> ****

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Thu, 19 Sep 2013 09:43:04 +0900

+1 to remove substitution.
But I really failed to read the spec as you mentioned "oldest" first in
substitution case.

---

From: Fred Akalin <[email-masked]>
Date: Wed, 18 Sep 2013 17:45:57 -0700

Hmm? The spec says to drop lowest index first for append or substitution:
see 3.2.4.