Subject: Review of QCRAM

From: Martin Thomson <[email-masked]>
Date: Fri, 9 Feb 2018 21:08:46 +1100

I have implemented QCRAM and have a few things to comment on.

My implementation is here:
  https://github.com/martinthomson/minhq/tree/master/hc

This is my first attempt at go, so this took a little longer than it might have
otherwise. Test coverage is still a little light, though go thinks that I have
pretty good coverage. There's probably still a lot to go on the corner cases,
but I think that I've done enough to get an idea for the complexity bump.

I started by implementing HPACK, which is surprisingly easy if you don't care
about being efficient. Though I knew that I was going to add QCRAM, I made only
minimal design concessions when building HPACK.

Building QCRAM on top of HPACK took at least 50% more than just doing HPACK (at
a guess, HPACK took about 10-12 hours, QCRAM took closer to 20). Even though
you can reuse Huffman coding and most of the primitives, retrofitting it was
tricky. My lack of familiarity with go definitely contributed a lot to that,
but I'd say that QCRAM is more difficult to implement than it seems in theory.

I didn't implement QCRAM entirely as specified. There are a few things that
I'll describe below that would make it either better or easier to implement (or
both).

# Separate Stream Roles

There are actually three streams of data that are of interest, and there is no
clarity about those streams.

1. I suggest that we use unidirectional streams in each direction for table
updates.

2. A separate stream for acknowledgments ensures that the encoder can consume
that separately to the decoder.

3. Request/response streams. I think that we all understand these.

These can be separate from the hq control stream, and they should be. Rather
than pick a specific stream number, we should add a header for these streams
that will allow them to be identified clearly. If we do that, add strict rules
about cardinality.

# Define Framing More Clearly

The definition of the framing that is used on the control stream is unclear. I
assume that the intent is to use HEADERS frames, but I'm only really guessing.
If you take my suggestion for separate framing, then you can use very different
logic for the different streams.

Honestly, the overhead of framing is excessive for anything but
request/response streams. I found that framing on the control stream wasn't
necessary at all. This might depend on implementation strategy, because it
might be easier to collect a framed thing than it is to read until you are
blocked, then pickle that state so that you can go back to something else. In
my implementation I hold state on the stack, so it's pretty easy.

Also, it should suffice to have just a stream of varints indicating
acknowledgments. Duplicates can be used to acknowledge multiple header blocks
on the same stream in order.

# Split the Instruction Space

Having to check that only certain instructions appear on different streams is
annoying to implement and a waste of bits. Define two separate spaces. That
should make things much simpler: there are exactly two instructions in each
space then (leaving aside acknowledgments, which I will cover below).

# Base in Every HEADERS Frame

Base (the number of inserts in the table at the start of a header block) seems
to be required for all HEADERS frames, including both table modification and
request/response streams.  But...

# Base on the Table Update Stream

You don't need base for table updates. It is more of a hazard than a help. It
is easier if you treat indexing on the table update stream as in HPACK where
each insert moves the reference point for the next insertion.

# Remove BLOCKING

The BLOCKING flag complicates the design unnecessarily. As a fixed overhead,
pay the extra byte always. Furthermore, the table update stream will never need
to use depends, so that further motivates having different instruction sets
(and formats) for different streams.  And you don't need it...

# Base and the Static Table

It is not explained at all that the base is applied to the dynamic table only.
That is, index 1 is a straight index into the static table and that index 62
will use the current number of inserts and the base to determine the actual
index into the dynamic table (this is the first table entry only when the
number of table inserts and base are the same, if the base is smaller, then it
will be further along the table).

To be clear, my logic for finding entries is:

    if i == 0: error
    if i <= len(staticTable): return staticTable[i-1]
    delta = tableBase - base
    if delta < 0: error
    return dynamicTable[i - len(staticTable) - 1 + delta]

# Remove Depends

Depends is useless. I did not implement it. Base is sufficient.

This follows from preferring to use the smallest value for base possible. Doing
that also keeps table references as small as possible. (Because references are
counted in the opposite direction to base, a larger base means larger
references.)

The cost is that you have to do a two pass check: the first to find the newest
reference, the second to write out the header block. I find that it's basically
necessary to do two passes anyway: on the first I write out the table updates,
on the second I write the header block. During that phase you want to do
lookups anyway, so you can save the largest base from that pass. Also, when you
insert anything, that tends to set the base, so it's pretty easy overall.

