Fix inconsistent FieldTrial group assignment due to float errors.

Fix inconsistent FieldTrial group assignment due to float errors.

This was discovered by the InstantExtended field trial that was
using very small group percentages and discovered several groups
of the same size were getting different user counts.

BUG=290438
TEST=New unit test that fails without the fix.

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

[Alexei Svitkine (slow), 2013-09-13 22:02:49]

Note: The reason this actually cares about the boundary cases is because in the
case of non-UMA users, we use the PermutedEntropyProvider which provides entropy
values by dividing a number in the range of [0,7999] by 8000, so these boundary
occur pretty often.

[Alexei Svitkine (slow), 2013-09-16 21:48:37]

jar: Ping - I'd like to get this in for M31.

[jar (doing other things), 2013-09-16 21:54:40]

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial....
base/metrics/field_trial.cc:47: // points to int. Without it, boundary values
have inconsistent results, e.g.:
Isn't what you really want is rounding, rather than raw truncation?  Is adding
0.5 and then truncating the right answer to get this?

[Alexei Svitkine (slow), 2013-09-16 22:30:46]

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial....
base/metrics/field_trial.cc:47: // points to int. Without it, boundary values
have inconsistent results, e.g.:
On 2013/09/16 21:54:40, jar wrote:
> Isn't what you really want is rounding, rather than raw truncation?  Is adding
> 0.5 and then truncating the right answer to get this?

I don't think so, let me see if you agree. Here's the counterexample I'm
thinking of:

