Subject: HPACK benchmark test for substitution indexing vs incremental indexing only

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 21 Sep 2013 21:12:28 +0900

I made a simple benchmark test for substitution indexing vs
incremental indexing only and share its results here.

The detailed results can be found at
https://github.com/tatsuhiro-t/nghttp2/wiki/hpackSubst

"""
HPACK draft offers 2 kind of indexing methods: incremental and
substitution. In nghttp2, we always use incremental
indexing. This is because we do not have good strategy to use
substitution indexing efficiently. We suspect that it is in the
draft because it has some use cases, but we don't see them yet.

So we did some tests comparing our incremental only strategy and
the experimental strategy utilizing substitution indexing.

Our incremental only strategy goes as follows:

1. If the name/value pair is in the header table, use indexed
   representation.

2. Else, if name is in the header table, use incremental indexing
   with indexed name.

3. Else, use incremental indexing with new name.

The experimental strategy utilizing substitution indexing changes
step 2 as follows:

2. Else, if name is in the header table, substitute that entry;
   use substitution indexing with indexed name.

We use data set in https://github.com/http2/http_samples.

The detailed results are listed in the following sections.

The end result is that, in the overall, incremental only strategy
is more efficient than the strategy with substitution. But the
difference is not so large. On some data set, the substitution
performed well, so depending on the data set, the winner may
change. Also there may be better strategy for substitution.
"""

It turns out that the experimental strategy is used in node-http2
and firefox.

---

From: Roberto Peon <[email-masked]>
Date: Sat, 21 Sep 2013 13:11:02 -0700

When I was doing a similar comparative analysis, I found that incremental
indexing did better than substitution indexing as well.
I suspect that substitution indexing benefits strongly from heuristics,
e.g. compute the probability that a header is reused and use that to
determine if you replace or not.
That being said, I'm still unsure if the complexity of substitution
indexing is worth the potential benefit.

-=R

---

From: Gábor Molnár <[email-masked]>
Date: Sat, 21 Sep 2013 23:21:01 +0200

It would be interesting to test if a substitution strategy is better than
incremental if it knows all the upcoming headers *in advance*. This would
simulate the performance of the best possible heuristic algorithm.

2013/9/21 Roberto Peon <[email-masked]>

> On Sat, Sep 21, 2013 at 5:12 AM, Tatsuhiro Tsujikawa <
> [email-masked]> wrote:
>

---

From: James M Snell <[email-masked]>
Date: Sat, 21 Sep 2013 14:56:16 -0700

Can't we just err on the side of simplicity and just use incremental? It is
possible to over analyze and over optimize.

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Sep 2013 06:40:01 +0000

I actually had written a compressor with foreknowledge to run against the data set that was sent to the list before the last meeting, specifically for the purpose of giving an "ideal" against which to measure real-world algorithms.

Today I did some refactoring and added a switch that blocks it from ever doing a substitution, always sending it down the path where it didn't find a suitable entry to replace.  The results suggest that the gain from being able to substitute is infinitesimal.  Given perfect knowledge of future headers, here's what I see from the first SQLite file:

  *
Substituting compressor:  36.036% of plaintext size
  *
Append-only compressor:  36.045% of plaintext size

When we're talking about ~0.01% gain in efficiency, I think there's a strong argument to be made in favor of simplicity.  (Incidentally, a quick performance profile of my code shows it spends the majority of its time deciding what entry to replace!)

Sent from Windows Mail

From: Gábor Molnár<mailto:[email-masked]>
Sent: ?Saturday?, ?September? ?21?, ?2013 ?4?:?23? ?PM
To: Roberto Peon<mailto:[email-masked]>
Cc: Tatsuhiro Tsujikawa<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>

It would be interesting to test if a substitution strategy is better than incremental if it knows all the upcoming headers *in advance*. This would simulate the performance of the best possible heuristic algorithm.

2013/9/21 Roberto Peon <[email-masked]<mailto:[email-masked]>>
When I was doing a similar comparative analysis, I found that incremental indexing did better than substitution indexing as well.
I suspect that substitution indexing benefits strongly from heuristics, e.g. compute the probability that a header is reused and use that to determine if you replace or not.
That being said, I'm still unsure if the complexity of substitution indexing is worth the potential benefit.

-=R

