Subject: Restore Header Table and Static Table Indices

From: Jeff Pinner <[email-masked]>
Date: Mon, 6 Oct 2014 08:02:44 -0700

As request by Mark, I propose that the current HPACK draft be changed
such that Sec. 2.3.3 Index Address Space reads,

"Indices between 1 and the length of the dynamic table (inclusive)
refer to elements in the dynamic table.

Indices strictly greater than the length of the dynamic table refer to
elements in the static table. The length of the dynamic table is
subtracted from the index into the static table."

with the associated diagram updated. This reverts the change made
between draft -08 and -09 in the change log, "Exchanged header and
static table positions."

---

From: Nicholas Hurley <[email-masked]>
Date: Mon, 06 Oct 2014 11:30:09 -0700

> between draft -08 and -09 in the change log, "Exchanged header and

I'm (still) a -1 on this. The change in 09 simplified both the spec and
the code implementing the spec, as well as making the common case (for
my users) more straightforward and efficient. I haven't seen anything
that convinces me the proposal does anything except make the uncommon
case (large amounts of custom header names) more efficient at the
expense of the common case.
-- 
Peace,
  -Nick

---

From: "Kulkarni, Saurabh" <[email-masked]>
Date: Mon, 6 Oct 2014 13:35:54 -0500

Same here, -1 on this. Our implementation (Akamai server) is much simpler
now because of this.

- Saurabh

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Mon, 06 Oct 2014 18:44:30 +0000

--------
>Same here, -1 on this. Our implementation (Akamai server) is much simpler

Same here: -1 on this.

Having the static table first is much simpler and no credible data
has shown that putting the dynamic table first will lead to overall
improvement of compression.

And if compression is that important, we can get much more of it by
compressing timestamps algorithmically than by flipping these two
tables.

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 7 Oct 2014 06:23:37 +1100

Thanks, Jeff.

I see people have already started to respond to this. 

Everyone else, please do the same — if you think this needs more discussion, please do so, but I think we’re at a point where people can just state their preferences.

Regards,

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

---

From: "Ludin, Stephen" <[email-masked]>
Date: Mon, 6 Oct 2014 14:58:22 -0500

-1 from me as well.  I can editorialize if need be but I will be rehashing what others are saying.

-stephen

From: Poul-Henning Kamp <[email-masked]<mailto:[email-masked]>>
Date: Monday, October 6, 2014 at 11:44 AM
To: "Kulkarni, Saurabh" <[email-masked]<mailto:[email-masked]>>
Cc: Nicholas Hurley <[email-masked]<mailto:[email-masked]>>, Jeff Pinner <[email-masked]<mailto:[email-masked]>>, HTTP Working Group <[email-masked]<mailto:[email-masked]>>
Subject: Re: Restore Header Table and Static Table Indices
Resent-From: <[email-masked]<mailto:[email-masked]>>
Resent-Date: Monday, October 6, 2014 at 11:44 AM

--------
In message <[email-masked]<mailto:[email-masked]>>, "Kulkarni, Saurabh" writes:
Same here, -1 on this. Our implementation (Akamai server) is much simpler
now because of this.

Same here: -1 on this.

--
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
[email-masked]<mailto:[email-masked]>         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe
Never attribute to malice what can adequately be explained by incompetence.

---

From: Michael Sweet <[email-masked]>
Date: Mon, 06 Oct 2014 16:44:28 -0400

Also -1.

> On Oct 6, 2014, at 2:44 PM, Poul-Henning Kamp <[email-masked]> wrote:
> 
> --------

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 7 Oct 2014 07:46:14 +1100

Also prefer to not switch back.

On 7 October 2014 06:58, Ludin, Stephen <[email-masked]> wrote:

> From: Poul-Henning Kamp <[email-masked]>
> To: "Kulkarni, Saurabh" <[email-masked]>
> Cc: Nicholas Hurley <[email-masked]>, Jeff Pinner <
> [email-masked]>, HTTP Working Group <[email-masked]>
> Resent-From: <[email-masked]>

-- 
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: Daniel Stenberg <[email-masked]>
Date: Mon, 6 Oct 2014 22:52:26 +0200 (CEST)

> Also prefer to not switch back.

... and another voice for not switching back.

-- 

  / daniel.haxx.se

---

From: "Simpson, Robby (GE Energy Management)" <[email-masked]>
Date: Mon, 6 Oct 2014 21:17:43 +0000

I too am a -1

---

From: Roberto Peon <[email-masked]>
Date: Mon, 6 Oct 2014 14:58:32 -0700

I'm a +1 on this.

The data thusfar shows that the current scheme significantly underperforms
the previously designed scheme when the headers to be used are not in the
current static set.

The complexity of adding an int to an int is low.
The amount of CPU necessary to add an int to an int is low.

The difference in performance in the non-idea case is large.

-=R

---

From: Mike Bishop <[email-masked]>
Date: Mon, 6 Oct 2014 22:00:16 +0000

Also -1.  We don't believe this introduces substantial gains for the common case, and would rather not take the churn for low return.

From: Ludin, Stephen [mailto:[email-masked]]
Sent: Monday, October 6, 2014 12:58 PM
To: Poul-Henning Kamp; Kulkarni, Saurabh
Cc: Nicholas Hurley; Jeff Pinner; HTTP Working Group
Subject: Re: Restore Header Table and Static Table Indices

-stephen

--------
In message <[email-masked]<mailto:[email-masked]>>, "Kulkarni, Saurabh" writes:
Same here, -1 on this. Our implementation (Akamai server) is much simpler
now because of this.

Same here: -1 on this.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 00:49:44 +0200

On Tue, Oct 07, 2014 at 06:23:37AM +1100, Mark Nottingham wrote:
> Everyone else, please do the same ? if you think this needs more discussion,
> please do so, but I think we?re at a point where people can just state their
> preferences.

I'm not strongly in either direction. I think the new design is simpler,
but I wouldn't want to see more failures in field later if we already have
one bad example. I do think that if we could shave one more bit somewhere
to be able to have a cheaper reference to the indexed headers, it would
satisfy everyone, and I'm pretty sure this could be achieved, probably
at the expense of making almost unused encodings more expensive. We need
to keep in mind that the compression has substantially changed since it
was designed and that maybe some combinations are not needed anymore but
their encodings are still assigned, thus could be reused for something
else to gain in efficiency.

I had sent two ideas about this subject that would probably deserve being
revisited here 3 months ago :

      http://article.gmane.org/gmane.ietf.http-wg/23155
      http://article.gmane.org/gmane.ietf.http-wg/23201

In both cases, the point is to be able to encode *at least* some indexed
header fields with low bits, and I think that would help in the case of
people who have many non-common headers. I guess this situation could
become more widespread on WAN links between many enterprises communicating
with web services because there it's common to see a lot of custom headers.

Regards,
Willy

---

From: Shigeki Ohtsu <[email-masked]>
Date: Tue, 07 Oct 2014 10:47:01 +0900

My preference is not to switch back it for implement simplicity, but I 
agree that  it does not have
a  good compression effciency  for a dynamic header not to be encoded in 
one byte intexed header rep.

I think the current number of static header entries is enough too large 
compared to the frequencies
  to be referred.  If we reduce a number of static header entries, it 
would be have a more chance for
a dynamic header to be referred in the index less than 63.

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 7 Oct 2014 14:14:42 +1100

On 7 October 2014 12:47, Shigeki Ohtsu <[email-masked]> wrote:

> If we reduce a number of static header entries, it would be have a more
> chance for

That could be a good compromise.  Seeing that three appears to be some
consensus to tweak the table a bit (add static values), then I'd certainly
consider dropping a few of the least frequent static entries to free up
some 1 byte encoding slots for some dynamic entries.

Is the original data used for the frequency analysis still available?   I'm
happy to extract the candidates to be dropped (and suggested values) from
the test data, but it is not that large and I don't know how representative
it is.

If somebody can make the data available, I'm happy to generate a pull
request for a static table with more values and a few less entries.

cheers

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 7 Oct 2014 15:24:45 +1100

That's not where we're at, Greg.

The current stance on changing the static table was that we'd do so *if* we've agreed to make other breaking changes. 

Thanks,

On 7 Oct 2014, at 2:14 pm, Greg Wilkins <[email-masked]> wrote:

> If we reduce a number of static header entries, it would be have a more chance for
> That could be a good compromise.  Seeing that three appears to be some consensus to tweak the table a bit (add static values), then I'd certainly consider dropping a few of the least frequent static entries to free up some 1 byte encoding slots for some dynamic entries.
> 
> Is the original data used for the frequency analysis still available?   I'm happy to extract the candidates to be dropped (and suggested values) from the test data, but it is not that large and I don't know how representative it is.
> 
> If somebody can make the data available, I'm happy to generate a pull request for a static table with more values and a few less entries.
> 
> cheers
> 
> -- 

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

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 07:28:47 +0200

