Subject: [quicwg/base-drafts] Duplication can use different indexing (#1128)

From: Martin Thomson <[email-masked]>
Date: Tue, 20 Feb 2018 19:18:45 -0800

A duplication instruction never references the static table.  Currently however, this is possible, and it's not a great idea.

Aside from it being pointless to duplicate entries in the static table (it costs space and time to do this, and references to these new entries will have longer encodings than static table references), in the current design the encoding of the duplication instruction is such that virtually every duplication instruction has to use a two octet encoding because exactly one entry in the dynamic table can be duplicated in one octet.  Duplication of this entry is completely useless because duplicating it does nothing to improve its position in the table.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128

---

From: MikkelFJ <[email-masked]>
Date: Wed, 21 Feb 2018 03:23:20 +0000 (UTC)

Can please refer to QCRAM or HTTP on this and similar issues - it’s otherwise hard to decipher context.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367201745

---

From: afrind <[email-masked]>
Date: Wed, 21 Feb 2018 17:20:43 +0000 (UTC)

One proposed solution comes from the QPACK draft, which is to use a bit in the instruction to indicate if a referenced index is static or dynamic.  I found that this actually simplified parts of the implementation compared to HPACK/QCRAM's unified index space.  If we separate the instruction space, then we can define duplication to always operate on the dynamic table index space.  It also may compress slightly better, since more dynamic indexes can be encoded by a single byte.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367402335

---

From: afrind <[email-masked]>
Date: Wed, 21 Feb 2018 10:20:36 -0800

@mikkelfj : is the -qcram tag insufficient to differentiate? Would you prefer something in the issue title?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367420969

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 21 Feb 2018 18:29:20 +0000 (UTC)

When I read these issues that are pushed in email there is no visibility of
the tag.

As a non-editor I cannot set tags for an issue, so it makes it hard to
imply scope.

This situation is not unliveable.

However, some projects define a namespace to be used in the issue title in
order to help such situations. "qcram" and "hq" might be enough to help to
disambiguate from transport, security etc.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367423821

---

From: MikkelFJ <[email-masked]>
Date: Wed, 21 Feb 2018 10:55:47 -0800

@afrind yes QCRAM in the title is fine, or qcram:, just something. The issue is with email as @LPardue says.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367432059

---

From: Martin Thomson <[email-masked]>
Date: Wed, 21 Feb 2018 15:42:29 -0800

@afrind, the extra bit is less efficient overall (see also why arithmetic coding is superior to Huffman).  Especially given that the static table is a fixed size.  I don't find the indexing that onerous, so I don't think that the extra bit would help.  That is, unless we get a proposal for a new, bigger static table.  Having references to the dynamic table start at (for example) 200, would make the bit a good investment.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367516719

---

From: afrind <[email-masked]>
Date: Thu, 22 Feb 2018 17:52:18 +0000 (UTC)

If we leave the on-the-wire index space unified, is the proposal to use a different indexing scheme for this instruction only (eg: skip the + 62)?  I'm not crazy about having two different indexing schemes in the design, but otherwise it would solve the issues you raise above.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367764371

---

From: Martin Thomson <[email-masked]>
Date: Fri, 23 Feb 2018 00:36:39 +0000 (UTC)

Well, let's decide the other thing first, because that will drive any design here.  (-62 is the obviously choice assuming we change nothing else).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-367871005

---

From: Mike Bishop <[email-masked]>
Date: Sun, 25 Feb 2018 14:45:34 +0000 (UTC)

Actually, the optimal change for length's sake would be to use a totally different reference point.  You typically want to duplicate the things that are about to fall off the end, so count from the **oldest** item that hasn't been dropped yet.  Since you can only send this on the control stream, both sides have a synchronized view about what that is.

That's not great for comprehension, necessarily, but....

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-368315024

---

From: Martin Thomson <[email-masked]>
Date: Sun, 25 Feb 2018 16:25:39 -0800

Right.  That was in my original write-up.  The reverse indexing is the most efficient.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-368359696

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 09:14:22 -0800

There's already of 3 different ways indexes are written on the wire: Absolute Index, Hybrid (relative an encoded base), and Relative (HPACK style, relative to head).  An implementation may also have an internal indexing scheme (eg: indexes into an array of headers).  How many bytes are we going to save introducing a Relative-to-end style?  A few every time user-agent and Accept get near the end of the table?  I'd prefer to burn the bytes and keep the draft a bit simpler.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-368576477

---

From: Mike Bishop <[email-masked]>
Date: Mon, 26 Feb 2018 18:56:44 +0000 (UTC)

Depends on how the instruction space lands, but odds are one byte per duplicate instruction seems a likely outcome.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-368609062

---

From: afrind <[email-masked]>
Date: Mon, 26 Feb 2018 21:19:45 +0000 (UTC)

My question was how often to we wrap around and need to duplicate, and how many will need duplication?  I assume it takes several or dozens of requests of normal usage to wrap.  How many headers will implementations want to duplicate when a wrap occurs?  I can see a browser re-adding the handful that are sent on every request.  Also note that this is all gravy over HPACK which would just evict and re-insert.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1128#issuecomment-368654230