W3C home > Mailing lists > Public > ietf-http-wg@w3.org > July to September 2013

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

From: Mike Bishop <Michael.Bishop@microsoft.com>
Date: Tue, 24 Sep 2013 20:52:41 +0000
To: James M Snell <jasnell@gmail.com>
CC: Roberto Peon <grmocg@gmail.com>, Gábor Molnár <gabor.molnar@sch.bme.hu>, Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com>, "ietf-http-wg@w3.org" <ietf-http-wg@w3.org>
Message-ID: <18fe855cc61e44428790ab44d7379a5f@BY2PR03MB025.namprd03.prod.outlook.com>
…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:jasnell@gmail.com>
Sent: ‎Tuesday‎, ‎September‎ ‎24‎, ‎2013 ‎3‎:‎26‎ ‎PM
To: Mike Bishop<mailto:Michael.Bishop@microsoft.com>
Cc: Roberto Peon<mailto:grmocg@gmail.com>, Gábor Molnár<mailto:gabor.molnar@sch.bme.hu>, Tatsuhiro Tsujikawa<mailto:tatsuhiro.t@gmail.com>, ietf-http-wg@w3.org<mailto:ietf-http-wg@w3.org>

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
<Michael.Bishop@microsoft.com> wrote:
> 36% vs. 42% by eliminating backreferences, on my testbed.  Not huge, but
> certainly noticeable.
>
> Sent from Windows Mail
>
> From: Roberto Peon
> Sent: ‎Tuesday‎, ‎September‎ ‎24‎, ‎2013 ‎2‎:‎53‎ ‎PM
> To: Mike Bishop
> Cc: James M Snell, Gábor Molnár, Tatsuhiro Tsujikawa, ietf-http-wg@w3.org
>
> 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 <grmocg@gmail.com> 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
>> <Michael.Bishop@microsoft.com> 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
>>> Sent: Tuesday, September 24, 2013 10:52 AM
>>>
>>> To: Mike Bishop
>>> Cc: Gábor Molnár, Roberto Peon, Tatsuhiro Tsujikawa, ietf-http-wg@w3.org
>>>
>>> On Mon, Sep 23, 2013 at 11:40 PM, Mike Bishop
>>> <Michael.Bishop@microsoft.com> 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
>>> > performance profile of my code shows it spends the majority of its time
>>> > deciding what entry to replace!)
>>> >
>>>
>>> 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, ietf-http-wg@w3.org
>>> >
>>> > 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 <grmocg@gmail.com>
>>> >>
>>> >> 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
>>> >> <tatsuhiro.t@gmail.com> wrote:
>>> >>>
>>> >>> 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.
>>> >>>
>>> >>
>>> >
>>
>>
>
Received on Tuesday, 24 September 2013 20:53:29 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 17:14:15 UTC