On Tue, Oct 07, 2014 at 03:24:45PM +1100, Mark Nottingham wrote:
> The current stance on changing the static table was that we'd do so *if*
> we've agreed to make other breaking changes. 

But Mark, people's experience differ depending on the environment where
they deploy the protocol, so that means that the current status is too
white or too black and that possibly making it a little bit grayer would
make it more suitable for most environments. I don't see what's wrong
with considering feedbacks from real deployments, *even at this stage*.
Otherwise that means testers are useless and we should just work on
paper with a wet finger in the wind.

Willy, confused.

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 7 Oct 2014 16:41:06 +1100

Willy,

> paper with a wet finger in the wind.

We are certainly considering feedback from deployment, and we're also considering many other things. 

So far, the WG is strongly leaning towards not making a change here, and I don't see any overriding security or interoperability concern that would make a change at this late stage necessary.

We've discussed this many times, and had it confirmed by our Area Director; it's entirely appropriate to reject changes that don't meet this bar (either an overriding security or interop issue, or strong group consensus to make the change) at this point in the lifetime of the protocol.

Cheers,

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 07:49:17 +0200

On Tue, Oct 07, 2014 at 04:41:06PM +1100, Mark Nottingham wrote:
> So far, the WG is strongly leaning towards not making a change here,

No, the WG is strongly against *reverting* as it's the only option that
was offered. One user in a very specific case encounters issues, and one
of the HPACK authors thinks this radical change was a mistake. I think it
at least deserves being studied. I don't think either that reverting would
be a good idea, but I too think that one of the benefit of HPACK lies in
its ability to act as a cache of recently used header fields at a very low
cost, and the last change has increased this cost. Maybe just offering
provisions for 16 indexed headers instead of zero would significantly
improve the situation without affecting other users at all, but that
option was not offered yet.

> and I
> don't see any overriding security or interoperability concern that would make
> a change at this late stage necessary.
> 
> We've discussed this many times, and had it confirmed by our Area Director;
> it's entirely appropriate to reject changes that don't meet this bar (either
> an overriding security or interop issue, or strong group consensus to make
> the change) at this point in the lifetime of the protocol.

I understand this, but I just think that we should at least wonder whether
Jeff's case is unique (in which case we can decide to ignore it) or just a
preview of many new ones that the protocol will meet after the release. At
least thinking a bit could avoid this bitter late feeling of "too bad we
didn't do X or Y when the same issue was reported 6 months ago".

That's my point.

Willy

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 7 Oct 2014 16:54:01 +1100

Willy, if you have a concrete proposal that you think can can strong consensus, please make it ASAP. Stopping the work to do research on whether a change is necessary isn't appropriate at this point in the work; that train left the station a while ago.

Cheers,

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 08:16:50 +0200

On Tue, Oct 07, 2014 at 04:54:01PM +1100, Mark Nottingham wrote:
> Willy, if you have a concrete proposal that you think can can strong
> consensus, please make it ASAP. Stopping the work to do research on whether a
> change is necessary isn't appropriate at this point in the work; that train
> left the station a while ago.

I have proposed two directions in July and was told it was already too late.
I'm sorry for not having accurate details anymore in my mind 3 months later,
but that was the first one :

"
I'm noticing that we need only 4 bits to send any possible static header+value
(assuming we swap accept-charset and accept-encoding), since all other values
are empty and will never be used as-is but as litterals.

So I think that based on your suggestion to split indexing of static and
dynamic, I'm suspecting we could systematically split indexes between static
and dynamic in opcodes. Indeed, some index fields are already small (6+ for
litterals and 4+ for litterals not indexed/never indexed), so having the
static first will force one extra byte for all dynamic headers. However,
stealing one bit in unused value ranges could help make that situation
better. Something along these lines seems possible (please forgive me for
errors, I'm encoding as I write) :

  11 XXXXXX => send 6+indexed header from *dynamic* table as-is  (0xC0 reserved)
  10 01XXXX => send 4+indexed header from *static* table as-is   (0x80 reserved)

  00 00XXXX => send 4+indexed *dynamic* header without indexing (unchanged)
  10 00XXXX => send 4+indexed *static* header without indexing

  10 1XXXXX => send litteral based on *dynamic* header table (0=new name or reserved)
  01 XXXXXX => send litteral based on *static* header table (0=new name)

The idea is that even when we have few bits to encode the index, we're not
forced to add an extra byte to encode the values from the other table, whatever
table we pick first as first.
"

The second one was much simpler and Greg seems to favor it as well :

"
If at least we had the ability to encode both static table and most recent
dynamic entries with a single index, I would feel better. For example you
can have another approach :
  - positive indexes = static table index
  - negative indexes = - dynamic table index

You encode (index + 10), so that you can encode up to the last 10 emitted
fields, and you can encode up to 54 static headers in a single byte (it's
just a matter of proper sorting but it's already reasonably clean). I think
you get the idea.
"

Greg proposed to run some tests. I really think the second one is *very*
easy to test in a sane environment, and represents a very small change.
It ensures that commonly used fields do not need an extra byte, that recently
indexed headers do not need an extra byte either, and that only old indexed
headers or rarely used static headers need one. Right now I think that some
of the static header fields might be less common than a number of the ones
that are found in the indexed table, precisely because if they're in the
indexed table, they're being used!

Regards,
Willy

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 7 Oct 2014 17:26:08 +1100

Thanks, Willy.

Everyone, please extend the straw poll to include these two options -- who prefers one of them as the solution?

Regards,

---

From: Amos Jeffries <[email-masked]>
Date: Tue, 07 Oct 2014 19:48:08 +1300

On 7/10/2014 7:26 p.m., Mark Nottingham wrote:
> Thanks, Willy.
> 
> Everyone, please extend the straw poll to include these two options
> -- who prefers one of them as the solution?
> 
> Regards,
> 
> 

<snip>

>> http://article.gmane.org/gmane.ietf.http-wg/23201

If that level of change is going to be accepted I prefer this one.
With h2-14 draft text as second choice.

Notice that this design allows for parallel experimentation on the
static table contents, with a slightly larger static table size. So
the WG can switch in a new static table in a later draft without
affecting anybodies coded logic or algorithms.

Amos

---

From: <[email-masked]>
Date: Tue, 7 Oct 2014 09:45:30 +0000

> With h2-14 draft text as second choice.

+1

This email message is intended only for the use of the named recipient. Information contained in this email message and its attachments may be privileged, confidential and protected from disclosure. If you are not the intended recipient, please do not read, copy, use or disclose this communication to others. Also please notify the sender by replying to this message and then delete it from your system.

---

From: Nicholas Hurley <[email-masked]>
Date: Tue, 07 Oct 2014 09:10:45 -0700

I'm a big -1 on both of those options. They are both rather significant
changes that have no proof of viability behind them, and are even larger
changes than the one Jeff proposed (and in my estimation - take that for
what you will - have no place being considered at this stage of the
process). Note: this does not in any way mean I'm any more positive on
Jeff's proposed change.

-- 
Peace,
  -Nick

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 18:26:40 +0200

Hi Nicholas,

> process). Note: this does not in any way mean I'm any more positive on

For the first proposal I can understand, but for the second one, where's
the big change in just applying an offset to the index number (since it's
basically what it boils down to, by having only the tail of the static
header table not fit in the single-byte encoding) ?

Regards,
Willy

---

From: Nicholas Hurley <[email-masked]>
Date: Tue, 07 Oct 2014 09:35:32 -0700

> header table not fit in the single-byte encoding) ?

My issue is that it's totally untested, and the fact that we have
offsets at all in HPACK (the 1-based indexing versus most languages
being 0-based) has already caused enough interop problems in my
experience. It's silly, in my opinion, to introduce the possibility for
even more interop problems of the same ilk as those we have already
fixed. That's what makes it significant.
-- 
Peace,
  -Nick

---

From: RUELLAN Herve <[email-masked]>
Date: Tue, 7 Oct 2014 16:49:05 +0000

I did some quick testing and the second proposal from Willy has almost no impact on the compaction size (on the HR test set from the compression testing suite).

I implemented it in a slightly different way: I use a 1-bit flag to determine if an index is into the static table or the dynamic table. It seemed much simpler to implement and less prone to errors.

Hervé.

> -----Original Message-----
> From: Nicholas Hurley [mailto:[email-masked]]
> Sent: mardi 7 octobre 2014 18:36
> To: Willy Tarreau
> Cc: Mark Nottingham; HTTP Working Group
> Subject: Re: Straw Poll: Restore Header Table and Static Table Indices
>

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 7 Oct 2014 19:08:37 +0200

On Tue, Oct 07, 2014 at 04:49:05PM +0000, RUELLAN Herve wrote:
> I did some quick testing and the second proposal from Willy has almost no
> impact on the compaction size (on the HR test set from the compression
> testing suite).
> 
> I implemented it in a slightly different way: I use a 1-bit flag to determine
> if an index is into the static table or the dynamic table. It seemed much
> simpler to implement and less prone to errors.

