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

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