Use a different algorithm with the low entropy source for field trials.

Use a different algorithm with the low entropy source for field trials.

The new algorithm maps the original 13-bit low entropy source to a
new 13-bit entropy value using a mapping that is shuffled using the
trial name as a seed.

The algorithm is roughly as follows:
Take the low entropy source as an integer between 0-8191.
Generate an identity mapping of size 8192 where mapping[i] == i.
Seed a Mersenne Twister random number generator with the hash of the field trial name.
Use the seeded random number generator to shuffle the mapping array.
Map the low entropy source using the mapping array, i.e. entropy' = mapping[entropy].
Divide the resulting entropy' by 8192 to produce a double in the range of [0, 1) that
will be used for bucketing in field_trial.cc.

The above algorithm improves uniformity over the existing entropy provider when
the 13-bit entropy source is used while still providing very little overlaps of
buckets between different field trials.

Adds third_party library mt19937ar, an implementation of Mersenne Twister, for
the seeded random number generation. This is needed until C++11 becomes available
for use in Chromium, at which point C++11's <random> could be used.

BUG=143239
TEST=Unit tests. Additionally, verified that the new algorithm produces uniform results
with very little overlap of buckets between different field trials.

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=153322

[Alexei Svitkine (slow), 2012-08-16 20:12:57]

Primary reviewers: Steve and Ilya
chrome/ and content/ OWNERS approval: Brett
chrome_frame/ OWNERS approval: Robert
third_party addition: open-source-third-party-reviews

[SteveT, 2012-08-16 20:55:42]

Looking good. Mostly questions and a few nits inline.

http://codereview.chromium.org/10830318/diff/5042/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

http://codereview.chromium.org/10830318/diff/5042/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:88: divisor_ *
entropy_provider_->GetEntropyForTrial(name_));
Could |entropy_provider_| be NULL?

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/chrome_brows...
File chrome/browser/chrome_browser_main_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:41: base::FieldTrialList
field_trial_list_(NULL);
This is to avoid that test error you saw earlier where the FTL was defined out
of order?

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:563: kMaxEntropySize);
Some weirdness with the alignment here.

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:32: // as likely as a result of 3 or
4).
nit: Looks like you can make better use of the 80 space line limit in the above
comment...

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:34: // TODO(asvitkine): Share the
implementation with variations_util.cc.
Recently I saw a comment in a CL about how bugs are preferred over TODOs. Do you
think HashName is something that would be useful in base? If so, log a bug about
moving it out there. Otherwise you can ignore this comment :)

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:46: // should contain a large amount of
entropy - for example a textual
nit: for example -> for example.

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:61: // sources (below 16 bits). It uses
the field trial name to generate a
Curious: Did we test this 16 bits assertion?

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
File third_party/mt19937ar/mt19937ar.h (right):

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
third_party/mt19937ar/mt19937ar.h:50: 
BTW, do we have to do any special documentation given we've made edits to the
original code? (to get it to fit in as a class, and to remove globals, etc).

[robertshield, 2012-08-16 21:18:01]

Chrome Frame stuff LGTM

http://codereview.chromium.org/10830318/diff/5042/chrome_frame/test/run_all_u...
File chrome_frame/test/run_all_unittests.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome_frame/test/run_all_u...
chrome_frame/test/run_all_unittests.cc:57: base::FieldTrialList
field_trial_list(NULL);
I disapprove of this change aesthetically, though pragmatically it looks right.

[Alexei Svitkine (slow), 2012-08-16 21:27:11]

Replying to some of the comments. Will address the others tomorrow.

Also, fixed an issue with one of the added unit tests.

http://codereview.chromium.org/10830318/diff/5042/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

http://codereview.chromium.org/10830318/diff/5042/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:88: divisor_ *
entropy_provider_->GetEntropyForTrial(name_));
On 2012/08/16 20:55:42, SteveT wrote:
> Could |entropy_provider_| be NULL?

If it is, then FieldTrialList::IsOneTimeRandomizationEnabled() will be true and
there will be an early return above.

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/chrome_brows...
File chrome/browser/chrome_browser_main_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:41: base::FieldTrialList
field_trial_list_(NULL);
On 2012/08/16 20:55:42, SteveT wrote:
> This is to avoid that test error you saw earlier where the FTL was defined out
> of order?

Right. Basically, the issue is that this test (and also the variations_util
test) end up using FieldTrialList statics without creating a FieldTrialList.
This ends up setting FieldTrialList::used_without_global_ = true, but that's
only checked the next time a FieldTrialList is created. So it ends up blowing up
the next test that does instantiate a FieldTrialList - such as the
EntropyProviderTest. This change fixes the issue.

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:563: kMaxEntropySize);
On 2012/08/16 20:55:42, SteveT wrote:
> Some weirdness with the alignment here.

Done.

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:32: // as likely as a result of 3 or
4).
On 2012/08/16 20:55:42, SteveT wrote:
> nit: Looks like you can make better use of the 80 space line limit in the
above
> comment...

This comment (and code) is copied out of base::RandGenerator(). I'd rather keep
them the same.

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:34: // TODO(asvitkine): Share the
implementation with variations_util.cc.
On 2012/08/16 20:55:42, SteveT wrote:
> Recently I saw a comment in a CL about how bugs are preferred over TODOs. Do
you
> think HashName is something that would be useful in base? If so, log a bug
about
> moving it out there. Otherwise you can ignore this comment :)

I'm not convinced it needs to be in base. I think we can just expose it in
variations_util.cc - the reason I didn't do this already is to make merging this
patch to earlier branches easier (if it gets approved for merge) - since
variations_util.cc has been refactored recently.

[Ilya Sherman, 2012-08-17 07:34:28]

lg (other than the concerns about the test code).

Jim should definitely take a look at this as well, though, since he has a lot
more familiarity than I do with what sorts of things can go wrong with this.

https://chromiumcodereview.appspot.com/10830318/diff/5044/base/metrics/field_...
File base/metrics/field_trial.h (right):

https://chromiumcodereview.appspot.com/10830318/diff/5044/base/metrics/field_...
base/metrics/field_trial.h:101: virtual ~EntropyProvider() {}
nit: Virtual functions should never be inlined.

