Subject: Implementer intent -- option 3 for #578

From: Mark Nottingham <[email-masked]>
Date: Thu, 23 Oct 2014 12:01:46 +1100

It looks like there's a good amount of interest in Option 3 (Willy's proposal) for issue #578. However, there's also concern that it is untested, and pushback on that basis.

I am *extremely* wary of making a substantial change in the protocol at the last minute without implementation and testing; there is a large risk of introducing bugs, security issues and interop problems.

So, if we want to pursue option #3, I think we need to do another Implementation Draft based upon it, with a subsequent interop. This will blow out our schedule by one cycle; historically, that means about two to three months (although the holiday season is approaching, so it may be longer).

Such an interop might be another Interim (likely in January), or it might be virtual; we'd figure that out later. 

With that in mind, I'd like to hear from our implementers -- who is interested in this enough to implement a new draft and be able to bring it an interop on such a timeframe?

Please, one person per implementation, and identify your implementation as you do so (we have enough now that it's necessary).

Note that I'm not saying we're converging on option 3 yet -- I'm trying to find out more about what it would mean if we go in that direction.

Cheers,

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

---

From: Greg Wilkins <[email-masked]>
Date: Thu, 23 Oct 2014 13:03:34 +1100

Speaking for Jetty.

I completely agree that if we were to adopt Option 3, then another cycle is
justified to test it.

I definitely think something needs to be done as if the current static
table is etched into a standard it will be a bit of an embarrassment for
all time (kind of like the spelling of referer :)

I think a revised static table like I've proposed in
https://github.com/http2/http2-spec/issues/587   is perhaps a compromise
that would not need the extra cycle, but achieve many of the benefits with
little cost.

In short, getting it right is more important for us than getting it out
before Q2-2015.  We don't think the status quo is right, but could live
with either a #587 style fix in the short term or an option 3 fix in the
mid term.

cheers

On 23 October 2014 12:01, Mark Nottingham <[email-masked]> wrote:

> It looks like there's a good amount of interest in Option 3 (Willy's
> proposal) for issue #578. However, there's also concern that it is
> untested, and pushback on that basis.
>
> I am *extremely* wary of making a substantial change in the protocol at
> the last minute without implementation and testing; there is a large risk
> of introducing bugs, security issues and interop problems.
>
> So, if we want to pursue option #3, I think we need to do another
> Implementation Draft based upon it, with a subsequent interop. This will
> blow out our schedule by one cycle; historically, that means about two to
> three months (although the holiday season is approaching, so it may be
> longer).
>
> With that in mind, I'd like to hear from our implementers -- who is
> interested in this enough to implement a new draft and be able to bring it
> an interop on such a timeframe?
>
> Please, one person per implementation, and identify your implementation as
> you do so (we have enough now that it's necessary).
>
> Note that I'm not saying we're converging on option 3 yet -- I'm trying to
> find out more about what it would mean if we go in that direction.
>
> Cheers,
>
>
> --

-- 
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: Adrian Cole <[email-masked]>
Date: Wed, 22 Oct 2014 19:52:34 -0700

For OkHttp (Android), I can do an implementation within a couple weeks of
the draft.

Depending on timing of the draft, it may get into version 2.1, which is
still baking, or worst 2.2.

I can also help test Netty and/or provide nagging service :)

-A

---

From: Shigeki Ohtsu <[email-masked]>
Date: Thu, 23 Oct 2014 12:44:53 +0900

I (iij-http2) will implement this. This change is not so hard to test 
and debug compared to the pasts.

Regards,

---

From: Mark Nottingham <[email-masked]>
Date: Thu, 23 Oct 2014 15:22:54 +1100

> On 23 Oct 2014, at 1:03 pm, Greg Wilkins <[email-masked]> wrote:
> 
> I think a revised static table like I've proposed in https://github.com/http2/http2-spec/issues/587   is perhaps a compromise that would not need the extra cycle, but achieve many of the benefits with little cost.
>   
> In short, getting it right is more important for us than getting it out before Q2-2015.  We don't think the status quo is right, but could live with either a #587 style fix in the short term or an option 3 fix in the mid term.

Thanks, Greg. If other folks feel this way, I'd appreciate hearing it.

Cheers,

---

From: Amos Jeffries <[email-masked]>
Date: Thu, 23 Oct 2014 17:50:26 +1300

On 23/10/2014 5:22 p.m., Mark Nottingham wrote:
>> https://github.com/http2/http2-spec/issues/587   is perhaps a
>> compromise that would not need the extra cycle, but achieve many
>> of the benefits with little cost.
>> 
>> In short, getting it right is more important for us than getting
>> it out before Q2-2015.  We don't think the status quo is right,
>> but could live with either a #587 style fix in the short term or
>> an option 3 fix in the mid term.
> 

