Subject: Header Table and Static Table Indicies Switched

From: Jeff Pinner <[email-masked]>
Date: Fri, 1 Aug 2014 10:20:33 -0700

Guessing I missed the discussion on this, but in the latest HPACK
draft the static table was to lower indices than the header table
instead of higher indices.

This now requires an extra byte (2 instead of 1) to index almost any
name not in the static table.

Opened https://github.com/http2/http2-spec/issues/578 to track.

---

From: Jason Greene <[email-masked]>
Date: Fri, 1 Aug 2014 12:35:18 -0500

This was discussed in "Call for Consensus: Remove "reference set" from HPACK (to address #552)”. Greg had a bunch of data showing static first was better.

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

---

From: Jeff Pinner <[email-masked]>
Date: Fri, 1 Aug 2014 10:37:30 -0700

Must have missed the connection between removing the "reference set"
and switching the table order.

I am happy to show data on how it is worse, specifically encoding
header names indices is now 200% worse ;)

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 08:39:13 +1000

> header names indices is now 200% worse ;)

Jeff,

I used the test data set and used header table sizes from 0 to 16KB.

There are 126 indexes that can be sent as a single byte, so the 61 static
entries take only half of those.   You have to have more than 65 indexed
headers before any two byte name indexes will be used.... and then it still
has to be a name that has not been used for one of those 65 custom entries.

Sure you can craft a data set that does end up using a lot of 2 byte name
indexes, but I'd be amazed if it was from anything approaching normal
traffic.

If there are are larger normal traffic data sets available, then I'm happy
to run the numbers again.

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: Jeff Pinner <[email-masked]>
Date: Fri, 1 Aug 2014 15:59:22 -0700

Greg,

I run a reverse proxy that handles things like authentication,
rate-limiting, etc. for the backend servers I talk to.

This means lots of custom headers that annotate requests with that information.

There are also lots of public APIs that use custom headers and these
have to all be proxied using names not in the header table. Here's a
google example:

https://developers.google.com/youtube/2.0/developers_guide_protocol_resumable_uploads

