hpackSubst

HPACK: substitution benchmark test

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.

incremental only strategy

comp1

Sum of compressed bytes of HTTP request

plain1

Sum of uncompressed bytes of HTTP request

ratio1

comp1/plain1

comp2

Sum of compressed bytes of HTTP response

plain2

Sum of uncompressed bytes of HTTP response

ratio2

comp2/plain2

overall ratio

(comp1+comp2)/(plain1+plain2)

data set	comp1	plain1	ratio1	comp2	plain2	ratio2	overall ratio
amazon.com.har	56277	197034	0.29	71250	147748	0.48	0.37
baidu.com.har	49096	210998	0.23	40056	112797	0.36	0.28
bbc.co.uk.har	94807	201809	0.47	53104	108675	0.49	0.48
craigslist.org.har	2020	12976	0.16	3538	9458	0.37	0.25
ebay.com.har	48226	125775	0.38	33155	71264	0.47	0.41
facebook.com.har	9411	42674	0.22	15357	37215	0.41	0.31
flickr.com.har	44009	122952	0.36	54818	133117	0.41	0.39
linkedin.com.har	42376	79604	0.53	19062	42692	0.45	0.50
msn.com.har	80021	196563	0.41	55037	116980	0.47	0.43
nytimes.com.har	216526	612472	0.35	89288	216843	0.41	0.37
pinterest.com.har	70482	394783	0.18	112276	204909	0.55	0.30
qq.com.har	20687	97420	0.21	20793	71385	0.29	0.25
sina.com.cn.har	98104	401158	0.24	102853	256925	0.40	0.31
taobao.com.har	73427	286154	0.26	97803	169648	0.58	0.38
wikipedia.org.har	23429	85504	0.27	37066	74069	0.50	0.38
yahoo.co.jp.har	23232	71189	0.33	43471	68381	0.64	0.48
yahoo.com.har	63481	105570	0.60	26790	54802	0.49	0.56
yandex.ru.har	25598	69288	0.37	11984	35918	0.33	0.36
youtube.com.har	33550	80778	0.42	16837	49420	0.34	0.39

overall: comp1=1074759 comp2=904538 total=1979297 ratio=0.37

experimental strategy utilizing substitution indexing

data set	comp1	plain1	ratio1	comp2	plain2	ratio2	overall ratio
amazon.com.har	56683	197034	0.29	63422	147748	0.43	0.35
baidu.com.har	55585	210998	0.26	43016	112797	0.38	0.30
bbc.co.uk.har	99676	201809	0.49	55141	108675	0.51	0.50
craigslist.org.har	2672	12976	0.21	3974	9458	0.42	0.30
ebay.com.har	49902	125775	0.40	34164	71264	0.48	0.43
facebook.com.har	10683	42674	0.25	15425	37215	0.41	0.33
flickr.com.har	44383	122952	0.36	52332	133117	0.39	0.38
linkedin.com.har	42145	79604	0.53	20414	42692	0.48	0.51
msn.com.har	85289	196563	0.43	57782	116980	0.49	0.46
nytimes.com.har	227394	612472	0.37	90889	216843	0.42	0.38
pinterest.com.har	78189	394783	0.20	109205	204909	0.53	0.31
qq.com.har	22038	97420	0.23	26303	71385	0.37	0.29
sina.com.cn.har	114834	401158	0.29	110756	256925	0.43	0.34
taobao.com.har	77258	286154	0.27	101822	169648	0.60	0.39
wikipedia.org.har	22588	85504	0.26	37200	74069	0.50	0.37
yahoo.co.jp.har	25253	71189	0.35	44085	68381	0.64	0.50
yahoo.com.har	64288	105570	0.61	28958	54802	0.53	0.58
yandex.ru.har	28518	69288	0.41	14030	35918	0.39	0.40
youtube.com.har	34667	80778	0.43	19534	49420	0.40	0.42

overall: comp1=1142045 comp2=928452 total=2070497 ratio=0.39