RE: QPACK - proposal to optimize compression

[Mike Bishop <[e-mail]>]

This is part of why I didn’t attempt to merge Alan’s post-base design into #1141, but left it as a separate PR.  That helps to identify exactly which instructions have been degraded by adding these two additional instructions.  The impact turned out to be:

  *   “Depends” was resurrected from the dead, one byte per header block
  *   Literal headers without name references now require one more byte for names which are 7-15 octets long

While the impact is certainly not non-zero, this seems fairly contained.  I don’t have a problem with two-pass encoding – that was actually my original design, and I still think it makes a lot of sense.  But part of the consensus at the Seattle interim was that we want to allow the intelligence and choices to live in the encoder, and I see permitting the encoder to choose single-pass versus double-pass as an example of that.

Also, double-pass has its own potential pitfalls – noting that you’ll refer to an entry which is in the dynamic table during your first pass, but then discovering that entry has been pushed out due to insertions when you try to actually reference it on the second pass, for example.  There are mitigations for these, of course, but I don’t see either as dramatically simpler than the other.

From: QUIC <[e-mail]> On Behalf Of Brian Swander
Sent: Tuesday, May 8, 2018 1:50 PM
To: Alan Frindell <[e-mail]>; [e-mail]
Subject: RE: QPACK - proposal to optimize compression

Of course single pass isn’t required.  But the PostBase is there only to support single pass.  So there are definitely (probably fringe) cases where the encoded size will be larger because of PostBase.

So IMO, it comes down to the tradeoff of the possible speed improvement of single pass vs. compression size.   And I just don’t see the speed of the single pass being very compelling either.  For instance, you can cache the indices, etc from pass 1, and just quickly burn thru the array again encoding the indices determined from pass 1.

Personally, given that the speed improvement of single pass is probably marginal at best, I’d err on the side of less complexity – and slightly better compression.

But I’m not passionate about this issue.   So I’m fine with the current draft, if everyone else likes it.   I just prefer simplicity when it seems like complexity isn’t buying us much.  And in this case, simplicity also gives slightly better compression.

bs

From: Alan Frindell <[e-mail]<mailto:[e-mail]>>
Sent: Tuesday, May 8, 2018 1:13 PM
To: Brian Swander <[e-mail]<mailto:[e-mail]>>; [e-mail]<mailto:[e-mail]>
Subject: Re: QPACK - proposal to optimize compression

Single pass encoding is not required, an encoder has the option to encode using one or two passes.  The only wire penalty for a two-pass encoder is one extra byte per header block in the prefix, as largest reference and base index can be the same in two-pass encoding.  The original specification (which used Depends) had a one bit flag in the HTTP frame that allowed the encoder save this byte as well, but the consensus seemed to be it was better to have a fixed format to the prefix.  Without post-base, there could also be one more bit available for the length of a literal header name without adding an extra byte (header names with 7 <= length < 15).  We can of course simulate it, but I expect the difference to be in the noise.

Decoders do need to support both kinds of instructions, but I don’t find it to be terribly complex.  The proxygen implementation of the latest draft including one-pass encoding/decoding should be synced to github this week.

I’m not sure what you mean when you say “Many of the headers are going to be encoded in both streams.”  If you mean it will encode an insert on the control stream and an index reference on the request stream, that is true, and the post-base encoding of the references occupies only one byte for the first 15 such headers per block.

-Alan


From: QUIC <[e-mail]<mailto:[e-mail]>> on behalf of Brian Swander <briansw=[e-mail]<mailto:briansw=[e-mail]>>
Date: Monday, May 7, 2018 at 2:35 PM
To: "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>
Subject: QPACK - proposal to optimize compression

Please correct me if I’m wrong here.

It looks like the latest QPACK draft has been optimized to allow encode of both control and data streams in a single pass.
Because of this, we now must support that post-base encoding, and the multiple encoding formats that use Post-Base.
I.e. Literal Header Field with Name Reference and Literal Header Filter With Post-Base Name Reference, and similarly for Indexed Header Field.

To me, it seems like the simpler, more efficient option of removing post-base entirely could be better.   At the cost of requiring 2-pass encode, we can save a few bits for most headers since we would never need the post base header prefix.

So it’s a question of looping thru the headers twice, vs. being less efficient on the wire.

I haven’t profiled it, but I’d guess that double pass thru the headers isn’t going to be that much slower than single pass.   Many of the headers are going to be encoded in both streams.   So the more efficient wire format may be more optimal.

bs