That's what I wanted initially but didn't find a spare bit.
It would be nice if Jeff could pass you some example data which exhibit
the trouble he faces so that we know if that can fix his issue or not.

Thanks,
Willy

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 8 Oct 2014 10:32:07 +1100

I support the current h2-14 text, except that if we are making a breaking
change for other reason, then I support adding in values to the current
static table entries.

However, if we make a breaking change AND somebody can provide a large data
set that is widely accepted as representative, then I'm happy to contribute
time and effort to come up with an new optimised static table that may or
may not be a little bit smaller depending on results.

cheers

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 12 Oct 2014 17:59:33 +1100

There doesn't seem to be support for making a change here; most people were against any change, and while there were a few other proposals made, they didn't get broad support. Since this isn't a security or interop issue, I'm inclined to close as WONTFIX.

Does anybody have new information here, or can we move on?

Cheers,

---

From: Roberto Peon <[email-masked]>
Date: Sun, 12 Oct 2014 09:28:24 -0700

The current mechanism is highly suboptimal when not using the headers in
the static table.

There has been no technical argument refuting this-- all arguments have
shown that the previous arrangement was approximately on par for
static-table heavy workloads in terms of compression efficiency.

We have no guarantee that users will always wish to use the arguments in
the static table.
We know that adding to the size of the static table decreases efficiency of
the compressor for any item that would not be in the static table.

No-one has shown that the new scheme is significantly better in terms of
CPU or memory.

There was no interop issue w.r.t. the previous text.

In fact, the previous text allowed for the static table to be changed
easily in future versions, with guaranteed detection of mismatch when new
elements have been appended to the static table by one implementation but
not the other. This is not true of the current version, which would require
a negotiation in order to figure any such things out, and would otherwise
result in corruption.

As currently specc'd we're half-assing the compression, and we already know
a better solution and have specc'd, implemented and demonstrated interop
with it.
-=R

On Sat, Oct 11, 2014 at 11:59 PM, Mark Nottingham <[email-masked]> wrote:

> There doesn't seem to be support for making a change here; most people
> were against any change, and while there were a few other proposals made,
> they didn't get broad support. Since this isn't a security or interop
> issue, I'm inclined to close as WONTFIX.
>
> > Everyone else, please do the same — if you think this needs more
> discussion, please do so, but I think we’re at a point where people can
> just state their preferences.
> >
> > Regards,
> >
> >

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 13 Oct 2014 11:16:27 +1100

Roberto,

I do understand that you and Jeff would prefer the compression bias to be
towards dynamic headers, but what I don't understand is the strength of
that preference.      You are so strongly in favour of reverting the
indexing that I feel that I must be missing something?   The compression
achieved by hpack regardless of the indexing is excellent.

I know that Mark is heavily leaning towards WONTFIX on this one - but I'd
be very interested to hear your thoughts on the proposed compromise of
reducing the size static table so that there are at lease a few 1 byte
index's available for dynamic headers and dynamic header names.  If we
opened up say 8 slots to be available for 1 byte dynamic index's (and added
static values at the same time), do you feel that would go some way to
addressing your concerns, or would it still be insufficient?    Do you have
some example header sets you can share with me so I can do some
experimentation?

To respond to your specific points:  I think that "highly suboptimal" is
over stating the situation.   Dynamic headers can still be reduced to a 2
byte index, which is a vast improvement over http/1.   There was technical
evaluation using the available test data an it did show a general
improvement with the low static indexes and that variations were essential
down among the noise considering the huge savings both approaches already
achieve.

I believe I have explained how the new scheme has allowed significant CPU
and memory savings in my server and there have been reports from other
implementers of code savings.     I cannot prove that such savings are only
available with the low index, and theoretically I might be able to achieve
some of them with reverted indexing.  However the reality we were not able
to achieve those savings with the high static indexing, despite there being
significant benefits if we could (and we did try). We have been able to
achieve them with the low index's.  I know this is not proof, but I think
it is good circumstantial evidence.

regards

On 13 October 2014 03:28, Roberto Peon <[email-masked]> wrote:

> We know that adding to the size of the static table decreases efficiency
> of the compressor for any item that would not be in the static table.
>
> As currently specc'd we're half-assing the compression, and we already
> know a better solution and have specc'd, implemented and demonstrated
> interop with it.
> -=R
>

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

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 13 Oct 2014 11:52:43 +1100

Roberto,

So far, we've had a large number of people -1 any change here. Summarising:

* It's been asserted that the current approach is "much simpler" to implement
* The difference is "marginal" 
* There's concern about "churn" in the spec and implementations
* There's concern that the proposals are untested 

You say it's "highly suboptimal", but you don't back this up. Indeed, we've long established that the WG is not terribly interested in getting the *most* efficient compression available -- especially if it's bought with complexity. As Mike said once long ago, the important part is that we get *some* compression, and my perception is that there's wide agreement in the WG on that point.

In the face of that, a one-byte overhead for dynamic headers is hard to characterise as "highly suboptimal."

Other folks have discussed / proposed more elaborate changes than Jeff, but I detect very little stomach in the WG for doing so.

At most, I think we're at a point where the most reasonable thing to do, *if* we do anything here, would be to revisit the static table and "make room" for more dynamic entries by pruning it some, as per <https://github.com/http2/http2-spec/issues/587>.

However, as discussed before, we'd need to see broad support for such a change; so far, we've held that #587 will only happen if we're making other breaking changes.

Regards,

On 13 Oct 2014, at 3:28 am, Roberto Peon <[email-masked]> wrote:

> The current mechanism is highly suboptimal when not using the headers in the static table.
> 
> There has been no technical argument refuting this-- all arguments have shown that the previous arrangement was approximately on par for static-table heavy workloads in terms of compression efficiency.
> 
> We have no guarantee that users will always wish to use the arguments in the static table.
> We know that adding to the size of the static table decreases efficiency of the compressor for any item that would not be in the static table.
> 
> No-one has shown that the new scheme is significantly better in terms of CPU or memory.
> 
> In fact, the previous text allowed for the static table to be changed easily in future versions, with guaranteed detection of mismatch when new elements have been appended to the static table by one implementation but not the other. This is not true of the current version, which would require a negotiation in order to figure any such things out, and would otherwise result in corruption.
> 
> 
> As currently specc'd we're half-assing the compression, and we already know a better solution and have specc'd, implemented and demonstrated interop with it.
> -=R
>

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 13 Oct 2014 03:23:26 +0200

Hi Mark,

On Mon, Oct 13, 2014 at 11:52:43AM +1100, Mark Nottingham wrote:
> You say it's "highly suboptimal", but you don't back this up. Indeed, we've
> long established that the WG is not terribly interested in getting the *most*
> efficient compression available -- especially if it's bought with complexity.

I think the complexity that was lost with the change was the copy from static
to dynamic. In fact, swapping static and dynamic was done only to get smaller
indexes on static that can now be compressed in one byte, possibility that was
previously offered to dynamic headers only. What we really need to satisfy all
users is to be able to encode *most common* static headers with 1 byte, and
a number of dynamic headers with 1 byte as well.

> As Mike said once long ago, the important part is that we get *some*
> compression, and my perception is that there's wide agreement in the WG on
> that point.

I also agree with this.

> characterise as "highly suboptimal."

I wouldn't be as categoric as Roberto here but I understand his point. The
previous design allowed headers not belonging to the static table to be
correctly compressed (whatever X-* headers appearing inside companies).
The new one makes new headers less efficient than the static ones, and I
think Roberto sees less possibilities of future improvements with this
design.

> Other folks have discussed / proposed more elaborate changes than Jeff, but I
> detect very little stomach in the WG for doing so.
> 
> At most, I think we're at a point where the most reasonable thing to do, *if*
> we do anything here, would be to revisit the static table and "make room" for
> more dynamic entries by pruning it some, as per
> <https://github.com/http2/http2-spec/issues/587>.

It's more or less similar to what I suggested as well to what I proposed except
that we don't need to *prune* some entries if the single-byte encoding covers
part of both tables.

> However, as discussed before, we'd need to see broad support for such a
> change; so far, we've held that #587 will only happen if we're making other
> breaking changes.

The problem when there are implementations available is that developers know
what it means for them to have to modify them : modify both encoders and
decoders in multiple products, plan certain outages etc... The problem is
that we need to be careful about future users, not early adopters, and all
of us have to think about how efficient the protocol will be in 1-10 years,
not just right now in implementations that will inevitably evolve in the
following months.

I personally think that the single-byte encoding of *some* dynamic headers
has a real value, and even if people are not pleased with revisiting their
code, we should do something for it.

Best regards,
Willy

---

From: Roberto Peon <[email-masked]>
Date: Tue, 14 Oct 2014 10:17:27 -0700

Sorry for the slow response; been a little sick over here. At least my
voice sounds cool, not that most of you will have heard it.

