summaryrefslogtreecommitdiffstats
path: root/mfbt/tests/TestFastBernoulliTrial.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'mfbt/tests/TestFastBernoulliTrial.cpp')
-rw-r--r--mfbt/tests/TestFastBernoulliTrial.cpp209
1 files changed, 209 insertions, 0 deletions
diff --git a/mfbt/tests/TestFastBernoulliTrial.cpp b/mfbt/tests/TestFastBernoulliTrial.cpp
new file mode 100644
index 000000000..62d4b51a7
--- /dev/null
+++ b/mfbt/tests/TestFastBernoulliTrial.cpp
@@ -0,0 +1,209 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Assertions.h"
+#include "mozilla/FastBernoulliTrial.h"
+
+#include <math.h>
+
+// Note that because we always provide FastBernoulliTrial with a fixed
+// pseudorandom seed in these tests, the results here are completely
+// deterministic.
+//
+// A non-optimized version of this test runs in .009s on my laptop. Using larger
+// sample sizes lets us meet tighter bounds on the counts.
+
+static void
+TestProportions()
+{
+ mozilla::FastBernoulliTrial bernoulli(1.0,
+ 698079309544035222ULL,
+ 6012389156611637584ULL);
+
+ for (size_t i = 0; i < 100; i++)
+ MOZ_RELEASE_ASSERT(bernoulli.trial());
+
+ {
+ bernoulli.setProbability(0.5);
+ size_t count = 0;
+ for (size_t i = 0; i < 1000; i++)
+ count += bernoulli.trial();
+ MOZ_RELEASE_ASSERT(count == 496);
+ }
+
+ {
+ bernoulli.setProbability(0.001);
+ size_t count = 0;
+ for (size_t i = 0; i < 1000; i++)
+ count += bernoulli.trial();
+ MOZ_RELEASE_ASSERT(count == 2);
+ }
+
+ {
+ bernoulli.setProbability(0.85);
+ size_t count = 0;
+ for (size_t i = 0; i < 1000; i++)
+ count += bernoulli.trial();
+ MOZ_RELEASE_ASSERT(count == 852);
+ }
+
+ bernoulli.setProbability(0.0);
+ for (size_t i = 0; i < 100; i++)
+ MOZ_RELEASE_ASSERT(!bernoulli.trial());
+}
+
+static void
+TestHarmonics()
+{
+ mozilla::FastBernoulliTrial bernoulli(0.1,
+ 698079309544035222ULL,
+ 6012389156611637584ULL);
+
+ const size_t n = 100000;
+ bool trials[n];
+ for (size_t i = 0; i < n; i++)
+ trials[i] = bernoulli.trial();
+
+ // For each harmonic and phase, check that the proportion sampled is
+ // within acceptable bounds.
+ for (size_t harmonic = 1; harmonic < 20; harmonic++) {
+ size_t expected = n / harmonic / 10;
+ size_t low_expected = expected * 85 / 100;
+ size_t high_expected = expected * 115 / 100;
+
+ for (size_t phase = 0; phase < harmonic; phase++) {
+ size_t count = 0;
+ for (size_t i = phase; i < n; i += harmonic)
+ count += trials[i];
+
+ MOZ_RELEASE_ASSERT(low_expected <= count && count <= high_expected);
+ }
+ }
+}
+
+static void
+TestTrialN()
+{
+ mozilla::FastBernoulliTrial bernoulli(0.01,
+ 0x67ff17e25d855942ULL,
+ 0x74f298193fe1c5b1ULL);
+
+ {
+ size_t count = 0;
+ for (size_t i = 0; i < 10000; i++)
+ count += bernoulli.trial(1);
+
+ // Expected value: 0.01 * 10000 == 100
+ MOZ_RELEASE_ASSERT(count == 97);
+ }
+
+ {
+ size_t count = 0;
+ for (size_t i = 0; i < 10000; i++)
+ count += bernoulli.trial(3);
+
+ // Expected value: (1 - (1 - 0.01) ** 3) == 0.0297,
+ // 0.0297 * 10000 == 297
+ MOZ_RELEASE_ASSERT(count == 304);
+ }
+
+ {
+ size_t count = 0;
+ for (size_t i = 0; i < 10000; i++)
+ count += bernoulli.trial(10);
+
+ // Expected value: (1 - (1 - 0.01) ** 10) == 0.0956,
+ // 0.0956 * 10000 == 956
+ MOZ_RELEASE_ASSERT(count == 936);
+ }
+
+ {
+ size_t count = 0;
+ for (size_t i = 0; i < 10000; i++)
+ count += bernoulli.trial(100);
+
+ // Expected value: (1 - (1 - 0.01) ** 100) == 0.6339
+ // 0.6339 * 10000 == 6339
+ MOZ_RELEASE_ASSERT(count == 6372);
+ }
+
+ {
+ size_t count = 0;
+ for (size_t i = 0; i < 10000; i++)
+ count += bernoulli.trial(1000);
+
+ // Expected value: (1 - (1 - 0.01) ** 1000) == 0.9999
+ // 0.9999 * 10000 == 9999
+ MOZ_RELEASE_ASSERT(count == 9998);
+ }
+}
+
+static void
+TestChangeProbability()
+{
+ mozilla::FastBernoulliTrial bernoulli(1.0,
+ 0x67ff17e25d855942ULL,
+ 0x74f298193fe1c5b1ULL);
+
+ // Establish a very high skip count.
+ bernoulli.setProbability(0.0);
+
+ // This should re-establish a zero skip count.
+ bernoulli.setProbability(1.0);
+
+ // So this should return true.
+ MOZ_RELEASE_ASSERT(bernoulli.trial());
+}
+
+static void
+TestCuspProbabilities()
+{
+ /*
+ * FastBernoulliTrial takes care to avoid screwing up on edge cases. The
+ * checks here all look pretty dumb, but they exercise paths in the code that
+ * could exhibit undefined behavior if coded naïvely.
+ */
+
+ /*
+ * This should not be perceptibly different from 1; for 64-bit doubles, this
+ * is a one in ten trillion chance of the trial not succeeding. Overflows
+ * converting doubles to size_t skip counts may change this, though.
+ */
+ mozilla::FastBernoulliTrial bernoulli(nextafter(1, 0),
+ 0x67ff17e25d855942ULL,
+ 0x74f298193fe1c5b1ULL);
+
+ for (size_t i = 0; i < 1000; i++)
+ MOZ_RELEASE_ASSERT(bernoulli.trial());
+
+ /*
+ * This should not be perceptibly different from 0; for 64-bit doubles,
+ * the FastBernoulliTrial will actually treat this as exactly zero.
+ */
+ bernoulli.setProbability(nextafter(0, 1));
+ for (size_t i = 0; i < 1000; i++)
+ MOZ_RELEASE_ASSERT(!bernoulli.trial());
+
+ /*
+ * This should be a vanishingly low probability which FastBernoulliTrial does
+ * *not* treat as exactly zero.
+ */
+ bernoulli.setProbability(1 - nextafter(1, 0));
+ for (size_t i = 0; i < 1000; i++)
+ MOZ_RELEASE_ASSERT(!bernoulli.trial());
+}
+
+int
+main()
+{
+ TestProportions();
+ TestHarmonics();
+ TestTrialN();
+ TestChangeProbability();
+ TestCuspProbabilities();
+
+ return 0;
+}