From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- mfbt/tests/TestFastBernoulliTrial.cpp | 177 ++++++++++++++++++++++++++++++++++ 1 file changed, 177 insertions(+) create mode 100644 mfbt/tests/TestFastBernoulliTrial.cpp (limited to 'mfbt/tests/TestFastBernoulliTrial.cpp') diff --git a/mfbt/tests/TestFastBernoulliTrial.cpp b/mfbt/tests/TestFastBernoulliTrial.cpp new file mode 100644 index 0000000000..f85d33b2db --- /dev/null +++ b/mfbt/tests/TestFastBernoulliTrial.cpp @@ -0,0 +1,177 @@ +/* -*- 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 + +// 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; +} -- cgit v1.2.3