So the TL;DR is that in browser use cases, yes most of the headers
sent will be in the static table. But for APIs, internal requests,
etc. the majority of headers will not be :(

- Jeff

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 09:57:35 +1000

Jeff,

in that example, there are only 7  headers, 10 if you count the request
line ones.
Of those 6 will probably stay pretty constant over multiple requests, 1
might do and only 3 will change on most requests.  Of those, only 1 has a
custom header name, which looks constant over time.

Thus for requests like these, you are looking at around 20 requests on a
connection before the 2 custom header name with constant values are pushed
into the 2 byte index range.   The one that is constantly changing will
constantly be in the low index range as it will freshly be added every
request.

So I'm still not seeing how 2 byte name index's will be that common with
requests like that.  Even if they are, they will not be until after 20 or
so requests, by which time the slow start windows are opening up and
compression is less important.

But data is king - so perhaps you can get a sequence of real requests from
some real users and run the numbers.     I'd be surprised if the 2 byte
name indexes were significant, but your mileage may vary.

cheers

---

From: Roberto Peon <[email-masked]>
Date: Fri, 1 Aug 2014 17:53:47 -0700

I don't recall that particular change being something I saw consensus
about, and certainly something that the discussion (at least AFAICT) didn't
have a resolution for.

I think that the change is likely to decrease compressor efficiency, and it
*certainly* will for any algorithm which searches the state context first
to see if there are any exact matches.

In order to know which index one must use, one must scan the entire table
(didn't used to be the case with the reference set, but, that is gone) and
look for matches for each header. If one scans the static table first, then
one very likely wastes CPU. One can optimize a bit by only dong so if the
length of the value is < max_static_table_value_length

The new approach affords increased efficiency to the first request, at the
cost of decreased efficiency to any subsequent request.

I'll revert it as soon as possible.

-=R

---

From: Jeff Pinner <[email-masked]>
Date: Fri, 1 Aug 2014 18:02:18 -0700

> some real users and run the numbers.     I'd be surprised if the 2 byte name
> indexes were significant, but your mileage may vary.

Looking at the annotated headers for a single domain, on each request there are:

16 unique header names annotating authentication information
5 unique header names annotating rate-limiting information

Of those headers, all but 1 will take 2 bytes to encode, increasing
the size needed to reference just these names alone from 21 bytes /
request to 41 bytes / request.

---

From: Roberto Peon <[email-masked]>
Date: Fri, 1 Aug 2014 18:05:42 -0700

Actually, it doesn't afford any efficiency to the first request.
It affords more efficiency IFF more replacement happens than referencing
and replacement isn't done from the header table.

-=R
On Aug 1, 2014 5:53 PM, "Roberto Peon" <[email-masked]> wrote:

> I think that the change is likely to decrease compressor efficiency, and
> it *certainly* will for any algorithm which searches the state context
> first to see if there are any exact matches.
>

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 12:22:52 +1000

> about, and certainly something that the discussion (at least AFAICT) didn't
I think that this was a detail left to the editor once consensus was
declared on the removal of the reference set.  Like dropping the copy
etc.   There was discussion about which index was best to be low and I
provided some data on the public address set, but in the end it was the
editors call I think.

> to see if there are any exact matches.
Can we move beyond "I think".  This is something for which it is possible
to achieve real numbers.  This was done of a publicly available data set
that had been used for the basis of removing the RefSet in the first place,
and it indicated very little change either way with regards to the index.

ummmm  do you have the authority to do that?

more detail replies below

> length of the value is < max_static_table_value_length
Hash don't scan!

For my own implementation there is no lookup difference between having the
static indexes low or high.  But there is a benefit of having the static
headers at fixed index's as I can pre-generate the bytes.

> cost of decreased efficiency to any subsequent request.

Can you back up that assertion with any real numbers?   It is certainly not
the case for my own implementation as it does hash lookups for fields and
then names, so size of table nor length of index are factors in neither.
You need to create at least 65 unique fields before there is any additional
data cost, which I would then suggest is a tiny fraction of the cost of
sending 65 unique fields in the first place.

But show me a data set that it a good general case that indicates having
the indexes the other way around is better and if we are to make any
breaking changes after -14 then I'll support swapping back.

> and replacement isn't done from the header table.
Again, can you show any actual numbers?   For my own implementation, having
the indexes low is a marginal improvement (same lookups but less
branching).  In terms of data efficiency you need 65 custom indexed fields
before it makes any difference.

numbers please.

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 12:30:44 +1000

Jeff,

that is just not correct.

You get 65 entries in the header table that have 1 byte to encode.
That's quiet a lot of entries so before you can complain about 2 byte
indexes, you have to demonstrate how you will get to 65 entries  (without
using a dumb encoder that indexes fields that are used only once).

The evidence from the test data publicly available is that most connections
do not get to 65 entries in the header table.  Very few fields needed 2
byte lookups.

Perhaps there is an argument for being able to send an indexed literal name
with a null value, so we can add just the name to the header table for use
with custom fields whose value changes every request - but that is an
optimisation that equally applies regardless if static indexes are high or
low.

regards

---

From: Martin Thomson <[email-masked]>
Date: Fri, 1 Aug 2014 19:40:48 -0700

> ummmm  do you have the authority to do that?

Let's not get into recriminations.

How about we open a WGLC issue... (which Jeff already did for us:
https://github.com/http2/http2-spec/issues/578) and place the onus on
those who want the outcome to go a particular direction to produce
data to support their position.

Maybe folks who have public endpoints can run both alternatives
through some real data and report aggregate numbers.  There might be
enough time to collect some real data (maybe I can convince Nick to
setup a test in Firefox).

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 13:25:22 +1000

> that is just not correct.

Sorry Jeff,  slight correction to my correction.

For indexed fields there are 7 bits available.    These apply to custom
fields whose values do not change every request (eg X-GData-Key:
key=DEVELOPER_KEY), 65 entries are available in the header table that will
encode to 1 byte fields.

Literal fields with indexing have only 6 name bits available, so only 2 1
bytes dynamic field name entries are available.   However, if the field
value is changing every request, then an encoder should not be using the
indexed encoding anyway, as the field will not be used again.   This
encoding should only be used for fields that are expected not to change ie
ones that do not need a name index encoding.   Perhaps this encoding can be
used occasionally for a changing field to get a custom name into the header
table for use with literal fields without indexing, but that is not a high
frequency occurrence.

Literal fields without indexing have only 4 name bits available, so
regardless of the index ordering, many (most?) name indexes are going to be
2 bytes.    But at least the some common names of fields with changing
values  (eg :path) will be 1 byte.  Note that an argument could be made to
reorder the static table so other known fields with changing values (eg
content-length and  if-modified-since) will have index's <16, but I'd like
to see some data first to indicate that any such changes are significant.

I stand by to run the numbers on any data set that anybody can make
available to me.    I do have access to some live header streams, but
nothing that would make any significant usage of custom headers.

regards

---

From: Greg Wilkins <[email-masked]>
Date: Sat, 2 Aug 2014 14:44:09 +1000

I have redone the numbers with the latest -09 hpack draft and the hpack
test data (4K header table)

38037 fields are compressed to 33.4%

  18647 49% Indexed custom field 1B
   7817 21% Literal  indexed static name 2B. Not indexed.
   4075 11% Literal indexed custom name 1B. Indexed.
   3938 10% Indexed static field 1B
   1313  3% Literal index custom name 2B. Not Indexed.
    720  2% Literal index static name 1B. Not Indexed.
    674  2% Literal. Indexed.
    384  1% Literal index static name 2B. Not Indexed.
    321  1% Indexed custom field 2B
    148  0% Literal index custom name 2B. Indexed.

Switching the indexes so static are high makes very little difference:

38037 files are compressed to 33.7%

  18968 50% Indexed custom field 1B
   8097 21% Literal indexed static name 2B. Not Indexed.
   3938 10% Indexed static field 1B
   3661 10% Literal Indexed static name 2B. Indexed.
   1029  3% Literal Indexed name 2B. Not Indexed.
    674  2% Literal. Indexed.
    440  1% Literal Indexed static name 1B. Not Indexed.
    414  1% Literal Indexed static name 1B. Indexed.
    384  1% Literal Indexed static name 2B. Not Indexed.
    284  1% Literal Indexed custom name 1B. Not Indexed.
    143  0% Literal Indexed custom name 1B. Indexed.
      5  0% Literal Indexed custom name 2B. Indexed.

So for the available data, static low index is marginally better overall
compression (but probably not significantly so as 0.3% better is well
within the variability of cases).

The differences between the tests in terms of number of 2B names vs 1B
names is also marginal. The -09 draft has 22% 2B static names and  3% 2B
custom names, while switching results in 32% static 2B names and 1% 2B
custom names.

So to reduce 2% of 2B custom names to 1B, we increase static 2B names by
10%!    Not a winning exchange for this data set.  Indeed that pretty much
accounts for the extra 3193B resulting from the switched indexed.

If static header names are more frequent than custom ones (as you would
expect them to be), then I think this result will be pretty much the same
on most data sets.

cheers

---

From: Amos Jeffries <[email-masked]>
Date: Sat, 02 Aug 2014 18:18:37 +1200

On 2/08/2014 2:40 p.m., Martin Thomson wrote:
> On 1 August 2014 19:22, Greg Wilkins wrote:

Reads like a legitimate procedural query to me.

Now that we have WG LC does the editor still have authority to make
interoperability breaking changes without a consensus?

Or am I completely mistaking which draft(s) are in LC ?

Amos

---

From: Jeff Pinner <[email-masked]>
Date: Sat, 2 Aug 2014 08:26:09 -0700

> table for use with literal fields without indexing, but that is not a high

It is a high frequency occurrence when, just not on the public side of
the infrastructure. We tag every request with 16 headers that are of
the form:

X-Some-Very-Large-Header-Name: someSmall#

Since the names here are much larger than the values that change it is
worth putting these in the header table and keeping them there.

> to see some data first to indicate that any such changes are significant.

The majority of headers that I send are not the "common" once since
these get replaced with internal values for processing. None of which
are in the static table.

> nothing that would make any significant usage of custom headers.

Importantly though, for those headers in the static table that you do
use and insert into the header table, you can use those names at the
lower index.

So :authority for example, since it is likely to be common between
requests, will be inserted and then you can reference it again with 1
byte.

---

From: Jeff Pinner <[email-masked]>
Date: Sat, 2 Aug 2014 08:31:14 -0700

> expect them to be), then I think this result will be pretty much the same on
> most data sets.

This is my point, they are only more frequent on "public" data sets
since you are getting web browser requests that have to interop with
every website. For APIs or internal requests that is very referenced.

And for those that do appear, they will be indexed and thus get a lower index.

Consider this, for a client encoding requests, there is no reason to
use the index space for response header names that will NEVER be sent.
Putting the header table below the static table moves those request
headers that are indexed below the static table, pushing the response
names to a higher value.

---

From: Jeff Pinner <[email-masked]>
Date: Sat, 2 Aug 2014 08:55:43 -0700

Looking at request on an internal upload API that 12 internal header fields:

On the first request I measure no change in compression efficiency
(not surprising as all header names are unique so nothing is being
reused).

On the second request I measure a size reduction of 8% when switching
the header table to occur before the static table.

---

From: Martin Thomson <[email-masked]>
Date: Sat, 2 Aug 2014 13:37:39 -0700

> interoperability breaking changes without a consensus?

No.

My point was that finger pointing or standing on process doesn't
really help.  We should focus on the issues and see if we can resolve
them.  This seems to be a genuine point of contention, but one that
should be easy to resolve with facts.

---

From: Greg Wilkins <[email-masked]>
Date: Sun, 3 Aug 2014 09:44:17 +1000

> the header table to occur before the static table.

Is that 8% relative to just the second request?

The percentages I have been reporting have been relative to to the entire
data stream of all requests, so if comparing your 8% to the numbers I've
quoted, then it should be much less < 8%.     I'm not saying that is not a
valid way to report compression, I'm just making sure we don't compare
apples with oranges.

Also, I don't doubt that there are usage patterns for each index ordering
will be better or worse.  The question is, are such examples widely
representative?      We are never going to find a perfect compression that
is one-size fits all and whilst we are looking at compression savings of
60-70%, I think that any variation that is +/- <8% for particular data sets
is pretty much down among the noise!

cheers

---

From: Jeff Pinner <[email-masked]>
Date: Sat, 2 Aug 2014 18:55:08 -0700

> Is that 8% relative to just the second request?

It is the relative difference in the size of the second request after
compression.

That is if using the static table first the request compressed to 100
bytes and with the header table first it compressed to 92 bytes then
it is 8% smaller.

> is pretty much down among the noise!

The order of the tables has no impact on the difficulty of
implementation, it's basically a swap of the length checks and which
table you offset. Why would we give up 8% in compression for free?

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 3 Aug 2014 10:12:55 +0300

> table you offset. Why would we give up 8% in compression for free?

There is a trick to quickly extract individual headers (or small groups
of headers) out of compressed header block. It works if static table
comes before header table, but not vice versa (the reasons for this
involve interaction between eviction and Huffman).

But that trick would be mostly useless if Host is removed[1][2] given
that :headers are on front anyway and the trick can't deal well with
multi-valued headers (e.g. Cookie).

[1] The current spec seems to mix and match Host with :authority
with little pattern that I can figure out (or perhaps just EPARSE).

If both :authority and Host are route headers, that would cause
the following problems:
- What if the two disagree?
- Host seems much more expensive to process than :authority, due
  to being potentially near end of large header block (:authority
  is always near the begining).

[2] Or made to compress like :headers.

-Ilari

---

From: Greg Wilkins <[email-masked]>
Date: Sun, 3 Aug 2014 18:28:16 +1000

On 3 August 2014 11:55, Jeff Pinner <[email-masked]> wrote:

> Why would we give up 8% in compression

If that 8% is something general, then I don't think we should give it up
and I would be happy to swap back.

But you'd have to admit that your use-case of 16 headers like:

is unlikely to be a common case.   In the data I have, the usage of known
headers exceeds the usage of custom headers, so my numbers show that it is
better to favour known headers with 1B indexes.        I'd be very
surprised if general traffic was any different to that, but hopefully
somebody with access to some good generally representative data can provide
the data.... perhaps the same data set used to determine the huffman
encoding?

cheers

---

From: Jeff Pinner <[email-masked]>
Date: Sun, 3 Aug 2014 10:19:58 -0700

> If that 8% is something general, then I don't think we should give it up and
> I would be happy to swap back.
>
> better to favour known headers with 1B indexes.        I'd be very surprised
> if general traffic was any different to that, but hopefully somebody with
> access to some good generally representative data can provide the data....
> perhaps the same data set used to determine the huffman encoding?
>

The huffman encoding was derived from Chrome. I'd be more interested
if we could get numbers from the headers internal headers emitted from
say GFE rather than from those emitted from Chrome.

---

From: Martin Thomson <[email-masked]>
Date: Sun, 3 Aug 2014 10:53:21 -0700

> say GFE rather than from those emitted from Chrome.

I'd have said that GFE data would exhibit biases peculiar to Google
properties that might be detrimental to other users. More so than the
Chrome data.

The data set we got from the Chrome experiment might be less well suited to
private use - or probably more importantly, API use - than might be ideal,
but I don't see any easy way to avoid bias in collecting data from other
sources.

---

From: Johnny Graettinger <[email-masked]>
Date: Mon, 4 Aug 2014 14:07:02 -0400

I'm afraid that there is no Chrome data set, only the frequency table
result (which isn't useful here). The browser was instrumented to aggregate
character counts without collecting raw data.

On Sun, Aug 3, 2014 at 1:53 PM, Martin Thomson <[email-masked]>
wrote:

> The data set we got from the Chrome experiment might be less well suited
> to private use - or probably more importantly, API use - than might be
> ideal, but I don't see any easy way to avoid bias in collecting data from
> other sources.
>

---

From: Mike Bishop <[email-masked]>
Date: Mon, 4 Aug 2014 18:17:13 +0000

IIRC, the presence of both :authority and Host was primarily to permit the relay of HTTP/1.1 messages.  Here’s my reading of the spec, particularly 8.1.2.3, informed by what I remember from the discussion at the Bellevue interim:

·         :authority SHOULD be used (and Host omitted) on a message that was HTTP/2 from the start

·         When relaying a legacy message onto an HTTP/2 link:

o   Host conveys what was in the Host header, if present

o   :authority coveys what was in the authority portion of an absolute URI, if any; MUST be omitted if translating a relative URI or asterisk.

·         When relaying an HTTP/2 message onto an HTTP/1.1 link:

o   If Host is present, relay it

o   If not, copy the content of :authority

Mismatches are just as possible in HTTP/1.1 when the absolute format is used – what would you do if you got this request?

GET http://www.foo.com/index.html HTTP/1.1

Host:  bar.baz.com

The difference is that HTTP/2 requests SHOULD be sent in absolute format if natively generated, so the fact that a mismatch is possible is much more obvious.  RFC 2616 says that if the request URI is absolute, ignore Host.  RFC 7230 says they MUST match, but implies the same behavior by saying that the effective request URI is the target URI if the absolute-form is used.

-----Original Message-----
From: Ilari Liusvaara [mailto:[email-masked]]
Sent: Sunday, August 3, 2014 12:13 AM
To: Jeff Pinner
Cc: Greg Wilkins; HTTP Working Group
Subject: Re: Header Table and Static Table Indicies Switched

On Sat, Aug 02, 2014 at 06:55:08PM -0700, Jeff Pinner wrote:

> table you offset. Why would we give up 8% in compression for free?

There is a trick to quickly extract individual headers (or small groups of headers) out of compressed header block. It works if static table comes before header table, but not vice versa (the reasons for this involve interaction between eviction and Huffman).

But that trick would be mostly useless if Host is removed[1][2] given that :headers are on front anyway and the trick can't deal well with multi-valued headers (e.g. Cookie).

[1] The current spec seems to mix and match Host with :authority with little pattern that I can figure out (or perhaps just EPARSE).

If both :authority and Host are route headers, that would cause the following problems:

-Ilari

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 6 Aug 2014 15:22:36 +1000

> involve interaction between eviction and Huffman).

There is also another good benefit for encoding with static indexes low.
Because the index does not change for fields like Date and Server, you can
every second pre-encode the bytes for fields like:

  server: jetty-9.3.0
  date: Wed, 06 Aug 2014 05:19:19 GMT

With the static index's low, this pre-encoded value is the same for all
connection, as it is not a function of the size of the dynamic table of
each connection.   Thus the same pre-encoded value may be used 10s of
thousands of times, rather than encoding these fields on each and every
response for each and every connection.

cheers

---

From: Jeff Pinner <[email-masked]>
Date: Wed, 6 Aug 2014 08:07:22 -0700

> connection, as it is not a function of the size of the dynamic table of each
> connection.   Thus the same pre-encoded value may be used 10s of thousands
> of times, rather than encoding these fields on each and every response for
> each and every connection.
>
> cheers

you still pre-encode the huffman strings

are you talking about pre-encoding the index for "date" to 33 instead
of 33 + headerTable.length() ?

if so, i'd argue that the pre-encoded huffman buys you way more than
the bit of arithmetic before you copy into the send buffer and doing
the addition is well worth the tradeoff

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 07 Aug 2014 04:36:07 +1200

> the addition is well worth the tradeoff

Every table entry could have a huffman pre-encoded for its index number
and just dump that out.

The same optimization can be applied to both header orderings and the
remaining problem in that particuular calculation is the repeated acts
of addition when static follows dynamic.

Also, don't forget the effected context. When inserting/deleting into
dynamic table all the static entries have to be re-indexed on top of any
later dynamic entries. All unnecessary work when static comes first.

Amos