I feel the same way as Greg on this, and feel confident saying the
other Squid develoeprs agree as well.

"Getting it right" is one of the reasons we have not run ahead with a
quick update and joined the implementors party already.

Amos

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 23 Oct 2014 07:15:32 +0200

Hi Mark,

> Note that I'm not saying we're converging on option 3 yet -- I'm trying to find out more about what it would mean if we go in that direction.

Speaking for haproxy, I'm far from having anything close to an implementation
and don't expect to have one by the time we have a standard. However I'll
implement whatever encoding we come up with by then since I'm not worried
with swapping a few bits around. What matters for me is that we don't emit
a new frozen standard that adapts poorly to new use cases. We've known the
set-cookie mess, NTLM, pipelining issues and such things causing all of us
some trouble with H1, I find it important to care a lot about possible
future implementations.

I would like it if someone with an easy-to-modify implementation could run
some tests quickly, as I mostly focused minimizing changes first without
having a working implementation to verify them, and am convinced the
encoding I proposed is not optimal (as shown later in the same thread),
and we'd rather ensure we don't degrade current performance in a new
draft (which was the cause for this proposal). But since we don't have
numbers yet, we could have good surprizes as well.

Also since Jeff is the one who experienced the regression in the first
place, he definitely has an example of problematic workload. It would
be nice if he could either give this a try, or provide some traces to
someone with a flexible implementation.

Best regards,
Willy

---

From: Cory Benfield <[email-masked]>
Date: Thu, 23 Oct 2014 08:55:35 +0100

> With that in mind, I'd like to hear from our implementers -- who is interested in this enough to implement a new draft and be able to bring it an interop on such a timeframe?

I'd implement for hyper.

---

From: Michael Sweet <[email-masked]>
Date: Thu, 23 Oct 2014 07:00:30 -0400

About getting it right? Absolutely I agree.

Much better to spend a little time getting HTTP/2 "right" than to have to abandon it  for the mythical HTTP/3 that keeps getting mentioned, particularly if the changes are relatively minor and can be tested quickly and easily.

The extra time will also give us more interop results, which can only help to improve the specification and protocol.

> On Oct 23, 2014, at 12:22 AM, Mark Nottingham <[email-masked]> wrote:
> 
> 

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: "Simpson, Robby (GE Energy Management)" <[email-masked]>
Date: Thu, 23 Oct 2014 14:51:42 +0000

On 10/22/14, 9:01 PM, "Mark Nottingham" <[email-masked]> wrote:

>interested in this enough to implement a new draft and be able to bring
>it an interop on such a timeframe?

Depending on location, I would be willing to participate.

My implementation doesn't have a name yet -- Embedded H2? ;-)

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 24 Oct 2014 01:53:09 +0900

On Thu, Oct 23, 2014 at 2:15 PM, Willy Tarreau <[email-masked]> wrote:

