Subject: Header compression question: duplicate header entry and current index on computing working set

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Thu, 18 Jul 2013 00:56:31 +0900

Hi,

The header compression draft 3.2 says the implementation must accept
duplicate entry
in header table.
In 3.4, to compute working set from reference set of headers, the index of
entry in header table is required.
The question is, when the duplicate entries are in the header table, which
index is used as the index of working set?
My understanding of reference set of headers is that it is just a set of
name/value pairs without index. To compute working set from it, one has to
check each pair in header table and get its index in it.

Best regards,

Tatsuhiro Tsujikawa

---

From: Martin Thomson <[email-masked]>
Date: Wed, 17 Jul 2013 09:36:22 -0700

> index is used as the index of working set?

If, for some strange reason, a compressor created multiple identical
entries in the table, the decompressor is required to respect that
choice, even if it is likely to be a bug.  This prevents the
decompressor and compressor from getting out of sync.

The compressor can then reference any of the entries when using an index.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Thu, 18 Jul 2013 01:51:33 +0900

> The compressor can then reference any of the entries when using an index.

If the choice is arbitrary, then the compressor and decompressor may choose
different index and
can get out of sync.

For example,
Current header table:
|0|name1|value1|
|1|name1|value1|

If name1/value1 is in reference set, compressor chooses index 0, and
decompressor chooses index 1.
compressor wants to remove name1/value1, so reference index 0.
In decompressor side, however, seeing index header representation with
index 0 and it is not in its reference set
(because name1/value1 is index 1), retrieve index 0 from header table and
add it to working set.
Maybe I misunderstand the draft.

If multiple identical entries are considered as a bug, then it would be
better to
prohibit it in the spec and we are happy to not to consider these things.

Best regards,

Tatsuhiro Tsujikawa

---

From: Mike Bishop <[email-masked]>
Date: Wed, 17 Jul 2013 16:59:08 +0000

How did the object get into the reference set?  Because the compressor referenced an object by index, or included it as a literal and added it to the table.

So the object in the reference set points to the entry in the table it was added with.  If there happens to be another identical entry in the table, nothing says that the decompressor will even notice that.  I don't recall anything that requires the decompressor to sweep the header table looking for matches - that's the compressor's job.

From: Tatsuhiro Tsujikawa [mailto:[email-masked]]
Sent: Wednesday, July 17, 2013 9:52 AM
To: Martin Thomson
Cc: [email-masked]
Subject: Re: Header compression question: duplicate header entry and current index on computing working set

On Thu, Jul 18, 2013 at 1:36 AM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:

If the choice is arbitrary, then the compressor and decompressor may choose different index and
can get out of sync.

For example,
Current header table:
|0|name1|value1|
|1|name1|value1|

If name1/value1 is in reference set, compressor chooses index 0, and decompressor chooses index 1.
compressor wants to remove name1/value1, so reference index 0.
In decompressor side, however, seeing index header representation with index 0 and it is not in its reference set
(because name1/value1 is index 1), retrieve index 0 from header table and add it to working set.
Maybe I misunderstand the draft.

If multiple identical entries are considered as a bug, then it would be better to
prohibit it in the spec and we are happy to not to consider these things.

Best regards,

Tatsuhiro Tsujikawa

---

From: Jeff Pinner <[email-masked]>
Date: Wed, 17 Jul 2013 10:08:15 -0700

Doesn't the decompressor have to sweep the table to create the new
reference set and compare the (index, name, value) entries?

On Wed, Jul 17, 2013 at 9:59 AM, Mike Bishop
<[email-masked]>wrote:

