Re: QCRAM Review Request: PR #1141

[Ian Swett <[e-mail]>]

The table above is great, but is it also possible to estimate 'small
efficiency gains' in terms of %?

On Mon, Mar 12, 2018 at 11:58 AM Alan Frindell <[e-mail]> wrote:

> I mentioned this on issue #1123, but will repeat it on the list.  I think
> redoing the instructions and string literal representation will limit code
> re-use between HPACK and QPACK (formerly called QCRAM).  Initial simulation
> of QPACK shows that it is pretty close to HPACK compression as is.  I’m
> more swayed by eliminating the possibility of sending an instruction in an
> invalid context (eg: a literal on the control stream), but on balance I
> prefer to keep the same instructions as HPACK.
>
>
>
> It would be great to hear from other implementers (eg folks not on the
> compression design committee) how they value code-reuse versus small
> efficiency gains and fewer error checks.
>
>
>
> -Alan
>
>
>
> *From: *QUIC <[e-mail]> on behalf of Martin Thomson <
> [e-mail]>
> *Date: *Thursday, March 1, 2018 at 8:15 PM
> *To: *Mike Bishop <[e-mail]>
> *Cc: *QUIC WG <[e-mail]>
> *Subject: *Re: QCRAM Review Request: PR #1141
>
>
>
> I was a little surprised to see the savings here, modest though they are.
> Overall, this is overwhelmingly in the right direction.
>
>
>
> We might quibble on some of the details, but I would prefer to see this
> larger change made and then iterate where the details are less good (for
> instance, we might revisit the notion of octet alignment in other ways, or
> go back to strings starting on octet boundaries).
>
>
>
> On Thu, Mar 1, 2018 at 11:39 AM, Mike Bishop <[e-mail]> wrote:
>
> https://github.com/quicwg/base-drafts/pull/1141
>
>
>
> One suggestion from Martin’s implementation feedback that has been
> mentioned before is reworking the QCRAM instruction space.  The QCRAM draft
> uses the HPACK instructions, except that it cannibalizes table size changes
> for the Duplicate instruction.  That leads to some inefficiency with the
> separate streams, since you have to validate that instructions aren’t used
> on the wrong stream and some of the opcode space is wasted on each stream.
>
>
>
> This PR observes that each stream has a fully disjoint set of commands
> from the other:
>
>    - Table updates
>
>
>    - Insert with Name Reference from Static Table
>       - Insert with Name Reference from Dynamic Table
>       - Insert without Name Reference
>       - Duplicate
>       - Change table size
>
>
>    - Header blocks
>
>
>    - Indexed entry from Static
>       - Indexed entry from Dynamic
>       - Literal with Name Reference from Static Table
>       - Literal with Name Reference from Static Table, Never Indexed
>       - Literal with Name Reference from Dynamic Table
>       - Literal with Name Reference from Dynamic Table, Never Indexed
>       - Literal without Name Reference
>       - Literal without Name Reference, Never Indexed
>
>
>
> The PR takes advantage of the disjoint space to rework the opcodes in
> hopes of saving bytes on common instructions.  It does this in two ways:
>
>    - Uses a bit in the opcode to differentiate static versus dynamic
>    tables, instead of concatenating them
>
>
>    - Gives us the future option to make the static table longer without
>       hurting the dynamic table performance
>
>
>    - Uses a bit in the opcode to identify string literals, instead of
>    using a sentinel value of zero
>
>
>    - Requires modifying the HPACK string definition to not require byte
>       alignment at the beginning
>       - Gives us the future option to make the tables zero-based instead
>       of one-based
>       - Makes indexing easier to explain in a future PR
>
>
>
> Here’s the impact:
>
>
>
> *Operation*
>
> *HPACK*
>
> *QCRAM*
>
> *PR#1141*
>
> *Impact*
>
> *Table updates*
>
>
>
>
>
>
>
>
>
> *Insert with Name Reference from Static Table*
>
> “01” + index < 62
>
> “01” + index < 62
>
> “11” + index
>
> Same
>
> *Insert with Name Reference from Dynamic Table*
>
> “01” + index >= 62
>
> (one byte for first 2 entries, then 2 bytes)
>
> “01” + index >= 62
>
> (one byte for first 2 entries, then 2 bytes)
>
> “10” + index
>
> (one byte for first 64 entries)
>
> One byte saved for 62 of 64 most recent entries
>
> *Insert without Name Reference*
>
> “01000000”
>
> “01000000”
>
> “01”
>
>
>
> One byte saved for header names < 32 octets
>
> *Duplicate*
>
> Not supported
>
> “001” + index >= 62
>
> “000” + index
>
> Moot; you’re unlikely to duplicate recent entries
>
> *Change table size*
>
> “001”
>
> Not supported
>
> “001”
>
> Same
>
> *Header blocks*
>
>
>
>
>
>
>
>
>
> *Indexed entry from Static*
>
> “1” + index < 62
>
> “1” + index < 62
>
> “11” + index
>
> Same
>
> *Indexed entry from Dynamic*
>
> “1” + index >= 62
>
> “1” + index >= 62
>
> “10” + index
>
> One byte longer for indices 62-63
>
> *Literal with Name Reference from Static Table*
>
> “0000” + index < 62
>
> (two bytes for index > 15)
>
> “0000” + index < 62
>
> (two bytes for index > 15)
>
> “0001” + index
>
> Same
>
> *Literal with Name Reference from Static Table, Never Indexed*
>
> “0001” + index < 62
>
> (two bytes for index > 15)
>
> “0001” + index < 62
>
> (two bytes for index > 15)
>
> “0011” + index
>
> Same
>
> *Literal with Name Reference from Dynamic Table*
>
> “0000” + index >= 62
>
> (always 2+ bytes)
>
> “0000” + index >= 62
>
> (always 2+ bytes)
>
> “0000” + index
>
> One byte saved for first 15 entries
>
> *Literal with Name Reference from Dynamic Table, Never Indexed*
>
> “0001” + index > 62
>
> (always 2+ bytes)
>
> “0001” + index > 62
>
> (always 2+ bytes)
>
> “0010” + index
>
> One byte saved for first 15 entries
>
> *Literal without Name Reference*
>
> “00000000”
>
> “00000000”
>
> “010”
>
> One byte saved for header names < 16 octets
>
> *Literal without Name Reference, Never Indexed*
>
> “00010000”
>
> “00010000”
>
> “011”
>
> One byte saved for header names < 16 octets
>
>
>
> There’s been some churn on the PR today as Martin and I worked some of
> this out, so please give it a read (or another read) now and provide
> feedback.
>
>
>
> Thanks!
>
>
>