Suppose you have a FieldTrial with 3 groups, each 1/3 probability. (i.e. total
is 3, each group's probability is 1).

Then, let's take an entropy_value of 0.58. Since it is below 0.666..., it should
logically be in the 2nd group.

However, if we do rounding, the result is that its in the 3rd group because:

First, divisor is 3 so 0.58 * divisor = 1.74. If we add 0.5 and truncate then
random_ becomes 2.

When the first AppendGroup(1) call is done, accumulated_group_probability_
becomes 1 and accumulated_group_probability_ > random_ is false (1 > 2).

Then, the second AppendGroup(1) call is done, accumulated_group_probability_
becomes 2 and accumulated_group_probability_ > random_ is still false (2 > 2).

So the 3rd group is selected (either its the default group or another
AppendGroup(1) call happens).

This is incorrect, since 0.58 should yield the 2nd group, not the third group -
i.e it's in the range (0.33,0.66).

Thus, rounding is incorrect. Do you agree?

[Alexei Svitkine (slow), 2013-09-17 21:01:08]

Friendly ping. If it would help, I'm in MTV this week, so we could discuss this
(and the other CL) in person, if you prefer.

[jar (doing other things), 2013-09-18 01:38:24]

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial....
base/metrics/field_trial.cc:47: // points to int. Without it, boundary values
have inconsistent results, e.g.:
On 2013/09/16 22:30:46, Alexei Svitkine wrote:
> Thus, rounding is incorrect. Do you agree?

I think rounding is incorrect (I should have looked at the context more
closely)... but I think adding an epsilon is also incorrect.  I didn't even look
back to how you were doing this calculation, but just knew that attempts to add
"epsilon" are almost always problematic.

In this case, the entropy is in a half-open interval from [0, 1).  When you add
epsilon, you may go beyond 1, and that seems like a bad thing.  In particular,
it can, when multiplied by the divisor, produce a quantity that truncates to the
complete value of the divisor (rather than giving only values 0 ... divisor-1).

The samples you gave in the comment presumed that the entropy was "trying" to be
a floating point representation of a two decimal quantity (e.g., 0.56 vs 0.57,
vs 0.58).  I don't think the entropy arrives with such coarse granularity, and
hence the epsilon addition seems unwarranted.  

As a specific example, suppose that the divisor was 2.  When we multiply by the
entropy, we get a number in the range [0,2).  When we truncate that value, we
get either a 0, or a 1, with equal probability.  If we had add an epsilon, we'd
also have a shot at getting a 2 after truncation. :-/

That epsilon commonly gets some probability tossed into the "all remaining"
probability bucket.  Maybe it is small... but I don't think it is valuable. 
Also, if the caller tries to explicitly list the different items that sum to the
divisor, there will still be some probability left over... and I'm not sure how
users of field trials would respond to that.

Can you better clarify the problem you're addressing, as I'm not seeing it.

[Alexei Svitkine (slow), 2013-09-18 16:39:53]

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial.cc
File base/metrics/field_trial.cc (right):

https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial....
base/metrics/field_trial.cc:47: // points to int. Without it, boundary values
have inconsistent results, e.g.:
> In this case, the entropy is in a half-open interval from [0, 1).  When you
add
> epsilon, you may go beyond 1, and that seems like a bad thing.  In particular,
> it can, when multiplied by the divisor, produce a quantity that truncates to
the
> complete value of the divisor (rather than giving only values 0 ...
divisor-1).

I agree that this is a potential issue. I think it can be addressed by doing:

  result = max(result, divisor - 1);

Other than that case, I can't think of any other issues and the above change
should handle that case without any ill-effects, I believe.

> 
> The samples you gave in the comment presumed that the entropy was "trying" to
be
> a floating point representation of a two decimal quantity (e.g., 0.56 vs 0.57,
> vs 0.58).  I don't think the entropy arrives with such coarse granularity, and
> hence the epsilon addition seems unwarranted.  

For users who are not opted-in to UMA, we use the PermutedEntropyProvider which
does result in values with this coarse granularity.

How it works is that it maps the client's low entropy source value [0, 7999], to
another value [0, 7999] and then generates the entropy value as a result of
dividing that by 8000.0

So for example, for a value 4480 (in the range [0, 7999]), this results in 0.56
(via 4480 / 8000).

This is a real issue that affected 1% groups in the InstantExtended field trial,
resulting in some 1% groups getting more users than others. If you're curious,
here's the internal discussion about it:

http://b/10699562

Hopefully, that will clarify the context / reason for this change.

In the meanwhile, I'll update the CL to add max(divisor-1) and a test for that
scenario.

[Alexei Svitkine (slow), 2013-09-18 16:53:32]

On 2013/09/18 16:39:53, Alexei Svitkine wrote:
>
https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial.cc
> File base/metrics/field_trial.cc (right):
> 
>
https://codereview.chromium.org/23710041/diff/30001/base/metrics/field_trial....
> base/metrics/field_trial.cc:47: // points to int. Without it, boundary values
> have inconsistent results, e.g.:
> > In this case, the entropy is in a half-open interval from [0, 1).  When you
> add
> > epsilon, you may go beyond 1, and that seems like a bad thing.  In
particular,
> > it can, when multiplied by the divisor, produce a quantity that truncates to
> the
> > complete value of the divisor (rather than giving only values 0 ...
> divisor-1).
> 
> I agree that this is a potential issue. I think it can be addressed by doing:
> 
>   result = max(result, divisor - 1);

(Above, I meant min() instead of max()).

[Alexei Svitkine (slow), 2013-09-18 16:54:40]

.

[Alexei Svitkine (slow), 2013-09-18 18:06:26]

I updated the CL with the fix for the issue, please take have another look - and
see my explanation in comment 8 for the motivation for this change. Thanks!

[jar (doing other things), 2013-09-18 21:45:22]

Ugh.... so the real problem tends to relate to using an 8000 sided die for
randomization.... and hence you can only get even percentages if you are a
divisor of 8000.  Anything else is problematic... even without the floating
point problem(s).

I'm OK with the epsilon, along with the min().

It sure seems like we should require a divisor selected that divides 8000. 
Perhaps this should even become a DCHECK.


LGTM

[Alexei Svitkine (slow), 2013-09-18 21:49:23]

Thanks Jim.

We actually have such a check on the server-side, for experiment configs that
are visible to GWS (i.e. for ones where we actually look at (server) metrics
from users that use the PermutedEntropyProvider).

(That check isn't enough to fix the floating problem this is fixing, just to be
clear.)

[commit-bot: I haz the power, 2013-09-18 21:52:43]

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

[commit-bot: I haz the power, 2013-09-19 01:11:18]

Change committed as 224011