Re: Header Compression Clarifications

+1..  The additional complexity is minimal.
On Jul 4, 2013 11:07 AM, "Roberto Peon" <grmocg@gmail.com> wrote:

> The approach of add-then-enforce guarantee has a glaring and huge
> problem--  it cannot guarantee the amount of memory I'll use.
> I'd much rather deal with some small complexity (demonstrably not big)
> here and have that guarantee.
> -=R
>
>
> On Thu, Jul 4, 2013 at 6:09 AM, RUELLAN Herve <Herve.Ruellan@crf.canon.fr>wrote:
>
>> Trying to catch on the discussion, I see three proposals for solving the
>> problem of substitution and eviction.
>>
>> 1. Size adjustment BEFORE doing the substitution.
>> This has several edge case problems as James showed and would lead to
>> complex implementations.
>>
>> 2. Size adjustment AFTER doing the substitution.
>> The problem is that the new entry may be dropped just after adding it.
>>
>> 3. Size adjustment BEFORE doing the substitution with pinning of the
>> replaced entry (Roberto's proposal).
>>
>>
>> I think that 2 and 3 are in fact close together.
>> With 2, a bad encoder could just have its new entry dropped from the
>> table just after adding it. However a good encoder could use an algorithm
>> like the one propose in 3 to find the right entry to replace and prevent
>> dropping the new entry.
>> On the decoder side, 2 is simpler.
>>
>> Taking James' example for what a "good" encoder should do.
>> With existing table (max size 15)
>>   0: FOO = 123
>>   1: BAR = 321
>>   2: BA = Z
>>
>> The encoder wants to substitute: TESTING = FOO at Index #0 (because entry
>> #0 is old or whatever).
>> It detects that index #0 and #1 need to be dropped, and therefore adjust
>> the substitution to replace Index #2.
>> It then can apply the substitution, and after that adjust the size.
>>
>>
>> So my preference is for the second solution. True, it can lead to
>> under-optimal usage of the header table. But I'm not in favor of making all
>> implementations more complex to help optimize bad implementations.
>> We should however warn implementers of this problem.
>>
>> Hervé.
>>
>>
>> > -----Original Message-----
>> > From: James M Snell [mailto:jasnell@gmail.com]
>> > Sent: mercredi 3 juillet 2013 02:36
>> > To: Roberto Peon
>> > Cc: ietf-http-wg@w3.org
>> > Subject: Re: Header Compression Clarifications
>> >
>> > Yes, I was simplifying :-) I think that rule should work..
>> > particularly in that it allows me to avoid having to check for as many
>> of these
>> > weird edge cases.
>> >
>> > On Tue, Jul 2, 2013 at 5:27 PM, Roberto Peon <grmocg@gmail.com> wrote:
>> > > Correct (assuming the overhead per item was assumed to be zero, which
>> > > isn't the case, but is good in example-land :) )
>> > >
>> > > -=R
>> > >
>> > >
>> > > On Tue, Jul 2, 2013 at 5:18 PM, James M Snell <jasnell@gmail.com>
>> wrote:
>> > >>
>> > >> So to make sure I have it right... Given the two examples I gave...
>> > >>
>> > >>   Header Table, Max size = 15
>> > >>
>> > >>   1  A = B
>> > >>   2  C = D
>> > >>   3  E = F
>> > >>   4  G = H
>> > >>   5  I = J
>> > >>
>> > >>   Substitute #5 with FOOBARBAZ = 123456
>> > >>
>> > >> The result would be a Header table with one item "FOOBARBAZ = 123456"
>> > >>
>> > >> And...
>> > >>
>> > >>   Header Table, Max size = 20
>> > >>
>> > >>   1  A = B
>> > >>   2  C = D
>> > >>   3  E = F
>> > >>   4  G = H
>> > >>   5  I = J
>> > >>   6  K = L
>> > >>   7  M = N
>> > >>
>> > >>   Substitute #3 with FOOBARBAZ = 123456
>> > >>
>> > >> The result would be a Header table with three items...
>> > >>
>> > >>   FOOBARBAZ = 123456
>> > >>   K = L
>> > >>   M = N
>> > >>
>> > >> Is that correct?
>> > >>
>> > >> On Tue, Jul 2, 2013 at 5:07 PM, Roberto Peon <grmocg@gmail.com>
>> > wrote:
>> > >> > The biggest reason that I don't like this is that it requires the
>> > >> > encoder keep more state.
>> > >> > I prefer to make this simple by having an easy-to-follow rule for
>> > >> > when it the slot it would have replaced would have been evicted
>> > >> > (once all predecessors to that slot have been evicted, then
>> > >> > elements following the element-to-be-replaced are removed, leaving
>> > >> > the new element at the head of the list).
>> > >> >
>> > >> > The pseudo code for this is:
>> > >> >
>> > >> > if not replacement_idx or new_element_size > max_table_size:
>> > >> >   PROTOCOL_ERROR()
>> > >> > if max_table_size ==new_element_size:
>> > >> >   table.clear()
>> > >> >   table[0] = new_element
>> > >> >   return
>> > >> >
>> > >> > # above is boilerplate true for any algorithm
>> > >> >
>> > >> > table[replacement_idx].clear()
>> > >> > table[replacement_idx].pin()
>> > >> > first_non_pinned = 0
>> > >> > while new_element_size + table_byte_size() > max_table_size:
>> > >> >     if table[first_non_pinned].pinned():
>> > >> >       ++first_non_pinned
>> > >> >        continue
>> > >> >       table[first_non_pinned].pop()
>> > >> >
>> > >> > This adds some small complexity here, but it makes encoding
>> > >> > significantly easier (you can have a naive encoder which leaps
>> > >> > without looking, which is far less complicated than having to look
>> > >> > before leap, and may still prove reasonable in terms of compressor
>> > >> > efficiency).
>> > >> >
>> > >> > I admit that I'm attracted to your idea. I just am afraid of what
>> > >> > it makes the encoder look like :) -=R
>> > >> >
>> > >> >
>> > >> > On Tue, Jul 2, 2013 at 4:37 PM, James M Snell <jasnell@gmail.com>
>> > wrote:
>> > >> >>
>> > >> >> On Tue, Jul 2, 2013 at 4:00 PM, Roberto Peon <grmocg@gmail.com>
>> > wrote:
>> > >> >> [snip]
>> > >> >> >
>> > >> >> > So, an example:
>> > >> >> > Imagine that you're replacing entry #10 with something 10
>> > >> >> > characters long.
>> > >> >> > The previous entry in that slot was 5 characters long, and the
>> > >> >> > table was already at max size.
>> > >> >> > This implies that you need to get rid of 5 characters before
>> > >> >> > replacing.
>> > >> >> > Assuming that items 1 and 2 are the oldest items and item 1 is 3
>> > >> >> > chars, and item 2 is 3 chars, you need to pop two.
>> > >> >> >
>> > >> >> > You now stick the 10 characters into what was formerly entry
>> #10.
>> > >> >> >[snip]
>> > >> >>
>> > >> >> That's problematic too. Let's go back to my example:
>> > >> >>
>> > >> >> Header Table, Max size = 15
>> > >> >>
>> > >> >> 1  A = B
>> > >> >> 2  C = D
>> > >> >> 3  E = F
>> > >> >> 4  G = H
>> > >> >> 5  I = J
>> > >> >>
>> > >> >> Substitute #5 with FOOBARBAZ = 123456
>> > >> >>
>> > >> >> Obviously, we end up popping all five entries, saying "stick the
>> > >> >> new characters into what was formerly entry #5" does not make any
>> > >> >> sense because the thing that was "formerly entry #5" no longer
>> exists.
>> > >> >>
>> > >> >> Now a variation on the same problem:
>> > >> >>
>> > >> >> Header Table, Max size = 20
>> > >> >>
>> > >> >> 1  A = B
>> > >> >> 2  C = D
>> > >> >> 3  E = F
>> > >> >> 4  G = H
>> > >> >> 5  I = J
>> > >> >> 6  K = L
>> > >> >> 7  M = N
>> > >> >>
>> > >> >> Substitute #3 with FOOBARBAZ = 123456
>> > >> >>
>> > >> >> We begin popping things off to make room before doing the
>> > >> >> substitution... 4 entries are removed, including the item being
>> > >> >> replaced... leaving
>> > >> >>
>> > >> >> 1  I = J
>> > >> >> 2  K = L
>> > >> >> 3  M = N
>> > >> >>
>> > >> >> What exactly do we replace? Are we replacing "M = N" (the current
>> > #3)?
>> > >> >> If so, how does that sync up with the "thing that was formerly
>> > >> >> entry #3" idea?
>> > >> >>
>> > >> >> I think the only reliable approach is to substitute AFTER freeing
>> > >> >> up space, substitute into whatever is in the index position after
>> > >> >> freeing up space, and if nothing is in that space, return an
>> > >> >> error. This means that the sender has to be careful to avoid
>> > >> >> getting into this state in the first place, which means very
>> > >> >> careful control over when and how substitution is being used.
>> > >> >> Given the current eviction strategy, that would be the most
>> > >> >> reliable approach I think. So in the two examples above, the first
>> > >> >> case returns an error and the second case results in "M = N" being
>> > replaced.
>> > >> >
>> > >> >
>> > >
>> > >
>>
>>
>