>  How did the object get into the reference set?  Because the compressor
> referenced an object by index, or included it as a literal and added it to
> the table.****
>
> ** **
>
> So the object in the reference set points to the entry in the table it was
> added with.  If there happens to be another identical entry in the table,
> nothing says that the decompressor will even notice that.  I don’t recall
> anything that requires the decompressor to sweep the header table looking
> for matches – that’s the compressor’s job.****
>
> ** **
>
> *From:* Tatsuhiro Tsujikawa [mailto:[email-masked]]
> *Sent:* Wednesday, July 17, 2013 9:52 AM
> *To:* Martin Thomson
> *Cc:* [email-masked]
> *Subject:* Re: Header compression question: duplicate header entry and
> current index on computing working set****
>
> ** **
>
> ** **
>
> ** **
>
> On Thu, Jul 18, 2013 at 1:36 AM, Martin Thomson <[email-masked]>
> wrote:****
>
> > index is used as the index of working set?****
>
> The compressor can then reference any of the entries when using an index.*
> ***
>
>  ** **
>
> If the choice is arbitrary, then the compressor and decompressor may
> choose different index and****
>
> can get out of sync.****
>
> ** **
>
> For example,****
>
> Current header table:****
>
> |0|name1|value1|****
>
> |1|name1|value1|****
>
> ** **
>
> decompressor chooses index 1.****
>
> compressor wants to remove name1/value1, so reference index 0.****
>
> index 0 and it is not in its reference set****
>
> add it to working set.****
>
> Maybe I misunderstand the draft.****
>
> ** **
>
> better to****
> prohibit it in the spec and we are happy to not to consider these things.*
> ***
>
> ** **
>
> Best regards,****
>
> ** **
>
> Tatsuhiro Tsujikawa****
>
> ** **
>
> ** **
>

---

From: Roberto Peon <[email-masked]>
Date: Wed, 17 Jul 2013 12:39:33 -0700

Not necessarily-- If the encoder/compressor says that element 5 is k,v, and
then it also appends k,v as element 7, for example.

When this happens things are less efficient, yes, but that is it.

There has been little optimization around duplicate k,v entries because
1) It is very uncommon
2) It doesn't break anything
3) There doesn't seem to be a good reason to encourage the behavior by
optimizing for it.
-=R

On Wed, Jul 17, 2013 at 10:08 AM, Jeff Pinner <[email-masked]> wrote:

> On Wed, Jul 17, 2013 at 9:59 AM, Mike Bishop <[email-masked]
> > wrote:
>
>> So the object in the reference set points to the entry in the table it
>> was added with.  If there happens to be another identical entry in the
>> table, nothing says that the decompressor will even notice that.  I don’t
>> recall anything that requires the decompressor to sweep the header table
>> looking for matches – that’s the compressor’s job.****
>>
>> ** **
>>
>> ****
>> ****

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 19 Jul 2013 00:48:34 +0900

>From the responses, I'm under the impression that reference set is the set
of reference to the entry in the header table, and not the set of
name/value pairs.
I am now convinced that multiple duplicate entries are no problem with this
method, well as long as the encoder and decoder uses this method.

Since the spec seems to infer that reference set is just a pair of name and
value (Appendix B shows only name/value pairs, not index), one may think
that the reference set is name/value pair set and do the sweep header table
to get index. The node-http2 implements this way.
If the encoder uses the method described above and decoder uses sweep, then
they may be out of sync if there is duplicate in the header table.
Personally I much prefer the first method since it avoids sweeps and string
matching.
But this problem only occurs when the encoder throws duplicate entry to the
header table and since it is buggy and even considered as "bug", so as long
as the encoder is good enough not to do this, there are no problem.

Best regards,

Tatsuhiro Tsujikawa

On Thu, Jul 18, 2013 at 4:39 AM, Roberto Peon <[email-masked]> wrote:

> Not necessarily-- If the encoder/compressor says that element 5 is k,v,
> and then it also appends k,v as element 7, for example.
>
>> On Wed, Jul 17, 2013 at 9:59 AM, Mike Bishop <
>> [email-masked]> wrote:
>>
>>> On Thu, Jul 18, 2013 at 1:36 AM, Martin Thomson <
>>> [email-masked]> wrote:****
>>>
>>> (because name1/value1 is index 1), retrieve index 0 from header table
>>> and add it to working set.****
>>>