Subject: incrementally indexed headers should be inserted in index '0' instead of len(table)+1

From: Roberto Peon <[email-masked]>
Date: Thu, 15 Aug 2013 13:00:25 -0700

https://github.com/http2/http2-spec/issues/233

####  summary of github issue chatter ###

Currently, index 0 is the 'top' of the table, and when a new header is
added using incremental indexing, it is added at the 'bottom' (i.e. the
highest number index).

This is potentially problematic from a compression-efficacy standpoint--
data analysis shows that newly added items are the most likely to be reused
or removed from the reference set, and thus most likely to be referred to
again.

This implies that we should change the spec to insert headers inserted via
incremental indexing into position '0' (i.e. the top)

 jpinner commenteda day ago

Does this also imply that eviction should occur from the "bottom" of the
table?

 grmocg commented21 hours ago

eviction from the bottom == oldest entry dies first when all one is using
is incremental indexing.

With substitution indexing, that isn't true. I'm happy with either one, but
I imagine that Herve might prefer one over the other.

 grmocg commented21 hours ago

And I'm fine with either, because I intend to only do incremental indexing,
since my research as shown it to be as good or better than substitution (at
least so far), and because I know that incremental indexing is suitable to
use in a world where we have something like TCP-minion or SCTP doing
out-of-order-delivery without HOL blocking at the compressor (with a couple
of small modifications).

 jpinner commented21 hours ago

Does the small modification require you to expose the sequence number?

 grmocg commented21 hours ago

Precisely!

 jpinner commented20 hours ago

An argument to drop substitution indexing from the spec?

 grmocg commented20 hours ago

Thusfar, we're assuming TCP transport, and I can imagine that substitution
has the capacity to help out there, but I imagine it wont help on
substrates like TCP-Minion, SCTP, etc. On those transports substitution
indexing probably hurts more than it helps.

#### end summary of github issue chatter ###

We absolutely should not close this issue without ensuring Herve has a
chance to chime in, but we can discuss for now. I can attempt to channel
Herve as much as possible in the interim (it will be a poor imitation
indeed, but better than nothing).

-=R

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Aug 2013 13:30:13 -0700

On 15 August 2013 13:00, Roberto Peon <[email-masked]> wrote:
> Currently, index 0 is the 'top' of the table, and when a new header is added
> using incremental indexing, it is added at the 'bottom' (i.e. the highest
> number index).

There are two separate issues here.  Strangely, the right decision
depends on the same question.  See below.

The first is whether the most recently added values should appear at
index 0 or index n when adding to the table.  This wouldn't matter at
all if it weren't for the fact that small values take less space to
encode.  So, any decision we make should be based on what we believe
is going to be reused more often: things that are added recently, or
things that have been present for a long time.  If it's recent items
that are being used more often, we probably need to add at index 0.

The second relates to eviction: which items be evicted from the header
table?  Those that were most recently added, or those that have been
around for a long time?  As I hinted before, this depends on the same
question.

Intuitively at least, I believe that there will be a split on the
header reuse question.  Some things, like :method=GET, are probably
going to be quite stable.  Other things, like cookies, tend to change
such that old values are invalid (Cookie in particular might be a good
candidate for substitution).  If there is a split, then I can imagine
that some optimizations could give good returns... maybe something
analogous to a generational garbage collector.  But then, I can't
imagine a way to avoid the resulting performance and complexity
issues.

But that's just analysis.  Testing might be an easier way to decide,
or at least to inform the choice.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 15 Aug 2013 14:06:45 -0700