My concern comes from an assumption that we'll use HTTP/2 for more than
just browsing, i.e. that it will see major use for non-web RPC protocols
both internal to networks, and between networks (i.e. RPCs to/from "the
cloud" and whatever it evolves to in the future).
The current compression scheme can end up having twice the amount of bloat
in terms of headers per request, even when these headers are used with much
greater frequency than the current set of static headers.
One byte more overhead is significant when the amount of overhead was
typically one byte to begin with, and not with huge changes in complexity.

On complexity:
The removal of the reference set removed the lion's share of complexity in
the previous set of changes.

The changing of the indexing, however, did not remove significant
complexity.
The total change in complexity resulting from the change of indexing can be
summarized as:

Previously:
  References to the static set are:
    dynamic_set_len + static_set_offset
  References to the dynamic set are:
    dynamic_set_offset

And with the spec as it stands now:
  References to the static set are:
      static_set_offset
  References to the dynamic set are:
      static_set_len + dynamic_set_offset

So, at worst, we're talking about adding an int instead of adding a const.
The worst possible impact of this means that one cannot bit-blit a large
number of static headers-- one must add them one at a time or fix them up.
I'll bet that I can show that this makes almost zero difference in CPU when
implemented properly (there is little magical about a bit-blit to begin
with)-- I'd be shocked if we couldn't do 100s of millions of header-sets
per second on a single core.

With the spec as it stands today w.r.t. indexing (which, again, was not a
change that we'd agreed on doing), we lose out in flexibility in the long
term.
"New" headers become significantly disadvantaged over the ones currently in
there, and are very likely to occur in a number of non-web deployments.
Adding new headers into the static set in the future with the current
scheme decreases overall dynamic efficiency. It is no longer a low-cost,
high reward decision.

-=R

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 14 Oct 2014 18:57:43 +0000

--------
In message <[email-masked]>

>So, at worst, we're talking about adding an int instead of adding a const.

It also means that the headers typically used by high-performance
load-balancers have variable numbers, rather than fixed numbers.

That makes a BIG difference at the highest performance levels,
in particular for hardware assist.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 14 Oct 2014 23:11:27 +0200

> in particular for hardware assist.

While in theory I agree that this is something to be considered for
*hardware* implementations, in practice the cost remains extremely
low by todays technologies. A typical 32-bit adder implemented in
45nm is 130 picoseconds [1]. Cut that in half for 16-bit. That's
with outdated technology already and not pipelined at all. In short,
it shows that a simple ASIC implemented with 2011 technology would
face a hard limit of 7-14 billion headers per second simply due to
this, so in this precise case I think that does not count, especially
if we compare this to the cost of emitting the resulting data. But
in general I tend to be very picky about microscopic costs that can
significantly limit high speed processing!

Best regards,
Willy

[1] http://www.mattkeeter.com/research/jackson.pdf

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 15 Oct 2014 13:37:15 +1100

On 15 October 2014 04:17, Roberto Peon <[email-masked]> wrote:

> typically one byte to begin with,
>

Well if looked at in that way, removing the reference set was an increase
of 0 bytes to 1 byte for many headers, so an infinite increase in size.
Yet when looked at overall, the impact was negligible.

I agree that we need good efficient compression for dynamic headers, and am
willing to consider changes to ensure we get the balance right (such as
reducing the static table).  But I think that switching the index's back
adjusts the balance too far away from the very common use case of static
headers and static header names.

Here are my numbers for the test data run with h2-14, then removing the
suggested static headers (except Date), then adding in the suggested static
values:

  *size* *H2-14* *reduced* *values*  0 63.50% 64.40% 62.10%  4096 34.50%
34.20% 33.50%  8192 33.20% 32.70% 32.60%  12288 33.30% 32.60% 32.50%
So for the test data, reducing the static table size has hardly any affect
and by adding in values, the effect is often slightly positive.    So such
a change looks to at least do no harm.     Question is, does it do any good
for lots of dynamic headers - I'm happy to try answer that, but can do so
only if somebody can give me some test data to run against.

> number of static headers-- one must add them one at a time or fix them up.

Not just static headers, but dynamic headers that use static names.

> I'll bet that I can show that this makes almost zero difference in CPU
> when implemented properly (there is little magical about a bit-blit to
> begin with)-- I'd be shocked if we couldn't do 100s of millions of
> header-sets per second on a single core.
>

While I'm sure that dedicated code can be written to generate h2 headers
very quickly, the reality is that servers are not written to be dedicated
to h2.   The fast bulk of the header generation and handling code is
written protocol neutral and has to work for  http, spdy, h2, fastcgi,
etc.   In that environment we have found it extraordinary difficult to
introduce header pre-generation when the bytes generated are a function of
the connection and sequence that the header will be sent.   For example, we
regenerate headers when we move a static resource into the cache, which is
done without reference to any particular protocol or connection.      While
the actual operation of customising a header for a particular connection
might just be a lookup and an add, there is a lot of complexity required to
work out when and if this addition is needed and bringing all the required
information to the correct point in the code.

I know this is a specific example, but I am sure that in general far better
and simpler optimisations can be done with encodings that are immutable
rather than with ones that are a function of connection and time.

regards

---

From: Adrian Cole <[email-masked]>
Date: Tue, 14 Oct 2014 21:22:21 -0700

I suppose I'm pretty biased in-so-far as most work I've done in the
last several years has been on http apis, not regular browser stuff.

For example, a cloud portability project with about 3 dozen api
deviants, almost all of which had several custom headers and often a
prefixed encoding scheme for user metadata.. maybe a Link header for
pagination, etc.

It could be possible to make some sort of story collector for RPC
apis, but it would be much more specific than browser traffic.  Ex.
PUT blob with user metadata, read them back with HEAD, etc. or 1000x
POST /servers with a shell script encoded in a header.  or turn on
debug logging on your android app, run a scenario that now has 7 extra
headers, etc.

Internal RPC use of headers is even less likely to be publicly
inventory-able. Ex. turn on request tracing and watch these two
intermediaries add side-channel headers.

I don't many would doubt this stuff exists and is commonplace in apis.
That doesn't change the fact that these scenarios aren't as easy to
inventory and create a test database out of, which we could use for
performance simulations.

IOTW, if we needed a test database to justify flipping back the
indexing, then we might as well call it game over and move on.

If we agree that api stuff does in fact use a lot of non-standard
headers, and we believe flipping back doesn't maim normal web, could
that be a strong enough case to revert?

As many have pointed out, this part of the implementation is easy, but
I can see how folks would be apprehensive about even doing a sensible
change due to reasons Mark clearly summarized.
-A

On Tue, Oct 14, 2014 at 10:17 AM, Roberto Peon <[email-masked]> wrote:
> Sorry for the slow response; been a little sick over here. At least my voice
> sounds cool, not that most of you will have heard it.
>
> My concern comes from an assumption that we'll use HTTP/2 for more than just
> browsing, i.e. that it will see major use for non-web RPC protocols both
> internal to networks, and between networks (i.e. RPCs to/from "the cloud"
> and whatever it evolves to in the future).
> with)-- I'd be shocked if we couldn't do 100s of millions of header-sets per
> second on a single core.
>
>
> Adding new headers into the static set in the future with the current scheme
> decreases overall dynamic efficiency. It is no longer a low-cost, high
> reward decision.
>
> -=R
>
>
>

---

From: Adrian Cole <[email-masked]>
Date: Tue, 14 Oct 2014 21:36:38 -0700

+1

For apis, this makes a lot of sense, as often custom headers equal or
outnumber ones in the static table.
This part of the implementation is easy, so churn isn't an issue for
me personally.

On Mon, Oct 6, 2014 at 2:58 PM, Roberto Peon <[email-masked]> wrote:
> On Mon, Oct 6, 2014 at 2:17 PM, Simpson, Robby (GE Energy Management)
> <[email-masked]> wrote:
>>
>> I too am a -1
>>

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 15 Oct 2014 15:59:29 +1100

> that be a strong enough case to revert?

I don't think we should set this up as standard headers vs dynamic
headers.   Both have
very valid use-cases and it is impossible to say which is more deserving of
the 1 byte
slots.   Simply flipping back just changes the bias and causes other
problems.

If an argument can be made that 2 byte encodings are still too large for
dynamic headers, then instead
of flipping back let's investigate how the 1 byte slots can be shared
between static and dynamic.
Reducing the size of the static table does not appear to have drastic
effects on compression, so if the
slots thus freed are a benefit for dynamic headers then we have a good
compromise.

I'm also OK with the status quo, as I think we are talking +/- 1% when we
are already saving >60%
But I'm happy to run the data if people think it is more than 1%.

cheers

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 15 Oct 2014 07:01:03 +0200

Hi Adrian,

> that be a strong enough case to revert?

Please to be clear, noone suggests to flip back to what we previously
had, there's no question about reintroducing the reference set whose
removal has considerably simplified developers' experience. The idea
is just to ensure that *at least* some dynamic headers can be encoded
with a single byte so that all the future headers that are not part of
the static set are not penalized so much as what Jeff observes.

Regards,
Willy

---

From: Adrian Cole <[email-masked]>
Date: Tue, 14 Oct 2014 22:07:41 -0700

Yep. Thanks for being clearer than me. Willy. I didn't mean flipping
back as reintroducing the reference set. I'm actually quite happy
that's gone as a developer: it led to deleting some gnarly things.

---

From: Adrian Cole <[email-masked]>
Date: Tue, 14 Oct 2014 22:11:46 -0700

> between static and dynamic.
FWIW, I'm happy to implement an alternate approach, if one comes out.
Thanks, Greg.

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 15 Oct 2014 18:20:00 +1300

On 15/10/2014 6:11 p.m., Adrian Cole wrote:
>> If an argument can be made that 2 byte encodings are still too
>> large for dynamic headers, then instead of flipping back let's
>> investigate how the 1 byte slots can be shared between static and
>> dynamic.
> FWIW, I'm happy to implement an alternate approach, if one comes
> out. Thanks, Greg.
> 

Alternative approach has already been proposed. That the first bit of
the index is used as a flag to indicate static or dynamic table for
the remaning 7+ bits.

That not only puts both on an even bias, but expands the range of
values getting 1-byte encodings in either table and removes the need
for the math complexity people are disliking.

1 stone, 3 birds.

(The paranoid in me can only think that it is being repeatedly
rejected despite evidence of its usefulness because of who proposed it.)

Amos

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 15 Oct 2014 05:32:29 +0000

--------
In message <CAHzwyDuuN=-DyGiWAfttwq7O_zUGOE=7kVf5J=[email-masked]>
>FWIW, I'm happy to implement an alternate approach, if one comes out.

Seriously...

If we are that worried about compression-ratio, we should compress
Date: and other timestamp headers to a 32 bit integer.

---

From: Adrian Cole <[email-masked]>
Date: Tue, 14 Oct 2014 22:37:15 -0700

> the index is used as a flag to indicate static or dynamic table for
You can probably guess I'm going to thank you for the status
summarizing! Also, that impl is fine by me from an impl pov.

---

From: RUELLAN Herve <[email-masked]>
Date: Wed, 15 Oct 2014 11:31:45 +0000

I dug a bit into the numbers myself, to find which removed static headers had a strong influence on the compaction results.
For requests, there are two: ":scheme:http" and "accept-charset". ":scheme:http" is probably not a problem as more traffic is expected to move to https. "accept-charset" is apparently no more commonly used, but is still in the testing data.

For responses, there are also two: "date" and "via". Their impact is roughly the same, and significant only for 1K or 2K dynamic tables. Keeping or removing them depends on the tradeoff we want to make. For a generic web usage, keep them to gain a small compaction increase, for a more versatile usage, remove them to reduce the size of the static table.

Hervé.

> From: Greg Wilkins [mailto:[email-masked]]
> Sent: mercredi 15 octobre 2014 04:37
> To: Roberto Peon
> Cc: Willy Tarreau; Mark Nottingham; HTTP Working Group; Jeff Pinner
> 	One byte more overhead is significant when the amount of overhead
> was typically one byte to begin with,
> 
> 
> 
> Well if looked at in that way, removing the reference set was an increase of 0
> bytes to 1 byte for many headers, so an infinite increase in size.    Yet when
> looked at overall, the impact was negligible.
> 
> 
> reducing the static table).  But I think that switching the index's back adjusts the
> balance too far away from the very common use case of static headers and
> static header names.
> 
> 
> size	 H2-14	 reduced	 values
> 0	 63.50%	 64.40%	 62.10%
> 4096	 34.50%	 34.20%	 33.50%
> 8192	 33.20%	 32.70%	 32.60%
> 12288	 33.30%	 32.60%	 32.50%
> 
> So for the test data, reducing the static table size has hardly any affect and by
> adding in values, the effect is often slightly positive.    So such a change looks to
> at least do no harm.     Question is, does it do any good for lots of dynamic
> headers - I'm happy to try answer that, but can do so only if somebody can give
> me some test data to run against.
> 
> 
> 
> 
> when implemented properly (there is little magical about a bit-blit to begin
> While I'm sure that dedicated code can be written to generate h2 headers very
> quickly, the reality is that servers are not written to be dedicated to h2.   The
> fast bulk of the header generation and handling code is written protocol neutral
> and has to work for  http, spdy, h2, fastcgi, etc.   In that environment we have
> found it extraordinary difficult to introduce header pre-generation when the
> bytes generated are a function of the connection and sequence that the header
> will be sent.   For example, we regenerate headers when we move a static
> resource into the cache, which is done without reference to any particular
> protocol or connection.      While the actual operation of customising a header
> for a particular connection might just be a lookup and an add, there is a lot of
> complexity required to work out when and if this addition is needed and
> bringing all the required information to the correct point in the code.
> 
> 
> I know this is a specific example, but I am sure that in general far better and
> simpler optimisations can be done with encodings that are immutable rather
> than with ones that are a function of connection and time.
> 
> 
> regards
> 
> 
> 
> 
> 
> 
> 
> 
> 
> --
> 
> Greg Wilkins <[email-masked]>  @  Webtide - an Intalio subsidiary

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 15 Oct 2014 11:50:47 +0000

--------

Sorry, but I simply cannot see us removing  ":scheme:http" in a standard
named HTTP/2.0...

Also, the fact that some people dream about more https is all fine
and dandy, but presuming that they will be right and using that
as an argument for removing ":scheme:http" is bogus.

---

From: "Simpson, Robby (GE Energy Management)" <[email-masked]>
Date: Wed, 15 Oct 2014 13:10:50 +0000

On 10/15/14, 7:31 AM, "RUELLAN Herve" <[email-masked]> wrote:

>For responses, there are also two: "date" and "via". Their impact is
>roughly the same, and significant only for 1K or 2K dynamic tables.
>Keeping or removing them depends on the tradeoff we want to make. For a
>generic web usage, keep them to gain a small compaction increase, for a
>more versatile usage, remove them to reduce the size of the static table.

"date" is an interesting example.  It is a MUST unless an accurate clock
is available (http://tools.ietf.org/html/rfc7231#section-7.1.1.2), yet it
is only 4 characters with a very dynamic value.

As I come from an embedded perspective, every bit counts and since this is
a MUST, I would suggest we keep it.  But this is not a strong opinion.

---

From: "Simpson, Robby (GE Energy Management)" <[email-masked]>
Date: Wed, 15 Oct 2014 13:40:13 +0000

>a MUST, I would suggest we keep it.  But this is not a strong opinion.

*unavailable

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 15 Oct 2014 22:15:41 +0200

On Wed, Oct 15, 2014 at 06:20:00PM +1300, Amos Jeffries wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 

I totally agree with this except that I don't see where you take that
spare bit from, that's what initially led me to rethink the encoding.
So if you konw where to find one bit, +1 for me obviously!

> rejected despite evidence of its usefulness because of who proposed it.)

No need to be paranoid here, the most common reason is that it's hard to
explain our thoughts and most of the time it ends up with each other
understanding something different and either useless or scary. Noone's
to blame for this, human languages are not appropriate for discussing
bits and bytes.

Thanks,
Willy

---

From: Jason Greene <[email-masked]>
Date: Wed, 15 Oct 2014 16:51:17 -0500

> for the math complexity people are disliking.

Another option I suggested awhile back (in case it was forgotten) is that there could be a control code (much like the table size code), which can be set to set the table ordering. Then a compressor can decide which is most advantageous for the data set. I like your idea better but if for some reason we can’t lose the bit, this would be a way.

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

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 16 Oct 2014 09:09:55 +0000

> From: Willy Tarreau [mailto:[email-masked]]
> Sent: mercredi 15 octobre 2014 22:16
> To: Amos Jeffries
> Cc: [email-masked]

Everywhere where there's an index into the static/dynamic table, reduce the index size by 1 bit and use this bit as a flag to find which table is used.

Hervé.

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 16 Oct 2014 11:16:26 +0200

On Thu, Oct 16, 2014 at 09:09:55AM +0000, RUELLAN Herve wrote:
> Everywhere where there's an index into the static/dynamic table, reduce the
> index size by 1 bit and use this bit as a flag to find which table is used.

OK that way it's clear. Initially I didn't want to do it that way (when
I tried to adjust the encoding to save more bits) because I believed we
needed to have all the static headers in 1 byte. But assuming the most
common ones have the lowest indexes, it makes sense to do so, as we can
encode the first 32 of them with 1 byte, same for the dynamic ones.

Thus +1 for me.

Willy

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 17 Oct 2014 10:23:35 +1100

I think we need to see a proposal here if we’re going to take this seriously — i.e., either fairly complete text or a pull request.

Are you interested, and can you do so in a small number of days?

Ill say outright that it feels to me that we’re in the weeds hyper-optimising the format, whereas we’ve agreed many times that doing so isn’t a high priority. Thus, I suspect that it’s going to be difficult to get consensus on such a proposal — but (as always) I’m happy to be proven wrong by the WG.

Cheers,

---

From: Willy Tarreau <[email-masked]>
Date: Sat, 18 Oct 2014 19:16:28 +0200

Hi Mark,

On Fri, Oct 17, 2014 at 10:23:35AM +1100, Mark Nottingham wrote:
> I think we need to see a proposal here if we?re going to take this seriously
> ? i.e., either fairly complete text or a pull request.
> 
> Ill say outright that it feels to me that we?re in the weeds hyper-optimising
> the format, whereas we?ve agreed many times that doing so isn?t a high
> priority.

I'm against hyper-optimising but I favor a balanced protocol. If some
users report that the current design is considerably worse than the
previous one, I think we should seek a balance point. And FWIW, using
a bit to indicate static vs dynamic will save less space than if we'd
use ranges but it will remain simpler to implement.

> Thus, I suspect that it?s going to be difficult to get consensus on
> such a proposal ? but (as always) I?m happy to be proven wrong by the WG.

I'm currently trying to find the best way to limit the amount of text
changes (or addition). If anyone already has something or is willing
to help, inputs are welcome!

Regards,
Willy

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 20 Oct 2014 18:53:53 +0200

Hi Mark,

> ? i.e., either fairly complete text or a pull request.

Here's the change I'm proposing. It's a diff against the text version because
it was easier for me to produce this, and it's easily readable by everyone here.

The diff looks like what's below, I think it addresses what was discussed in
a way that is pretty straightforward since there's no more the need to explain
the split between the two tables.

I have not changed anything else eventhough I'm seeing room for improvement
(eg: swapping encoding prefix of "literal without indexing" with the one
for "dynamic table size update" and gain one bit of encoding per header).

Anyone would please review and/or comment ?

Thanks,
Willy

------------

diff --git a/compression.txt b/compression.txt
index a4c8a40..56b2ea0 100644
--- a/compression.txt
+++ b/compression.txt
@@ -309,9 +309,6 @@ Internet-Draft                    HPACK                     October 2014
    (see Section 2.3.2) is dynamic and can be used by the encoder to
    index header fields repeated in the encoded header lists.
 
-   These two tables are combined into a single address space for
-   defining index values (see Section 2.3.3).
-
 2.3.1.  Static Table
 
    The static table consists of a predefined static list of header
@@ -348,37 +345,21 @@ Internet-Draft                    HPACK                     October 2014
 
 2.3.3.  Index Address Space
 
-   The static table and the dynamic table are combined into a single
-   index address space.
-
-   Indices between 1 and the length of the static table (inclusive)
-   refer to elements in the static table (see Section 2.3.1).
-
+   Both the static and the dynamic tables are indexed starting at 1.
    Indices strictly greater than the length of the static table refer to
    elements in the dynamic table (see Section 2.3.2).  The length of the
    static table is subtracted to find the index into the dynamic table.
 
-   Indices strictly greater than the sum of the lengths of both tables
-   MUST be treated as a decoding error.
+   Static table indices strictly greater than the length of the table as
+   defined in Appendix A MUST be treated as a decoding error. Dynamic table
+   indices strictly greater than the length of the dynamic table MUST be
+   treated as a decoding error.
 
-   For a static table size of s and a dynamic table size of k, the
-   following diagram shows the entire valid index address space.
-
-           <----------  Index Address Space ---------->
-           <-- Static  Table -->  <-- Dynamic Table -->
-           +---+-----------+---+  +---+-----------+---+
-           | 1 |    ...    | s |  |s+1|    ...    |s+k|
-           +---+-----------+---+  +---+-----------+---+
-                                  ^                   |
-                                  |                   V
-                           Insertion Point      Dropping Point
-
-                       Figure 1: Index Address Space
 
 2.4.  Header Field Representation
 
    An encoded header field can be represented either as a literal or as
-   an index.
+   an index in one of the tables.
 
    A literal representation defines a header field by specifying its
    name and value.  The header field name can be represented literally
@@ -740,14 +721,15 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 1 |        Index (7+)         |
-   +---+---------------------------+
+   | 1 | D |     Index (6+)        |
+   +---+---+---+---+---+---+---+---+
 
                       Figure 5: Indexed Header Field
 
-   An indexed header field starts with the '1' 1-bit pattern, followed
-   by the index of the matching pair, represented as an integer with a
-   7-bit prefix (see Section 5.1).
+   An indexed header field starts with the '1' 1-bit pattern, followed by
+   the D bit indicating if the index references the static table (0) or
+   the dynamic table (1), and the index of the matching pair, represented
+   as an integer with a 6-bit prefix (see Section 5.1).
 
    The index value of 0 is not used.  It MUST be treated as a decoding
    error if found in an indexed header field representation.
@@ -788,8 +770,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 1 |      Index (6+)       |
-   +---+---+-----------------------+
+   | 0 | 1 | D |  Index (5+)       |
+   +---+---+---+-------------------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -800,8 +782,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 1 |           0           |
-   +---+---+-----------------------+
+   | 0 | 1 | 0 |       0           |
+   +---+---+---+-------------------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -819,11 +801,13 @@ Internet-Draft                    HPACK                     October 2014
    If the header field name matches the header field name of an entry
    stored in the static table or the dynamic table, the header field
    name can be represented using the index of that entry.  In this case,
-   the index of the entry is represented as an integer with a 6-bit
-   prefix (see Section 5.1).  This value is always non-zero.
+   the index of the entry is represented as the D bit indicating if the
+   index references the static table (0) or the dynamic table (1),
+   followed by an integer with a 5-bit prefix (see Section 5.1).  This
+   value is always non-zero.
 
    Otherwise, the header field name is represented as a literal string
-   (see Section 5.2).  A value 0 is used in place of the 6-bit index,
+   (see Section 5.2).  A value 0 is used in place of the 5-bit index,
    followed by the header field name.
 
    Either form of header field name representation is followed by the
@@ -844,8 +828,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 0 |  Index (4+)   |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 0 | D | Index (3+)|
+   +---+---+---+---+---+-----------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -855,8 +839,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 0 |       0       |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 0 | 0 |     0     |
+   +---+---+---+---+---+-----------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -874,11 +858,13 @@ Internet-Draft                    HPACK                     October 2014
    If the header field name matches the header field name of an entry
    stored in the static table or the dynamic table, the header field
    name can be represented using the index of that entry.  In this case,
-   the index of the entry is represented as an integer with a 4-bit
-   prefix (see Section 5.1).  This value is always non-zero.
+   the index of the entry is represented as the D bit indicating if the
+   index references the static table (0) or the dynamic table (1),
+   followed by as an integer with a 3-bit prefix (see Section 5.1).
+   This value is always non-zero.
 
    Otherwise, the header field name is represented as a literal string
-   (see Section 5.2).  A value 0 is used in place of the 4-bit index,
+   (see Section 5.2).  A value 0 is used in place of the 3-bit index,
    followed by the header field name.
 
    Either form of header field name representation is followed by the
@@ -900,8 +886,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 1 |  Index (4+)   |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 1 | D | Index (3+)|
+   +---+---+---+---+---+-----------+
    | H |     Value Length (7+)     |
    +---+---------------------------+
    | Value String (Length octets)  |
@@ -911,8 +897,8 @@ Internet-Draft                    HPACK                     October 2014
 
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
-   | 0 | 0 | 0 | 1 |       0       |
-   +---+---+-----------------------+
+   | 0 | 0 | 0 | 1 | 0 |     0     |
+   +---+---+---+---+---+-----------+
    | H |     Name Length (7+)      |
    +---+---------------------------+
    |  Name String (Length octets)  |
@@ -957,7 +943,7 @@ Internet-Draft                    HPACK                     October 2014
      0   1   2   3   4   5   6   7
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 1 |   Max size (5+)   |
-   +---+---------------------------+
+   +---+---+---+-------------------+
 
                Figure 12: Maximum Dynamic Table Size Change
 
------------

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Mon, 20 Oct 2014 19:48:50 +0000

--------
In message <[email-masked]>, Willy Tarreau writes:

+1

I like this, it's nice and orthogonal.

>    static table is subtracted to find the index into the dynamic table.

These three lines left in conflict somewhat with the four lines you
add below.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 20 Oct 2014 22:17:19 +0200

Hi Poul-Henning,

> I like this, it's nice and orthogonal.

Thank you.

> These three lines left in conflict somewhat with the four lines you

Ah yes indeed, good catch. I tried to be careful and the spec is already
quite clean but I missed these ones.

Best regards,
Willy

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 21 Oct 2014 09:06:50 +1100

Willy,

IF we are changing, then I'm fine with your approach IFF those that are
advocating bias to dynamic headers are also satisfied with it.

However, note that I think it needs to be considered together with a review
of the static table itself.  With your pattern we get :

   - 62 static 1 byte indexed fields - which are only useful if we have
   values for most of the first 62 entries in the static table - so we need to
   add as many valus as possible
   - For static name, literal value encodings, we only get 6 1 byte indexed
   fields, so we need to review the table order to ensure that the first 7
   static entries are most frequently used with dynamic values. Currently that
   is most definitely not the case.  Also consideration has to be given to the
   length of the 6 selected fields as if Date encodes to 2 byte index, then
   you may as well send it huffman encoded and save the 1 byte index for
   something like last-modified.

So currently I'm +0 on this, but if somebody proposed a well tuned static
table to match then I'd be +1

If those who are advocating dynamic header support don't dismiss this
approach, then I'll give a go at proposing such a tuned static table
tomorrow.

cheers

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 21 Oct 2014 10:29:17 +1100

Thanks for that, Willy.

At the risk of repeating myself -- making this kind of change (one that does not impact security or interoperability) at this stage in our process needs to have *strong* consensus. 

What do others think?

Regards,

> On 21 Oct 2014, at 3:53 am, Willy Tarreau <[email-masked]> wrote:
> 
> Hi Mark,
>

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 06:31:11 +0200

Hi Greg,

>    add as many valus as possible

Yes I know. Note that it was the case previously as well, which is what
wasted part of the encodable bytes. In the more complex change I proposed
in July, the goal was to only be able to encode static values on 4 bits to
be able to only encode the 16 first static headers which carry a value (and
swap accept-charset and accept-encoding so that we have 16 values first).

>    something like last-modified.

Well, till now we could only encode the first 14 ones anyway, and I guess
that the ability to pick the encoding for "status 500" in a literal is much
less common than using accept-encoding or if-modified-since. In my opinion,
the beginning of the static table should only contain *different* header
names. And I still think that inverting the dyn table size update and
literal encodings should be appropriate to save at least one bit for the
latter.

> approach, then I'll give a go at proposing such a tuned static table

I agree with you. My deep feelings are that we changed the behaviour of
the encoder by removing the ref set and using the static table more than
the dynamic table, and we never reconsidered the impact it had on the way
the opcodes are used, which I suspect has significantly changed. Normally
we should have reworked the encoding based on this to get something more
efficient. But it seems most participants do not want this to happen that
late in the process, while I'm sure we can do much better :-(

Thanks,
Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 21 Oct 2014 06:47:21 +0000

--------
In message <[email-masked]>

>   add as many valus as possible

... in due time.

I agree that the current table should be reviewed now, but we should
not fill it up with junk, just to fill it up.

It makes a lot of sense to leave the remaning slots available for future 
extensions.  Maybe we should already add a SETTING to tell how long
a table an implementation supports, to make such additions quick and
painless.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 21 Oct 2014 00:01:19 -0700

While I prefer the indexing scheme of the previous draft, this proposal
would be better than what is currently drafted.

-=R

On Mon, Oct 20, 2014 at 4:29 PM, Mark Nottingham <[email-masked]> wrote:

> Thanks for that, Willy.
>
> At the risk of repeating myself -- making this kind of change (one that
> does not impact security or interoperability) at this stage in our process
> needs to have *strong* consensus.
>
> What do others think?
>
> Regards,
>
>

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 11:25:05 +0200

Hi Roberto,

> would be better than what is currently drafted.

Thanks. Do you know how the following representations are ordered in
terms of frequency/probability ?

  - Indexed Header Field Representation
  - Literal Header Field with Incremental Indexing
  - Literal Header Field without Indexing
  - Literal Header Field never Indexed

I would guess they should appear in the order above, though that's not
obvious to me. And I'm still sad at the idea of leaving many encoding
values unused (eg: static header values above 16). Thus, we'll typically
have 48 possible values out of 256 for the first byte that will never be
emitted just for the indexed headers alone, that's a 20% waste, and I
really think we can do better without making anything more complex. I
just need to ensure I don't propose something stupid.

Thanks,
Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 21 Oct 2014 09:32:55 +0000

--------
In message <[email-masked]>, Willy Tarreau writes:

>emitted just for the indexed headers alone, that's a 20% waste, 

If you are that worried about wasted compression opportunities, you
should spend your time to get timestamps compressed to integers since
that will save more bytes than you can ever do by tweaking the current
HPACK in any way.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 11:40:33 +0200

> just need to ensure I don't propose something stupid.

For example something like this (CCing Greg who also has concerns about
all this), which supports a single-byte encoding for :
   - 14 or the 16 static headers with values
   - all 62 static headers for literals
   - 62 dynamic headers for literals

   +---+---+----------------------+
   | 1 | D |  index 6+            |      literal with incremetal indexing
   +---+---+----------------------+

   +---+---+----------------------+
   | 0 | 1 |  index 6+            |      indexed dynamic header
   +---+---+----------------------+

   +---+---+---+---+--------------+
   | 0 | 0 | 1 | 1 |  index 4+    |      indexed static header
   +---+---+---+---+--------------+

   +---+---+---+---+--------------+
   | 0 | 0 | 1 | 0 |  size 4+     |      max dynamic table size change
   +---+---+---+---+--------------+

   +---+---+---+---+---+----------+
   | 0 | 0 | 0 | 0 | D | index 3+ |      literal without indexing 
   +---+---+---+---+---+----------+

   +---+---+---+---+---+----------+
   | 0 | 0 | 0 | 1 | D | index 3+ |      literal never indexed
   +---+---+---+---+---+----------+

Willy

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 11:44:25 +0200

Hi Poul-Henning,

> that will save more bytes than you can ever do by tweaking the current

I know, and you remember, that was one of the basic points of our
proposal 2 years ago. I think we'll hardly propose this here since
it changes the ability to pass certain invalid values. However, I
think we could do it by writing a proposal for a few header names
and their binary representation that could be used as an alternative
to Date/IMS/LM. A settings frame could indicate whether each side
supports this extension and would only emit these ones instead of
the regular ones. What do you think ?

Willy

---

From: Julian Reschke <[email-masked]>
Date: Tue, 21 Oct 2014 12:02:39 +0200

On 2014-10-21 11:44, Willy Tarreau wrote:
> ...
 > ...

Right. But maybe we could try something the represents valid values 
well, but still allows transporting invalid values?

Best regards, Julian

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 12:20:16 +0200

> well, but still allows transporting invalid values?

I hadn't thought about that option honnestly and I find that it could be
very efficient and even save a lot of CPU by avoiding to process anything
complicated or out of range. I mean, if the date respects a very precise
format, we encode it and transport it in binary. Otherwise we leave it
in plain text mode. We can have an encoding starting with something
impossible in text mode (eg: LF byte) to mark that what follows is a
32-bit binary encoding of a timestamp. A variable-length encoding would
allow to pass end of the current epoch and to use less bytes currently.
This method would even be compatible with existing encoding and parsers.

Do you think it's still possible to propose something along this without 
conflicting with the goal of stabilizing changes ?

Willy

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Tue, 21 Oct 2014 10:23:19 +0000

--------
In message <[email-masked]>, Willy Tarreau writes:

>We can have an encoding starting with something
>impossible in text mode (eg: LF byte) to mark [...]

I would simply put two "Date:" entries in the static table, one
for text-encoded and one for number-encoded.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 12:28:00 +0200

> for text-encoded and one for number-encoded.

That would not be compatible with dynamic indexing. I suspect that
a number of applications emit many very similar dates in responses
(when pages are dynamically generated), resulting in exact same
values between the application and the frontend (lb/cache/etc).
Given that you have much more experience than me looking at Date
headers, don't you think that can be a loss ? Also it would require
specific handling from the encoder to know that they must not index
this specific header. We already have the set-cookie header which is
boring, better try not to have another one.

Just my few cents
willy

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 22 Oct 2014 00:36:30 +1100

Willy,

I actually think that literal without/never indexed should be favoured over
literal indexed or at least on event footing, because by nature the literal
indexed headers are sent only once and then used by index, while the
literal without/never indexed headers are sent literally every time they
are used.

Thus I would think something like:

Indexed Header:
   | 1 | D |    Index (6+)         |

Literal Never Indexed:
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 0 | D | Index (4+)    |
   +---+---------------------------+

Literal Not Indexed:
   +---+---+---+---+---+---+---+---+
   | 0 | 0 | 1 | D | Index (4+)    |
   +---+---------------------------+

Literal Indexed:
   +---+---+---+---+---+---+---+---+
   | 0 | 1 | 0 | D | Index (4+)    |
   +---+---------------------------+

Max Dynamic Table size change:
   +---+---+---+---+---+---+---+---+
   | 0 | 1 | 1 |  Index (5+)       |
   +---+---------------------------+

I believe that most 62 static slots can easily be filled with values that
will be used.   I'll come up with a suggestion for this tomorrow.

cheers

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 16:08:43 +0200

Hi Greg,

> literal without/never indexed headers are sent literally every time they

OK, thanks for explaining.

> Thus I would think something like:

Here we still have the 20% waste I wanted to address : ~48/256 values
will never be sent (those for static entries >16). That's where I
wanted to recover that many values (5.5 bits) which are clearly
missing from other encodings.

> Literal Never Indexed:

Two of them can then be increased by 1..1.5 bit by recovering
the unused encoding above.

> Max Dynamic Table size change:

And this one looks like a huge waste to me, it only happens
once in a long while and kills 32 possible values that we'd
better use for each individual header. In practice, 80/256
code points are unusable for each header, that's roughly 33%
wasted encoding space :-/.

> will be used.

That's where I'm really doubting to be honnest.

> I'll come up with a suggestion for this tomorrow.

OK great!

Cheers,
Willy

---

From: Jason Greene <[email-masked]>
Date: Tue, 21 Oct 2014 09:24:53 -0500

> On Oct 21, 2014, at 4:32 AM, Poul-Henning Kamp <[email-masked]> wrote:
> 
> --------

+Graham’s number

I am still surprised we aren’t doing this, as it would mean huge bandwidth and performance savings. I like the idea of an extension, which hopefully transitions to an official part of HTTP/3.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 21 Oct 2014 16:24:51 +0200

> This method would even be compatible with existing encoding and parsers.

I just experimented with this : variable length encoding of the date using
255/256 possible values for each byte, so that it remains compatible with
string processing in programs (no zero byte is produced).

The example code below converts valid strings to their compacted form
and leaves the non-convertable ones intact. The converted string's format
indicates what format it's in (ie: if it begins with 0xA its a compact one).
The gains are interesting, just tested on example.com, there are 3 dates
there, 24 bytes each, and reduced to 5 bytes each, that's 57 bytes saved
in one response header (19 bytes saved per valid header).

The encoding function works this way : it tries to parse a valid HTTP date
and returns either the original string or the compacted one :

	const char *http_date_encode(const char *date)
	{
		struct tm tm;
		static char buf[10];

		if (strptime(date, "%a, %d %b %Y %H:%M:%S %Z", &tm) == NULL)
			return date;

		if (!nz_encode(buf + 1, sizeof(buf) - 1, mktime(&tm)))
			return date;

		buf[0] = '\n';
		return buf;
	}

The decoder does the opposite, it checks whether the date string starts
with an LF character and returns either its expansion or the string itself :

	const char *http_date_decode(const char *date)
	{
		struct tm *tm;
		static char buf[200];
		time_t t;

		if (*date != '\n')
			return date;

		t = nz_decode(date + 1);
		tm = gmtime(&t);
		strftime(buf, sizeof(buf), "%a, %d %b %Y %H:%M:%S %Z", tm);
		return buf;
	}

The non-zero encoding/decoding functions are simple base255 encoders which
ensure that we won't add an extra byte for a long time, but if someone doesn't
feel at ease with these, it's possible to use another format (and waste more
space) :

	/* decode a non-zero encoded string into a long int */
	unsigned long nz_decode(const char *buf)
	{
		unsigned long v;
		unsigned long mul = 1;

		for (v = 0; *buf; buf++) {
			v += mul * (unsigned char)(*buf - 1);
			mul *= 255;
		}
		return v;
	}

	/* encode value <v> into a non-zero string */
	const char *nz_encode(char *buf, int size, unsigned long v)
	{
		char *out;

		for (out = buf; size >= 1;) {
			if (!v) {
				*out = 0;
				return buf;
			}
			*(out++) = 1 + (v % 255);
			v /= 255;
		}
		return NULL;
	}

