Subject: [quicwg/base-drafts] 3+ and 4+ in the QPACK wire format are complex and inefficient (#3561)

From: Kazu Yamamoto <[email-masked]>
Date: Mon, 30 Mar 2020 18:21:53 -0700

For instance, QPACK uses the following wire format:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |NameLen(3+)|
+---+---+---+---+---+-----------+
|  Name String (Length bytes)   |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
|  Value String (Length bytes)  |
+-------------------------------+
```

The designers of QPACK make use of 3 bits of the flag part. But HPACK uses the following wire format:

```
0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

The designers of HPACK did not use 4 bits and chose 7+ for name length.

Let's calculate integer ranges of one/two/three bytes for each N+:

```
N+   1   2     3 <- bytes
8  127 382 16638
7   63 254 16510
6   31 190 16446
5   15 158 16414
4    7 142 16398
3    3 134 16390
2    1 130 16386
1    0 128 16384
```

One byte of 3+ can only express 0 - 3. In most cases, two bytes of 3+ are necessary for the length of header names. 

So, why don't we use 7+ for simplicity?

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |     0     |
+---+---+---+---+---+-----------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length bytes)   |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
|  Value String (Length bytes)  |
+-------------------------------+
```

This keeps the length of wire format in most cases and enables us to reuse the code of HPACK.

-- 
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/3561

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Mar 2020 20:14:13 -0700

This isn't as bad as is made out.  An 8+ prefix can encode up to 254 without overflowing.  A 3+ prefix can encode 6.  4+ is 14.  These fields are used both for indexing and for name lengths.

For name lengths, there are quite a few header fields that can be encoded in 14 bytes.  Post-base indexing (a feature I still don't really like) is a little hard up, but there are still a few 6 byte names.

Using these for indexing likely does save a lot of space as I expect that indices won't be far from the base in most cases (especially for post-base).

Finally, I'd be opposed to making changes this late in the process.

-- 
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/3561#issuecomment-606373129

---

From: Kazu Yamamoto <[email-masked]>
Date: Mon, 30 Mar 2020 21:14:01 -0700

The table above is not correct. Here is the right one:

```
8  254 382 16638
7  126 254 16510
6   62 190 16446
5   30 158 16414
4   14 142 16398
3    6 134 16390
2    2 130 16386
1    0 128 16384
```

-- 
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/3561#issuecomment-606388346

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Mar 2020 10:30:57 -0700

The current encoding is consistent with the design principle agreed to in Seattle that compression performance trumps other considerations.  This decision has driven much of the subsequent QPACK development.

-- 
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/3561#issuecomment-606767671

---

From: Mike Bishop <[email-masked]>
Date: Tue, 31 Mar 2020 11:02:34 -0700

Let's look at the 3+ and 4+ cases:

- Literal with Post-Base Name Reference.  A 3+ can reference up to 6 values before spilling into a second byte, and the expectation is that there will usually be very few post-base entries to reference.  I would expect this to be single-byte much of the time.
- Literal without Name Reference.  I agree that there are very few names that won't require a second byte, so this doesn't come out any better most of the time.  There are also very few names that will require a third byte, so it's also no worse.
- Indexed with Post-Base Index.  A 4+ can reference up to 14 values in a single byte.  Here again, we expect there to be few Post-Base entries, so I would expect this to be single-byte most of the time.
- Literal with Name Reference.  We designed the static table's order to fill the first 14 slots with names of fields that you often won't to add to the dynamic table.  (That's why so many of the first 14 entries have an empty value.)  My expectation, which could be proven wrong by more data, is that this fits in a single byte often enough to have some benefit.

As to the complexity, I don't see it.  As soon as you have to write an encoder/decoder function that takes the prefix length as an argument, no prefix length is more complex than any other.

-- 
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/3561#issuecomment-606783795

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 31 Mar 2020 11:11:47 -0700

This issue proposes a design change to QPACK. Further evidence that weighs against the responses above is required before considering taking this on in the Late Stage Process.

-- 
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/3561#issuecomment-606788145

---

From: afrind <[email-masked]>
Date: Tue, 31 Mar 2020 11:23:28 -0700

I concur with the other responders here.  

1. Sharing code with HPACK is a non-goal 
2. The instructions as specified do save some bytes
3. It's not that complex to add a string encoding function that takes a prefix for the length 
4. Most of all, we shouldn't be making design changes this late

-- 
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/3561#issuecomment-606793719

---

From: Kazu Yamamoto <[email-masked]>
Date: Tue, 31 Mar 2020 13:49:28 -0700

Thank you for discussions. It seems to me that people feel "we shouldn't be making design changes this late". So, let's close this.

-- 
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/3561#issuecomment-606867236

---

From: Kazu Yamamoto <[email-masked]>
Date: Tue, 31 Mar 2020 13:49:30 -0700

Closed #3561.

-- 
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/3561#event-3185112227