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

Can't we just err on the side of simplicity and just use incremental? It is
possible to over analyze and over optimize.
On Sep 21, 2013 2:23 PM, "Gábor Molnár" <gabor.molnar@sch.bme.hu> wrote:

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