> > Such an interop might be another Interim (likely in January), or it
> might be virtual; we'd figure that out later.
> >
> > Please, one person per implementation, and identify your implementation
> as you do so (we have enough now that it's necessary).
> >
> > Note that I'm not saying we're converging on option 3 yet -- I'm trying
> to find out more about what it would mean if we go in that direction.
>
​I've done quick hack to implement option 3 in nghttp2:
https://github.com/tatsuhiro-t/nghttp2/tree/hpack-opt3

Not much tested, but it should work for me with hpack-test-cases.

deflatehd under src directory is handy to test compression ratio.
I don't have custom header dominated data to experiment with.

​I still think that unless it shows drastic improvements over -09 draft,
another interop is not worth it.

​Best regards,
Tatsuhiro Tsujikawa
​

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 23 Oct 2014 19:23:02 +0200

Hello,

On Fri, Oct 24, 2014 at 01:53:09AM +0900, Tatsuhiro Tsujikawa wrote:
> ???I've done quick hack to implement option 3 in nghttp2:

Thank you very much for this!

> I don't have custom header dominated data to experiment with.

Maybe Jeff can run his headers through it and compare ? That way he
won't have to publish sensitive data.

> ???I still think that unless it shows drastic improvements over -09 draft,

The goal was not to show some drastic improvements but to address the
regressions that make Jeff want to switch back to previous one, and at
the same time try to avoid that same situation repeating for many other
users in the future. I do think that what we have is fine but does not
adequately cover *certain* workloads (it tends to be over-optimized for
regular browsing only as we know it in 2014).

Best regards,
Willy

---

From: Nicholas Hurley <[email-masked]>
Date: Thu, 23 Oct 2014 10:39:22 -0700

I'm not convinced another interop is worth considering until this scheme
has been shown to be a *significant* improvement for *all* use cases
over the status quo. Mark has said the only four reasons we would accept
any changes at this point are:

> a) editorial improvements
> b) substantial interop problems
> c) serious security issues
> d) changes that have broad consensus (i.e., we all agree it's worth it)

and furthermore went on to say that the only category this option falls
under is (d), and that "if making these changes is controversial, we
haven't met the bar".

So far, I haven't seen this be a totally non-controversial change
(though I understand it's not my call to make). That said, there is (to
my mind) a way the proponents of this change can remove any controversy
- by proving that this option is a wholesale improvement. We don't need
another interop draft for that, just someone to run a decent number of
test cases (that fall under both the "better with static table first"
and "better with dynamic table first" buckets) and show us the numbers.
Tatsuhiro has provided an implementation for anyone who doesn't want to
update their own (or write their own), so let's wait to see what the
numbers tell us before making what is currently at best a speculative
change to the spec.
-- 
Peace,
  -Nick

---

From: "Kulkarni, Saurabh" <[email-masked]>
Date: Thu, 23 Oct 2014 12:49:25 -0500

+1 (Akamai server). Not worth it at this point of time.

- Saurabh

---

From: Mike Bishop <[email-masked]>
Date: Thu, 23 Oct 2014 18:02:00 +0000

+1 to this.  Microsoft is not going to implement this in our code in the required time frame, but if there's data that can demonstrate substantial advantages across the board, we wouldn't object to pulling the change into the spec.

-----Original Message-----
From: Nicholas Hurley [mailto:[email-masked]] 
Sent: Thursday, October 23, 2014 10:39 AM
To: Mark Nottingham; HTTP Working Group
Subject: Re: Implementer intent -- option 3 for #578

> d) changes that have broad consensus (i.e., we all agree it's worth 

and furthermore went on to say that the only category this option falls under is (d), and that "if making these changes is controversial, we haven't met the bar".

So far, I haven't seen this be a totally non-controversial change (though I understand it's not my call to make). That said, there is (to my mind) a way the proponents of this change can remove any controversy
- by proving that this option is a wholesale improvement. We don't need another interop draft for that, just someone to run a decent number of test cases (that fall under both the "better with static table first"
and "better with dynamic table first" buckets) and show us the numbers.
Tatsuhiro has provided an implementation for anyone who doesn't want to update their own (or write their own), so let's wait to see what the numbers tell us before making what is currently at best a speculative change to the spec.
--
Peace,
  -Nick

---

From: Michaela LaVan <[email-masked]>
Date: Thu, 23 Oct 2014 18:46:03 -0400

Google is in favor of adopting Willy's proposal if there is data
demonstrating improved performance as a result of the change. We may not be
able to contribute data of our own in time for IETF 90, however.

On Thu, Oct 23, 2014 at 2:02 PM, Mike Bishop <[email-masked]>
wrote:

> +1 to this.  Microsoft is not going to implement this in our code in the
> required time frame, but if there's data that can demonstrate substantial
> advantages across the board, we wouldn't object to pulling the change into
> the spec.
>
> has been shown to be a *significant* improvement for *all* use cases over
> the status quo. Mark has said the only four reasons we would accept any
> changes at this point are:
>
> So far, I haven't seen this be a totally non-controversial change (though
> I understand it's not my call to make). That said, there is (to my mind) a
> way the proponents of this change can remove any controversy
> another interop draft for that, just someone to run a decent number of test
> cases (that fall under both the "better with static table first"

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 24 Oct 2014 14:20:23 +1100

I'm sensing a theme develop here, and it's entirely reasonable to say that we shouldn't block for 2+ months for an optimisation without any supporting data.

We already have an implementation of the proposal, so what we need now is a test corpus.

That presents a problem, since it's highly subjective (extension headers are very site-specific) and often fraught with privacy issues. 

What I'd suggest is that we agree upon an algorithm to synthesise some headers, do so, and use one corpus to test both approaches.

Straw-man:

- 10000 request messages, using the same gzip context
- each request has five standard headers (:method :scheme :authority :path user-agent)
- each standard header has a fixed value of an appropriate length
- each request has five custom headers, selected from a pool of ten custom headers
- each custom header has a field-name between 10 and 20 characters long
- five of the custom headers has a field-value consisting of random data 40 characters long
- five of the custom headers have a fixed value 40 characters long

Thoughts? 

> On 24 Oct 2014, at 9:46 am, Michaela LaVan <[email-masked]> wrote:
> 
> Google is in favor of adopting Willy's proposal if there is data demonstrating improved performance as a result of the change. We may not be able to contribute data of our own in time for IETF 90, however.
> 
> On Thu, Oct 23, 2014 at 2:02 PM, Mike Bishop <[email-masked]> wrote:

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 24 Oct 2014 14:25:48 +1100

To clarify: we'd test with these synthetic headers to get an idea of how things that use custom headers would behave; we'd still test using the "normal" web corpus as we have before.

Cheers,

> On 24 Oct 2014, at 2:20 pm, Mark Nottingham <[email-masked]> wrote:
>

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 07:55:02 +0200

Hi Mark,

On Fri, Oct 24, 2014 at 02:20:23PM +1100, Mark Nottingham wrote:
> I'm sensing a theme develop here, and it's entirely reasonable to say that we
> shouldn't block for 2+ months for an optimisation without any supporting
> data.
> 
> That presents a problem, since it's highly subjective (extension headers are
> very site-specific) and often fraught with privacy issues. 
> 
> What I'd suggest is that we agree upon an algorithm to synthesise some
> headers, do so, and use one corpus to test both approaches.
> 
> Straw-man:
> 

