From: Roberto Peon <grmocg@gmail.com>

Date: Thu, 4 Jul 2013 11:07:28 -0700

Message-ID: <CAP+FsNe1qDFRSv1BW+visFRyH9q_0tu4SaRSzJF8BzzQZCNG2w@mail.gmail.com>

To: RUELLAN Herve <Herve.Ruellan@crf.canon.fr>

Cc: James M Snell <jasnell@gmail.com>, "ietf-http-wg@w3.org" <ietf-http-wg@w3.org>

Date: Thu, 4 Jul 2013 11:07:28 -0700

Message-ID: <CAP+FsNe1qDFRSv1BW+visFRyH9q_0tu4SaRSzJF8BzzQZCNG2w@mail.gmail.com>

To: RUELLAN Herve <Herve.Ruellan@crf.canon.fr>

Cc: James M Snell <jasnell@gmail.com>, "ietf-http-wg@w3.org" <ietf-http-wg@w3.org>

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. > > >> > > > >> > > > > > > > > >Received on Thursday, 4 July 2013 18:07:56 UTC

*
This archive was generated by hypermail 2.4.0
: Friday, 17 January 2020 17:14:14 UTC
*