# Tracking ACKs is Harder Than It Seems

There are multiple header blocks per stream, and ACKs only identify the stream.
You can't just store a stream reference (or Request-ID) against each header
block, you have to store a tuple of stream and header block index. This needs
to be explained somewhere.

I decided to externalize ACKs - the QCRAM encoder takes a generic blob as input
when it encodes a header block and the same generic blob to acknowledge it. The
caller then has to combine stream ID and header block index in a sensible
fashion.

# Acknowledge Dmitry

So I don't forget... Dmitry did a lot of work on the design team.

# Dynamic Table Overhead

The draft has a TODO about overhead for each dynamic entry. I added a field to
every entry that allows it to know its own position in the table, but that is a
simplification/optimization, and you don't really need that. The other
per-record overheads are all the same for the decoder, with a small increase to
the fixed overhead. It's a little more state for an encoder, but that is mostly
because of having to track usage.

I don't think that we need to change from a 32 byte overhead. This decision
could reduce code complexity in shared QCRAM/HPACK implementations (in my
implementation it would).

# Duplication Doesn't Need to Reference the Static Table

Duplication only makes sense for dynamic entries and yet the index is (I
assume), the normal table index. That is highly suboptimal. This is worse
because the prefix is only 5 bits for this instruction (up to 62 values), which
leads to the encoding taking an extra byte always. If you take my suggestion
for separate instruction spaces, this is better, but still not as good as a
direct index into the dynamic table, starting at 0. Better yet would be a
reverse index, starting from the end of the table, because duplication often
needs to refer to the end of the table.

# Need Better Advice on Referencing strategy

Referencing entries near the end of the table in a new header block is
hazardous. If you just compress as you do in HPACK, you can end up pinning
entries in the header table, making it impossible to add new entries. Thus, you
have to stop referencing entries as they get nearer to the table capacity
limit.

In my implementation I added a threshold variable that governs my referencing
strategy. A portion of the header table space is marked as being off-limits for
header block usage. The encoder duplicates those entries if it wants to
compress, but won't reference them. If the table is under pressure from the new
header fields being added, then it should be able to advance by at least this
amount every round trip.

This is a simple strategy, and probably suboptimal in various ways, but it
seems to work out. For instance, I continuously update the cutoff as entries
are inserted, so that a header block might end up referencing things that get
pushed into this space by later header fields.

You can imagine more advanced techniques. For instance, you might tune this
window automatically based on the rate that the header table grows. Because
references in that window block eviction, it should be sized to the rate of
*desired* growth in the header table over a round trip. Taking a running
estimate of that desired growth and allowing a margin for variance could
produce the right value. I haven't experimented with this.

---

From: Lucas Pardue <[email-masked]>
Date: Fri, 9 Feb 2018 10:51:05 +0000

Hi Martin,

Very interesting, thanks.

Given that your implementation supports both HPACK and QCRAM, do you have any opinion how much pain it would be to have different static tables between them?

Regards
Lucas