We should have a few variations on the value (eg: :path, accept, cookie).

> - five of the custom headers have a fixed value 40 characters long

I think that's entirely reasonable but at the same time it contains the
same default as what lead to this thread : we define a single model that
looks average and we don't measure the variations when going to more or
less standard cases, which explains why people with working implementations
are more or less interested in a change depending on what they observe.

Thus I think that we should define 3 "models" to test in fact :
  - the "average" one as you describe above
  - the "browser" one with a single custom header out of the 10
  - the "partner" one with 9 out of the 10 custom headers

That way we can see if one model shows an important deviation using one or
another encoding. In my opinion, an adequate encoding (I mean a safe one
for the future) should be reasonably good on all cases and show limited
variations around the average model.

Once we're able to synthetize the requests for a given model, it's easy
to build the two other ones, so  think it should be done.

Opinions ?

Thanks,
Willy

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 24 Oct 2014 17:56:37 +1100

> On 24 Oct 2014, at 4:55 pm, Willy Tarreau <[email-masked]> wrote:
> 
> Hi Mark,
> 

Yup.

> to build the two other ones, so  think it should be done.

Sure, with the proviso that actually interpreting what's a useful difference is still undefined, and likely to cause some debate.

But let's go ahead and try, since the cost is relatively low. I'll write some Python this weekend (possibly tonight, subject to family stuff) to generate some header sets; if other folks can do the crunching code and have it ready, that'd be much appreciated.

Unless I hear otherwise, I'm going to do HTTP/1 style header sets separated by double-newlines; e.g.,

:scheme: https
:authority: foo.com
:path: /abc
foo: bar

:scheme: http
:authority: bar.com
:path: /def
baz: bat

and so on...

I'll put it in a repo for inspection / pulls. Whoever does the other code should as well.

Cheers,

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 09:50:18 +0200

On Fri, Oct 24, 2014 at 05:56:37PM +1100, Mark Nottingham wrote:
> Sure, with the proviso that actually interpreting what's a useful difference
> is still undefined, and likely to cause some debate.

Sure, but I think it's not a big issue, because :
  - if we find important differences, there should be a rought consensus
    for the best solution
  - if there's no noticeale gain, that means it's best not to change a iota.

And at least I hear that the persons less interested in changing are in
this thinking so that should not be a problem.

> But let's go ahead and try, since the cost is relatively low. I'll write some
> Python this weekend (possibly tonight, subject to family stuff) to generate
> some header sets; if other folks can do the crunching code and have it ready,
> that'd be much appreciated.

Great. I unfortunately cannot build deflatehd, I'm still trying to figure
why it fails while the rest is OK.

> by double-newlines; e.g.,

Looks fine, it's how I've been handling headers as well till now.

> I'll put it in a repo for inspection / pulls. Whoever does the other code

Does anyone have an encoder which can be easily extracted from his/her
implementation and be fed with many requests like this ? It would save
a significant amount of work.

Cheers,
Willy

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 24 Oct 2014 21:33:12 +1100

Toy up at:
  https://gist.github.com/mnot/434ab029a6e878b2af4c

Cheers,

> On 24 Oct 2014, at 6:50 pm, Willy Tarreau <[email-masked]> wrote:
> 

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

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 24 Oct 2014 21:29:17 +0900

Hi,

The option 3 implementation I emailed earlier had D bit accidentally flipped
(so D is 1 for static table).  It was now fixed in github repository.

