Subject: Reference set in HPACK

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 02 Jul 2014 14:30:41 +0900 (JST)

Hi,

As you may remember, I implemented several HPACK *encoding* algorithms
and calculated compression ratio. I tried it again based on HPACK
08. I have 8 algorithms.

- Naive    -- No compression
- Naive-H  -- Using Huffman only
- Static   -- Using static table only
- Static-H -- Using static table and Huffman
- Linear   -- Using header table
- Linear-H -- Using header table and Huffman
- Diff     -- Using header table and reference set
- Diff-H   -- Using header table, reference set and Huffman

The implementations above pass all test cases in
https://github.com/http2jp/hpack-test-case/.  Using this test cases as
input, I calculated compression ratio again. The ratio is calculated
by dividing the number of bytes after compression by that before
compression.

Here is results:

Naive     1.10
Naive-H   0.86
Static    0.84
Static-H  0.66
Linear    0.39 
Linear-H  0.31
Diff      0.39
Diff-H    0.31

Linear-H and Diff-H results in almost the same. To my calculation,
Diff-H is only 1.6 byte shorter than Linear-H in average. This means
that reference set does NOT much contribute to compress headers
although it is very difficult to implement.

I have NOT seen any header examples for which reference set work
effectively so far.

So, if the authors of HPACK want to retain reference set, I would like
to see evidence that there are some cases in which reference set
contributes the compression ratio. HPACK 08 says "Updated Huffman
table, using data set provided by Google". So, I guess that the
authors can calculate the compression ratio based on this data.

If there is not such an evidence, I would like to strongly recommend
to remove reference set from HPACK. This makes HPACK much simpler, so
implementations gets bug less and inter-operability is improved. Plus,
the order of headers is reserved always.

Regards,

--Kazu

---

From: Roberto Peon <[email-masked]>
Date: Tue, 1 Jul 2014 22:39:46 -0700

You're basing conclusions on today's data, instead of looking forward as to
what might happen when the set of headers sent adapts to the compression
method, making it significantly more likely for items in the reference set
to be emitted.

You may want to look at how many of those entries would be regularized if
HPACK was in use and servers/clients intended on sending headers that were
similar.
-=R

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 2 Jul 2014 15:44:41 +1000

Hi Kazu,

As I understand it, one of the purposes of the reference set is to accommodate cases where intermediaries multiplex requests from different clients -- thus having different cookies, UAs, etc. -- into one upstream connection.

Does your test data reflect this kind of use case?

Regards,

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

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 02 Jul 2014 14:52:15 +0900 (JST)

Hi Roberto,

> method, making it significantly more likely for items in the reference set

If you believe that reference set is suitable for headers in the
future, please give me such examples so that I can convince.

In my understating, reference set cannot contribute for ANY headers.
Typically an index is represented by one byte. Even if you can omit
sending some indices, we can save just some bytes.

--Kazu

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 02 Jul 2014 14:58:37 +0900 (JST)

Hi Mark,

> Does your test data reflect this kind of use case?

No.

I believe the header table can contribute to compress cookies (i.e. a
long cookie become one byte). But I don't understand why you think
reference set can contribute to compress cookies (i.e. just saving
some bytes).

Anyway, please give me an concrete example data so that I can
convince.

--Kazu

---

From: Roberto Peon <[email-masked]>
Date: Tue, 1 Jul 2014 23:09:56 -0700

Kazu--

Even a few bytes per request adds up as the number of requests go up.
Lets think about a page today that has 100 elements, which is something we
see today.
If the headers were regularized, with the use of a reference set, one could
imagine a reduction of 20 bytes per header.
With 100 elements, this is approximately 2k of data, or two packets worth.

This makes the difference between being able to use server push as a
workable optimization technique or not being able to do so since it might
require more packets/space than inlining, and thus present a disadvantage
as compared to inlining for the first, cold, pageload.

The trend is to increase the number of individual resources on a page.