> -----Original Message-----
> From: QUIC [mailto:[email-masked]] On Behalf Of Martin Thomson
> Sent: 09 February 2018 10:09
> To: QUIC WG <[email-masked]>
> Subject: Review of QCRAM
> 
> about being efficient. Though I knew that I was going to add QCRAM, I made
> only minimal design concessions when building HPACK.
> 
> Building QCRAM on top of HPACK took at least 50% more than just doing
> HPACK (at a guess, HPACK took about 10-12 hours, QCRAM took closer to 20).
> Even though you can reuse Huffman coding and most of the primitives,
> retrofitting it was tricky. My lack of familiarity with go definitely contributed a
> lot to that, but I'd say that QCRAM is more difficult to implement than it
> seems in theory.
> 
> I'll describe below that would make it either better or easier to implement
> (or both).
> 
> 
> # Separate Stream Roles
> 
> 2. A separate stream for acknowledgments ensures that the encoder can
> consume that separately to the decoder.
> 
> These can be separate from the hq control stream, and they should be.
> Rather than pick a specific stream number, we should add a header for these
> streams that will allow them to be identified clearly. If we do that, add strict
> rules about cardinality.
> 
> If you take my suggestion for separate framing, then you can use very
> different logic for the different streams.
> 
> acknowledgments. Duplicates can be used to acknowledge multiple header
> blocks on the same stream in order.
> 
> You don't need base for table updates. It is more of a hazard than a help. It is
> easier if you treat indexing on the table update stream as in HPACK where
> The BLOCKING flag complicates the design unnecessarily. As a fixed
> overhead, pay the extra byte always. Furthermore, the table update stream
> will never need to use depends, so that further motivates having different
> instruction sets (and formats) for different streams.  And you don't need it...
> 
> That is, index 1 is a straight index into the static table and that index 62 will
> use the current number of inserts and the base to determine the actual
> This follows from preferring to use the smallest value for base possible.
> Doing that also keeps table references as small as possible. (Because
> references are counted in the opposite direction to base, a larger base
> means larger
> references.)
> 
> necessary to do two passes anyway: on the first I write out the table
> updates, on the second I write the header block. During that phase you want
> to do lookups anyway, so you can save the largest base from that pass. Also,
> when you insert anything, that tends to set the base, so it's pretty easy
> overall.
> 
> I decided to externalize ACKs - the QCRAM encoder takes a generic blob as
> input when it encodes a header block and the same generic blob to
> acknowledge it. The caller then has to combine stream ID and header block
> index in a sensible fashion.
> 
> # Acknowledge Dmitry
> 
> The draft has a TODO about overhead for each dynamic entry. I added a field
> to every entry that allows it to know its own position in the table, but that is a
> simplification/optimization, and you don't really need that. The other per-
> record overheads are all the same for the decoder, with a small increase to
> could reduce code complexity in shared QCRAM/HPACK implementations (in
> my implementation it would).
> 
> for separate instruction spaces, this is better, but still not as good as a direct
> index into the dynamic table, starting at 0. Better yet would be a reverse
> index, starting from the end of the table, because duplication often needs to
> refer to the end of the table.
> 
> entries in the header table, making it impossible to add new entries. Thus,
> you have to stop referencing entries as they get nearer to the table capacity
> limit.
> 
> In my implementation I added a threshold variable that governs my
> referencing strategy. A portion of the header table space is marked as being
> off-limits for header block usage. The encoder duplicates those entries if it
> wants to compress, but won't reference them. If the table is under pressure
> from the new header fields being added, then it should be able to advance
> by at least this amount every round trip.
> 
> You can imagine more advanced techniques. For instance, you might tune
> this window automatically based on the rate that the header table grows.
> Because references in that window block eviction, it should be sized to the
> rate of

---

From: Mike Bishop <[email-masked]>
Date: Fri, 9 Feb 2018 17:56:15 +0000

Thanks for doing this, Martin.  I've been waiting for the adoption call to be formally concluded before I started bringing the laundry list of improvements, but my own aligns with yours:

  *   Three-layered stream model, distinct instruction spaces on each stream
  *   Consider changing from the static-at-front model to a static/dynamic bit and a shorter reference
     *   This would make a larger static table more palatable, and seems to break even for dynamic entries in the distinct instruction spaces

Your observation that you’re keeping a tuple of stream-blocknum on each entry is interesting.  Can you go into more detail where this is?  Couldn’t you also keep a simple refcount of outstanding blocks, then separately track which entries are referenced by outstanding blocks?  IIRC, in QCRAM there’s not a situation in which you need to determine which outstanding header block is blocking eviction, only whether an outstanding HEADERS frame blocks eviction.  Or am I misunderstanding where you’re keeping the tuple?

Of course, a dictionary of queues might be more expensive than just storing the tuple, but I believe you need something like that regardless so you can find the entries you need to remove the outstanding reference from.

-----Original Message-----
From: QUIC [mailto:[email-masked]] On Behalf Of Lucas Pardue
Sent: Friday, February 9, 2018 2:51 AM
To: Martin Thomson <[email-masked]>; QUIC WG <[email-masked]>
Subject: RE: Review of QCRAM

Hi Martin,

Regards

Lucas

> To: QUIC WG <[email-masked]<mailto:[email-masked]>>

> This is my first attempt at go, so this took a little longer than it

> might have otherwise. Test coverage is still a little light, though go

> thinks that I have pretty good coverage. There's probably still a lot

> to go on the corner cases, but I think that I've done enough to get an idea for the complexity bump.

> I started by implementing HPACK, which is surprisingly easy if you

> don't care about being efficient. Though I knew that I was going to

> add QCRAM, I made only minimal design concessions when building HPACK.

> retrofitting it was tricky. My lack of familiarity with go definitely

