Subject: [quicwg/base-drafts] Make using static table and Huffman encoding in QPACK opt-in (#3622)

From: Victor Vasiliev <[email-masked]>
Date: Fri, 01 May 2020 00:21:31 -0700

I've spent some time recently thinking about how easy it is to implement a minimal version of HTTP/3 on top of an existing QUIC implementation.  HTTP/3 wire protocol at its very core is conceptually a really simple thing (it's just a way to transfer some stream of data with key-value pairs attached on both sides).  It has a lot of more advanced features, but most of those (server push, priorities) are opt-in.  However, one notable thing that is not opt-in is QPACK, as it's the only supported way to serialize headers.

Currently, an endpoint can avoid a lot of complexity in QPACK by setting SETTINGS_QPACK_MAX_TABLE_CAPACITY to zero; this allows implementing QPACK without having to manage the dynamic table.  However, this still leaves the static table and especially the Huffman decoder as big sources of complexity.  I propose that we add a new setting (I suggest SETTINGS_QPACK_ENABLE_COMPRESSION since I don't have any better ideas right now) that indicates to the peer that the decoder is capable of accepting Huffman-encoded strings and header blocks formatted in any way other than "Literal Header Field Without Name Reference".  This way, QPACK effectively reverts to just being a key-value pair format, and it should be easy to add this parameter to an existing QPACK implementation.

This is obviously only helpful if we do it from the beginning, so I didn't want to file this away as a v2 issue.

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

---

From: Lucas Pardue <[email-masked]>
Date: Fri, 01 May 2020 05:24:56 -0700

I understand the attractiveness of the idea but I think we're too late in the process to seriously consider changing this, independent of the specific details of proposals.

How should a server that has no intention of enabling this setting respond to HEADERS that include other instructions? If the answer is to blow up the connection then the (unintended?) side effect will encourage clients to start connections by sending all requests as "Literal Header Field Without Name Reference" until they receive the setting. But that stage of a HTTP/3 connection is the exact place where static and huffman have the most value; we groomed the static table to suit best the first flights of client requests.

My concern is that by trying to accommodate some smaller segment of HTTP clients, we cause a serious regression compared to HTTP/2.

This sort of thing seems better suited to a version that is "profile of HTTP/3" that disables some things and mandates others.

-- 
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/3622#issuecomment-622367141

---

From: Christian Huitema <[email-masked]>
Date: Sun, 03 May 2020 06:37:48 -0700

@vasilvv Picoquic pretty much fits in your target category, an endpoint that wants to implement a minimal version of HTTP/3. The strategy was indeed to set the SETTINGS_QPACK_MAX_TABLE_CAPACITY to zero, and also to never attempt Huffman encoding. It turns out that Huffman decoding is mandatory, but Huffman encoding is not.

To gauge the resulting capacity, you can look at the file "h3zero.c" and "h3zero.h" in the [picoquic distribution](https://github.com/private-octopus): 
```
ubuntu@ip-172-31-61-32:~/picoquic/picohttp$ wc h3zero.*
 1407  7726 61150 h3zero.c
  235   897  9024 h3zero.h
 1642  8623 70174 total
```
The code includes Qpack, Huffman, and the formatting and parsing of H3 messages. It uses static tables used for Qpack and Huffman decoding. The Huffman decoding accounts for 327 lines of tables and code in h3zero.c, 23% of the total.

Back to your point, yes there is some complexity, but no it is not overwhelming. The complexity is mostly in analyzing the specs and then coding them. I suppose I could extract "h3zero" in a separate project so minimal implementations could link with it without bothering with Picoquic proper. 

-- 
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/3622#issuecomment-623111609

---

From: Martin Thomson <[email-masked]>
Date: Sun, 03 May 2020 22:30:42 -0700

```
$ gcc -Os -c -o h3zero.o h3zero.c && strip h3zero.o && wc -c h3zero.o
13488 h3zero.o
$ clang -Os -c -o h3zero.o h3zero.c && strip h3zero.o && wc -c h3zero.o
13456 h3zero.o
```

Not sure if this is helpful or not.  A constrained implementation might find 13k of object code horrifying.  The `picohttp_ct` program compiled with `-Os` and stripped is 685816 bytes, which isn't exactly lean, but it makes the 13k appear reasonable.

What is the benchmark here?

-- 
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/3622#issuecomment-623264799

---

From: Christian Huitema <[email-masked]>
Date: Mon, 04 May 2020 08:00:14 -0700

To answer the question, I did `#ifdef` the Huffman functionality in h3zero and redid the test. Compiling on an Ubuntu 19 VM with Huffman defined:
```
$ gcc -Os -c -o h3zero.o h3zero.c && strip h3zero.o && wc -c h3zero.o
13680 h3zero.o
```
And with Huffman defined out:
```
$ gcc -Os -c -o h3zero.o h3zero.c && strip h3zero.o && wc -c h3zero.o
8640 h3zero.o
```
The cost of Huffman decoding support appears to be 5KB of code. The remaining 8.6K include static QPACK and the parsing of minimal H3 frames.

The `picohttp_ct` program is a test program. It links with the test framework, so the 685K size has to be taken with a grain of salt. To give an other data point, the DNS over QUIC program built with the picoquic library is around 300KB. If I take that as a minimum reference, the added cost of Huffman decoding would be less than 1.5% of the total. But of course everything is relative, and 

@lars has experience developing QUIC for tiny devices. Maybe he has an opinion on 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/3622#issuecomment-623516017

---

From: Lucas Pardue <[email-masked]>
Date: Mon, 04 May 2020 08:23:21 -0700

You can also trade off object code for faster decoding, see @dtikhonov's blog post https://blog.litespeedtech.com/2019/09/16/fast-huffman-decoder/

Debating optimization trade-offs for a hypothetical customer is interesting but does not meet the criteria of evidence to accept this issue IMO.

-- 
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/3622#issuecomment-623529573

---

From: Lars Eggert <[email-masked]>
Date: Mon, 04 May 2020 08:29:41 -0700

With the ARM toolchain for the Cortex M4, here is the object size (second column) of the various functions in `h3zero.c`, largest first:
```
000007a8 00001010 D h3zero_qpack_huffman_table
00000000 00000630 D qpack_static
00000eb8 000003e8 T h3zero_parse_data_stream
00000c70 00000248 T h3zero_parse_qpack_header_frame
00000814 00000228 T hzero_qpack_huffman_decode
00000638 00000170 D h3zero_qpack_index
00000a3c 00000164 T h3zero_parse_qpack_header_value
000001e4 00000100 T h3zero_qpack_int_decode
000004c4 000000d4 T h3zero_create_post_header_frame
00000ba0 000000d0 T h3zero_get_interesting_header_type
0000008c 000000b8 T h3zero_qpack_int_encode
00000598 000000b8 T h3zero_create_request_header_frame
00000700 000000a4 T h3zero_create_bad_method_header_frame
00000370 00000094 T h3zero_get_content_type_by_name
000002e4 0000008c T h3zero_get_method_by_name
00000444 00000080 T h3zero_encode_content_type
00000014 00000078 T h3zero_varint_decode
00000174 00000070 t h3zero_qpack_literal_plus_ref_encode
000007a4 00000070 T h3zero_delete_data_stream_state
00000650 00000060 T h3zero_create_response_header_frame
000006b0 00000050 T h3zero_create_not_found_header_frame
00000404 00000040 T h3zero_parse_status
00000144 00000030 t h3zero_qpack_code_encode
00000000 00000014 T h3zero_varint_skip
0000006c 00000007 r h3zero_default_setting_frame_val
00000634 00000004 D nb_h3zero_qpack_index
000017b8 00000004 D nb_h3zero_qpack_huffman_table
00000630 00000004 D h3zero_qpack_nb_static
00000068 00000004 R h3zero_default_setting_frame_size
000017bc 00000004 D h3zero_default_setting_frame
```
So the table alone is about 1K. That's not great, but I'm also not sure if `qpack_static` is the most compact representation of this data.

In terms of code size, there are some easy gains just by using minimally-sized integer types. For example, only changing `index` to `uint8_t` and `enum_as_int` to `uint16_t` in `st_h3zero_qpack_static_t` saves you 368 bytes. If you can get rid of `uint64_t` as much as possible, that would probaly save you 1-2K in size right there. 

-- 
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/3622#issuecomment-623533385

---

From: Lars Eggert <[email-masked]>
Date: Mon, 04 May 2020 09:04:31 -0700

Need more coffee. `h3zero_qpack_huffman_table` is obviously ~4K, since this is hex. And very large.

With some easy changes to the `int` types, it goes down 2K, which is better, but still not great.

-- 
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/3622#issuecomment-623553793

---

From: Lars Eggert <[email-masked]>
Date: Mon, 04 May 2020 09:07:16 -0700

For comparison, I can fit an entire QUIC and TLS1.3 stack into 64KB.

-- 
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/3622#issuecomment-623555323

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 04 May 2020 09:29:39 -0700

> How should a server that has no intention of enabling this setting respond to HEADERS that include other instructions? If the answer is to blow up the connection then the (unintended?) side effect…

Well, I suggest this mechanism as an opt-in, rather than an opt-out, so it's less of "encourage" and more of "require".

This will in fact affect the first flight of requests if the client does not receive server's SETTINGS frame fast enough.  That does sound like a problem, but it will be eventually fixed when we fix #3086, so I'm not particularly concerned.

> My concern is that by trying to accommodate some smaller segment of HTTP clients, we cause a serious regression compared to HTTP/2.

That's a fair point.  On the other hand, HTTP/2 did come with a lot of features that we decided to make optional in HTTP/3, so that would be another step in this direction.

> This sort of thing seems better suited to a version that is "profile of HTTP/3" that disables some things and mandates others.

I am not sure how that kind of profile would look in practice.  The reason I am filing this for v1 is that in general, you can add complexity as an opt-in, but opting out of it does not really work.

-- 
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/3622#issuecomment-623568022

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 04 May 2020 09:39:55 -0700

The Huffman table can be fit into 512 bytes that is used by a simple (and small), one-bit-at-a-time decoder.

-- 
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/3622#issuecomment-623573463

---

From: Christian Huitema <[email-masked]>
Date: Mon, 04 May 2020 10:40:07 -0700

@dtikhonov is right. The Huffman code in h3zero was not optimized for size -- I was more concerned about being able to directly copy tables from the specs, and making sure that the result was conformant. The result in 4K of table and 1K of code. As Dmitri says, this can be easily optimized for size -- a table of 256 elements could be represented as a flat tree of 256 entries, 16 bits per entry, thus 512 bytes. The decoding code might be reduced in size too. The code size could shrink to just over 1K of code and table.

That was not my priority. But if there is demand for that, I could certainly export h3zero in its own github project, and let volunteers drive down the code size. 

-- 
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/3622#issuecomment-623604100

---

From: Lucas Pardue <[email-masked]>
Date: Mon, 04 May 2020 10:46:16 -0700

> This will in fact affect the first flight of requests if the client does not receive server's SETTINGS frame fast enough. That does sound like a problem, but it will be eventually fixed when we fix…

hat-off:  I would push back against introducing a performance regression in v1 that *might* possibly be fixed in v2

> I am not sure how that kind of profile would look in practice. The reason I am filing this for v1 is that in general, you can add complexity as an opt-in, but opting out of it does not really work.

CoAP has done a pretty decent job and seems to have traction.

One way is to profile things is to create a new Application Protocol e.g. "h3-lite" or whatever, that can completely profile away all the features that are deemed as too much overhead. One could then make sweeping changes such as rewriting the message exchanges to use an ASCII-HEADERS frame that just carries verbatim headers.

-- 
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/3622#issuecomment-623607334

---

From: Mike Bishop <[email-masked]>
Date: Mon, 04 May 2020 14:02:57 -0700

The way we've designed SETTINGS is that you assume the minimal required capabilities from the peer until you learn that it supports more capabilities.  #3086 was an alternative design the working group did not consider acceptable given the current capabilities of TLS; any discussion of "when we fix" that issue depends on a hypothetical future version of HTTP that uses a hypothetical future version of QUIC that depends on ECHO or kin.  That may not particularly concern @vasilvv, but it concerns me.

If we reduced the minimum capability for QPACK, then the client is even further down the road of needing to either wait for the SETTINGS frame to learn capabilities or not compressing the headers.  I agree that there's some code size; there's also benefit as to size of the outgoing requests.  Based on that compression benefit, I would strongly oppose changing the default stance of the protocol.

There's actually no need for QPACK at all without these features.  There was a push in the HTTP/2 era to define a second ALPN token with more constrained defaults so that you never needed to drop back further from the defaults.  A new ALPN token that uses a simple encoding for HEADERS frames might be a better solution here.  I don't think that needs to be in the core spec; it would be a simple document to write if you think there's application demand for it.

-- 
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/3622#issuecomment-623704092

---

From: Lucas Pardue <[email-masked]>
Date: Mon, 04 May 2020 14:08:04 -0700

To avoid any doubt, I do not think any profiling activity such as I mentioned should take place in the scope of v1 core QUIC drafts

-- 
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/3622#issuecomment-623706488

---

From: Martin Thomson <[email-masked]>
Date: Mon, 04 May 2020 19:20:28 -0700

I've reached two conclusions:

1. This is a design issue.

2. I don't want to do what is being requested.  That is, I agree with Lucas about the future potential for profiling to address any need of this sort.  I hadn't considered the impact of this sort of change on h3, but it would negatively affect performance.  So let's not.

So the proposal I would make is to close this with no action.

-- 
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/3622#issuecomment-623800917

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 04 May 2020 21:24:19 -0700

Indeed, this is a design issue, and unfortunately the design problem turned out to be more complicated than I anticipated.  Let's close this for now.

-- 
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/3622#issuecomment-623850218

---

From: Lars Eggert <[email-masked]>
Date: Mon, 04 May 2020 22:50:23 -0700

Labelled as requested. @vasilvv, should i close entirely or label as v2?

-- 
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/3622#issuecomment-623867967

---

From: David Schinazi <[email-masked]>
Date: Tue, 05 May 2020 12:57:13 -0700

I would like to see this labelled as v2 if possible - I think making it so that HTTP SETTINGS are available before the client can send its first request would be a very useful feature for v2, and that would make this change not impact performance.

-- 
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/3622#issuecomment-624273617

---

From: Lucas Pardue <[email-masked]>
Date: Tue, 05 May 2020 15:19:33 -0700

The proposal is to mark this as v2.

-- 
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/3622#issuecomment-624336629

---

From: Mike Bishop <[email-masked]>
Date: Tue, 05 May 2020 15:45:05 -0700

I don't oppose the v2 marking.  Having SETTINGS available before any application data is sent would enable a broader design such as #1343 if we have interest, with "no static table" being one possible choice; a parallel option for the Huffman table would make sense.

-- 
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/3622#issuecomment-624345346

---

From: Christian Huitema <[email-masked]>
Date: Thu, 07 May 2020 18:14:41 -0700

First, I do agree with the decision to push this to v2. Second, I confirm that the Huffman decoding code can fit in less than 1K, which means that the issue is maybe not too urgent. As @MikeBishop said, if we want to negotiate for code size, we might consider negotiating Qpack as well as Huffman.

-- 
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/3622#issuecomment-625575624