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

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.
>>
>>
>