On Sat, Sep 21, 2013 at 5:12 AM, Tatsuhiro Tsujikawa <[email-masked]<mailto:[email-masked]>> wrote:
I made a simple benchmark test for substitution indexing vs
incremental indexing only and share its results here.

"""

---

From: Roberto Peon <[email-masked]>
Date: Mon, 23 Sep 2013 23:56:14 -0700

The other part to the argument for using only appends is that it allows for
some out-of-order processing for transports like TCP-Minion, where you can
receive segments out of order (e.g. when packet loss occurs for one
request, but the following one is unaffected).

I'm sure that none of us want to swallow that complexity today, mind you,
but it could be important in the nearish future.

-=R

On Mon, Sep 23, 2013 at 11:40 PM, Mike Bishop
<[email-masked]>wrote:

>  I actually had written a compressor with foreknowledge to run against
> the data set that was sent to the list before the last meeting,
> specifically for the purpose of giving an “ideal” against which to measure
> real-world algorithms.
>
>  Today I did some refactoring and added a switch that blocks it from ever
> doing a substitution, always sending it down the path where it didn’t find
> a suitable entry to replace.  The results suggest that the gain from being
> able to substitute is infinitesimal.  Given perfect knowledge of future
> headers, here’s what I see from the first SQLite file:
>
>    - Substituting compressor:  36.036% of plaintext size
>    - Append-only compressor:  36.045% of plaintext size
>
>
>  When we’re talking about ~0.01% gain in efficiency, I think there’s a
> strong argument to be made in favor of simplicity.  (Incidentally, a quick
> performance profile of my code shows it spends the majority of its time
> deciding what entry to replace!)
>
>  Sent from Windows Mail
>
>  *From:* Gábor Molnár <[email-masked]>
> *Sent:* Saturday, September 21, 2013 4:23 PM
> *To:* Roberto Peon <[email-masked]>
> *Cc:* Tatsuhiro Tsujikawa <[email-masked]>, [email-masked]
>
>  It would be interesting to test if a substitution strategy is better
> than incremental if it knows all the upcoming headers *in advance*. This
> would simulate the performance of the best possible heuristic algorithm.
>
>

---

From: James M Snell <[email-masked]>
Date: Tue, 24 Sep 2013 08:51:49 -0700

On Mon, Sep 23, 2013 at 11:40 PM, Mike Bishop
<[email-masked]> wrote:
>[snip]
>
> When we’re talking about ~0.01% gain in efficiency, I think there’s a strong
> argument to be made in favor of simplicity.  (Incidentally, a quick

Similar results on this end. Substitution is simply not worth the
extra complexity. +1 to dropping it.

I'm also not a fan of the name index reference option given that it
requires us to search the table for a suitable name index. I'd rather
take the somewhat less efficient on-the-wire encoding than scan the
table for name indexes.

- James

> Sent from Windows Mail
>
> From: Gábor Molnár
> Sent: ‎Saturday‎, ‎September‎ ‎21‎, ‎2013 ‎4‎:‎23‎ ‎PM
> To: Roberto Peon
> Cc: Tatsuhiro Tsujikawa, [email-masked]
>
>> <[email-masked]> wrote:
>>>

---

From: Fred Akalin <[email-masked]>
Date: Tue, 24 Sep 2013 10:53:10 -0700

> take the somewhat less efficient on-the-wire encoding than scan the

What "search"/"scan" is involved? If it's an index, then it's an index
lookup, which is pretty efficient for a deque, which is what the header
table should be implemented as.

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Sep 2013 19:49:14 +0000

Here I'll disagree, though I haven't coded a test for how much it's worth.  On the decompressor side, the expense is minimal (index lookup), and on the compressor side it's strictly optional.  (Though I suppose the same argument exists for substitution, really....)

Sent from Windows Mail

From: James M Snell<mailto:[email-masked]>
Sent: ?Tuesday?, ?September? ?24?, ?2013 ?10?:?52? ?AM
To: Mike Bishop<mailto:[email-masked]>
Cc: Gábor Molnár<mailto:[email-masked]>, Roberto Peon<mailto:[email-masked]>, Tatsuhiro Tsujikawa<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>

On Mon, Sep 23, 2013 at 11:40 PM, Mike Bishop
<[email-masked]> wrote:
>[snip]
>
> When we're talking about ~0.01% gain in efficiency, I think there's a strong

- James

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Sep 2013 12:52:13 -0700

No, substitution is different because it prevents some future usecases (the
head-of-line unblocking one).
Substitution is also different because it requires a non-linear memory
model and generally results in heap fragmentation, whereas strict
incremental indexing allows for a completely linear memory model with no
fragmenting.
-=R

On Tue, Sep 24, 2013 at 12:49 PM, Mike Bishop
<[email-masked]>wrote:

>  Here I’ll disagree, though I haven’t coded a test for how much it’s
> worth.  On the decompressor side, the expense is minimal (index lookup),
> and on the compressor side it’s strictly optional.  (Though I suppose the
> same argument exists for substitution, really….)
>
>  Sent from Windows Mail
>
>   *From:* James M Snell <[email-masked]>
> *Sent:* Tuesday, September 24, 2013 10:52 AM
> *To:* Mike Bishop <[email-masked]>
> *Cc:* Gábor Molnár <[email-masked]>, Roberto Peon<[email-masked]>,
> Tatsuhiro Tsujikawa <[email-masked]>, [email-masked]
>
> strong
> > Sent: Saturday, September 21, 2013 4:23 PM
> > To: Roberto Peon

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Sep 2013 12:53:00 -0700

Not to mention that the name encoding has a fair size impact on compression
efficiency.

-=R

On Tue, Sep 24, 2013 at 12:52 PM, Roberto Peon <[email-masked]> wrote:

> No, substitution is different because it prevents some future usecases
> (the head-of-line unblocking one).
> On Tue, Sep 24, 2013 at 12:49 PM, Mike Bishop <
> [email-masked]> wrote:
>
>> than

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Sep 2013 20:17:51 +0000

36% vs. 42% by eliminating backreferences, on my testbed.  Not huge, but certainly noticeable.

Sent from Windows Mail

From: Roberto Peon<mailto:[email-masked]>
Sent: ?Tuesday?, ?September? ?24?, ?2013 ?2?:?53? ?PM
To: Mike Bishop<mailto:[email-masked]>
Cc: James M Snell<mailto:[email-masked]>, Gábor Molnár<mailto:[email-masked]>, Tatsuhiro Tsujikawa<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>

Not to mention that the name encoding has a fair size impact on compression efficiency.

-=R

On Tue, Sep 24, 2013 at 12:52 PM, Roberto Peon <[email-masked]<mailto:[email-masked]>> wrote:
No, substitution is different because it prevents some future usecases (the head-of-line unblocking one).
Substitution is also different because it requires a non-linear memory model and generally results in heap fragmentation, whereas strict incremental indexing allows for a completely linear memory model with no fragmenting.
-=R

On Tue, Sep 24, 2013 at 12:49 PM, Mike Bishop <[email-masked]<mailto:[email-masked]>> wrote:
Here I'll disagree, though I haven't coded a test for how much it's worth.  On the decompressor side, the expense is minimal (index lookup), and on the compressor side it's strictly optional.  (Though I suppose the same argument exists for substitution, really....)

Sent from Windows Mail

From: James M Snell<mailto:[email-masked]>
Sent: Tuesday, September 24, 2013 10:52 AM

- James

> To: Roberto Peon
> Cc: Tatsuhiro Tsujikawa, [email-masked]<mailto:[email-masked]>
>
>> <[email-masked]<mailto:[email-masked]>> wrote:
>>>

---

From: James M Snell <[email-masked]>
Date: Tue, 24 Sep 2013 13:26:24 -0700

A difference we likely could easily make up for by applying typed
codecs on values that frequently change (e.g. dates, content-length,
etc).

On Tue, Sep 24, 2013 at 1:17 PM, Mike Bishop
<[email-masked]> wrote:
> From: Roberto Peon
> Sent: ‎Tuesday‎, ‎September‎ ‎24‎, ‎2013 ‎2‎:‎53‎ ‎PM
> To: Mike Bishop
> Cc: James M Snell, Gábor Molnár, Tatsuhiro Tsujikawa, [email-masked]
>
>>> worth.  On the decompressor side, the expense is minimal (index lookup), and
>>> on the compressor side it’s strictly optional.  (Though I suppose the same
>>> argument exists for substitution, really….)
>>>
>>> Sent from Windows Mail
>>>
>>> From: James M Snell
>>> To: Mike Bishop
>>> Cc: Gábor Molnár, Roberto Peon, Tatsuhiro Tsujikawa, [email-masked]
>>>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 24 Sep 2013 13:29:06 -0700

Yup, roughly ~15% of the compressor's efficiency is due to this, per my old
calculations. Yours suggests ~14%, which seems in-line.
This is regardless of using various other encodings (e.g. huffman), which
also affect output size-- those should affect the output roughly linearly
with the amount of text given.

-=R

On Tue, Sep 24, 2013 at 1:17 PM, Mike Bishop
<[email-masked]>wrote:

>   *From:* Roberto Peon <[email-masked]>
> *Sent:* Tuesday, September 24, 2013 2:53 PM
> *Cc:* James M Snell <[email-masked]>, Gábor Molnár<[email-masked]>,

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Sep 2013 20:52:41 +0000

…or squeeze further, since those are wins on values, while this is a win on the names.  😊

Sent from Windows Mail

From: James M Snell<mailto:[email-masked]>
Sent: ‎Tuesday‎, ‎September‎ ‎24‎, ‎2013 ‎3‎:‎26‎ ‎PM
To: Mike Bishop<mailto:[email-masked]>
Cc: Roberto Peon<mailto:[email-masked]>, Gábor Molnár<mailto:[email-masked]>, Tatsuhiro Tsujikawa<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 27 Sep 2013 16:34:56 +0000

I've ran some tests on the "mnot" test set and I've been able to see some effect from using substitution:
- Substituting compressor:   29.5%
- Append-only compressor: 30.3%

It's true that the effect of substitution is limited on average. However, it allows building an intelligent encoder that can take advantage of knowledge about the headers.

Hervé.

> -----Original Message-----
> From: Mike Bishop [mailto:[email-masked]]
> Sent: mardi 24 septembre 2013 08:40
> To: Gábor Molnár; Roberto Peon
> Cc: Tatsuhiro Tsujikawa; [email-masked]
> Subject: Re: HPACK benchmark test for substitution indexing vs incremental
> indexing only
> 
> I actually had written a compressor with foreknowledge to run against the
> data set that was sent to the list before the last meeting, specifically for the
> purpose of giving an “ideal” against which to measure real-world algorithms.
> 
> doing a substitution, always sending it down the path where it didn’t find a
> suitable entry to replace.  The results suggest that the gain from being able to
> substitute is infinitesimal.  Given perfect knowledge of future headers,
> here’s what I see from the first SQLite file:
> 
> *
> From: Gábor Molnár <mailto:[email-masked]>
> To: Roberto Peon <mailto:[email-masked]>
> Cc: Tatsuhiro Tsujikawa <mailto:[email-masked]> , ietf-http-
> [email-masked]
> 
> 	When I was doing a similar comparative analysis, I found that
> incremental indexing did better than substitution indexing as well.
> 		We use data set in https://github.com/http2/http_samples
> <https://github.com/http2/http_samples> .
>

---

From: Leif Hedstrom <[email-masked]>
Date: Fri, 27 Sep 2013 14:08:50 -0600

> It's true that the effect of substitution is limited on average. However, it allows building an intelligent encoder that can take advantage of knowledge about the headers.

That seems very underwhelming. Are there any other (public) test sets / results that shows that this "intelligence" is worth the complexity?

I much prefer keeping things simple too, I have concerns that the complexity of the compressor will be a deterrent for adoptation.

Cheers,

-- Leif

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 28 Sep 2013 23:35:45 +0900

> - Append-only compressor: 30.3%
Since these numbers are much better than the my results (which is 39% and
37% respectively),
I'm very interested in the algorithm you used to achieve them.
Could you share it with us?
Is it some kind of algorithm to take advantage of the complete knowledge of
incoming headers?
Or based on statistics on today's web traffic?

Note that my results combine request and response headers.

Because of relative difference is small, I'm lean to the side to remove
substitution for now.
Mostly it is because the decoder have to pay for it. The encoder can just
skip substitution
if it wants, but decoder has no choice.

Best regards,

Tatsuhiro Tsujikawa

> It's true that the effect of substitution is limited on average. However,
> it allows building an intelligent encoder that can take advantage of
> knowledge about the headers.
>
> Hervé.
>
> >               It turns out that the experimental strategy is used in
> node-
> > http2
> >               and firefox.
> >
> >
> >
>
>