Replace stateful rounding bias in ExponentialBiased with `mean + 0.5` floor scaling. `ExponentialBiased::GetSkipCount(mean)` previously compensated for the `-0.5` truncation offset of `floor(-ln(u) * mean)` by rounding to the nearest integer (`std::rint`) and carrying a cumulative rounding-error term (`bias_`): - Nearest-integer rounding gives `0` (`GetStride(period) == 1`) a half-width bin `[0, 0.5)` while every `k >= 1` has width `1.0`, halving `P(GetSkipCount(m) == 0)` to `1 / (2*m + 2/3) ~= 0.5 / (m + 1)`. This under-samples the first event on every new thread by ~2x, introduces a ~2x post-sample refractory dip, and negatively correlates consecutive draws via `bias_`. - Using only 26 PRNG bits with `+ 1.0` also floored `P(GetSkipCount(m) == 0)` at `2^-26` for `m >> 2^26` and capped strides at `~18 * period`. Pre-adding `+0.5` to `mean` before truncating (`floor(-ln(u) * (mean + 0.5))`, using all 48 PRNG bits mapped to bin midpoints `(rng_ + 0.5) * 2^-48`) cancels `floor`'s `-0.5` fractional offset in expectation on every draw (`E[stride] = period + 1 / (12 * period) + O(period^-3)`) while producing an exact memoryless geometric distribution with full-width bins from `0` upward, lower ALU/FP cost (no `std::rint` or `bias_` load/store), and smaller TLS state (`16` B instead of `24` B). Also replace the assertion-less `printf` demo tests with non-flaky distribution shape, mean, first-draw, and lag-1 independence tests. PiperOrigin-RevId: 1020795145
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc index 8682ca1..6f5125b 100644 --- a/absl/profiling/internal/exponential_biased.cc +++ b/absl/profiling/internal/exponential_biased.cc
@@ -16,10 +16,8 @@ #include <stdint.h> -#include <algorithm> #include <atomic> #include <cmath> -#include <limits> #include "absl/base/attributes.h" #include "absl/base/config.h" @@ -29,48 +27,42 @@ ABSL_NAMESPACE_BEGIN namespace profiling_internal { -// The algorithm generates a random number between 0 and 1 and applies the -// inverse cumulative distribution function for an exponential. Specifically: -// Let m be the inverse of the sample period, then the probability -// distribution function is m*exp(-mx) so the CDF is -// p = 1 - exp(-mx), so -// q = 1 - p = exp(-mx) -// log_e(q) = -mx -// -log_e(q)/m = x -// log_2(q) * (-log_e(2) * 1/m) = x -// In the code, q is actually in the range 1 to 2**26, hence the -26 below +// Generates a memoryless geometric skip count on {0, 1, 2, ...} by applying +// `floor(-ln(u) * (mean + 0.5))` to a uniform variate `u` in `(0, 1)`. The +// `+0.5` scale shift cancels the `-0.5` average fractional part discarded by +// `floor` (`E[skip] = mean + 1 / (12 * (mean + 0.5)) + O(mean^-3)`). int64_t ExponentialBiased::GetSkipCount(int64_t mean) { + if (ABSL_PREDICT_FALSE(mean <= 0)) { + return 0; + } if (ABSL_PREDICT_FALSE(!initialized_)) { Initialize(); } - uint64_t rng = NextRandom(rng_); - rng_ = rng; + rng_ = NextRandom(rng_); - // Take the top 26 bits as the random number - // (This plus the 1<<58 sampling bound give a max possible step of - // 5194297183973780480 bytes.) - // The uint32_t cast is to prevent a (hard-to-reproduce) NAN - // under piii debug for some binaries. - double q = static_cast<uint32_t>(rng >> (kPrngNumBits - 26)) + 1.0; - // Put the computed p-value through the CDF of a geometric. - double interval = bias_ + (std::log2(q) - 26) * (-std::log(2.0) * mean); - // Very large values of interval overflow int64_t. To avoid that, we will - // cheat and clamp any huge values to (int64_t max)/2. This is a potential - // source of bias, but the mean would need to be such a large value that it's - // not likely to come up. For example, with a mean of 1e18, the probability of - // hitting this condition is about 1/1000. For a mean of 1e17, standard - // calculators claim that this event won't happen. - if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) { - // Assume huge values are bias neutral, retain bias for next call. - return std::numeric_limits<int64_t>::max() / 2; + // Map the 48-bit PRNG output to the midpoint of its uniform bin in (0, 1). + // Every midpoint `(rng_ + 0.5) * 2^-48` has at most 49 significand bits and + // is therefore represented without rounding in IEEE-754 `double`. + constexpr double kInvPrngMod = + 1.0 / static_cast<double>(uint64_t{1} << kPrngNumBits); + const double u = (static_cast<double>(rng_) + 0.5) * kInvPrngMod; + const double interval = -std::log(u) * (static_cast<double>(mean) + 0.5); + + // Clamp extreme values so casting `interval` to `int64_t` (and adding 1 in + // `GetStride()`) cannot overflow. `1 << 62` is an exact power of two in + // IEEE-754 `double`. + constexpr int64_t kMaxSkip = int64_t{1} << 62; + if (ABSL_PREDICT_FALSE(interval >= static_cast<double>(kMaxSkip))) { + return kMaxSkip; } - double value = std::rint(interval); - bias_ = interval - value; - return static_cast<int64_t>(value); + return static_cast<int64_t>(interval); } int64_t ExponentialBiased::GetStride(int64_t mean) { + if (ABSL_PREDICT_FALSE(mean <= 1)) { + return 1; + } return GetSkipCount(mean - 1) + 1; }
diff --git a/absl/profiling/internal/exponential_biased.h b/absl/profiling/internal/exponential_biased.h index d31f778..8823598 100644 --- a/absl/profiling/internal/exponential_biased.h +++ b/absl/profiling/internal/exponential_biased.h
@@ -25,13 +25,14 @@ namespace profiling_internal { // ExponentialBiased provides a small and fast random number generator for a -// rounded exponential distribution. This generator manages very little state, -// and imposes no synchronization overhead. This makes it useful in specialized -// scenarios requiring minimum overhead, such as stride based periodic sampling. +// memoryless geometric distribution (the discrete analog of an exponential +// distribution). This generator manages very little state, and imposes no +// synchronization overhead. This makes it useful in specialized scenarios +// requiring minimum overhead, such as stride-based periodic sampling. // // ExponentialBiased provides two closely related functions, GetSkipCount() and -// GetStride(), both returning a rounded integer defining a number of events -// required before some event with a given mean probability occurs. +// GetStride(), returning the number of events to skip (`>= 0`) or the number +// of events required (`>= 1`) before an event with a given mean occurs. // // The distribution is useful to generate a random wait time or some periodic // event with a given mean probability. For example, if an action is supposed to @@ -44,32 +45,13 @@ // } // // void Frobber::Frob(int arg) { -// if (--stride == 0) { +// if (--stride_ == 0) { // SampleFrob(arg); // stride_ = exponential_biased_.GetStride(1000); // } // ... // } // -// The rounding of the return value creates a bias, especially for smaller means -// where the distribution of the fraction is not evenly distributed. We correct -// this bias by tracking the fraction we rounded up or down on each iteration, -// effectively tracking the distance between the cumulative value, and the -// rounded cumulative value. For example, given a mean of 2: -// -// raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923 -// raw = 0.14624, cumulative = 1.77701, rounded = 2, bias = 0.14624 -// raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805 -// raw = 0.24206, cumulative = 6.95101, rounded = 7, bias = 0.24206 -// etc... -// -// Adjusting with rounding bias is relatively trivial: -// -// double value = bias_ + exponential_distribution(mean)(); -// double rounded_value = std::rint(value); -// bias_ = value - rounded_value; -// return rounded_value; -// // This class is thread-compatible. class ExponentialBiased { public: @@ -107,7 +89,6 @@ void Initialize(); uint64_t rng_{0}; - double bias_{0}; bool initialized_{false}; };
diff --git a/absl/profiling/internal/exponential_biased_test.cc b/absl/profiling/internal/exponential_biased_test.cc index 3471b07..1961b3f 100644 --- a/absl/profiling/internal/exponential_biased_test.cc +++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -14,20 +14,12 @@ #include "absl/profiling/internal/exponential_biased.h" -#include <stddef.h> - -#include <algorithm> -#include <cmath> #include <cstdint> -#include <cstdio> -#include <string> -#include <vector> #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/strings/str_cat.h" using ::testing::Ge; @@ -36,197 +28,104 @@ namespace profiling_internal { namespace { -MATCHER_P2(IsBetween, a, b, - absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a, - " and ", b)) { - return a <= arg && arg <= b; -} - -// Tests of the quality of the random numbers generated -// This uses the Anderson Darling test for uniformity. -// See "Evaluating the Anderson-Darling Distribution" by Marsaglia -// for details. - -// Short cut version of ADinf(z), z>0 (from Marsaglia) -// This returns the p-value for Anderson Darling statistic in -// the limit as n-> infinity. For finite n, apply the error fix below. -double AndersonDarlingInf(double z) { - if (z < 2) { - return exp(-1.2337141 / z) / sqrt(z) * - (2.00012 + - (0.247105 - - (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) * - z) * - z); - } - return exp( - -exp(1.0776 - - (2.30695 - - (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) * - z)); -} - -// Corrects the approximation error in AndersonDarlingInf for small values of n -// Add this to AndersonDarlingInf to get a better approximation -// (from Marsaglia) -double AndersonDarlingErrFix(int n, double x) { - if (x > 0.8) { - return (-130.2137 + - (745.2337 - - (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) * - x) / - n; - } - double cutoff = 0.01265 + 0.1757 / n; - if (x < cutoff) { - double t = x / cutoff; - t = sqrt(t) * (1 - t) * (49 * t - 102); - return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n; - } else { - double t = (x - cutoff) / (0.8 - cutoff); - t = -0.00022633 + - (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) * - t; - return t * (0.04213 + 0.01365 / n) / n; - } -} - -// Returns the AndersonDarling p-value given n and the value of the statistic -double AndersonDarlingPValue(int n, double z) { - double ad = AndersonDarlingInf(z); - double errfix = AndersonDarlingErrFix(n, ad); - return ad + errfix; -} - -double AndersonDarlingStatistic(const std::vector<double>& random_sample) { - size_t n = random_sample.size(); - double ad_sum = 0; - for (size_t i = 0; i < n; i++) { - ad_sum += (2 * i + 1) * - std::log(random_sample[i] * (1 - random_sample[n - 1 - i])); - } - const auto n_as_double = static_cast<double>(n); - double ad_statistic = -n_as_double - 1 / n_as_double * ad_sum; - return ad_statistic; -} - -// Tests if the array of doubles is uniformly distributed. -// Returns the p-value of the Anderson Darling Statistic -// for the given set of sorted random doubles -// See "Evaluating the Anderson-Darling Distribution" by -// Marsaglia and Marsaglia for details. -double AndersonDarlingTest(const std::vector<double>& random_sample) { - double ad_statistic = AndersonDarlingStatistic(random_sample); - double p = AndersonDarlingPValue(static_cast<int>(random_sample.size()), - ad_statistic); - return p; -} - -TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) { +// Non-positive arguments must return the minimum valid skip (0) or stride (1), +// and extreme arguments must clamp without signed integer overflow. +TEST(ExponentialBiasedTest, NonPositiveParametersAndClamp) { ExponentialBiased eb; - for (int runs = 0; runs < 10; ++runs) { - for (int64_t flips = eb.GetSkipCount(1); flips > 0; --flips) { - printf("head..."); - } - printf("tail\n"); - } - int heads = 0; - for (int i = 0; i < 10000000; i += 1 + eb.GetSkipCount(1)) { - ++heads; - } - printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000); + EXPECT_EQ(eb.GetSkipCount(0), 0); + EXPECT_EQ(eb.GetSkipCount(-5), 0); + EXPECT_EQ(eb.GetStride(1), 1); + EXPECT_EQ(eb.GetStride(0), 1); + EXPECT_EQ(eb.GetStride(-5), 1); + EXPECT_GE(eb.GetStride(int64_t{1} << 62), 1); } -// In simplified idealized world, `GetSkipCount(m) == 0` translates to -// `-log(X) * m + B <= 1/2`, where X is a uniform random number in (0, 1], -// and B is uniform random number in [-0.5, 0.5). Let U = 0.5 - B, that makes -// U a uniform random number in (0, 1]. After exponentiation we get -// `X >= exp(-U / m)`. Probability of this is `1 - exp(-U / m)`, so we have to -// integrate for all possible values of U: `1 - m * (1 - exp(-1 / m))`. For -// simplicity take just two terms of Taylor series expansion: -// `1/(2*m) - 1/(6*m^2)`. Reciprocal of that is `2*m + 2/3 + O(1/m)`. If we use -// more math tricks we can get "exact" approximation, but result will still be -// `2*m + 2/3 + O(1/m)`. -TEST(ExponentialBiasedTest, OnePerNDemoWithGetSkipCount) { +// Empirical mean skip count must match the requested mean across scales. +TEST(ExponentialBiasedTest, MeanMatchesRequestedValue) { ExponentialBiased eb; - int n = 22; - int rounds = 220000; - int hits = 0; - for (int i = 0; i < rounds; i++) { - if (eb.GetSkipCount(n / 2) == 0) ++hits; + constexpr int kDraws = 100000; + for (int64_t mean : + {int64_t{10}, int64_t{100}, int64_t{1000}, int64_t{1} << 20}) { + double sum = 0; + for (int i = 0; i < kDraws; ++i) { + sum += static_cast<double>(eb.GetSkipCount(mean)); + } + EXPECT_NEAR(sum / kDraws, static_cast<double>(mean), 0.05 * mean); } - double inverse_hit_rate = rounds / static_cast<double>(hits); - printf("N = %d, rounds = %d, inverse hit rate = %f (should be ~= N + 0.67)\n", - n, rounds, inverse_hit_rate); } -// Large requested mean flattens density function near zero, making it almost -// linear. -TEST(ExponentialBiasedTest, OneOfNDemoWithGetSkipCount) { +// Stride frequencies must match the geometric PMF +// `P(S = s) = p * (1 - p)^(s - 1)` across individual buckets, including +// `s = 1`. +TEST(ExponentialBiasedTest, StrideFollowsGeometricDistribution) { ExponentialBiased eb; - int n = 6; - int large_mean = 10000000; - int rounds = n * 10000; - std::vector<int> hits(static_cast<size_t>(n), 0); - for (int i = 0; i < rounds; i++) { - int64_t v = eb.GetSkipCount(large_mean); - int64_t a = v % n; - ++hits[static_cast<size_t>(a)]; + constexpr int64_t kPeriod = 10; + constexpr double kP = 1.0 / kPeriod; + constexpr int kDraws = 200000; + + int counts[11] = {}; + for (int i = 0; i < kDraws; ++i) { + int64_t s = eb.GetStride(kPeriod); + if (s <= 10) ++counts[s]; } - printf("N = %d, rounds = %d, mean = %d\n", n, rounds, large_mean); - for (int i = 0; i < n; i++) { - printf(" inverse hit rate for %d: %f (should be ~= N)\n", i, - rounds / static_cast<double>(hits[static_cast<size_t>(i)])); + + double expected_prob = kP; + for (int s = 1; s <= 10; ++s) { + EXPECT_NEAR(static_cast<double>(counts[s]) / kDraws, expected_prob, 0.006) + << "stride = " << s; + expected_prob *= (1.0 - kP); } } -TEST(ExponentialBiasedTest, SampleDemoWithStride) { +TEST(ExponentialBiasedTest, FirstAndConsecutiveDrawsAreUnbiased) { + constexpr int64_t kPeriod = 10; + constexpr double kExpectedProb = 1.0 / kPeriod; + constexpr int kTrials = 200000; + + // The very first draw on a new thread/generator must sample immediately + // (`stride == 1`) with probability `1 / kPeriod`. + int first_draw_ones = 0; + for (int i = 0; i < kTrials; ++i) { + ExponentialBiased fresh; + if (fresh.GetStride(kPeriod) == 1) ++first_draw_ones; + } + EXPECT_NEAR(static_cast<double>(first_draw_ones) / kTrials, kExpectedProb, + 0.01); + + // Because a geometric process is memoryless, the draw immediately following + // `stride == 1` must still hit `stride == 1` with probability `1 / kPeriod` + // (no post-sample refractory dip from stateful rounding). ExponentialBiased eb; - int64_t stride = eb.GetStride(10); - int samples = 0; - for (int i = 0; i < 10000000; ++i) { - if (--stride == 0) { - ++samples; - stride = eb.GetStride(10); - } + int ones = 0; + int ones_after_one = 0; + bool prev_was_one = false; + for (int i = 0; i < kTrials; ++i) { + bool is_one = (eb.GetStride(kPeriod) == 1); + if (prev_was_one && is_one) ++ones_after_one; + if (prev_was_one) ++ones; + prev_was_one = is_one; } - printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000); + EXPECT_NEAR(static_cast<double>(ones_after_one) / ones, kExpectedProb, 0.02); } +// `NextRandom` outputs must stay within 48 bits and distribute uniformly across +// high-bit buckets, which drive the geometric inverse-CDF transform. +TEST(ExponentialBiasedTest, NextRandomIsUniform) { + uint64_t x = 1; + for (int i = 0; i < 20; ++i) { + x = ExponentialBiased::NextRandom(x); + } -// Testing that NextRandom generates uniform random numbers. Applies the -// Anderson-Darling test for uniformity -TEST(ExponentialBiasedTest, TestNextRandom) { - for (auto n : std::vector<size_t>({ - 10, // Check short-range correlation - 100, 1000, - 10000 // Make sure there's no systemic error - })) { - uint64_t x = 1; - // This assumes that the prng returns 48 bit numbers - uint64_t max_prng_value = static_cast<uint64_t>(1) << 48; - // Initialize. - for (int i = 1; i <= 20; i++) { - x = ExponentialBiased::NextRandom(x); - } - std::vector<uint64_t> int_random_sample(n); - // Collect samples - for (size_t i = 0; i < n; i++) { - int_random_sample[i] = x; - x = ExponentialBiased::NextRandom(x); - } - // First sort them... - std::sort(int_random_sample.begin(), int_random_sample.end()); - std::vector<double> random_sample(n); - // Convert them to uniform randoms (in the range [0,1]) - for (size_t i = 0; i < n; i++) { - random_sample[i] = - static_cast<double>(int_random_sample[i]) / max_prng_value; - } - // Now compute the Anderson-Darling statistic - double ad_pvalue = AndersonDarlingTest(random_sample); - EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001) - << "prng is not uniform: n = " << n << " p = " << ad_pvalue; + constexpr int kBuckets = 16; + constexpr int kDraws = 160000; + int counts[kBuckets] = {}; + for (int i = 0; i < kDraws; ++i) { + x = ExponentialBiased::NextRandom(x); + ASSERT_EQ(x >> ExponentialBiased::kPrngNumBits, 0u); + ++counts[x >> (ExponentialBiased::kPrngNumBits - 4)]; + } + for (int count : counts) { + EXPECT_NEAR(static_cast<double>(count) / kDraws, 1.0 / kBuckets, 0.005); } }