Then the calling code which converts the date both ways and compares
outputs.

	int main(int argc, char **argv)
	{
		const char *in;
		const char *enc;
		const char *dec;

		if (argc < 2)
			return 1;

		in = argv[1];
		enc = http_date_encode(argv[1]);
		dec = http_date_decode(enc);

		printf("in =<%s> (%d chars)\n", in, strlen(in));
		printf("enc=<%s> (%d chars) savings=%d\n", enc, strlen(enc), strlen(in)-strlen(enc));
		printf("dec=<%s> (%d chars) strcmp=%d\n", dec, strlen(dec), strcmp(in, dec));
		return 0;
	}

$ curl -I example.com
HTTP/1.1 200 OK
Accept-Ranges: bytes
Cache-Control: max-age=604800
Content-Type: text/html
Date: Tue, 21 Oct 2014 14:20:53 GMT
Etag: "359670651"
Expires: Tue, 28 Oct 2014 14:20:53 GMT
Last-Modified: Fri, 09 Aug 2013 23:54:35 GMT
Server: ECS (iad/182A)
X-Cache: HIT
x-ec-custom-error: 1
Content-Length: 1270

These 3 dates (Date, Expires, Last-Modified) can then be shrunk by 57 bytes
total without the risk of altering an invalid content. What's nice with this
method is that only the producer needs to know what headers it wants to
compact, the recipient doesn't need to know them since it can use the LF
byte to know if a value needs to be expanded or not. An if-modified-since
in a request could be reduced by 19 bytes, which is nice as well.

