Fix inconsistent FieldTrial group assignment due to float errors.

base/metrics/field_trial.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/metrics/field_trial.h"
 
 #include "base/build_time.h"
 #include "base/logging.h"
 #include "base/rand_util.h"
 #include "base/sha1.h"
@@ skipping 20 matching lines @@
   exploded.day_of_week = 0;  // Should be unused.
   exploded.day_of_month = day_of_month;
   exploded.hour = 0;
   exploded.minute = 0;
   exploded.second = 0;
   exploded.millisecond = 0;
 
   return Time::FromLocalExploded(exploded);
 }
 
+// Returns the boundary value for comparing against the FieldTrial's added
+// groups for a given |divisor| (total probability) and |entropy_value|.
+FieldTrial::Probability GetGroupBoundaryValue(
+    FieldTrial::Probability divisor,
+    double entropy_value) {
+  // Add a tiny epsilon value to get consistent results when converting floating
+  // points to int. Without it, boundary values have inconsistent results, e.g.:

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

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]

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?

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

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]

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.
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.

+  //
+  //   static_cast<FieldTrial::Probability>(100 * 0.56) == 56
+  //   static_cast<FieldTrial::Probability>(100 * 0.57) == 56
+  //   static_cast<FieldTrial::Probability>(100 * 0.58) == 57
+  //   static_cast<FieldTrial::Probability>(100 * 0.59) == 59
+  const double kEpsilon = 1e-8;
+  return static_cast<FieldTrial::Probability>(divisor * entropy_value +
+                                              kEpsilon);
+}
+
 }  // namespace
 
-static const char kHistogramFieldTrialSeparator('_');
-
 // statics
 const int FieldTrial::kNotFinalized = -1;
 const int FieldTrial::kDefaultGroupNumber = 0;
 bool FieldTrial::enable_benchmarking_ = false;
 
 const char FieldTrialList::kPersistentStringSeparator('/');
 int FieldTrialList::kNoExpirationYear = 0;
 
 //------------------------------------------------------------------------------
 // FieldTrial methods and members.
 
 FieldTrial::FieldTrial(const std::string& trial_name,
                        const Probability total_probability,
                        const std::string& default_group_name,
                        double entropy_value)
     : trial_name_(trial_name),
       divisor_(total_probability),
       default_group_name_(default_group_name),
-      random_(static_cast<Probability>(divisor_ * entropy_value)),
+      random_(GetGroupBoundaryValue(total_probability, entropy_value)),
       accumulated_group_probability_(0),
       next_group_number_(kDefaultGroupNumber + 1),
       group_(kNotFinalized),
       enable_field_trial_(true),
       forced_(false),
       group_reported_(false) {
   DCHECK_GT(total_probability, 0);
   DCHECK(!trial_name_.empty());
   DCHECK(!default_group_name_.empty());
 }
@@ skipping 414 matching lines @@
     used_without_global_ = true;
     return;
   }
   AutoLock auto_lock(global_->lock_);
   DCHECK(!global_->PreLockedFind(trial->trial_name()));
   trial->AddRef();
   global_->registered_[trial->trial_name()] = trial;
 }
 
 }  // namespace base