HPACK optimal Huffman code instrumentation and UMA collection.

HPACK optimal Huffman code instrumentation and UMA collection.

Adds support for aggregating observed character counts in literals emitted by
a per-origin HPACK encoder. This is intended to approximate the literal
encodings which would be used were the user agent speaking HTTP/2 to the
origin. Character counts sampled and aggregated across a population will be used
to design an optimial static Huffman compression table for the HTTP/2 standard.

See design doc:
https://docs.google.com/a/google.com/document/d/1Y6pnBf8u24AHNFcA6GADn2XgHzfIvZiIN39Kf11raIY/edit#

BUG=368301
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=267131

[Johnny, 2014-04-18 18:06:27]

Hi Ryan & Jim,

I'll need to rebase this on top of other CL's I'm currently merging, but I
expect those changes to be minor.

Jim, hpack_huffman_aggregator.cc is (ab)using histograms in perhaps a somewhat
novel way. I'd appreciate your take on that.

thanks,
-johnny

[jar (doing other things), 2014-04-18 21:14:53]

Why are you using Huffman coding?  All compressors leak info about content via
length analysis.... you're just choosing a method that will do a poorer job (in
some cases!?!).

Can you clarify what you gain going this route?

https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
File net/spdy/hpack_huffman_aggregator.cc (right):

https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
net/spdy/hpack_huffman_aggregator.cc:82: // HACK(jgraettinger): To be removed
before submission.
hmmmm.... this seems like a bad plan.... and subject to landing without removing
it by accident.

Is this the "approved" way of doing this??

https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
net/spdy/hpack_huffman_aggregator.cc:169: samples.Accumulate(i + 1, counts_[i]);
Why are you putting samples into your personal histogram, and then copying them
over to the global histogram??

Why don't you just use a standard histogram?  They are plenty efficient. Are you
fearful that you wont get an atomic group of all samples?  Even with this
approach it will not be atomic :-/.

[Johnny, 2014-04-18 21:42:21]

On 2014/04/18 21:14:53, jar wrote:
> Why are you using Huffman coding?  All compressors leak info about content via
> length analysis.... you're just choosing a method that will do a poorer job
(in
> some cases!?!).
> 
> Can you clarify what you gain going this route?

See the (draft) specification:
https://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07

Particularly, "4.1.2.  String Literal Representation" & "5.1.  Compression-based
Attacks".


>
https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
> File net/spdy/hpack_huffman_aggregator.cc (right):
> 
>
https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
> net/spdy/hpack_huffman_aggregator.cc:82: // HACK(jgraettinger): To be removed
> before submission.
> hmmmm.... this seems like a bad plan.... and subject to landing without
removing
> it by accident.
> 
> Is this the "approved" way of doing this??

It's an easy way to get trybots to run the trial codepath, which is certainly
required. By default once checked in, they won't run it.


>
https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
> net/spdy/hpack_huffman_aggregator.cc:169: samples.Accumulate(i + 1,
counts_[i]);
> Why are you putting samples into your personal histogram, and then copying
them
> over to the global histogram??

The biggest reason for keeping internal counts is privacy. We shouldn't be
publishing histogram updates which sample an insufficiently large number of
headers.


> Why don't you just use a standard histogram?  They are plenty efficient. Are
you
> fearful that you wont get an atomic group of all samples?  Even with this
> approach it will not be atomic :-/.


Atomicity isn't a concern. I am worried about performance from using
UMA_HISTOGRAM_ENUMERATION or similar, though. That means locking to lookup up
the histogram plus a couple of virtual calls for every character of every
literal header that passes through. Again though, this is a secondary reason for
the internal counts.

Histograms don't support an Accumulate() method for individual samples, just
Add(): thus the indirection through creating and populating a SampleVector
first.

[jar (doing other things), 2014-04-18 22:30:43]

On 2014/04/18 21:42:21, Johnny wrote:
> On 2014/04/18 21:14:53, jar wrote:
> > Why are you using Huffman coding? ...
> 
> See the (draft) specification:
> https://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07
> 
> Particularly, "4.1.2.  String Literal Representation" & "5.1. 
Compression-based
> Attacks".

Ah... ok. Thanks.

> >
https://codereview.chromium.org/243153003/diff/1/net/spdy/hpack_huffman_aggre...
> > net/spdy/hpack_huffman_aggregator.cc:82: // HACK(jgraettinger): To be
removed
> > before submission.
> > hmmmm.... this seems like a bad plan.... and subject to landing without
> removing
> > it by accident.
> > 
> > Is this the "approved" way of doing this??
> 
> It's an easy way to get trybots to run the trial codepath, which is certainly
> required. By default once checked in, they won't run it.

FWIW: Once checked in... if the experiment is not defined... I think it will
always run.
I guess that may be OK.  I'd assume that once the Finch experiment "expires,"
that
there will (again) be no name... and will run forever in the field.

> > Why are you putting samples into your personal histogram, and then copying
> them
> > over to the global histogram??


> 
> The biggest reason for keeping internal counts is privacy. We shouldn't be
> publishing histogram updates which sample an insufficiently large number of
> headers.

That is a pretty good reason that I hadn't considered. thanks!