Best regards,
Tatsuhiro Tsujikawa

On Fri, Oct 24, 2014 at 7:33 PM, Mark Nottingham <[email-masked]> wrote:

> >> Unless I hear otherwise, I'm going to do HTTP/1 style header sets
> separated
> >> by double-newlines; e.g.,
> >>
> >> :scheme: https
> >> :authority: foo.com
> >> :path: /abc
> >> foo: bar
> >>
> >> :scheme: http
> >> :authority: bar.com
> >> :path: /def
> >> baz: bat
> >>
> >> and so on...
> >
> >> I'll put it in a repo for inspection / pulls. Whoever does the other
> code
> >> should as well.
> >

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 20:56:08 +0200

Hi Mark,

>   https://gist.github.com/mnot/434ab029a6e878b2af4c

Thank you, I could use it. I noticed that the random names it produces
can sometimes be used as a custom fixed header, sometimes as a custom
random header. It's no big deal, but I think it does not accurately
model reality since we'd rather have some fixed headers (eg: customer
name) and some always random ones (eg: signature, timestamp). I also
thought that we could have a few partially random values (those who
change from time to time such as x-forwarded-for behind a proxy), but
I don't think it will change things a lot anyway.

So in turn I have worked today :-)

I implemented a simple encoder which parses your program's output and
emits statistics on the output data. It does not emit the output bytes,
it just performs the encoding and counts. It's almost nothing to add,
it is just that I had no use for the output.

It supports 4 encodings :
  - draft 09
  - the proposal I sent that was called "option 3"
  - the proposed revision I sent just after it
  - Greg's proposed revision

It reports various statistics such as number of strings encoded, number
of integers encoded, average integer size etc... I have run some tests
all on the same output from your program, and got interesting findings
already :

Draft-09 :
        Total input bytes : 7455384
        Total output bytes : 2318395            (100%)
        Overall compression ratio : 0.310969    (100%)
        Total encoded integers: 218865
        Total encoded integers bytes: 295036    (100%)
        Avg bytes per integers: 1.348027        (100%)

option3 :
        Total input bytes : 7455384
        Total output bytes : 2268350            (97.84%)
        Overall compression ratio : 0.304257    (97.84%)
        Total encoded integers: 218865
        Total encoded integers bytes: 244991    (83.03%)
        Avg bytes per integers: 1.119370        (83.03%)

revised option3 :
        Total input bytes : 7455384
        Total output bytes : 2264722            (97.68%)
        Overall compression ratio : 0.303770    (97.68%)
        Total encoded integers: 218865
        Total encoded integers bytes: 241363    (81.81%)
        Avg bytes per integers: 1.102794        (81.81%)

Greg's revision :
        Total input bytes : 7455384
        Total output bytes : 2280713            (98.37%)
        Overall compression ratio : 0.305915    (98.37%)
        Total encoded integers: 218865
        Total encoded integers bytes: 257354    (87.23%)
        Avg bytes per integers: 1.175857        (87.23%)

First, the overall compression ratio is never exceptional given that the
input contains a significant amount of random data, so that's expected.
Second, we observe that the integer encoding is 17-18% smaller compared
to draft-09. And if we consider the integer encoding's overhead, then it
is even divided by 3.4 (0.34 byte to 0.10 byte per integer).

The overall savings are 2.1% for "option 3", 2.3% for its revision, and
1.7% for Greg's proposal. To my initial surprise, Greg's proposal provides
less savings here despite being balanced. But in the end there's a reason,
it offers more bits to literals while it's the case where we already have
to pay for the literal overhead so the occasional saving of 1-byte doesn't
save much.

