Subject: #578: Header Table and Static Table Indices Switched

From: Mark Nottingham <[email-masked]>
Date: Fri, 26 Sep 2014 16:51:50 +0100

<https://github.com/http2/http2-spec/issues/578>

This hasn’t seen much discussion on list, and no one seems to have complained about it beyond Jeff.

Does anyone want to argue for changing this, or should we WONTFIX?

Regards,

--
Mark Nottingham   http://www.mnot.net/

---

From: Jeff Pinner <[email-masked]>
Date: Fri, 26 Sep 2014 09:05:28 -0700

FWIW I am still opposed to this having changed in the first place as I
have to deal with lots and lots of custom headers.

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 27 Sep 2014 07:07:45 +1000

I'm still very much in favour of the switch.  It has resulted in good code
simplications and enabled several optimisations.

I understand Jeff's concern, but essentially one size doesn't fit all and I
think Jeff's use-case is not the norm.   But even for Jeff's usecase, h2
headers should be far better than h1.

cheers

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Glen Knowles <[email-masked]>
Date: Fri, 26 Sep 2014 14:19:25 -0700

It would be better for me if they were switched back as well, for the same
reason -- a large corpus of internal custom headers. But it's marginal so I
can't get that excited about it either way.

---

From: Matthew Kerwin <[email-masked]>
Date: Sat, 27 Sep 2014 08:01:05 +1000

> headers should be far better than h1.

+1

-- 
  Matthew Kerwin
  http://matthew.kerwin.net.au/

---

From: Amos Jeffries <[email-masked]>
Date: Sat, 27 Sep 2014 17:12:58 +1200

On 27/09/2014 10:01 a.m., Matthew Kerwin wrote:
>> I'm still very much in favour of the switch.  It has resulted in
>> good code simplications and enabled several optimisations.
>> 
>> I understand Jeff's concern, but essentially one size doesn't fit
>> all and I think Jeff's use-case is not the norm.   But even for
>> Jeff's usecase, h2 headers should be far better than h1.
>> 
> 
> +1
> 

+1.

Amos

---

From: Roberto Peon <[email-masked]>
Date: Fri, 26 Sep 2014 23:08:50 -0700

It really needs to be changed back.
-=R

On Fri, Sep 26, 2014 at 10:12 PM, Amos Jeffries <[email-masked]>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.22 (MingW32)
>
> iQEcBAEBAgAGBQJUJkdaAAoJELJo5wb/XPRjR0cH/2tmIgP5a+TYZkgQ0fgCZH+3
> 439QVTQP0Iy07kxC/ZjZCE7j4iJyDbGfpLQg7BW2P3GikUpWhStKzh7AZAKA33zK
> rOUyRCI3gJWbmZMltlNzFdx4FQk7hVlyLck6J7NSyVgie31x42wvkxEW3+MFcB7g
> W5L3lO5JlPkmnrbBn23fgUXxjj67NMUaRSzEei7hyCoXZVncRTdmF1uU8e84V8MR
> LXuljOYEGhPUcGcPskQSssYHu2CMHUmFHnstDebEWV4g9yC2eD3pC07Tws0L0dpn
> 1JpxFcr02/fmN8DU5a3brQyYxDiutxBGb+pfI+A0kl+5pXj6tdFUbp1jZHIVgio=
> =T+s1
> -----END PGP SIGNATURE-----
>
>

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 27 Sep 2014 09:09:29 +0200

On Fri, Sep 26, 2014 at 04:51:50PM +0100, Mark Nottingham wrote:
> This hasn?t seen much discussion on list, and no one seems to have complained about it beyond Jeff.
> 

I think that if there are strong opinions in both directions, it deserves
being still studied openly. It's just a matter of encoding, variations are
possible (I proposed one some time ago, I don't know if it would have
addressed both usages).

Why not put numbers on the table. How many different non-standard headers
Jeff needs, etc...