Thoughts ?

Willy

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 22 Oct 2014 11:53:21 +1100

This thread seems to be going off into defining an extension, which is entirely appropriate.

I'm not seeing broad acclaim for making any changes to the existing scheme in the spec itself; in particular, Jeff's proposal failed to get wide support. 

So, I think we can mark #578 as closed without action.

Regards,

> On 22 Oct 2014, at 1:24 am, Jason Greene <[email-masked]> wrote:
> 
>>

---

From: "Martin Nilsson" <[email-masked]>
Date: Wed, 22 Oct 2014 03:13:55 +0200

> in one response header (19 bytes saved per valid header).

That's before huffman encoding.

Taking a now:ish timestamp of 1413938411 creates the byte sequence  
0a.84.89.46.56. These 5 bytes are encoded with 89 bits after huffman  
encoding, whereas the 10 byte numeric literal "1413938411" is encoded with  
56 bits. Not completely fair since you have an encoding token in front,  
which is needed here to distinguish between time and time offsets. If we  
pick "t" to mean time, which is encoded with 5 bits, we get 64 bits for  
your method and 61 bits for ASCII, for this example. For this size of  
numbers you'll get an average of 4*18.2 = 72.8 bits while ASCII gives  
10*5.7 = 57 bits (plus encoding token).