> contributed a lot to that, but I'd say that QCRAM is more difficult to

> implement than it seems in theory.

> I didn't implement QCRAM entirely as specified. There are a few things

> that I'll describe below that would make it either better or easier to

> implement (or both).

> There are actually three streams of data that are of interest, and

> there is no clarity about those streams.

> 1. I suggest that we use unidirectional streams in each direction for

> table updates.

> Rather than pick a specific stream number, we should add a header for

> these streams that will allow them to be identified clearly. If we do

> that, add strict rules about cardinality.

> The definition of the framing that is used on the control stream is

> unclear. I assume that the intent is to use HEADERS frames, but I'm

> only really guessing.

> request/response streams. I found that framing on the control stream

> wasn't necessary at all. This might depend on implementation strategy,

> because it might be easier to collect a framed thing than it is to

> read until you are blocked, then pickle that state so that you can go

> back to something else. In my implementation I hold state on the stack, so it's pretty easy.

> Having to check that only certain instructions appear on different

> streams is annoying to implement and a waste of bits. Define two

> separate spaces. That should make things much simpler: there are

> exactly two instructions in each space then (leaving aside acknowledgments, which I will cover below).

> Base (the number of inserts in the table at the start of a header

> block) seems to be required for all HEADERS frames, including both

> table modification and request/response streams.  But...

> You don't need base for table updates. It is more of a hazard than a

> help. It is easier if you treat indexing on the table update stream as

> in HPACK where each insert moves the reference point for the next insertion.

> overhead, pay the extra byte always. Furthermore, the table update

> stream will never need to use depends, so that further motivates

> having different instruction sets (and formats) for different streams.  And you don't need it...

> That is, index 1 is a straight index into the static table and that

> index 62 will use the current number of inserts and the base to

> determine the actual index into the dynamic table (this is the first

> table entry only when the number of table inserts and base are the

> same, if the base is smaller, then it will be further along the table).

> references are counted in the opposite direction to base, a larger

> base means larger

> The cost is that you have to do a two pass check: the first to find

> the newest reference, the second to write out the header block. I find

> that it's basically necessary to do two passes anyway: on the first I

> write out the table updates, on the second I write the header block.

> During that phase you want to do lookups anyway, so you can save the

> largest base from that pass. Also, when you insert anything, that

> tends to set the base, so it's pretty easy overall.

> There are multiple header blocks per stream, and ACKs only identify

> the stream.

> You can't just store a stream reference (or Request-ID) against each

> header block, you have to store a tuple of stream and header block

> index. This needs to be explained somewhere.

> I decided to externalize ACKs - the QCRAM encoder takes a generic blob

> as input when it encodes a header block and the same generic blob to

> acknowledge it. The caller then has to combine stream ID and header

> block index in a sensible fashion.

> The draft has a TODO about overhead for each dynamic entry. I added a

> field to every entry that allows it to know its own position in the

> table, but that is a simplification/optimization, and you don't really

> need that. The other per- record overheads are all the same for the

> decoder, with a small increase to the fixed overhead. It's a little

> more state for an encoder, but that is mostly because of having to track usage.

> I don't think that we need to change from a 32 byte overhead. This

> decision could reduce code complexity in shared QCRAM/HPACK

> implementations (in my implementation it would).

> Duplication only makes sense for dynamic entries and yet the index is

> (I assume), the normal table index. That is highly suboptimal. This is

> worse because the prefix is only 5 bits for this instruction (up to 62

> values), which leads to the encoding taking an extra byte always. If

> you take my suggestion for separate instruction spaces, this is

> better, but still not as good as a direct index into the dynamic

> table, starting at 0. Better yet would be a reverse index, starting

> from the end of the table, because duplication often needs to refer to the end of the table.

> hazardous. If you just compress as you do in HPACK, you can end up

> pinning entries in the header table, making it impossible to add new

> entries. Thus, you have to stop referencing entries as they get nearer

> to the table capacity limit.

> referencing strategy. A portion of the header table space is marked as

> being off-limits for header block usage. The encoder duplicates those

> entries if it wants to compress, but won't reference them. If the

> table is under pressure from the new header fields being added, then

> it should be able to advance by at least this amount every round trip.

> This is a simple strategy, and probably suboptimal in various ways,

> but it seems to work out. For instance, I continuously update the

> cutoff as entries are inserted, so that a header block might end up