I have experimented with an option in the code to write fully random headers
as literal-without-indexing (as the producer would do, but not a gateway
which doesn't know which ones are stable and which ones are not). And while
doing so improves the compression ratio, the offset from draft-09 and the
other ones does not change.

I have not yet tried to modify your program to vary the output between a
browser (less custom) or a partner site (more custom). But I wanted to share
these results already as I think they can be helpful.

All the code is available here :

  https://github.com/wtarreau/http2-exp

The readme is ugly when parsed as md, I've never written md docs so it
seems I'm lacking some basic practice here. But I'm sure nobody will
care, reading it in the console or as raw is OK.

Ah, there's also a debug mode which indicates what encoding is chosen for
each field and how long the resulting sequence is. It helped me debug it,
and I found it useful to understand how the table evolves.

Comments welcome. It's my first HPACK encoder, it's very possible that I
messed up a lot with certain things, though I didn't notice that. In any
case, feel free to comment/fork/fix/etc.

Best regards,
Willy

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 21:01:33 +0200

BTW, I forgot to say something, I was very surprized to find the encoding
for character zero in the huffmann table be shorter than some non-ascii
encodings, and the same size as some chars such as '$' or '@'. I wonder
how this byte could have landed here with such a high frequency. Wouldn't
this mean that the trailing zero of analyzed strings was accidentely
counted when the table was built ? That probably has a very minimal impact
on the overall compression ratio but I found this surprizing.

Regards,
Willy

---

From: Martin Thomson <[email-masked]>
Date: Fri, 24 Oct 2014 21:19:54 +0200

On 24 October 2014 21:01, Willy Tarreau <[email-masked]> wrote:
> encodings, and the same size as some chars such as '
> or '@'. I wonder

That's because it was being used to delineate values for repeated
header fields, prior to the removal of the reference set.  We could
remove it from the frequency analysis and generate a new character
table if we were making other changes.  The difference might not be
noticeable.

https://github.com/http2/http2-spec/issues/636 opened and closed.

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 21:39:45 +0200

> these results already as I think they can be helpful.

OK so I did experiment a bit with it, by changing numCustom, randPortion,
and the header length in xrange() (which I couldn't manage to make random,
I don't know python unfortunately so I stopped after a few failed attempts).
BTW, your program is east to tweak, I like the ability to play with the
random ratio :-)

With 0 custom header, both option3 and its revision show exactly
identical encoding size as draft-09. Things start to diverge as we
add some custom headers, make them random, and/or shrink them.
Here are a few measures :

1 custom, 0 random
==================

              Draft09       Option3   Option3-rev
Out Bytes       290515       290516      290515
Comp ratio    0.127440     0.127441    0.127440
Avg int len   1.000000     1.000014    1.000000

10 custom, 0 random
==================
              Draft09       Option3   Option3-rev
Out Bytes       380494       380495      380494
Comp ratio    0.051046     0.051046    0.051046
Avg int len   1.000000     1.000006    1.000000

10 custom, 1 random (40 chars)
==============================
              Draft09       Option3   Option3-rev
Out Bytes       807817       800899      800154
Comp ratio    0.108350     0.107422    0.107322
Avg int len   1.268482     1.228282    1.223953

10 custom, 5 random (40 chars)
==============================
              Draft09       Option3   Option3-rev
Out Bytes      2317974      2267884     2264295
Comp ratio    0.310991     0.304270    0.303789
Avg int len   1.347906     1.119018    1.102618

10 custom, 9 random (40 chars)
==============================
              Draft09       Option3   Option3-rev
Out Bytes      3642593      3554173     3548090
Comp ratio    0.488855     0.476989    0.476172
Avg int len   1.391184     1.051465    1.028093

10 custom, 10 random (40 chars)
==============================
              Draft09       Option3   Option3-rev
Out Bytes      3775212      3683286     3676886
Comp ratio    0.506571     0.494236    0.493378
Avg int len   1.395324     1.048590    1.024449

10 custom, 1 random (15 chars, like an IP address)
==================================================
              Draft09       Option3   Option3-rev
Out Bytes       619601       612145      611510
Comp ratio    0.086027     0.084992    0.084904
Avg int len   1.380320     1.336844    1.333141

10 custom, 5 random (15 chars, like an IP address)
==================================================
              Draft09       Option3   Option3-rev
Out Bytes      1315119      1266085     1262805
Comp ratio    0.211944     0.204041    0.203513
Avg int len   1.396611     1.170302    1.155164

10 custom, 9 random (15 chars, like an IP address)
==================================================
              Draft09       Option3   Option3-rev
Out Bytes      1890435      1802153     1796431
Comp ratio    0.363410     0.346439    0.345339
Avg int len   1.409927     1.068155    1.046003

10 custom, 1 random (4 chars like for "True", "On", "off", "none", ...)
=======================================================================
              Draft09       Option3   Option3-rev
Out Bytes       537138       529401      528759
Comp ratio    0.075722     0.074632    0.074541
Avg int len   1.434113     1.388931    1.385182

10 custom, 5 random (4 chars like for "True", "On", "off", "none", ...)
=======================================================================
              Draft09       Option3   Option3-rev
Out Bytes       867352       818404      815336
Comp ratio    0.153420     0.144762    0.144219
Avg int len   1.422646     1.195593    1.181362

10 custom, 9 random (4 chars like for "True", "On", "off", "none", ...)
=======================================================================
              Draft09       Option3   Option3-rev
Out Bytes      1111734      1023424     1018046
Comp ratio    0.263832     0.242875    0.241598
Avg int len   1.418619     1.075517    1.054622

10 custom, 10 random (4 chars like for "True", "On", "off", "none", ...)
=======================================================================
              Draft09       Option3   Option3-rev
Out Bytes      1017368       924432      918561
Comp ratio    0.263935     0.239825    0.238302
Avg int len   1.417041     1.064313    1.042030

Note that at this point, we've reached 10% savings on the wire!

So I guess that if Jeff is using a lot of custom headers as he says,
he might very well have observed a significant degradation. It's worth
noting that the encoded integer length quickly reaches high levels as
soon as there are a few random custom headers in draft-09. The shorter
these custom headers, the higher the impact of the integer encoding.
In the last example above, an average request was 102 bytes with
draft-09 and only 92 with the proposals. That's 10 bytes saved per
request for only 10 short custom headers. I think it's worth studying
that option.

Best regards,
Willy

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 24 Oct 2014 21:41:50 +0200

Hi Martin!

On Fri, Oct 24, 2014 at 09:19:54PM +0200, Martin Thomson wrote:
> header fields, prior to the removal of the reference set.

Ah yes I remember now, thanks!

> We could

Indeed. I don't expect any savings either, but if the table is ever
revisited, sure it's worth taking care of this.

Thanks!
Willy

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 27 Oct 2014 13:48:31 -0700

Thanks for that, Willy.

Asking the question directly — of the people who -1’d making changes for #578, have these numbers changed your mind?

Cheers,

> On 24 Oct 2014, at 11:56 am, Willy Tarreau <[email-masked]> wrote:
> 
> Hi Mark,
>

---

From: Nicholas Hurley <[email-masked]>
Date: Mon, 27 Oct 2014 17:05:03 -0700

I'll chime in. Short answer - no, these have not changed my mind at all.
If anything, they've reinforced my view.

These numbers are, once again, along the same lines of other changes
we've already rejected as a working group - relatively miniscule
improvements that are not worth invalidating testing we have already
done. If this change improved the compression ratio significantly then
we might have something worth investigating in another implementation
draft. These numbers don't indicate any significant improvement in
compression ratio, and so don't warrant any further investigation.

On Mon, Oct 27, 2014, at 13:48, Mark Nottingham wrote:
> Thanks for that, Willy.
> 
> Asking the question directly — of the people who -1’d making changes for
> #578, have these numbers changed your mind?
> 
> Cheers,
> 
> 

-- 
Peace,
  -Nick

---

From: Amos Jeffries <[email-masked]>
Date: Tue, 28 Oct 2014 15:10:00 +1300

On 28/10/2014 1:05 p.m., Nicholas Hurley wrote:
> I'll chime in. Short answer - no, these have not changed my mind at
> all. If anything, they've reinforced my view.
> 
> These numbers are, once again, along the same lines of other
> changes we've already rejected as a working group - relatively
> miniscule improvements that are not worth invalidating testing we
> have already done. If this change improved the compression ratio
> significantly then we might have something worth investigating in
> another implementation draft. These numbers don't indicate any
> significant improvement in compression ratio, and so don't warrant
> any further investigation.

Huh?  -10% bandwidth reduction == "miniscule" savings ?

Statistically speaking 5% change in any one use case is "sigificant".

Amos

---

From: Nicholas Hurley <[email-masked]>
Date: Mon, 27 Oct 2014 19:48:20 -0700

> Huh?  -10% bandwidth reduction == "miniscule" savings ?

*sigh* I should've known someone would pull that out, wrong/misleading
though it may be in this case. Taking 10% off of an already really small
number leaves you with (drumroll, please)... an insignificantly smaller
number! And let's not forget, that (miniscule) 10% was in only one case;
the other cases Willy showed were even less impressive than that (and I
maintain that his "amazing" 10% is in no way impressive to begin with).
-- 
Peace,
  -Nick

---

From: Amos Jeffries <[email-masked]>
Date: Tue, 28 Oct 2014 17:43:52 +1300

On 28/10/2014 3:48 p.m., Nicholas Hurley wrote:
> *sigh* I should've known someone would pull that out,
> wrong/misleading though it may be in this case. Taking 10% off of
> an already really small number leaves you with (drumroll,
> please)... an insignificantly smaller number!

Statistical significance is (N >= 0.05) .

Only in *absolute* terms is the number small. At these compression
scales it means the difference of a whole extra request per packet.
Scale that up to TB/s rates and call it insignificant!

> And let's not forget, that (miniscule) 10% was in only one case; 
> the other cases Willy showed were even less impressive than that
> (and I maintain that his "amazing" 10% is in no way impressive to
> begin with).
> 

What I see in Willys' numbers is a handful of use-cases. Some of which
are not benefiting much - but most importantly not being degraded),
and some which have been causing controversy getting a significant %
reduction.