/Martin Nilsson

-- 
Using Opera's mail client: http://www.opera.com/mail/

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 22 Oct 2014 15:07:59 +1300

On 22/10/2014 2:13 p.m., Martin Nilsson wrote:
> On Tue, 21 Oct 2014 16:24:51 +0200, Willy Tarreau wrote:
> 
>> 
>> The example code below converts valid strings to their compacted
>> form and leaves the non-convertable ones intact. The converted
>> string's format indicates what format it's in (ie: if it begins
>> with 0xA its a compact one). The gains are interesting, just
>> tested on example.com, there are 3 dates there, 24 bytes each,
>> and reduced to 5 bytes each, that's 57 bytes saved in one
>> response header (19 bytes saved per valid header).
>> 
> 
> 0a.84.89.46.56. These 5 bytes are encoded with 89 bits after
> huffman encoding, whereas the 10 byte numeric literal "1413938411"
> is encoded with 56 bits. Not completely fair since you have an
> encoding token in front, which is needed here to distinguish
> between time and time offsets. If we pick "t" to mean time, which
> is encoded with 5 bits, we get 64 bits for your method and 61 bits
> for ASCII, for this example. For this size of numbers you'll get an
> average of 4*18.2 = 72.8 bits while ASCII gives 10*5.7 = 57 bits
> (plus encoding token).

