Fix base::RandGenerator bug (it had non-uniform random distribution).

base/rand_util_unittest.cc

Index: base/rand_util_unittest.cc
diff --git a/base/rand_util_unittest.cc b/base/rand_util_unittest.cc
index d7fa37af827e8589299c4a066ef83308ca4a384a..98b64d08101ffd5500cb31a5ddbec924c8f0e4a8 100644
--- a/base/rand_util_unittest.cc
+++ b/base/rand_util_unittest.cc
@@ -61,3 +61,47 @@ TEST(RandUtilTest, RandGeneratorForRandomShuffle) {
   EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(),
             std::numeric_limits<int64>::max());
 }
+
+TEST(RandUtilTest, RandGeneratorIsUniform) {

[brettw, 2011/05/27 18:13:21]

I'm not super excited about this test. It seems by definition flaky. You've
tried to make it less flaky by running it a million times. How long does this
take?

[Paweł Hajdan Jr., 2011/05/27 19:28:11]

Right, everything based on randomness is quite hard to test. I think it's
important to keep this test fast, ideally no longer than few seconds, or even
less.

I wonder if it would be useful to do slightly different - rather than calling
RandGenerator many times, feed it different values of |max| and
|base::RandUint64()|, and see how it behaves. That should be deterministic, and
still test the right thing...

[Jói, 2011/05/27 19:41:48]

That wouldn't verify that the random distribution is uniform. Asserting that it
converges to close to the expected average value is the only good way to do that
AFAIK.

+  // Verify that RandGenerator has a uniform distribution. This is a
+  // regression test that consistently failed when RandGenerator was
+  // implemented this way:
+  //
+  //   return base::RandUint64() % max;
+  //
+  // The worst case for such an implementation is e.g. a top of range
+  // that is 2/3rds of the way to MAX_UINT64, in which case the bottom
+  // half of the range would be twice as likely to occur as the top
+  // half, assuming a naive modulus implementation of RandGenerator.
+  const uint64 kTopOfRange = (std::numeric_limits<uint64>::max() / 3L) * 2L;
+  const uint64 kExpectedAverage = kTopOfRange / 2L;
+  const uint64 kAllowedVariance = kExpectedAverage / 100L;  // 1% either way.

[Paweł Hajdan Jr., 2011/05/27 19:28:11]

nit: 1% seems quite strict, how about something more like 5% ?

Initially rand_util was not intended for anything other than test code iirc, and
it has no guarantees about strength or quality anyway.

[Jói, 2011/05/27 19:41:48]

The test already passes in an average of 14 ms wall-clock time on a somewhat
slow machine, and in about 12 thousand test runs I've never seen it need more
than 50K iterations (which takes a couple of hundred milliseconds or so on a
reasonable machine) to converge.  I've changed it to +/- 2% though, as the
failure mode that existed before was much more skewed than that, but I'd prefer
not to make the interval even wider in case future failure modes are more
subtle.

+  const int kMaxAttempts = 1000000;
+  const int kReportEveryNAttempts = 10000;
+
+  double cumulative_average = 0.0;
+  int count = 0;
+  while (count < kMaxAttempts) {

[Paweł Hajdan Jr., 2011/05/27 19:28:11]

nit: Why not a for loop then?

[Jói, 2011/05/27 19:41:48]

Because I want to test the value of count after the loop.

+    uint64 value = base::RandGenerator(kTopOfRange);
+    cumulative_average = (count * cumulative_average + value) / (count + 1);
+
+    // Don't quit too quickly for things to start converging.
+    if (count > 1000) {

[Ilya Sherman, 2011/05/27 19:23:26]

nit: As long as you're making everything else a named constant, let's make 1000
a named constant too.

[Jói, 2011/05/27 19:41:48]

Done.

+      if (kExpectedAverage - kAllowedVariance < cumulative_average &&
+          cumulative_average < kExpectedAverage + kAllowedVariance) {
+        break;
+      }
+    }
+
+    if (count >= kReportEveryNAttempts && count % kReportEveryNAttempts == 0) {

[brettw, 2011/05/27 18:22:20]

I don't think tests should be printing stuff out. This typically just confuses
people when they see it in the logs.

[Ilya Sherman, 2011/05/27 19:23:26]

Yes, please remove these printf()'s, or find a way to log them only on failure.

[Paweł Hajdan Jr., 2011/05/27 19:28:11]

Yeah, and also it's better to use LOG or gtest macros instead of printf.

[Jói, 2011/05/27 19:41:48]

Done.

[Jói, 2011/05/27 19:41:48]

Done.

[Jói, 2011/05/27 19:41:48]

Done.

+      if (count == kReportEveryNAttempts)
+        printf("Expected average is %ld\n", kExpectedAverage);
+      printf("Cumulative average hasn't converged, is %.0f after %d samples.\n",
+             cumulative_average, count);
+    }
+
+    ++count;
+  }
+
+  ASSERT_LT(count, kMaxAttempts);
+}