I also see people arguing earlier over reduction of a few individual
bits on the wire. Here is several whole bytes easily shaved off in a
way that reduces controversy. What's not to like?

Amos

---

From: Martin Thomson <[email-masked]>
Date: Mon, 27 Oct 2014 21:55:42 -0700

> Statistical significance is (N >= 0.05) .

I think that this is a good time to remind people that we aren't
looking for perfection.  The reference set provides a far better
compression gain than anything I've seen in this thread, in any case.
We dropped that due to concerns over complexity.

We've always said that we are merely looking for a robust and
efficient compression scheme, not a perfect one.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 28 Oct 2014 08:04:57 +0100

Hi Martin,

> efficient compression scheme, not a perfect one.

The goal of the proposed change was not to seek perfection at all, but
to fix a defect of the current method which makes it degrade in certain
environments and *will* make it degrade over time as new headers are
introduced. It may for example save us from having to introduce a new
static table in a few years to work around the current defect.

In my opinion it's important to listen to people who invented this
compressor. When one of its authors considers that the current version
is now biased and will not correctly adapt to the future, this has
much more significance to me than the few minutes a handful of early
implementers who do not need to understand how compression works
will have to spend to update their running code (because changing
from draft-09 to the other ones really took minutes here). Also,
Tatsuhiro has already updated his code so for some people it might
simply be a matter of rebuilding the code.