I'd like that we don't release a protocol which causes significant
frustration to every single participant for one reason or another.
At least the schedule is not a valid response to tell these people
that they'll get a less efficient protocol for their use case, and
I'd expect that a short time later someone would have found the
best solution, so let's seek it now!

Willy

---

From: Mark Nottingham <[email-masked]>
Date: Sat, 27 Sep 2014 18:52:07 +0100

> possible (I proposed one some time ago, I don't know if it would have

I think the time for that has truly past; most of our implementers want to get this out the door and running, not do another round of R&D.

Jeff, you said “FWIW” — were you just telling us how you feel, or that you really think this needs to change?

In the latter case, we can do a call for consensus.

Regards,

---

From: Jeff Pinner <[email-masked]>
Date: Mon, 29 Sep 2014 16:02:54 -0700

> In the latter case, we can do a call for consensus.

I think that you will find this to be an issue for those implementers
running large sites. If you go with a consensus call I'm guessing
browsers will be a don't care, container providers (serverlets, Jetty,
etc.) will be -1, and large HTTP-RPC based services will be a +1
(Google, Twitter, Facebook, etc.)

---

From: "Simpson, Robby (GE Energy Management)" <[email-masked]>
Date: Tue, 30 Sep 2014 00:53:23 +0000

>>> Jeff's usecase, h2 headers should be far better than h1.

+1 - I think this boils down to the use of standard headers vs. custom
headers.  For my use cases, standard headers are more common and so I
prefer them to have lower indices.

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 30 Sep 2014 08:54:01 +0000

I did some quick experiments before putting the change in the spec.

The impact (of putting the dynamic table after the static table) is very small and positive for requests.
For responses, the impact is very small, positive or negative, for small maximum table size (1-4K). It becomes larger (still being small) and negative for medium table size (8-16K). It is reduced, still negative for larger table size (32K).

My analysis is that:
- For small table size, the number of entries is limited, and in both cases, indexes into the dynamic table always fit in 1 octet.
- For large table size, there are many entries, and in both cases, most indexes into the dynamic table need 2 octets.
- For medium table size, indexes into the dynamic table use either 1 or 2 octets, with roughly equivalent probability. Therefore, the ordering of the tables has an impact on the compaction.

My conclusion was, and still is, that the compaction impact was slightly negative, but very small and was more than balanced by the other benefits of putting the dynamic table after the static table.

Hervé.

> -----Original Message-----
> From: Willy Tarreau [mailto:[email-masked]]
> Sent: samedi 27 septembre 2014 09:09
> To: Mark Nottingham
> Cc: HTTP Working Group
> Subject: Re: #578: Header Table and Static Table Indices Switched
>

---

From: Jeff Pinner <[email-masked]>
Date: Tue, 30 Sep 2014 08:22:21 -0700

> I did some quick experiments before putting the change in the spec.

Experiments using what corpus? Again with a corpus that has more
custom headers than standard ones (as almost every request sent
between our backend servers does), the change almost doubled the
compressed size.

> My conclusion was, and still is, that the compaction impact was slightly negative, but very small and was more than balanced by the other benefits of putting the dynamic table after the static tabl…

What are these other benefits? I certainly don't believe there are any
-- having to know the size of the dynamic table to compute a static
index offset?

Why was the change put in, without a discussion on the list, when it
admittedly had a negative impact on compression in your testing?

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 1 Oct 2014 01:39:45 +1000

> -- having to know the size of the dynamic table to compute a static

At least one benefit is that you have the ability to pre compute values for
statics fields, or even series of static fields, so they do not need to be
calculated on every generation.
Now that we don't copy static entries to the dynamic field this generate
once use many times extends to fields using a static name and custom value.

> admittedly had a negative impact on compression in your testing?

There was definitely discussion on the list at the time.   It had also been
discussed previously and there were reasons not to make the change earlier,
but they evaporated with the removal of the reference set.

My tests (also published in the list) with test headers available (and used
for other decisions here) showed a small but positive change.

cheers

---

From: Jeff Pinner <[email-masked]>
Date: Tue, 30 Sep 2014 08:51:51 -0700