Note that a single byte is used only when the number of table entries is
fairly small. This is likely to be the case for client<->server
communication, and less likely to be true for proxies.
-=R

---

From: Kazu Yamamoto (山本和彦) <[email-masked]>
Date: Wed, 02 Jul 2014 15:30:27 +0900 (JST)

Roberto,

> imagine a reduction of 20 bytes per header.

OK. Suppose we can save 20 bytes.

> With 100 elements, this is approximately 2k of data, or two packets worth.

I don't understand this.

Each HTTP request/response is stored in its own IP packets. Suppose an
HTTP request is stored in N IP packets. I don't think saving 20 bytes
can reduce N to N - 1. So, the total number of IP packets is the same.

--Kazu

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 02 Jul 2014 06:34:22 +0000

>With 100 elements, this is approximately 2k of data, or two packets worth.

You'd save as many if not more bytes by being able to transfer the
biggest of the 100 elements in DATA frames larger than 16383 bytes.

I think it is fair to ask for some credible real-world data that shows
reference sets making an actual difference that justifies the added
complexity.

-- 
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: Roberto Peon <[email-masked]>
Date: Tue, 1 Jul 2014 23:36:44 -0700

On Tue, Jul 1, 2014 at 11:30 PM, Kazu Yamamoto <[email-masked]> wrote:

> Each HTTP request/response is stored in its own IP packets.

This isn't correct. Implementations typically pack many requests or
responses into single packets, true even of implementations which turn
nagle off when they know that there is likely to be more data forthcoming.
-=R

> Suppose an

---

From: Roberto Peon <[email-masked]>
Date: Tue, 1 Jul 2014 23:39:12 -0700

Poul--

That is orthogonal-- small data frames are necessary for latency as well,
and the impact on packetization with full DATA frames is minimal, with near
zero impact on latency.

-=R

On Tue, Jul 1, 2014 at 11:34 PM, Poul-Henning Kamp <[email-masked]>
wrote:

> In message <
> [email-masked]>,
> Roberto Peon writes:
>

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 02 Jul 2014 07:22:25 +0000

In message <CAP+FsNf=[email-masked]>, Roberto Peon writes:
>--047d7b2e50c07345ea04fd30267d

>That is orthogonal-- small data frames are necessary for latency as well,

I don't dispute that, I just dispute the value chosen for "small".

But back to your two saved packets:

I just tried loading a typical well engineered major news site over
HTTP/1 and captured a tcpdump.

A total of 1891906 bytes were sent in the TCP packets and 146 HTTP
transactions performed.

1718723 of those byes are accounted for by Content-Length (there
is a single chunked object but I can't be bothered to tally it from
the tcpdump).

If the 1718723 bytes optimistically had been sent on a single TCP
in one direction from a single server, that would take 1193 packets
(without HTTP/2 overhead of framing).

Your proposed saving of 2 packets can therefore never exceed a
0.17% ratio for this particular case.

In practice 15 different servers were involved and just the
distribution of content over 15 TCP connections alone adds
7.5 packets on average in "rounding error", in addition to
the three-way handshakes and so on.

It also reduces the chances of the few bytes shaved by the reference
set from saving any packets (as opposed to having a few byts
less in a packet).

If I remeber my statistics right, your already pretty slim chances
of shaving a packet is reduced by sqrt(15), since the reference
set doesn't do anything for you cross-site.

So provided the byte for byte savings previously quoted are correct
on average you'd probably save half a packet out of the total 1200.

That is 0.04 %.

Unless you have actual non-contrived data that shows a remarkably
better outcome than that, the reference set is not worth the added
complexity.

---

From: Greg Wilkins <[email-masked]>
Date: Wed, 2 Jul 2014 09:37:23 +0200

On 2 July 2014 08:09, Roberto Peon <[email-masked]> wrote:

> If the headers were regularized, with the use of a reference set, one
> could imagine a reduction of 20 bytes per header.

Roberto,