> > Why don't you just use a standard histogram?  They are plenty efficient. Are
> you
> > fearful that you wont get an atomic group of all samples?  Even with this
> > approach it will not be atomic :-/.
> 
> 
> Atomicity isn't a concern. I am worried about performance from using
> UMA_HISTOGRAM_ENUMERATION or similar, though. That means locking to lookup up
> the histogram plus a couple of virtual calls for every character of every
> literal header that passes through. Again though, this is a secondary reason
for
> the internal counts.

For future reference (since your privacy concern SGTM here), the histogram
avoids
locking, and avoids doing a map lookup, in all but the first sampling-call.  The
standard macro caches a static pointer to the "never to be destroyed" histogram,
making performance a non problem.  [again... for future reference only. ]

> Histograms don't support an Accumulate() method for individual samples, just
> Add(): thus the indirection through creating and populating a SampleVector
> first.

Yeah... it was strange (very atypical) to go this deeply into the histogram
code (messing with macros that are really only in the header to induce
inlining, and most critically, creation of a function static which C++ can't do
in any nice way.

If you do the transfer from your vector to the histogram more frequently, you
might be much more readable by just using the standard way of pushing samples
(one at a time) into the public histogram.

For instance, maybe you could just reduce:
const size_t kTotalCountsPublishThreshold = 200;
and then use the standard (even if painful) way of moving across values
into the public histogram.  I'd bet that 200 would be more than private
enough (there are a lot of permutations of 200 items... assuming they are
not all the same!), and the code to do the Histogram accumulation is very very
fast.

I'm impressed by your hackery/reading to use the internal macro... and since
I think this code will be ripped out long before folks need to mess with
the macro.... I'll:

LGTM % add a TODO to remove this code once you've gotten your data from the
world ;-).

If you think you want to keep the code around a loooong time... it would
probably
be better (more readable/maintainable) to reduce the threshold (as noted above)
and 
then use standard UMA_HISTOGRAM_ENUMERATION(...)

[Ryan Hamilton, 2014-04-20 02:25:06]

lgtm

[Johnny, 2014-04-21 23:00:43]

Thank you both.

I'm working on merging upstream changes which I'd like to rebase this CL upon
(particularly the actual HPACK delta encoder). Changes should be minor, and I'll
ping again when I've done that and fully addressed the feedback here.

[Johnny, 2014-04-29 17:06:08]

Hi Ryan & Jim,

This is ready for a last check before landing:

I've rebased atop the HPACK delta encoder (and other recent SPDY merges).

I've updated the experiment membership check and confirmed that the new code is
disabled by default in browsing sessions & tests.

I also bumped the publishing threshold to 50K characters. In my testing, that
cause a histogram publish to occur every few browsed pages for content-heavy
sites like cnn.com.

thanks,
-johnny

[jar (doing other things), 2014-04-29 18:40:18]

LGTM % nits

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
File net/spdy/hpack_huffman_aggregator.h (right):

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
net/spdy/hpack_huffman_aggregator.h:62: typedef std::list<OriginEncoder>
OriginEncoders;
nit: move typedefs at the start of the private section.

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
net/spdy/hpack_huffman_aggregator.h:69: };
nit: DISALLOW_COPY_AND_ASSIGN  (unless you have a real need)

https://codereview.chromium.org/243153003/diff/70001/tools/metrics/histograms...
File tools/metrics/histograms/histograms.xml (right):

https://codereview.chromium.org/243153003/diff/70001/tools/metrics/histograms...
tools/metrics/histograms/histograms.xml:13285: +<histogram
name="Net.SpdyHpackEncodedCharacterFrequency" units="count">
nit: Units refers to the buckets, which are (as noted) "character ordinals" or
perhaps "ASCII codes."

[Johnny, 2014-04-29 20:53:16]

Thanks

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
File net/spdy/hpack_huffman_aggregator.h (right):

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
net/spdy/hpack_huffman_aggregator.h:62: typedef std::list<OriginEncoder>
OriginEncoders;
On 2014/04/29 18:40:19, jar wrote:
> nit: move typedefs at the start of the private section.

Done.

https://codereview.chromium.org/243153003/diff/70001/net/spdy/hpack_huffman_a...
net/spdy/hpack_huffman_aggregator.h:69: };
On 2014/04/29 18:40:19, jar wrote:
> nit: DISALLOW_COPY_AND_ASSIGN  (unless you have a real need)

Done.

https://codereview.chromium.org/243153003/diff/70001/tools/metrics/histograms...
File tools/metrics/histograms/histograms.xml (right):

https://codereview.chromium.org/243153003/diff/70001/tools/metrics/histograms...
tools/metrics/histograms/histograms.xml:13285: +<histogram
name="Net.SpdyHpackEncodedCharacterFrequency" units="count">
On 2014/04/29 18:40:19, jar wrote:
> nit: Units refers to the buckets, which are (as noted) "character ordinals" or
> perhaps "ASCII codes."

Done.

[Johnny, 2014-04-29 22:30:27]

The CQ bit was checked by jgraettinger@chromium.org

[commit-bot: I haz the power, 2014-04-29 22:31:15]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jgraettinger@chromium.org/243153003/90001

[commit-bot: I haz the power, 2014-04-30 08:06:45]

Change committed as 267131