Draw exact memoryless geometric skip counts in ExponentialBiased. `ExponentialBiased::GetSkipCount(mean)` previously approximated a geometric distribution by rounding `-ln(u) * mean` 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` gets width `1.0`. As a result, `P(GetSkipCount(m) == 0)` was `1 / (2*m + 2/3) ~= 0.5 / (m + 1)` instead of `1 / (m + 1)`, under-sampling the first event on every new thread by ~2x, introducing a ~2x refractory dip immediately after each sampled event, and negatively correlating consecutive strides through `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`. Evaluate the exact `Geometric(1 / (mean + 1))` inverse CDF `floor(ln(u) / ln(1 - 1 / (mean + 1)))` using all 48 PRNG bits mapped to bin midpoints `(rng_ + 0.5) * 2^-48`, and drop `bias_` (shrinking `ExponentialBiased` from 24 B to 16 B). Every integer `k >= 0` now has exact geometric probability, exact expectation `mean`, and independent memoryless draws from the first call onward. PiperOrigin-RevId: 1020748224
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc index 8682ca1..b843136 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,48 @@ 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 geometric skip count on {0, 1, 2, ...} with exact expectation +// `mean` (success probability `p = 1 / (mean + 1)`) by applying the geometric +// inverse CDF `floor(ln(u) / ln(1 - p))` to a uniform variate `u` in `(0, 1)`. 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; + + // For mean >= 2^26, `-1 / ln(1 - 1 / (mean + 1))` differs from `mean + 0.5` + // by `1 / (12 * (mean + 1)) < 0.1` ULP of `double(mean)`. + const double inv_neg_log1p = + (mean < (int64_t{1} << 26)) + ? (-1.0 / std::log1p(-1.0 / (static_cast<double>(mean) + 1.0))) + : (static_cast<double>(mean) + 0.5); + const double interval = -std::log(u) * inv_neg_log1p; + + // 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..127358b 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,31 +45,26 @@ // } // // 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; +// `GetSkipCount(mean)` evaluates the exact geometric inverse CDF +// `floor(ln(u) / ln(1 - 1 / (mean + 1)))` (`~= floor(-ln(u) * (mean + 0.5))`): +// * Truncating `-ln(u) * mean` directly (`floor`) would underestimate the +// mean by ~0.5, which is significant for small means. +// * Rounding `-ln(u) * mean` to the nearest integer (`std::rint`) with a +// cumulative rounding-error term gives `0` (`stride == 1`) a half-width +// bin `[0, 0.5)` while every `k >= 1` has width `1.0`, halving the +// probability of `skip == 0` (`stride == 1`) to `~0.5 / (mean + 1)` on a +// fresh generator and immediately after each sampled event. +// Using `floor` with the exact geometric scale `1 / -ln(1 - 1 / (mean + 1))` +// gives every integer `k >= 0` a full-width geometric bin, exact expectation +// `mean`, exact `P(GetSkipCount(mean) == 0) = 1 / (mean + 1)` (`P(GetStride(N) +// == 1) = 1 / N`), and independent memoryless draws without extra state. // // This class is thread-compatible. class ExponentialBiased { @@ -107,7 +103,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..edcd9f0 100644 --- a/absl/profiling/internal/exponential_biased_test.cc +++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -137,27 +137,20 @@ printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000); } -// 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)`. +// `GetSkipCount(m)` is distributed as Geometric(1 / (m + 1)) on {0, 1, ...}, +// so `P(GetSkipCount(n - 1) == 0) == 1 / n`. TEST(ExponentialBiasedTest, OnePerNDemoWithGetSkipCount) { 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; + if (eb.GetSkipCount(n - 1) == 0) ++hits; } 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); + printf("N = %d, rounds = %d, inverse hit rate = %f (should be ~= N)\n", n, + rounds, inverse_hit_rate); + EXPECT_THAT(inverse_hit_rate, IsBetween(20.5, 23.5)); } // Large requested mean flattens density function near zero, making it almost @@ -245,6 +238,95 @@ EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0)); } +TEST(ExponentialBiasedTest, NonPositiveParameters) { + ExponentialBiased eb; + 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); +} + +TEST(ExponentialBiasedTest, ExactMeanAndFirstDrawProbability) { + // Coin toss (`mean == 1`, `period == 2`): exact P(skip == 0) = 0.5 and + // E[skip] = 1.0. + ExponentialBiased coin; + constexpr int kFlips = 200000; + int zero_skips = 0; + int64_t total_skips = 0; + for (int i = 0; i < kFlips; ++i) { + const int64_t skip = coin.GetSkipCount(1); + if (skip == 0) ++zero_skips; + total_skips += skip; + } + // std(zero_skips) ~= 224; std(total_skips) = sqrt(200000 * 2) ~= 632. + EXPECT_THAT(zero_skips, IsBetween(98000, 102000)); + EXPECT_THAT(total_skips, IsBetween(195000, 205000)); + + // Freshly constructed generators must also have exact `1 / kPeriod` + // probability of `GetStride(kPeriod) == 1` on their very first draw + // (previously `~0.5 / kPeriod` due to `std::rint`'s `[0, 0.5)` zero bin). + constexpr int64_t kPeriod = 16; + constexpr int kFreshTrials = 160000; + int fresh_unit_strides = 0; + for (int i = 0; i < kFreshTrials; ++i) { + ExponentialBiased fresh; + if (fresh.GetStride(kPeriod) == 1) { + ++fresh_unit_strides; + } + } + // Expected = 10000, std ~= 96.8. + EXPECT_THAT(fresh_unit_strides, IsBetween(9000, 11000)); +} + +TEST(ExponentialBiasedTest, MemorylessNoPostSampleRefractoryDip) { + ExponentialBiased eb; + constexpr int64_t kPeriod = 8; + constexpr int kDraws = 640000; + bool prev_was_one = false; + int prev_one_count = 0; + int consecutive_ones = 0; + int64_t stride_sum = 0; + for (int i = 0; i < kDraws; ++i) { + const int64_t s = eb.GetStride(kPeriod); + ASSERT_GE(s, 1); + stride_sum += s; + if (prev_was_one) { + ++prev_one_count; + if (s == 1) ++consecutive_ones; + } + prev_was_one = (s == 1); + } + // Expected sum = 5,120,000, std = sqrt(640000 * 8 * 7) ~= 5987. + EXPECT_THAT(stride_sum, IsBetween(5060000, 5180000)); + // Expected prev_one_count ~= 80000; expected consecutive_ones = 1/8 of that + // (~= 10000, std ~= 93.5). Under the old `std::rint` + `bias_` generator, + // `P(S == 1)` was ~1/14.7, yielding only ~2900 consecutive ones. + const double conditional_rate = + static_cast<double>(consecutive_ones) / prev_one_count; + EXPECT_THAT(conditional_rate, IsBetween(0.11, 0.14)); +} + +TEST(ExponentialBiasedTest, LargeMeanBranchAndClamp) { + ExponentialBiased eb; + constexpr int64_t kLargeMean = int64_t{1} << 30; + constexpr int kDraws = 20000; + double sum = 0; + for (int i = 0; i < kDraws; ++i) { + const int64_t skip = eb.GetSkipCount(kLargeMean); + ASSERT_GE(skip, 0); + sum += static_cast<double>(skip); + } + const double expected = static_cast<double>(kDraws) * kLargeMean; + // std / expected = 1 / sqrt(20000) ~= 0.71%. + EXPECT_THAT(sum, IsBetween(0.94 * expected, 1.06 * expected)); + + // Extreme mean near INT64_MAX must clamp cleanly without signed overflow. + for (int i = 0; i < 100; ++i) { + EXPECT_GE(eb.GetStride(int64_t{1} << 62), 1); + } +} + } // namespace } // namespace profiling_internal ABSL_NAMESPACE_END