> once use many times extends to fields using a static name and custom value.

At most 4 headers can be used directly from the static table on a
single message (:method, :path, :scheme, and accept-encoding) since
none of the others have values, and that assumes the default values.

For any other headers (or these without default values), assuming they
are repeated between messages (likely given you are precomputing their
values as static fields), they will be inserted into the dynamic table
and their offsets will change as more headers are added.

Thus I don't see how you can realistically reuse them with a
precomputed offset, regardless of the location of the static table.

---

From: Jason Greene <[email-masked]>
Date: Tue, 30 Sep 2014 10:57:00 -0500

It’s probably not worth the added complexity, but we could add an HPACK control code to swap the tables. A compressor would then be able to pick the best compression for the dataset.

--
Jason T. Greene
WildFly Lead / JBoss EAP Platform Architect
JBoss, a division of Red Hat

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 1 Oct 2014 02:51:02 +1000

> precomputed offset, regardless of the location of the static table.

Firstly I think that there is good support for adding default values for
most of the static entries, which will further improve the compression for
the low static entries.

Then headers with static names and custom values don't need to be
indexed.   For example after this change Jetty generates a date field only
once per second with a static date name index and a huffman encoded date
value.   This precomputed field is then used 10's or 100s of thousands of
times in the next second.   Previously we had to recalculate that field for
each and every connection because the date name index was different for
every connection.

Similarly for the server header, we pre-compute and can send to every new
connection because we know what the server name index will be.

 Static content in the content cache can also pregenerate last-modified and
etag headers which again will get used on lots of different connections and
don't need to be regenerated.

Previously we had pre-generated headers for http1, but were not able to add
the mechanism for h2 because every field was always custom generated for
each connection.   After this change was made we were able to generalise
pre-generation for both h1 and h2 and this is a significant saving in
scalable servers.  EVEN IF the cost was larger headers they would be
worthwhile, but the average header appears to be the same or a little
smaller.

regards

---

From: Jeff Pinner <[email-masked]>
Date: Tue, 30 Sep 2014 15:55:00 -0700

> Then headers with static names and custom values don't need to be indexed.
> For example after this change Jetty generates a date field only once per
> second with a static date name index and a huffman encoded date value.
> This precomputed field is then used 10's or 100s of thousands of times in
> the next second.   Previously we had to recalculate that field for each and
> every connection because the date name index was different for every
> connection.

This isn't a compelling argument to me.

Without indexing, you can still re-use the huffman encoded data value
regardless of where the static table is.

And if you do index, to say share this value between responses on the
same HTTP/2 connection, then you have to lookup the offset even if the
static table comes first.

> connection because we know what the server name index will be.

Again here, you can none of the benefit of sharing the value amongst
multiple responses on the same connection. You are trading off
compression efficiency for not having to do a index lookup.

> worthwhile, but the average header appears to be the same or a little

So the TL;DR here seems to be you're not using indexing.

My response is to use indexing, it has low computational overhead and
you get much higher compression efficiency reusing these values.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 1 Oct 2014 09:31:15 +1000

Jeff,

in the examples I gave I'm using a mix of indexed and non-indexed fields.

For some fields, like date, it may be that we are sending them < once per
second to a large number of connections.  Indexing does not help.

For fields like Server, they still need to be sent initially on new
connections, so we pregenerate that version of them.

Yes we could just pre-generate only the field value, but our pregeneration
framework has to work for h1,spdy and h2.   It is setup to pregenerate
entire fields for code that does not know what protocols are being
spoken.    To break this down to separate header name and header value
pregeneration would double the handling we have to do for h1.   It is not
an option to have protocol specific code.

When implementing h2-12, we looked at pregeneration and we were simply not
able to do it without breaking h1.    With h2-14 we have been able to add
it easily for significant benefit and we are increasing the amount of
pregeneration we do in various situations as a result.   This is not a
theoretical efficiency but a real world deployed working code saving.

regards

On 1 October 2014 08:55, Jeff Pinner <[email-masked]> wrote:

> indexed.