> referencing things that get pushed into this space by later header fields.

> Because references in that window block eviction, it should be sized

> to the rate of

> *desired* growth in the header table over a round trip. Taking a

> running estimate of that desired growth and allowing a margin for

> variance could produce the right value. I haven't experimented with this.

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Fri, 9 Feb 2018 10:15:04 -0800

Thanks Martin!

I am behind in digesting this, I intend to comment later today.

In the meantime though, have you looked at QCRAM doc github repo
<https://github.com/krasic/draft-krasic-quic-hpack> ?  (Notice it has
working diff against -04).  The reason I ask, is that I made updates there
in response to various comments around the time of the interim.   I think
the diffs relate partially to some of your ideas.

On Fri, Feb 9, 2018 at 2:08 AM, Martin Thomson <[email-masked]>
wrote:

> only
> HPACK (at
> Rather
> unclear. I
> overhead,
> Doing
> updates,
> input
> field to
> referencing

-- 
Charles 'Buck' Krasic | Software Engineer | [email-masked] | +1 (408)
412-1141

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Fri, 9 Feb 2018 12:36:32 -0800

Some comments below, but

*tldr;*  Sorry for crossed wires, but I think much of what you raise is
addressed in 3.2
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.3.2>
, 3.3
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.3.3>
and 4.2
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.4.2>
of
the editor's copy
<https://krasic.github.io/draft-krasic-quic-hpack/#go.draft-krasic-quic-qcram.html>
(changes were announced on this list
<https://mailarchive.ietf.org/arch/msg/quic/CS-guyGGwgTXUMr3I2BfxSqUtSg/?qid=730e62053d1db65f86e00c822184f971>
).

> that separately to the decoder.

I have a hard time seeing a practical difference, but sure.

> request/response streams.  But...
FWIW, in the editor's copy there was already a change that the prefix is
only for request-response streams (see 3.2
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.3.2>
 and 3.3
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.3.3>
)

> each insert moves the reference point for the next insertion.

Yep, see above.

> pay the extra byte always.

I disagree.  Fixed overheads in every header block do really hurt.   Close
to 1% per byte.   Since blocking is less than 10% of blocks, I think your
proposal is a material waste.

> Furthermore, the table update stream will never need
> This is true, and was already addressed as mentioned above.

> It is not explained at all that the base is applied to the dynamic table

afrind@ pointed this out Jan. 24 in a design committee thread (About
simplifying QCRAM further.)    The editors copy had significant work to try
and clarify these points.   Again sections 3.2 and 3.3.  Also in response
to earlier feedback, Section 4.2
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.4.2>,
has a lot of new implementation guidance.

> insert anything, that tends to set the base, so it's pretty easy overall.

It's a nit, but in my proxygen prototype
<https://github.com/krasic/proxygen>, I didn't have to do two passes,
partly because FB's IOBuf abstraction has powerful abilities to prepend
prefixes to an existing buf, avoiding the need for two pass logic.

> to be explained somewhere.

See above, I think the new stuff in Section 4.2
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.4.2>
covers
this.

> So I don't forget... Dmitry did a lot of work on the design team.

Already done in the editor's copy.

> implementation it would).Section 4.2
>

---

From: Martin Thomson <[email-masked]>
Date: Sat, 10 Feb 2018 08:35:03 +1100

On Sat, Feb 10, 2018 at 4:56 AM, Mike Bishop <[email-masked]> wrote:
> Your observation that you’re keeping a tuple of stream-blocknum on each
> entry is interesting.  Can you go into more detail where this is?  Couldn’t
> you also keep a simple refcount of outstanding blocks, then separately track
> which entries are referenced by outstanding blocks?  IIRC, in QCRAM there’s
> not a situation in which you need to determine which outstanding header
> block is blocking eviction, only whether an outstanding HEADERS frame blocks
> eviction.  Or am I misunderstanding where you’re keeping the tuple?

So you send out two header blocks on a stream.  One includes
:status=307, the other digest=blah.  When the acks come in, they
identify the stream.  The first ack needs to ensure that it removes
any block on :status=307, the second digest=blah.  You can't just say
that ":status=307 is blocked from eviction, because you need to know
when it is no longer blocked, which means tracking where you sent it.

A refcount of outstanding blocks will likely never hit zero, meaning
you can never evict.

I realize now that I didn't consider stream resets, which my scheme
doesn't manage well (you need to have a nuke-all-that-partially-match
option).