I did this testing a while back (look for email entitled "Compression
analysis of perfect atom-based compressor").

Someone can hack something up to do this again on the new corpus, but the
data was pretty unequivocal.
I've attached a PNG version of the freq vs dist-from-newest-element graph.

Again, this was with a "perfect" FIFO-based compressor, which had no expiry
and infinite space over the test corpus (with each domain having a separate
compressor, but summing into the final total) that was available to us
before the new larger, if munged, corpus that was recently contributed.

This is a graph of the number of times that you'd like to have
backreferenced something (y-axis) at the distance from the newest element
(x-axis).
If we always found that we wished to backreference the 10th most recent
item (which is most certainly not the case, but IF), then this graph would
be a single spike at 10.

And here is the data.
I'd welcome someone computing this again!

-=R

On Thu, Aug 15, 2013 at 1:30 PM, Martin Thomson <[email-masked]>wrote:

> added

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Aug 2013 14:21:38 -0700

That's an interesting graph.  Let me just clarify two things:

1. Does this show the frequency distribution for the distance from the
current appearance of a given name/value pair to the most recent appearance
of the same pair.  Aren't we more interested in the distance to the first
appearance of the same pair?  Would it make sense to also have data on
distance between last appearance and first appearance as well (maybe we do
want the triangular distribution resulting from multiple consecutive
:method=GET pairings, and number of reuses is interesting, but duration of
usage is also interesting)?

2. When you say "distance", is this number of messages since last seeing
the same values, or is it the number of headers processed since seeing the
same value?

On 15 August 2013 14:06, Roberto Peon <[email-masked]> wrote:

> Again, this was with a "perfect" FIFO-based compressor, which had no
> expiry and infinite space over the test corpus (with each domain having a
> separate compressor, but summing into the final total) that was available
> to us before the new larger, if munged, corpus that was recently
> contributed.
>
>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 15 Aug 2013 14:35:31 -0700

inline

> usage is also interesting)?
Correct. This is the freq distribution for the most recent occurance of the
key/value pair that the compressor has just encountered.
i.e., the compressor is fed compressHeader(key, value), and this is the
distance to the most recent matching key, value

The distance to the first appearance is algorithmically the wrong thing to
do-- Why scan N, where N > k key-values when you can just scan k?
Also, if one wishes to create a 'constant effort' encoder, which is
interesting for security and real-time performance, then you want to be
scanning at most L items, and you'll want those L items to have the highest
probability of including the item you're hoping to compress.

I'd never stop someone from looking at it in the ways you suggest, though--
one could build a 'from the oldest-entry' freq table, which, who knows,
could possibly look the same (but I sincerely doubt it, given I
accidentally did this once :) ).
Another way of cutting the cookie would be to scan all entries, and
increment that bucket if it happens to be there. This would mean that more
than one bucket could be incremented per compressed key-value, but would
immuminate the places in-between...

> the same values, or is it the number of headers processed since seeing the

Number of key-value-pairs since that value had been seen, assuming
delta-encoding.

-=R

>> On Thu, Aug 15, 2013 at 1:30 PM, Martin Thomson <[email-masked]
>> > wrote:
>>

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Aug 2013 14:57:26 -0700

On 15 August 2013 14:35, Roberto Peon <[email-masked]> wrote:
>
> The distance to the first appearance is algorithmically the wrong thing to do

Actually I think that you've got the wrong end there.  You are
thinking about the code that you built to assemble this particular
graph.  However, if you want compression, you want to reference a
table entry multiple times.  The longer it lives in the table, the
better the compression.  Therefore, the longer the distance, the
longer the period you get to reuse value over.

Of course it's more expensive to scan back to the first appearance.
But you aren't doing that when compressing, you are just scanning back
to the point where the entry lives in the header table.  The distance
to which is bounded by the amount of memory you are allocating to the
table.

That said, counting the number of times as opposed to the span of time
is probably better.

---

From: Jeff Pinner <[email-masked]>
Date: Thu, 15 Aug 2013 15:08:08 -0700

isn't the point of delta-compression not to reference the entry again?

you reference user-agent once for example and then never again (and
hopefully it doesn't fall out of the table)

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Aug 2013 15:13:58 -0700

> isn't the point of delta-compression not to reference the entry again?

That's exactly my point.  :method is probably more interesting in that regard.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 15 Aug 2013 15:22:21 -0700

The point is to not reference it again, except to remove it or add it to
the reference set.
This actually happens often enough that the size of the representation of
the index causes a decent increase in the on-the-wire size.

-=R