https://chromiumcodereview.appspot.com/10830318/diff/5044/base/metrics/field_...
base/metrics/field_trial.h:203: FieldTrial(EntropyProvider* entropy_provider,
nit: Unless you're planning to modify the |entropy_provider| (I'd expect not),
this should be passed as a const pointer.

https://chromiumcodereview.appspot.com/10830318/diff/5044/base/metrics/field_...
base/metrics/field_trial.h:220: EntropyProvider* entropy_provider_;
nit: const EntropyProvider* const?

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/browser/metr...
File chrome/browser/metrics/metrics_service.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/browser/metr...
chrome/browser/metrics/metrics_service.cc:558: return new
SHA1EntropyProvider(high_entropy_source);
I'm not a fan of functions that return heap-allocated memory.  This places the
burden on the caller to remember to free the memory, or else we leak it.  Can
you return a scoped_ptr instead, e.g. using the Pass() method to transfer
ownership?

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/browser/metr...
File chrome/browser/metrics/metrics_service.h (right):

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/browser/metr...
chrome/browser/metrics/metrics_service.h:42: class EntropyProvider;
Isn't this class defined as a subtype of the FieldTrial class?

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:31: new
PermutedEntropyProvider(entropy_source, entropy_max));
nit: Why not just stack-allocate this guy?

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:134: int current_number =
base::RandInt(0, std::numeric_limits<int>::max());
We should print the seed on failure, so that failures are reproducible.

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:143: // range (i.e. the test
would start timing out occasionally).
Hmm, this sounds like it's just checking that the distribution is symmetric, not
that it's uniform.  Why not do something like have 20 buckets and check their
counts?

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:147: while (true) {
Rather than having a while (true) loop, let's figure out how many iterations we
need to gain 99.999999% confidence for convergence, and iterate that many times.

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:156: double kExpectedMax =
0.52;
This is a pretty big range for the high-entropy source.  Do we really expect so
much variance?

[Ilya Sherman, 2012-08-17 07:35:15]

Also, I think it might be best to have the Mersenne Twister library reviewed in
a separate CL, rather than as part of this one...

[Alexei Svitkine (slow), 2012-08-17 14:08:59]

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:46: // should contain a large amount of
entropy - for example a textual
On 2012/08/16 20:55:42, SteveT wrote:
> nit: for example -> for example.

Done.

http://codereview.chromium.org/10830318/diff/5042/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:61: // sources (below 16 bits). It uses
the field trial name to generate a
On 2012/08/16 20:55:42, SteveT wrote:
> Curious: Did we test this 16 bits assertion?

I guess it's kind of arbitrary - the thing is that the performance of this
entropy provider is O(n^2) where n = number of bits in the entropy source. So
using a high entropy source would just make this extremely slow. (I've now added
a comment about this).

The 16 bits specifically isn't enforced anywhere except in the fact that I'm
using a uint16 for |low_entropy_source|.

I've now also added some DCHECKs() in the implementation of the constructor that
assert this too.

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
File third_party/mt19937ar/mt19937ar.h (right):

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
third_party/mt19937ar/mt19937ar.h:50: 
On 2012/08/16 20:55:42, SteveT wrote:
> BTW, do we have to do any special documentation given we've made edits to the
> original code? (to get it to fit in as a class, and to remove globals, etc).

I'm not sure. Let's see what open-source-third-party-reviews say.

http://codereview.chromium.org/10830318/diff/5044/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/5044/base/metrics/field_trial.h#...
base/metrics/field_trial.h:101: virtual ~EntropyProvider() {}
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> nit: Virtual functions should never be inlined.

Done. I also fixed this for FieldTrialList::Observer below.

http://codereview.chromium.org/10830318/diff/5044/base/metrics/field_trial.h#...
base/metrics/field_trial.h:203: FieldTrial(EntropyProvider* entropy_provider,
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> nit: Unless you're planning to modify the |entropy_provider| (I'd expect not),
> this should be passed as a const pointer.

Done.

http://codereview.chromium.org/10830318/diff/5044/base/metrics/field_trial.h#...
base/metrics/field_trial.h:220: EntropyProvider* entropy_provider_;
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> nit: const EntropyProvider* const?

Done.

http://codereview.chromium.org/10830318/diff/5044/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/5044/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:558: return new
SHA1EntropyProvider(high_entropy_source);
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> I'm not a fan of functions that return heap-allocated memory.  This places the
> burden on the caller to remember to free the memory, or else we leak it.  Can
> you return a scoped_ptr instead, e.g. using the Pass() method to transfer
> ownership?

Done.

http://codereview.chromium.org/10830318/diff/5044/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.h (right):

http://codereview.chromium.org/10830318/diff/5044/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:42: class EntropyProvider;
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> Isn't this class defined as a subtype of the FieldTrial class?

You're right. This got left over from a previous iteration where I had the
EntropyProvider as a standalone interface. Removed.

http://codereview.chromium.org/10830318/diff/5044/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/5044/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:31: new
PermutedEntropyProvider(entropy_source, entropy_max));
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> nit: Why not just stack-allocate this guy?

Good point. Done.

[Alexei Svitkine (slow), 2012-08-17 14:11:10]

Ilya: Regarding the test you have some concerns about - it's actually just an
existing test I'm moving from field_trial_unittest.cc.

Do you want me to scrap it and write the new one with the 20 buckets like you
suggest?

About splitting off the third_party addition from the CL: for now I'd like to
keep them together which makes things like try jobs much easier (or even
possible?). I can split them off later if we want.

[SteveT, 2012-08-17 14:26:57]

LGTM. Thanks for answering those questions and addressing those nits. Curious to
see what the third-party reviewers say about this new lib.

[Alexei Svitkine (slow), 2012-08-17 16:42:16]

http://codereview.chromium.org/10830318/diff/5042/chrome_frame/test/run_all_u...
File chrome_frame/test/run_all_unittests.cc (right):

