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

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****
>>>
>>>    ** **
>>>
>>>
>>
>