---

From: Martin Thomson <[email-masked]>
Date: Sat, 10 Feb 2018 08:36:02 +1100

It would be relatively easy in my implementation to have different
static tables.  (I was a bit harder in other versions of my code.)

---

From: Martin Thomson <[email-masked]>
Date: Sat, 10 Feb 2018 08:49:51 +1100

> I have a hard time seeing a practical difference, but sure.

Consider that acknowledgments go to an encoder, and stream updates go
to a decoder.  These are entirely separate in my code, and I'd expect
that to be common.  Having to demux could be difficult - and it adds
overhead.

> and clarify these points.   Again sections 3.2 and 3.3.  Also in response to
> earlier feedback, Section 4.2, has a lot of new implementation guidance.

I don't understand 3.3.  I'm happy to send a PR that clarifies things.

> It's a nit, but in my proxygen prototype, I didn't have to do two passes,

Sure, if you can do that, you just update the base at the end.  I
found that to be unnecessary because it's easy to write out table
changes in one pass, then all the references in a second pass.  The
only extra overhead is iteration (over small N, that's not a real
cost).

> See above, I think the new stuff in Section 4.2 covers this.

I think that could be improved.  I might have a PR for you later (or
maybe after this becomes a WG item).

---

From: "Charles 'Buck' Krasic" <[email-masked]>
Date: Fri, 9 Feb 2018 14:22:22 -0800

On blocked evictions.

a) there's a real possibility that setting table size to 64KB is the most
elegant solution, because evictions may not happen for the vast majority of
connections.
    Perhaps something along these lines is worth mentioning (in section 4?).

b) if not it should be possible to prevent blocked evictions using indexed
duplicates (Section 3.5
<https://krasic.github.io/draft-krasic-quic-hpack/draft-krasic-quic-qcram.html#rfc.section.3.5>),
I can think of a couple of complementary policies that might be useful:

   1. based on index, duplicate if the encoder emits a reference that is
   (getting close to) the threshold where the HPACK instruction size jumps
   from 1 to 2 bytes.  (I'm feeling too lazy to figure this out precisely, but
   I think it is when the HPACK relative index is getting close to 128).  this
   practice also benefits compression ratio independent of evictions.
   2. based on dynamic table fill.  duplicate if the encoder the cumulative
   number of bytes for the referenced entry (the size of the entry and all
   newer entries in the table) is more than some threshold (e.g. 80% of table
   capacity).

   Neither of the above works if you have an entry that sits in the table
un-referenced until it is time to evict.  My intuition is such a scenario
should not arise in practice.

---

From: Martin Thomson <[email-masked]>
Date: Sat, 10 Feb 2018 19:48:48 +1100

>     Perhaps something along these lines is worth mentioning (in section 4?).

Setting a higher limit just delays things (or makes them much more
unlikely).  It's not a real solution, unless you think that throwing
away the connection or suffering compression degradation is preferable
to using duplication.

> duplicates (Section 3.5), I can think of a couple of complementary policies
> that might be useful:
>
> based on index, duplicate if the encoder emits a reference that is (getting
> close to) the threshold where the HPACK instruction size jumps from 1 to 2
> bytes.  (I'm feeling too lazy to figure this out precisely, but I think it
> is when the HPACK relative index is getting close to 128).  this practice
> also benefits compression ratio independent of evictions.
> based on dynamic table fill.  duplicate if the encoder the cumulative number
> of bytes for the referenced entry (the size of the entry and all newer
> entries in the table) is more than some threshold (e.g. 80% of table
> capacity).

I have implemented the latter, and though I don't have a lot of tests
to confirm it, it seems to work.  The threshold is tunable (I covered
this point in the OP).

> should not arise in practice.

Not sure why you would be concerned about this.  That would only
happen if you speculatively added things to the table.  Possible, but
probably not that useful.  Nor is this really a problem aside from the
opportunity cost, which could be zero anyway.

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sat, 10 Feb 2018 11:08:18 -0500

> elegant solution, because evictions may not happen for the vast majority of

I think this is the opposite of "elegant."

HTTPQ is not just a protocol for web browsers.  We should try to make
the header compression mechanism perform well in various scenarios.

In addition, we were getting good compression performance with 4KB tables
in our simulations.  Increasing the size to 64KB to address that which
can be solved by other means seems like a suboptimal approach.

  - Dmitri.