W3C home > Mailing lists > Public > ietf-http-wg@w3.org > July to September 2013

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

From: Martin Thomson <martin.thomson@gmail.com>
Date: Thu, 15 Aug 2013 13:30:13 -0700
Message-ID: <CABkgnnV1La4-EA8gO+FqOPY3i891J5E8u7dM8V2RRwangbw0Qw@mail.gmail.com>
To: Roberto Peon <grmocg@gmail.com>
Cc: HTTP Working Group <ietf-http-wg@w3.org>
On 15 August 2013 13:00, Roberto Peon <grmocg@gmail.com> 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.
Received on Thursday, 15 August 2013 20:30:41 UTC

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