Huffman encoding applies only to String literals. This numeric is an
Integer Literal byte sequence.

Also, if you are going to signal a binary state (delta vs absolute
time) use a 1-bit flag, built into the value type code this wastes no
space. As you can see a separate 5-bit String Literal character just
biases the encoding towards ASCII.

Amos

---

From: Amos Jeffries <[email-masked]>
Date: Wed, 22 Oct 2014 15:31:11 +1300

On 22/10/2014 1:53 p.m., Mark Nottingham wrote:
> I'm not seeing broad acclaim for making any changes to the existing
> scheme in the spec itself; in particular, Jeff's proposal failed to
> get wide support.
> 

I see only an extension for the unrelated timestamp things.

Can we try seriously for a consensus on just Willys' patch to separate
the tables?

Other proposals got their own "vote" threads and many days before a
consensus/non-consensus was declared. This one has only just had 25hrs
buried at the back end of a long heated discussion.

It is distinct from Jeff's reversal proposal and offers benefits to
all participant "camps" over both that and the status quo. I fear it
has got lost amidst this long thread on a rushed timescale.

Amos

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 22 Oct 2014 14:27:01 +1100

That's reasonable, Amos; I'll start a separate thread to ask for positions on status quo vs. Jeff's proposal vs. Willy's.

Cheers,

> On 22 Oct 2014, at 1:31 pm, Amos Jeffries <[email-masked]> wrote:
>

---

From: "Martin Nilsson" <[email-masked]>
Date: Thu, 23 Oct 2014 16:00:36 +0200

> Integer Literal byte sequence.

Ah, of course. That flips the size advantage to something like 5 bytes vs  
9 bytes in worst case.

> space.

I wasn't actually thinking about encoding here, but different semantics,  
like the Retry-After header which both has a date and number as possible  
values, with different interpretations.

/Martin Nilsson