Best regards,
Willy

---

From: "Kulkarni, Saurabh" <[email-masked]>
Date: Tue, 28 Oct 2014 12:22:02 -0500

+1 to Nick¹s comment. Not interesting enough to warrant another
implementation draft.

- Saurabh

On 10/27/14, 5:05 PM, "Nicholas Hurley" <[email-masked]> wrote:

>> Asking the question directly ‹ of the people who -1¹d making changes for

---

From: Mike Bishop <[email-masked]>
Date: Tue, 28 Oct 2014 20:08:28 +0000

+1 here, as well.  Interesting, but going from ~40% efficiency to ~36% efficiency doesn't feel like it's really moving the needle enough to respin.

-----Original Message-----
From: Kulkarni, Saurabh [mailto:[email-masked]] 
Sent: Tuesday, October 28, 2014 10:22 AM
To: Nicholas Hurley; Mark Nottingham; Willy Tarreau; HTTP Working Group
Subject: Re: #578: getting real-ish numbers for option 3

- Saurabh

On 10/27/14, 5:05 PM, "Nicholas Hurley" <[email-masked]> wrote:

>> Asking the question directly < of the people who -1¹d making changes 
>> for #578, have these numbers changed your mind?
>> 
>> Cheers,
>> 
>> 
>> > Thank you, I could use it. I noticed that the random names it 
>> > produces can sometimes be used as a custom fixed header, sometimes 
>> > as a custom random header. It's no big deal, but I think it does 
>> > not accurately model reality since we'd rather have some fixed 
>> > headers (eg: customer
>> > name) and some always random ones (eg: signature, timestamp). I 
>> > also thought that we could have a few partially random values 
>> > (those who change from time to time such as x-forwarded-for behind 
>> > a proxy), but I don't think it will change things a lot anyway.
>> > 
>> > I implemented a simple encoder which parses your program's output 
>> > and emits statistics on the output data. It does not emit the 
>> > output
>>bytes,
>> > it just performs the encoding and counts. It's almost nothing to 
>> > add, it is just that I had no use for the output.
>> > 
>> > of integers encoded, average integer size etc... I have run some 
>> > tests all on the same output from your program, and got interesting 
>> > findings already :
>> > 
>> > Draft-09 :
>> > First, the overall compression ratio is never exceptional given 
>> > that
>>the
>> > to draft-09. And if we consider the integer encoding's overhead, 
>> > then
>>it
>> > it offers more bits to literals while it's the case where we 
>> > already
>>have
>> > I have experimented with an option in the code to write fully 
>> > random
>>headers
>> > which doesn't know which ones are stable and which ones are not). 
>> > And
>>while
>> > doing so improves the compression ratio, the offset from draft-09 
>> > and
>>the
>> > The readme is ugly when parsed as md, I've never written md docs so 
>> > it seems I'm lacking some basic practice here. But I'm sure nobody 
>> > will care, reading it in the console or as raw is OK.
>> > 
>> > Ah, there's also a debug mode which indicates what encoding is 
>> > chosen
>>for
>> > each field and how long the resulting sequence is. It helped me 
>> > debug
>>it,
>> > messed up a lot with certain things, though I didn't notice that. 
>> > In
>>any