I think this kind of calculation needs some real data.     Maintaining a
reference set is not a zero byte deal, as it still requires bytes to be
sent to remove entries from the reference set that are not needed.  If real
data shows that removals are frequent, then they may add up to close to the
2k also.

I don't think that it is unreasonable to request that realistic data is
provided to prove that a reference set is worthwhile.   It  would be good
to obtain and evaluate such data for both a single connection and coalesced
connections.

regards

-- 
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: Roberto Peon <[email-masked]>
Date: Wed, 2 Jul 2014 00:43:14 -0700

On Wed, Jul 2, 2014 at 12:22 AM, Poul-Henning Kamp <[email-masked]>
wrote:

> In message <CAP+FsNf=
> [email-masked]>, Roberto Peon
> writes:

Your analysis seems a bit flawed.

>From the server side, server push is most likely to be used during
slowstart, and during the time that the initial resource (e.g. the HTML)
would be sent.
Inlining is the technique most often used to reduce the number of request.
It is a strategy that works well most of the time for cold pageloads, but
it also harms latency for subsequent navigations deeper into the site as
those resources cannot be cached.
For server push to be effective, it should not take significantly more time
than inlining. Its primary benefit ends up being to navigations after the
first cold page load, though it can also remove a single RT from a cold
page load assuming the window opens enough to allow that (which is not
certain).
When server push becomes adopted better (there is a chicken and egg issue
now which is hopefully being addressed), sites change how they present
resources to HTTP2 connections, and the number of resources for a page
seems likely to increase as folks get to abandon inlining, spriteing, etc.

For a client which is creating a new connection, e.g. on a browser restart,
it may have a great many requests to send. I often have 20 or more tabs
open, for instance. In cases such as these there are a fair number of
requests which will look more similar and which should be sent in the first
few packets.
-=R

---

From: Roberto Peon <[email-masked]>
Date: Wed, 2 Jul 2014 00:45:56 -0700

I'm all for people generating such data and coming to conclusions based on
it.
I'd caution that one should not predicate the analysis on pages that look
exactly as they do today, nor headers which look exactly as they do today.

Essentially all of the time that I commit to HTTP2 these days comes out of
personal time, and doing such an analysis would require more time than I'm
willing to take away from my family or more likely, sleep.

-=R

On Wed, Jul 2, 2014 at 12:37 AM, Greg Wilkins <[email-masked]> wrote:

>> Lets think about a page today that has 100 elements, which is something
>> we see today.

---

From: <[email-masked]>
Date: Wed, 2 Jul 2014 07:51:10 +0000

On Wednesday,02 July 2014 09:43, [email-masked] wrote:
> it may have a great many requests to send. I often have 20 or more tabs open,
> for instance. In cases such as these there are a fair number of requests which
> will look more similar and which should be sent in the first few packets.
> -=R

It doesn't matter if you have 2 tabs or 50 tabs open.  You can only look at the content from 1 tab at a time.

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: Roberto Peon <[email-masked]>
Date: Wed, 2 Jul 2014 00:55:24 -0700

On Wed, Jul 2, 2014 at 12:51 AM, <[email-masked]> wrote:

> open,

Though this is factually incorrect (I have three monitors, and thus often
have three browser instances in full-screen on each), the spirit is that
the number of visible tabs is often much less than that of the number of
tabs total.
Agreed.

The requests still need to be sent, though they should be prioritized
appropriately, and the responses to them from the server sent according to
that priority.
That prioritization is mostly orthogonal, however.
-=R

>
> 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: <[email-masked]>
Date: Wed, 2 Jul 2014 07:58:09 +0000

On Wednesday,02 July 2014 09:46, [email-masked] wrote:
> I'm all for people generating such data and coming to conclusions based on it.
> I'd caution that one should not predicate the analysis on pages that look exactly
> as they do today, nor headers which look exactly as they do today.
>
> Essentially all of the time that I commit to HTTP2 these days comes out of personal
> time, and doing such an analysis would require more time than I'm willing to take
> away from my family or more likely, sleep.
> -=R

