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

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 <grmocg@gmail.com> wrote:

> 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 <akalin@google.com> wrote:
>
>> 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 <grmocg@gmail.com> wrote:
>>
>>> 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 <
>>> Michael.Bishop@microsoft.com> 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:grmocg@gmail.com]
>>>> *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" <akalin@google.com> 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 <grmocg@gmail.com> wrote:
>>>> ****
>>>>
>>>> Awesome!****
>>>>
>>>> The expiry mechanism should always be oldest item first.****
>>>>
>>>> -=R****
>>>>
>>>> On Sep 13, 2013 2:53 PM, "Fred Akalin" <akalin@google.com> 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.****
>>>>
>>>> ** **
>>>>
>>>> Comments, pull requests, etc. welcome!****
>>>>
>>>> ** **
>>>>
>>>> -- Fred****
>>>>
>>>>    ** **
>>>>
>>>>
>>>
>>
>