http://codereview.chromium.org/10830318/diff/5042/chrome_frame/test/run_all_u...
chrome_frame/test/run_all_unittests.cc:57: base::FieldTrialList
field_trial_list(NULL);
On 2012/08/16 21:18:01, robertshield wrote:
> I disapprove of this change aesthetically, though pragmatically it looks
right.

In fact, I had to change this back to not pass NULL since it caused some
chrome_frame tests failures (I guess some chrome frame field trials require one
time randomization).

[hfung, 2012-08-17 17:35:40]

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:562: entropy_provider.reset(new
PermutedEntropyProvider(GetLowEntropySource(),
GetLowEntropySource() -> low_entropy_source?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:73: // is desirable so that we don't
skew any part of the 0-100% spectrum.
Mention that it doesn't work as well when there's less entropy (since the
comment seems to imply otherwise)?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:64: // Note: This provider's
performance is O(n^2), where n is the number of bits
Isn't it O(low_entropy_source_max), since it has to shuffle that many elements,
so O(2^n)?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:182: // distribution from
[0.0, 1.0) this would be 0.5.
So you aren't testing the distribution among different buckets (which is what
the actual problem we had) such as the min/max number of samples that fall
within 100 different buckets?  Would that be a stricter test?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:220: // Verifies. that
SeededRandGenerator has a uniform distribution.
extra period?

[Ilya Sherman, 2012-08-17 17:53:11]

On 2012/08/17 14:11:10, Alexei Svitkine wrote:
> Ilya: Regarding the test you have some concerns about - it's actually just an
> existing test I'm moving from field_trial_unittest.cc.
> 
> Do you want me to scrap it and write the new one with the 20 buckets like you
> suggest?

I don't think you should necessarily scrap the old test, but I do think
including a test to cover the particular failure case that motivated this CL
would be wise.

> About splitting off the third_party addition from the CL: for now I'd like to
> keep them together which makes things like try jobs much easier (or even
> possible?). I can split them off later if we want.

[Ilya Sherman, 2012-08-17 17:53:20]

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
File third_party/mt19937ar/mt19937ar.h (right):

http://codereview.chromium.org/10830318/diff/5042/third_party/mt19937ar/mt199...
third_party/mt19937ar/mt19937ar.h:50: 
On 2012/08/17 14:08:59, Alexei Svitkine wrote:
> On 2012/08/16 20:55:42, SteveT wrote:
> > BTW, do we have to do any special documentation given we've made edits to
the
> > original code? (to get it to fit in as a class, and to remove globals, etc).
> 
> I'm not sure. Let's see what open-source-third-party-reviews say.

I think that edits are usually saved to a .patch file within the third_party
directory, plus a README file that specifies how to apply the patches.  That way
you can update to a newer version of the library and re-apply the patch so that
it plays nicely with Chrome code.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:295: explicit
FieldTrialList(FieldTrial::EntropyProvider* entropy_provider);
Optional nit: I would pass this in as a scoped_ptr<> as well, and transfer
ownership internally.  The motivation for this pattern is that it's then harder
for the implementation to e.g. return early and fail to take ownership.  That's
obviously not a problem for the current implementation, but explicit transfers
of ownership make it less likely for this sort of error to creep in in the
future.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:545:
scoped_ptr<base::FieldTrial::EntropyProvider> entropy_provider;
Optional nit: I think you can still return the entropy provider directly, rather
than storing it in a local variable, like so:

return scoped_ptr<base::FieldTrial::EntropyProvider(new
SHA1EntropyProvider(high_entropy_source));

(Note that .Pass() is not required if you declare the scoped_ptr<> as part of
the return statement.)

[Alexei Svitkine (slow), 2012-08-17 17:57:40]

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:562: entropy_provider.reset(new
PermutedEntropyProvider(GetLowEntropySource(),
On 2012/08/17 17:35:40, hfung wrote:
> GetLowEntropySource() -> low_entropy_source?

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:73: // is desirable so that we don't
skew any part of the 0-100% spectrum.
On 2012/08/17 17:35:40, hfung wrote:
> Mention that it doesn't work as well when there's less entropy (since the
> comment seems to imply otherwise)?

Updated the comment.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:64: // Note: This provider's
performance is O(n^2), where n is the number of bits
On 2012/08/17 17:35:40, hfung wrote:
> Isn't it O(low_entropy_source_max), since it has to shuffle that many
elements,
> so O(2^n)?

That's correct - I accidentally transposed the two. Fixed.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:182: // distribution from
[0.0, 1.0) this would be 0.5.
On 2012/08/17 17:35:40, hfung wrote:
> So you aren't testing the distribution among different buckets (which is what
> the actual problem we had) such as the min/max number of samples that fall
> within 100 different buckets?  Would that be a stricter test?

Ilya had the same concern / suggestion. (Note: This test is actually an existing
test that was moved over from field_trial_unittest.cc and adjusted to also test
the permuted entropy source.)

I'll write a new test that better verifies that the actual issue we saw.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:220: // Verifies. that
SeededRandGenerator has a uniform distribution.
On 2012/08/17 17:35:40, hfung wrote:
> extra period?

Done.

[Alexei Svitkine (slow), 2012-08-17 17:58:58]

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:295: explicit
FieldTrialList(FieldTrial::EntropyProvider* entropy_provider);
On 2012/08/17 17:53:20, Ilya Sherman wrote:
> Optional nit: I would pass this in as a scoped_ptr<> as well, and transfer
> ownership internally.  The motivation for this pattern is that it's then
harder
> for the implementation to e.g. return early and fail to take ownership. 
That's
> obviously not a problem for the current implementation, but explicit transfers
> of ownership make it less likely for this sort of error to creep in in the
> future.

I tried that, but then FieldTrialList(NULL) doesn't compile.

[Ilya Sherman, 2012-08-17 18:16:55]

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:295: explicit
FieldTrialList(FieldTrial::EntropyProvider* entropy_provider);
On 2012/08/17 17:58:58, Alexei Svitkine wrote:
> On 2012/08/17 17:53:20, Ilya Sherman wrote:
> > Optional nit: I would pass this in as a scoped_ptr<> as well, and transfer
> > ownership internally.  The motivation for this pattern is that it's then
> harder
> > for the implementation to e.g. return early and fail to take ownership. 
> That's
> > obviously not a problem for the current implementation, but explicit
transfers
> > of ownership make it less likely for this sort of error to creep in in the
> > future.
> 
> I tried that, but then FieldTrialList(NULL) doesn't compile.

How about FieldTrialList<scoped_ptr<FieldTrial::EntropyProvider>()>?  If that
doesn't work either, no worries, this is ok as it is.

[jar (doing other things), 2012-08-17 19:06:19]

Per comment by Isherman... I looked through the code.  I didn't see any
problems, other than a few questions, and a lot of nits.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:60: : entropy_provider_(entropy_provider),
nit: Please indent the ":" by four spaces.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:84: if
(!FieldTrialList::IsOneTimeRandomizationEnabled()) {
This function, could, for example, return an entropy_provider, and then there
would be no reason to maintain a slot in the FieldTrial instance.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:438: bool
FieldTrialList::IsOneTimeRandomizationEnabled() {
You might change this to:
GetEntropyProviderForOneTimeRandomization()

...or... if you don't want to bother passing around the functoid... you could
pass in the string, and get back the entropy (with a bool if there was no
provider):
bool GetOneTimeEntropy(const std::string name, double* entropy);

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:107: };
Please add DISALLOW_COPY_AND_ASSIGN(..)

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:203: FieldTrial(const EntropyProvider*
entropy_provider,
nit: add comment that |entropy_provider_| is null when one time randomization is
not supported.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:220: const EntropyProvider* const entropy_provider_;
Why is this needed on a per-FieldTrial basis?  I would have expected the entropy
to be calculated exactly once. Why do we need this hanging around (resulting in
having to talk about weak pointers)?

Note the original code was a static method... which could equally well have
existed in the TrialList class.

Perhaps this method could even be passed in when needed, closer to
one-time-randomization time.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:294: // entropy values. Takes ownership of
|entropy_provider|.
nit: Comment should be explicit that a NULL value is legal.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
File chrome/browser/chrome_browser_main_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:36:
scoped_ptr<content::BrowserMainParts> bw(
nit: use descriptive names, not abbreviations such as |bw|

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:38: ChromeBrowserMainParts* cbw =
static_cast<ChromeBrowserMainParts*>(bw.get());
nit: |cbw| --> descriptive name

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:52: ChromeBrowserMainParts* cbw =
static_cast<ChromeBrowserMainParts*>(bw.get());
nit: use descriptive names for variables (line 50 and 52), as well as later in
file.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:546: const int low_entropy_source =
GetLowEntropySource();
nit: move this definition closer to first (and only?) use (which is inside a
conditional).

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:91: // based on whether or not metrics
reporting will permitted on this client.
nit: typo:   "metrics reporting will permitted"

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:103:
scoped_ptr<base::FieldTrial::EntropyProvider> GetEntropyProvider(
nit: I'd prefer to see an out-parameter for the entropy provider, as this
pattern caused me to have to think far too much about what is going on.  

At a minimum, it would help to have a name that makes it clear that a malloc
(new) is being done. A "getter" traditinoally leaves some ownership with the
instance. Perhaps:
void NewEntropyProvider(bool reporting_will_be_enabled,
                        const EntropyProvider* entropy_provider);

or (kindred to your scoped_ptr pattern):

void NewEntropyProvider(bool reporting_will_be_enabled,
                        scoped_ptr<const EntropyProvider>* entropy_provider);

Also, why is a mutable EntropyProvide() needed, rather than a const instance?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:48:
base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(name.c_str()),
Can we get away with a static_cast here?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:76:
base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),
Would static_cast work here?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:91: :
low_entropy_source_(low_entropy_source),
nit: indent ":" 4 spaces from the "P" in "Permuted..."

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:18: namespace internal {
This seems like a strange choice of global namespace names, and doesn't match
any of the path elements. Style guide suggests:

"choose the name based on the project, and possibly its path"

Could you consider something with the word "metrics," or nested inside of a
"metrics" namespace?

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:44:
base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
nit: 4 character indent (I think) for this line overflow.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:48: };
nit: This curly is not a block closure, and is more like a paren, which should
appear at the end of line 48.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:74:
base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
nit: 4 character indent

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:78: };
nit: This curly is not a block closure, and is more like a paren.  (the same
later in the file).

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:95: GenerateSHA1Entropy("hi",
"1"),
nit: indent 4.

[Ilya Sherman, 2012-08-17 19:14:00]

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:103:
scoped_ptr<base::FieldTrial::EntropyProvider> GetEntropyProvider(
On 2012/08/17 19:06:19, jar wrote:
> nit: I'd prefer to see an out-parameter for the entropy provider, as this
> pattern caused me to have to think far too much about what is going on.  
> 
> At a minimum, it would help to have a name that makes it clear that a malloc
> (new) is being done. A "getter" traditinoally leaves some ownership with the
> instance. Perhaps:
> void NewEntropyProvider(bool reporting_will_be_enabled,
>                         const EntropyProvider* entropy_provider);
> 
> or (kindred to your scoped_ptr pattern):
> 
> void NewEntropyProvider(bool reporting_will_be_enabled,
>                         scoped_ptr<const EntropyProvider>* entropy_provider);
> 
> Also, why is a mutable EntropyProvide() needed, rather than a const instance? 

FWIW, I think we used to use out params for things like this, but are now
gradually moving over to returning a scoped_ptr<> directly, now that we have the
Pass() method available to support this generally.

[Alexei Svitkine (slow), 2012-08-20 15:57:40]

Thanks Jim, I've addressed your comments below.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:60: : entropy_provider_(entropy_provider),
On 2012/08/17 19:06:19, jar wrote:
> nit: Please indent the ":" by four spaces.

Done.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:84: if
(!FieldTrialList::IsOneTimeRandomizationEnabled()) {
On 2012/08/17 19:06:19, jar wrote:
> This function, could, for example, return an entropy_provider, and then there
> would be no reason to maintain a slot in the FieldTrial instance.

Done.

By having the entropy provider passed in explicitly to the FieldTrial
constructor, the idea was to reduce coupling between FieldTrial and
FieldTrialList (by explicitly passing in dependencies). But it seems that the
two are already deeply coupled so it seems like a lost cause.

In particular, you're right to point out that this method already uses a static
function of FieldTrialList anyway, so I did as you suggested and made that
function return the EntropyProvider, removing the need for FieldTrial to hold
on to one.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:438: bool
FieldTrialList::IsOneTimeRandomizationEnabled() {
On 2012/08/17 19:06:19, jar wrote:
> You might change this to:
> GetEntropyProviderForOneTimeRandomization()
> 
> ...or... if you don't want to bother passing around the functoid... you could
> pass in the string, and get back the entropy (with a bool if there was no
> provider):
> bool GetOneTimeEntropy(const std::string name, double* entropy);

Done.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h
File base/metrics/field_trial.h (right):

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:107: };
On 2012/08/17 19:06:19, jar wrote:
> Please add DISALLOW_COPY_AND_ASSIGN(..)

We don't usually do this for pure interface classes. Here's an example search
for "Delegate", which brings up a bunch of these (that don't use the macro):

http://code.google.com/p/chromium/source/search?q=Delegate

Using the macro creates the following problem for subclasses that implement the
interface (i.e. forcing them to declare an empty constructor):

error: constructor for 'SHA1EntropyProvider' must explicitly initialize the base
class 'base::FieldTrial::EntropyProvider' which does not have a default
constructor

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:203: FieldTrial(const EntropyProvider*
entropy_provider,
On 2012/08/17 19:06:19, jar wrote:
> nit: add comment that |entropy_provider_| is null when one time randomization
is
> not supported.

No longer needed since the param is removed.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:220: const EntropyProvider* const entropy_provider_;
On 2012/08/17 19:06:19, jar wrote:
> Why is this needed on a per-FieldTrial basis?  I would have expected the
entropy
> to be calculated exactly once. Why do we need this hanging around (resulting
in
> having to talk about weak pointers)?

The entropy provider is responsible for providing a random number dice roll
based on the entropy and the trial name. So calculating it exactly once doesn't
work.

We also can't just calculate the double in FieldTrialList and pass to that value
to the constructor because we only want to do this for one time randomized field
trials - and it is not known whether a trial will be such until
|UseOneTimeRandomization()| is called.

> 
> Note the original code was a static method... which could equally well have
> existed in the TrialList class.
> 
> Perhaps this method could even be passed in when needed, closer to
> one-time-randomization time.

http://codereview.chromium.org/10830318/diff/4096/base/metrics/field_trial.h#...
base/metrics/field_trial.h:294: // entropy values. Takes ownership of
|entropy_provider|.
On 2012/08/17 19:06:19, jar wrote:
> nit: Comment should be explicit that a NULL value is legal.

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
File chrome/browser/chrome_browser_main_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:36:
scoped_ptr<content::BrowserMainParts> bw(
On 2012/08/17 19:06:19, jar wrote:
> nit: use descriptive names, not abbreviations such as |bw|

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:38: ChromeBrowserMainParts* cbw =
static_cast<ChromeBrowserMainParts*>(bw.get());
On 2012/08/17 19:06:19, jar wrote:
> nit: |cbw| --> descriptive name

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/chrome_brows...
chrome/browser/chrome_browser_main_unittest.cc:52: ChromeBrowserMainParts* cbw =
static_cast<ChromeBrowserMainParts*>(bw.get());
On 2012/08/17 19:06:19, jar wrote:
> nit: use descriptive names for variables (line 50 and 52), as well as later in
> file.

Done. I didn't write this code, but I shaved the yak at your request.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:545:
scoped_ptr<base::FieldTrial::EntropyProvider> entropy_provider;
On 2012/08/17 17:53:20, Ilya Sherman wrote:
> Optional nit: I think you can still return the entropy provider directly,
rather
> than storing it in a local variable, like so:
> 
> return scoped_ptr<base::FieldTrial::EntropyProvider(new
> SHA1EntropyProvider(high_entropy_source));
> 
> (Note that .Pass() is not required if you declare the scoped_ptr<> as part of
> the return statement.)

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.cc:546: const int low_entropy_source =
GetLowEntropySource();
On 2012/08/17 19:06:19, jar wrote:
> nit: move this definition closer to first (and only?) use (which is inside a
> conditional).

I've inlined this into the two callers.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
File chrome/browser/metrics/metrics_service.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:91: // based on whether or not metrics
reporting will permitted on this client.
On 2012/08/17 19:06:19, jar wrote:
> nit: typo:   "metrics reporting will permitted"

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/browser/metrics/metr...
chrome/browser/metrics/metrics_service.h:103:
scoped_ptr<base::FieldTrial::EntropyProvider> GetEntropyProvider(
On 2012/08/17 19:06:19, jar wrote:
> nit: I'd prefer to see an out-parameter for the entropy provider, as this
> pattern caused me to have to think far too much about what is going on.  
> 
> At a minimum, it would help to have a name that makes it clear that a malloc
> (new) is being done. A "getter" traditinoally leaves some ownership with the
> instance. Perhaps:
> void NewEntropyProvider(bool reporting_will_be_enabled,
>                         const EntropyProvider* entropy_provider);
> 
> or (kindred to your scoped_ptr pattern):
> 
> void NewEntropyProvider(bool reporting_will_be_enabled,
>                         scoped_ptr<const EntropyProvider>* entropy_provider);
> 
> Also, why is a mutable EntropyProvide() needed, rather than a const instance? 

Changed name to CreateEntropyProvider() and made the returned provider const.
Still kept it returning a scoped_ptr per the same reasoning as Ilya mentioned.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:48:
base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(name.c_str()),
On 2012/08/17 19:06:19, jar wrote:
> Can we get away with a static_cast here?

Doesn't look like it. This is what the compiler says:

 error: static_cast from 'const char *' to 'const unsigned char *' is not
allowed

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:76:
base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(input.c_str()),
On 2012/08/17 19:06:19, jar wrote:
> Would static_cast work here?

Same as above.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.cc:91: :
low_entropy_source_(low_entropy_source),
On 2012/08/17 19:06:19, jar wrote:
> nit: indent ":" 4 spaces from the "P" in "Permuted..."

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:18: namespace internal {
On 2012/08/17 19:06:19, jar wrote:
> This seems like a strange choice of global namespace names, and doesn't match
> any of the path elements. Style guide suggests:
> 
> "choose the name based on the project, and possibly its path"
> 
> Could you consider something with the word "metrics," or nested inside of a
> "metrics" namespace?

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:44:
base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
On 2012/08/17 19:06:19, jar wrote:
> nit: 4 character indent (I think) for this line overflow.

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:48: };
On 2012/08/17 19:06:19, jar wrote:
> nit: This curly is not a block closure, and is more like a paren, which should
> appear at the end of line 48.

On 2012/08/17 19:06:19, jar wrote:
> nit: This curly is not a block closure, and is more like a paren.  (the same
> later in the file).

That suggestion doesn't seem consistent with the style used elsewhere in
Chromium codebase where arrays are initialized like this.

For example, see some of the results of this code search:

http://code.google.com/searchframe#search/&exact_package=chromium&q=test_case...

So I'm leaving it as is.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:74:
base::FieldTrialList::FactoryGetFieldTrial("one", 100, "default",
On 2012/08/17 19:06:19, jar wrote:
> nit: 4 character indent 

Done.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:78: };
On 2012/08/17 19:06:19, jar wrote:
> nit: This curly is not a block closure, and is more like a paren.  (the same
> later in the file).

That suggestion doesn't seem consistent with the style used elsewhere in
Chromium codebase where arrays are initialized like this.

For example, see some of the results of this code search:

http://code.google.com/searchframe#search/&exact_package=chromium&q=test_case...

So I'm leaving it as is.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:95: GenerateSHA1Entropy("hi",
"1"),
On 2012/08/17 19:06:19, jar wrote:
> nit: indent 4.

Done.

[Alexei Svitkine (slow), 2012-08-20 16:02:55]

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/5044/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:143: // range (i.e. the test
would start timing out occasionally).
On 2012/08/17 07:34:28, Ilya Sherman wrote:
> Why not do something like have 20 buckets and check their counts?

I've now replaces this test with one that distributes 100000 samples between 20
buckets and checks the min and max sizes of the buckets and the standard
deviation of the counts per bucket.

The results seem more or less consistent between the high entropy source using
SHA1 and the low entropy source using the permuted method, although still having
more variance than I expected.

For example, here's the output from a run of both:

[ RUN      ] EntropyProviderTest.SHA1EntropyIsUniform
min = 4871, max = 5107, stddev = 63.812225
min = 4850, max = 5129, stddev = 70.342022
min = 4875, max = 5185, stddev = 86.602540
[       OK ] EntropyProviderTest.SHA1EntropyIsUniform (2950 ms)
[ RUN      ] EntropyProviderTest.PermutedEntropyIsUniform
min = 4933, max = 5071, stddev = 44.294469
min = 4817, max = 5194, stddev = 74.188948
min = 4894, max = 5109, stddev = 58.932164
[       OK ] EntropyProviderTest.PermutedEntropyIsUniform (515 ms)


I am not sure what's a good way to choose the success / failure criteria for
such a test without introducing flakiness. For example, I've seen the standard
deviation go to as far as 105. So unless we make it really high (like 200), it
seems like the test would be prone to be flaky. Any suggestions?

[Ilya Sherman, 2012-08-21 03:42:27]

Thanks for writing the distribution-based tests, Alexei :)

I think the most appropriate pass/fail conditions would be ones that should
statistically pass with 99.9999999% confidence (or whatever confidence interval
we think is appropriate so that the tests are both fast and pragmatically not
flaky).  I don't have quite enough statistics background, though, to compute the
appropriate conditions easily :/

https://chromiumcodereview.appspot.com/10830318/diff/6116/base/metrics/field_...
File base/metrics/field_trial.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/6116/base/metrics/field_...
base/metrics/field_trial.cc:218: FieldTrialList::FieldTrialList(const
FieldTrial::EntropyProvider* provider)
nit: I think you should continue to call this variable |entropy_provider|, as
|provider| is quite generic.

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
File chrome/common/metrics/entropy_provider.h (right):

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
chrome/common/metrics/entropy_provider.h:19: namespace metrics_internal {
nit: Actually, since this is all new code, let's wrap all of it in the metrics::
namespace.  We're not consistently using namespaces in Chrome code yet, but the
desired direction, AFAIK, is to have all code live in an appropriate namespace.

So, rather than naming this namespace |metrics_internal|, let's have an outer
namespace |metrics| for all of the declarations in this header, and an inner
namespace |internal| for the internal ones exposed for testing.

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:22: const int mean = sum /
values.size();
nit: Should this be a double rather than an int?

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:150: const int
kIterationCount = 100000;
nit: size_t throughout?

https://chromiumcodereview.appspot.com/10830318/diff/6116/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:204: // name and index into
it each iteration.
Is this performance optimization needed for the test to run smoothly?  If not,
I'd prefer to test the actual code, so that there's no chance for a bug to get
fixed there and not in the test.  If the optimization is necessary, though,
well, so be it.

[Alexei Svitkine (slow), 2012-08-21 14:25:48]

http://codereview.chromium.org/10830318/diff/6116/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

http://codereview.chromium.org/10830318/diff/6116/base/metrics/field_trial.cc...
base/metrics/field_trial.cc:218: FieldTrialList::FieldTrialList(const
FieldTrial::EntropyProvider* provider)
On 2012/08/21 03:42:27, Ilya Sherman wrote:
> nit: I think you should continue to call this variable |entropy_provider|, as
> |provider| is quite generic.

Done.

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider.h (right):

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider.h:19: namespace metrics_internal {
On 2012/08/21 03:42:27, Ilya Sherman wrote:
> nit: Actually, since this is all new code, let's wrap all of it in the
metrics::
> namespace.  We're not consistently using namespaces in Chrome code yet, but
the
> desired direction, AFAIK, is to have all code live in an appropriate
namespace.
> 
> So, rather than naming this namespace |metrics_internal|, let's have an outer
> namespace |metrics| for all of the declarations in this header, and an inner
> namespace |internal| for the internal ones exposed for testing.

Done.

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:22: const int mean = sum /
values.size();
On 2012/08/21 03:42:27, Ilya Sherman wrote:
> nit: Should this be a double rather than an int?

Changed to use doubles throughout the function.

(The previous code was correct but only because the mean was always a full
integer - i.e. for 100000 iterations and 20 buckets, it would always be 5000).

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:150: const int
kIterationCount = 100000;
On 2012/08/21 03:42:27, Ilya Sherman wrote:
> nit: size_t throughout?

Done.

http://codereview.chromium.org/10830318/diff/6116/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:204: // name and index into
it each iteration.
On 2012/08/21 03:42:27, Ilya Sherman wrote:
> Is this performance optimization needed for the test to run smoothly?  If not,
> I'd prefer to test the actual code, so that there's no chance for a bug to get
> fixed there and not in the test.  If the optimization is necessary, though,
> well, so be it.

Unfortunately, yes it is needed. Without it, this test case takes 15s to run on
my machine. With the optimization, it runs in 0.5s.

(Note: That 15s on my beefy machine may very well mean a timeout on our much
slower bots.)

[Alexei Svitkine (slow), 2012-08-21 17:53:58]

I've updated the uniformity test to use the Chi-Square Goodness of Fit test,
which is able to determine (with a given confidence) whether the observed
values follow the uniform distribution. Please take another look.

[Alexei Svitkine (slow), 2012-08-21 19:47:48]

On 2012/08/21 17:53:58, Alexei Svitkine wrote:
> I've updated the uniformity test to use the Chi-Square Goodness of Fit test,
> which is able to determine (with a given confidence) whether the observed
> values follow the uniform distribution. Please take another look.

I've also verified using this same test that using SHA1 entropy provider with
the low entropy source fails the test (not consistently, but about 50% of the
time on my machine).

[Ilya Sherman, 2012-08-22 04:07:41]

LGTM, though I don't know enough of the statistics to know whether the
chi-squared test has all the desired properties.  (Based on the comments, it
looks like if the test fails, we would have a 99.9% [or higher] confidence that
the distribution is *not* uniform.  I would have expected the test to have the
property property that if the test succeeds, we would have a 99.9% [or higher]
confidence that the distribution *is* uniform.  Is that also guaranteed?]

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:163: const size_t
kCheckIterationCount = 10000;
Is it really important to check every 10000 iterations, or would checking just
once at the end be good enough?

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:178: for (size_t j = 0; j <
kMaxIterationCount; ++j) {
nit: Perhaps this loop should start from j = 1, so that you don't keep having to
use "j + 1" within the loop body?

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:199: // if the distribution
will converge, up to |kMaxIterationCount|.
Perhaps instead of running the test multiple times, we should choose a threshold
that has a higher confidence?  Or would that make the test too weak?

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:212: " after " <<
kMaxIterationCount << " iterations.";
This test should choose a random seed for the random number generator, and print
it out upon failure, so that failures are reproducible.

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:231: const double
kChiSquareThreshold = 43.82;
nit: Almost all of these constants are repeated from the above test.  Please
pull them out to be shared between the two tests.

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:281: }
nit: There is a lot of repeated code with the above test.  It would be nice to
refactor the code to be shared, to the extent that that's possible and not super
painful.

[Alexei Svitkine (slow), 2012-08-22 16:53:27]

Hi Ilya,

I've addressed your latest nits. See below for responses to your comments.

"Based on the comments, it looks like if the test fails, we would have a 99.9%
[or higher] confidence that the distribution is *not* uniform. I would have
expected the test to have the property property that if the test succeeds, we
would have a 99.9% [or higher] confidence that the distribution *is* uniform. 
Is that also guaranteed?"

First, I'd like to make sure we're all on the same page: the only thing we can
test is whether the observed values are consistent with those coming from a
uniform distribution. I don't think there's a way we can really ensure the
observed values are uniform themselves in a test that we expect to pass
consistently (while keeping them independent e.g. not basing them on previous
values - such as e.g. via the server making the dice rolls and knowing how many
clients it assigned to a given group, which is not how this works). So the only
reasonable test is whether the observed values are consistent with those that
are expected to come from a uniform distribution.

Ok now, that that's out of the way... I believe that concluding with 99.9%
confidence that a given set of observed samples does not follow a uniform
distribution is the same as concluding with a 99.9% confidence that the sets
where that conclusion wasn't reached are indeed samples from a uniform
distribution. So it seems to me that the two are equivalent given the above
definition. Does that make sense?

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:163: const size_t
kCheckIterationCount = 10000;
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> Is it really important to check every 10000 iterations, or would checking just
> once at the end be good enough?

The test verifies whether the observed distribution appears uniform with a 99.9%
confidence level. The idea of checking multiple times is to make sure we don't
run into the 0.1% case and cause flakiness 1 out of 1000 runs. As far as I
understand this, just checking once at the end will still have that problem.

Additionally, checking early makes it so the test has a much shorter run-time
the vast majority of times (i.e. can stop after 10k values instead of having to
do 100000), which is a Good Thing (cycle times and all).

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:178: for (size_t j = 0; j <
kMaxIterationCount; ++j) {
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> nit: Perhaps this loop should start from j = 1, so that you don't keep having
to
> use "j + 1" within the loop body?

Done.

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:199: // if the distribution
will converge, up to |kMaxIterationCount|.
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> Perhaps instead of running the test multiple times, we should choose a
threshold
> that has a higher confidence?  Or would that make the test too weak?

Using a threshold that has a higher confidence does make the test much weaker
(which is why I opted not to do that).

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:212: " after " <<
kMaxIterationCount << " iterations.";
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> This test should choose a random seed for the random number generator, and
print
> it out upon failure, so that failures are reproducible.

The random number generator used for the original entropy source is from
base/rand_util.cc and is not seeded. For example, on Posix systems, it comes
from reading /dev/urandom. 

So this is not possible.

(And it doesn't make sense to use a different random number generator here since
then we wouldn't be testing what the real code will be doing.)

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:231: const double
kChiSquareThreshold = 43.82;
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> nit: Almost all of these constants are repeated from the above test.  Please
> pull them out to be shared between the two tests.

Refactored the two tests to share a majority of their code (including these
constants).

https://chromiumcodereview.appspot.com/10830318/diff/9083/chrome/common/metri...
chrome/common/metrics/entropy_provider_unittest.cc:281: }
On 2012/08/22 04:07:42, Ilya Sherman wrote:
> nit: There is a lot of repeated code with the above test.  It would be nice to
> refactor the code to be shared, to the extent that that's possible and not
super
> painful.

Done.

[Ilya Sherman, 2012-08-22 22:20:02]

On 2012/08/22 16:53:27, Alexei Svitkine wrote:
> Ok now, that that's out of the way... I believe that concluding with 99.9%
> confidence that a given set of observed samples does not follow a uniform
> distribution is the same as concluding with a 99.9% confidence that the sets
> where that conclusion wasn't reached are indeed samples from a uniform
> distribution. So it seems to me that the two are equivalent given the above
> definition. Does that make sense?

Not quite.  You mentioned in response to one of my comments that increasing the
threshold to give a higher confidence makes the test weaker.  I think this means
that the two are not equivalent, and that we're not clear on what the confidence
is for this test that observed samples are following a uniform distribution. 
For an extreme example, suppose we set the threshold to some truly huge value,
such that very nearly all the samples would need to fall in the same bucket in
order to exceed it.  Then if the threshold is exceeded, we could say with
extremely high confidence that the samples are not following a uniform
distribution; but if the threshold is not exceeded, we don't have much
confidence that the samples *are* following a uniform distribution -- there
could be totally empty buckets without exceeding the threshold.

[Alexei Svitkine (slow), 2012-08-22 22:39:11]

On Wed, Aug 22, 2012 at 6:20 PM, <isherman@chromium.org> wrote:

> On 2012/08/22 16:53:27, Alexei Svitkine wrote:
>
>> Ok now, that that's out of the way... I believe that concluding with 99.9%
>> confidence that a given set of observed samples does not follow a uniform
>> distribution is the same as concluding with a 99.9% confidence that the
>> sets
>> where that conclusion wasn't reached are indeed samples from a uniform
>> distribution. So it seems to me that the two are equivalent given the
>> above
>> definition. Does that make sense?
>>
>
> Not quite.  You mentioned in response to one of my comments that
> increasing the
> threshold to give a higher confidence makes the test weaker.  I think this
> means
> that the two are not equivalent, and that we're not clear on what the
> confidence
> is for this test that observed samples are following a uniform
> distribution.


Hmm, you are indeed right - just re-reading my own quote makes this obvious
to me now - my bad.

I'm not sure what a better test would be.

I suppose we could lower the threshold to something lower than 99.9% such
that the test is less lenient towards non-uniform looking data, although
that still wouldn't provide the kind of guarantees you're looking for...

Of note though, having more samples appears to dramatically increase the
chi-square statistic value in the case of a non-uniform distribution - e.g.
running the test on the sha1 13-bit entropy method with more iterations
produces higher values of the chi-square statistic, making its
non-uniformity more apparent. The chi-square threshold level provides a
level of confidence of "at least" the amount corresponding to the
threshold. Greater values of the chi-square statistic mean even more
confidence that the distribution is non-uniform. Although it's not clear to
me right now how we can use that information to help devise a better test.

-Alexei

[jar (doing other things), 2012-08-23 01:38:29]

Please fix the one nit below....

and then LGTM.

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:48: };
I checked with BrettW, and WillChan (Google readability reviewers). Brett
indicated
"usually indent these things 4 spaces since it's a wrapped statement rather than
a block."

Will was airborne, and not sure, but thought the trailing curly could go on its
own line (but presumably indented 4 also?)

Other code in other files is probably not a good justification (though I do
readily admit it is reasonable... I just don't think it is Chrome style).

On 2012/08/20 15:57:40, Alexei Svitkine wrote:
> On 2012/08/17 19:06:19, jar wrote:
> > nit: This curly is not a block closure, and is more like a paren, which
should
> > appear at the end of line 48.
> 
> On 2012/08/17 19:06:19, jar wrote:
> > nit: This curly is not a block closure, and is more like a paren.  (the same
> > later in the file).
> 
> That suggestion doesn't seem consistent with the style used elsewhere in
> Chromium codebase where arrays are initialized like this.
> 
> For example, see some of the results of this code search:
> 
>
http://code.google.com/searchframe#search/&exact_package=chromium&q=test_case...
> 
> So I'm leaving it as is.

[Alexei Svitkine (slow), 2012-08-23 15:10:42]

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
File chrome/common/metrics/entropy_provider_unittest.cc (right):

http://codereview.chromium.org/10830318/diff/4096/chrome/common/metrics/entro...
chrome/common/metrics/entropy_provider_unittest.cc:48: };
On 2012/08/23 01:38:30, jar wrote:
> I checked with BrettW, and WillChan (Google readability reviewers). Brett
> indicated
> "usually indent these things 4 spaces since it's a wrapped statement rather
than
> a block."
> 
> Will was airborne, and not sure, but thought the trailing curly could go on
its
> own line (but presumably indented 4 also?)
> 
> Other code in other files is probably not a good justification (though I do
> readily admit it is reasonable... I just don't think it is Chrome style).

Done.

[Alexei Svitkine (slow), 2012-08-23 19:28:14]

Brett: Ping for OWNERS approval for chrome/ and content/ directories. Thanks!

[brettw, 2012-08-24 17:40:28]

owners lgtm

[Daniel Berlin, 2012-08-24 20:10:47]

lgtm

[commit-bot: I haz the power, 2012-08-24 20:12:27]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/asvitkine@chromium.org/10830318/18027

[commit-bot: I haz the power, 2012-08-24 22:33:04]

Change committed as 153322