I certainly can empathize.  I appreciate your commitment to your family (I really do, *this is not a snark*, I'm a family man too).

My only debate is that there is no data to show that reference sets are worthwhile, *just theory*.

So the onus is on the theorists to come up with proof that reference sets are worthwhile.  Whether that's you or somebody else.

---

From: <[email-masked]>
Date: Wed, 2 Jul 2014 08:00:27 +0000

On Wednesday,02 July 2014 09:55, [email-masked] wrote:
> Though this is factually incorrect (I have three monitors, and thus often have
> three browser instances in full-screen on each) ...

Note that I said *look* at one tab at a time.  I'm really impressed if you can focus on more than one tab at once :)

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 02 Jul 2014 08:02:09 +0000

>Your analysis seems a bit flawed.

But based on actual data.

Where is your data ?

---

From: "Poul-Henning Kamp" <[email-masked]>
Date: Wed, 02 Jul 2014 08:07:44 +0000

In message <CAP+FsNeGCUEoiAdrL2gr_P=[email-masked]>, Roberto Peon writes:
>--047d7b2e50c01b83ea04fd3115d3

>willing to take away from my family or more likely, sleep.

But you are willing to insist that everybody else spends time implementing
the reference set, without any factual data to show that it is going
to provide a relevant benefit ?

The reference set should be dropped if nobody can document that it helps.

Gettys rule #1, #3 and #5:

1. Do not add new functionality unless an implementor cannot complete
   a real application without it.

3. The only thing worse than generalizing from one example is
   generalizing from no examples at all.

5. If you can get 90 percent of the desired effect for 10 percent
   of the work, use the simpler solution.

---

From: <[email-masked]>
Date: Wed, 2 Jul 2014 09:15:34 +0000

On Wednesday,02 July 2014 09:55, [email-masked] wrote:
> [snip]
> The requests still need to be sent, though they should be prioritized appropriately,
> and the responses to them from the server sent according to that priority.

I don't understand how the prioritization is orthogonal?  You claimed that when restarting a browser there are many requests to send which will look similar. (I agree.)  But the browser should prioritize the requests for the "open" tab first (i.e. no/little benefit from a reference set for those requests).  Of course the requests for the other tabs _might_ benefit (still theory) from a reference set*, but does it really matter what the page load time is for the N-1 tabs the user isn't interacting with?

*I think this must also assume there is a proxy, rather than the client talking directly to multiple origins?

---

From: Michael Sweet <[email-masked]>
Date: Wed, 02 Jul 2014 06:52:57 -0400

Roberto,

On Jul 2, 2014, at 1:39 AM, Roberto Peon <[email-masked]> wrote:
> You're basing conclusions on today's data, instead of looking forward as to what might happen when the set of headers sent adapts to the compression method, making it significantly more likely for items in the reference set to be emitted.

Isn't that basically confirming what Kazu found: the reference set doesn't help with today's headers?

Here is running code that demonstrates that the reference set does not contribute significantly to the performance of HPACK. Unless you can demonstrate a significant improvement from (simple) server/client changes, your assertion that things will improve doesn't have any evidence to support it.

My observation is that the headers emitted by most web sites are not controlled by the web site developer, they will rely on the underlying web server and scripting engine (PHP, Perl, Python, Ruby, etc.) to do that.  The only header they generally do control is Set-Cookie, and then only for their own site (i.e. not for the advertising networks that are used).  What changes on the server side would be useful here to get the full benefit of the reference table?

(And IMHO if we do have this information then it should be in the HPACK spec...)

> 
> You may want to look at how many of those entries would be regularized if HPACK was in use and servers/clients intended on sending headers that were similar.
> -=R
> 
> 

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Kaoru Maeda <[email-masked]>
Date: Wed, 2 Jul 2014 22:52:51 +0900

Another advantage of removing reference set is that the order of header
fields is preserved.
This removes the needs for the following rule:
- section-8.1.2.3
      To preserve the order of multiple occurrences of a header field with
      the same name, its ordered values are concatenated into a single
      value using a zero-valued octet (0x0) to delimit them.

      After decompression, header fields that have values containing zero
      octets (0x0) MUST be split into multiple header fields before being
      processed.

Cookie now preserves the order of key-value pairs even if they are split
for "better-compression".  This might be important with regard to request
signing.

--
Kaoru Maeda

2014-07-02 19:52 GMT+09:00 Michael Sweet <[email-masked]>:

> You're basing conclusions on today's data, instead of looking forward as
> to what might happen when the set of headers sent adapts to the compression
> Here is running code that demonstrates that the reference set does not
> contribute significantly to the performance of HPACK. Unless you can
> demonstrate a significant improvement from (simple) server/client changes,
> your assertion that things will improve doesn't have any evidence to
> support it.
>
> My observation is that the headers emitted by most web sites are not
> controlled by the web site developer, they will rely on the underlying web
> server and scripting engine (PHP, Perl, Python, Ruby, etc.) to do that.
>  The only header they generally do control is Set-Cookie, and then only for
> their own site (i.e. not for the advertising networks that are used).  What
> changes on the server side would be useful here to get the full benefit of
> the reference table?
>

---

From: Johnny Graettinger <[email-masked]>
Date: Wed, 2 Jul 2014 12:06:38 -0400

A couple of comments:

The test set at https://github.com/http2jp/hpack-test-case/ tremendously
under-represents the impact of cookies. It's not *at all* uncommon to see
sites with 50+ cookie crumbs (nytimes.com had 58 at last count). My own
anecdote from browsing around and observing HPACK performance is that the
reference set helped, and that the real problem was the default initial
table size was too small to make full use of it. Of course, for obvious
privacy reasons it's tough to create a public test-set which fully
incorporates natural browsing sessions & cookies.

Chromium is already running a trial where all headers (including HTTP/1
origins) are run through an HPACK encoder (for purposes of identifying a
better Huffman code). It may be possible to extend the trial to examine
compression performance with & without the reference set; I'll look into it.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 2 Jul 2014 11:27:16 -0700

> As I understand it, one of the purposes of the reference set is to accommodate cases where intermediaries multiplex requests from different clients -- thus having different cookies, UAs, etc. -- in…

It's kinda the opposite actually.  The reference set clear is for that case.

Reference set is really good for server-to-server cases where the
request header fields are basically constant inter-request.  In those
cases, the marginal cost depends on how many headers are present, but
the difference is approximately 1 byte per header.

---

From: "Eric J. Bowman" <[email-masked]>
Date: Wed, 2 Jul 2014 18:54:39 -0600

> Inlining is the technique most often used to reduce the number of

I've also always considered it a worthwhile technique for byte-shaving,
as combining lots of small images into one mosaic image eliminates 
whatever redundant bytes are inherent to the chosen image format.

>
> It is a strategy that works well most of the time for cold
> pageloads, but it also harms latency for subsequent navigations
> deeper into the site as those resources cannot be cached.
>

But you lost me there, as I've never had a problem caching those
resources? Or does "inlining" not mean what I think it means?

-Eric

---

From: Roberto Peon <[email-masked]>
Date: Wed, 2 Jul 2014 18:16:37 -0700

You can cache an object that has inlined resources within it, but you
cannot cache those resources separately.
You can't cache a resource that doesn't have a name.

-=R

---

From: "Eric J. Bowman" <[email-masked]>
Date: Wed, 2 Jul 2014 19:38:12 -0600

> You can't cache a resource that doesn't have a name.

If I need to cache a resource separately, I don't inline it. I'm just
not seeing the latency problem with inlining, if it only occurs when
the technique isn't used properly?

-Eric

> > I've also always considered it a worthwhile technique for
> > byte-shaving, as combining lots of small images into one mosaic
> > image eliminates whatever redundant bytes are inherent to the
> > chosen image format.
> >
> > >

---

From: Roberto Peon <[email-masked]>
Date: Wed, 2 Jul 2014 18:54:59 -0700

It is fairly common to want to use the same css, js, and often even images
on the first pageload and subsequent navigations.

When you inline a resource, you cannot cache that inlined resource.
That means that you'll need to send it again if it is to be in the cache.
This implies wasted bytes, additional latency for that page load, or
complexity in doing fancy background loads.

With an efficient push mechanism, you don't inline.
You send the resources as themselves, achieving the benefit of inlining
without the poor caching consequences of using it.

-=R

---

From: "Eric J. Bowman" <[email-masked]>
Date: Wed, 2 Jul 2014 20:54:26 -0600

Roberto Peon wrote:
>
> It is fairly common to want to use the same css, js, and often even
> images on the first pageload and subsequent navigations.
> 

Sure.

> That means that you'll need to send it again if it is to be in the
> cache. This implies wasted bytes, additional latency for that page
> load, or complexity in doing fancy background loads.
> 

I still see this as a non-problem; if a resource needs to be cached
separately then it's silly to inline it, no? If it doesn't need to be a
first-order resource, then it'll cache just fine inlined. At least when
I use this technique, it's with images that are used most, if not every,
page load and I never need to refer to them individually. The result is
a simple background pre-load which saves bytes and reduces latency, and
I fail to see how the opposite is "implied" by inlining -- unless the
technique is being used improperly for resources which should have
their own URLs to begin with?

> You send the resources as themselves, achieving the benefit of
> inlining without the poor caching consequences of using it.
> 

Poor caching consequences of *mis-*using inlining. I still don't see
how it applies to how I, or anyone I know, uses inlining. I also
disagree that an efficient push mechanism will stop me from inlining
all the little images which make up the "chrome" of a site design
(which surely don't need to be first-order resources).

Say for instance, I have several "slivers" of gradient or whatever that
I'm going to repeat-x repeat-y. Inlining these into one image has no
downside vis-a-vis caching, plus the upside that it can shave maybe 80%
of the bytes incurred by image-format overhead. How would using push to
send them individually, benefit me in any way?

Of course, there are uses for push, I'm just not seeing it as any sort
of replacement for inlining. There's also a risk that one "sliver" needs
to be re-requested, leading to initial page-load rendering where the
"chrome" fills in at different times and looks awkward -- so I'd also
lose the cheap, no-frills "pre-load" inlining gives me such that site 
visitors come away with a positive first impression of site performance.

-Eric

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 3 Jul 2014 17:31:34 +0000

> send them individually, benefit me in any way?

I think you are using different definitions of inlining. Your view of inlining is to pack several images into one big image. Roberto's view is to encode these images inside the html document (this is more relevant for javascript and css than for images).

With one large html document including the images, you don't need to request these images after receiving the html, but you can't cache them for the next html document.

Hervé.

---

From: "Eric J. Bowman" <[email-masked]>
Date: Thu, 3 Jul 2014 17:43:51 -0600

RUELLAN Herve wrote:
> > Say for instance, I have several "slivers" of gradient or whatever
> > that I'm going to repeat-x repeat-y. Inlining these into one image
> > has no downside vis-a-vis caching, plus the upside that it can
> > shave maybe 80% of the bytes incurred by image-format overhead. How
> > would using push to send them individually, benefit me in any way?
> 
> I think you are using different definitions of inlining. Your view of
> inlining is to pack several images into one big image. Roberto's view
> is to encode these images inside the html document (this is more
> relevant for javascript and css than for images).
> 

Inlining can also refer to embedding images in CSS as data. Thanks for
clarifying, I was wondering if we were talking around each other.

>
> With one large html document including the images, you don't need to
> request these images after receiving the html, but you can't cache
> them for the next html document.
> 

OK, that makes sense, thanks.

-Eric