Weight periodic samples by configured period instead of random stride. `hashtablez` and `cordz` previously weighted each sampled instance by the realized exponential countdown draw (`GetStride(period)`) rather than the configured sampling period. Because an exponential/geometric countdown is memoryless, every instance has the same `1 / period` inclusion probability regardless of the random gap that preceded it: - Weighting by the realized draw doubles per-callsite estimator variance and produces single-sample weights up to ~18x the configured period. - On a newly started thread, any stride finishing at the `t`-th item satisfies `stride <= t` (`1 - (1 - 1/period)^t` expected weight instead of `1`), systematically undercounting items created early in a thread's lifetime. Add `absl::profiling_internal::ExponentialSampler` (`ShouldSampleNext` and `SampleSlow`), embedding `ExponentialBiased` and snapshotting the active period when each stride is armed so callers need only a single constant-initializable TLS sampler with unbiased sample weights (including multi-unit steps with overshoot weighting). Switch `hashtablez` and `cordz` to use it. PiperOrigin-RevId: 1020303527
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index a25788b..227ab64 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc
@@ -51,11 +51,6 @@ ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10}; std::atomic<HashtablezConfigListener> g_hashtablez_config_listener{nullptr}; -#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -ABSL_PER_THREAD_TLS_KEYWORD absl::profiling_internal::ExponentialBiased - g_exponential_biased_generator; -#endif - void TriggerHashtablezConfigListener() { auto* listener = g_hashtablez_config_listener.load(std::memory_order_acquire); if (listener != nullptr) listener(); @@ -88,7 +83,7 @@ } // namespace #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample = {0, 0}; +ABSL_PER_THREAD_TLS_KEYWORD ExponentialSampler global_next_sample; #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) HashtablezSampler& GlobalHashtablezSampler() { @@ -128,6 +123,7 @@ soo_capacity = soo_capacity_value; } +#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) static bool ShouldForceSampling() { enum ForceState { kDontForce, @@ -148,7 +144,6 @@ return state == kForce; } -#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) HashtablezInfoHandle ForcedTrySample(const HashtableTypeInfo& info) { if (!info.is_hashtablez_enabled) return HashtablezInfoHandle(nullptr); return HashtablezInfoHandle( @@ -156,63 +151,44 @@ info.value_size, info.soo_capacity())); } void TestOnlyRefreshSamplingStateForCurrentThread() { - global_next_sample.next_sample = + const int32_t rate = g_hashtablez_sample_parameter.load(std::memory_order_relaxed); - global_next_sample.sample_stride = global_next_sample.next_sample; + global_next_sample.SetStateForTesting(rate, rate); +} + +HashtablezInfo* SampleSlow(ExponentialSampler& next_sample, + size_t inline_element_size, size_t key_size, + size_t value_size, uint16_t soo_capacity) { + // Override `enabled` and `rate` when link-time force-sampling + // (`AbslContainerInternalSampleEverything`) is active. + const bool force = ABSL_PREDICT_FALSE(ShouldForceSampling()); + const int32_t rate = + force ? 1 + : g_hashtablez_sample_parameter.load(std::memory_order_relaxed); + const bool enabled = + force || g_hashtablez_enabled.load(std::memory_order_relaxed); + // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold + // low enough that we will start sampling in a reasonable time, so we just use + // the configured sampling rate. + const int64_t weight = next_sample.SampleSlow( + enabled ? rate : 0, /*step=*/1, + /*disabled_stride=*/rate > 0 ? rate : (1 << 10)); + if (weight <= 0) return nullptr; + return GlobalHashtablezSampler().Register(weight, inline_element_size, + key_size, value_size, soo_capacity); } #else HashtablezInfoHandle ForcedTrySample(const HashtableTypeInfo&) { return HashtablezInfoHandle{nullptr}; } void TestOnlyRefreshSamplingStateForCurrentThread() {} -#endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE - -HashtablezInfo* SampleSlow(SamplingState& next_sample, - size_t inline_element_size, size_t key_size, - size_t value_size, uint16_t soo_capacity) { - if (ABSL_PREDICT_FALSE(ShouldForceSampling())) { - next_sample.next_sample = 1; - const int64_t old_stride = std::exchange(next_sample.sample_stride, 1); - HashtablezInfo* result = GlobalHashtablezSampler().Register( - old_stride, inline_element_size, key_size, value_size, soo_capacity); - return result; - } - -#if !defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) - next_sample = { - std::numeric_limits<int64_t>::max(), - std::numeric_limits<int64_t>::max(), - }; +HashtablezInfo* SampleSlow(ExponentialSampler& next_sample, + size_t /*inline_element_size*/, size_t /*key_size*/, + size_t /*value_size*/, uint16_t /*soo_capacity*/) { + next_sample.DisablePermanently(); return nullptr; -#else - bool first = next_sample.next_sample < 0; - - const int64_t next_stride = g_exponential_biased_generator.GetStride( - g_hashtablez_sample_parameter.load(std::memory_order_relaxed)); - - next_sample.next_sample = next_stride; - const int64_t old_stride = - std::exchange(next_sample.sample_stride, next_stride); - // Small values of interval are equivalent to just sampling next time. - ABSL_ASSERT(next_stride >= 1); - - // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold - // low enough that we will start sampling in a reasonable time, so we just use - // the default sampling rate. - if (!g_hashtablez_enabled.load(std::memory_order_relaxed)) return nullptr; - - // We will only be negative on our first count, so we should just retry in - // that case. - if (first) { - if (ABSL_PREDICT_TRUE(--next_sample.next_sample > 0)) return nullptr; - return SampleSlow(next_sample, inline_element_size, key_size, value_size, - soo_capacity); - } - - return GlobalHashtablezSampler().Register(old_stride, inline_element_size, - key_size, value_size, soo_capacity); -#endif } +#endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE void UnsampleSlow(HashtablezInfo* info) { GlobalHashtablezSampler().Unregister(info);
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h index 4ad5e5f..9a79430 100644 --- a/absl/container/internal/hashtablez_sampler.h +++ b/absl/container/internal/hashtablez_sampler.h
@@ -53,6 +53,7 @@ #include "absl/base/optimization.h" #include "absl/base/thread_annotations.h" #include "absl/container/internal/container_memory.h" +#include "absl/profiling/internal/exponential_biased.h" #include "absl/profiling/internal/sample_recorder.h" #include "absl/synchronization/mutex.h" #include "absl/time/time.h" @@ -124,14 +125,9 @@ void RecordEraseSlow(HashtablezInfo* info); -struct SamplingState { - int64_t next_sample; - // When we make a sampling decision, we record that distance so we can weight - // each sample. - int64_t sample_stride; -}; +using ExponentialSampler = ::absl::profiling_internal::ExponentialSampler; -HashtablezInfo* SampleSlow(SamplingState& next_sample, +HashtablezInfo* SampleSlow(ExponentialSampler& next_sample, size_t inline_element_size, size_t key_size, size_t value_size, uint16_t soo_capacity); void UnsampleSlow(HashtablezInfo* info); @@ -218,7 +214,7 @@ #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -extern ABSL_PER_THREAD_TLS_KEYWORD SamplingState global_next_sample; +extern ABSL_PER_THREAD_TLS_KEYWORD ExponentialSampler global_next_sample; #endif // defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) // Returns true if the next table should be sampled. @@ -227,10 +223,7 @@ // ForcedTrySample(). inline bool ShouldSampleNextTable() { #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) - if (ABSL_PREDICT_TRUE(--global_next_sample.next_sample > 0)) { - return false; - } - return true; + return global_next_sample.ShouldSampleNext(/*step=*/1); #else return false; #endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE
diff --git a/absl/container/internal/hashtablez_sampler_test.cc b/absl/container/internal/hashtablez_sampler_test.cc index b61976d..a28045e 100644 --- a/absl/container/internal/hashtablez_sampler_test.cc +++ b/absl/container/internal/hashtablez_sampler_test.cc
@@ -287,16 +287,18 @@ SetHashtablezEnabled(true); SetHashtablezSampleParameter(100); + ExponentialSampler next_sample; for (int i = 0; i < 1000; ++i) { - SamplingState next_sample = {0, 0}; + next_sample.SetStateForTesting(0, 100); HashtablezInfo* sample = SampleSlow(next_sample, test_element_size, /*key_size=*/test_key_size, /*value_size=*/test_value_size, /*soo_capacity=*/0); - EXPECT_GT(next_sample.next_sample, 0); - EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); - EXPECT_NE(sample, nullptr); + EXPECT_GT(next_sample.next_sample(), 0); + EXPECT_EQ(next_sample.sample_period(), 100); + ASSERT_NE(sample, nullptr); + EXPECT_EQ(sample->weight, 100); UnsampleSlow(sample); } } @@ -305,18 +307,21 @@ const size_t test_element_size = 31; const size_t test_key_size = 33; const size_t test_value_size = 35; + constexpr int32_t kMaxParam = (std::numeric_limits<int32_t>::max)(); SetHashtablezEnabled(true); - SetHashtablezSampleParameter(std::numeric_limits<int32_t>::max()); + SetHashtablezSampleParameter(kMaxParam); + ExponentialSampler next_sample; for (int i = 0; i < 1000; ++i) { - SamplingState next_sample = {0, 0}; + next_sample.SetStateForTesting(0, kMaxParam); HashtablezInfo* sample = SampleSlow(next_sample, test_element_size, /*key_size=*/test_key_size, /*value_size=*/test_value_size, /*soo_capacity=*/0); - EXPECT_GT(next_sample.next_sample, 0); - EXPECT_EQ(next_sample.next_sample, next_sample.sample_stride); - EXPECT_NE(sample, nullptr); + EXPECT_GT(next_sample.next_sample(), 0); + EXPECT_EQ(next_sample.sample_period(), kMaxParam); + ASSERT_NE(sample, nullptr); + EXPECT_EQ(sample->weight, kMaxParam); UnsampleSlow(sample); } }
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc index 8682ca1..2821375 100644 --- a/absl/profiling/internal/exponential_biased.cc +++ b/absl/profiling/internal/exponential_biased.cc
@@ -16,7 +16,6 @@ #include <stdint.h> -#include <algorithm> #include <atomic> #include <cmath> #include <limits> @@ -29,48 +28,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; } @@ -89,6 +82,60 @@ initialized_ = true; } +int64_t ExponentialSampler::SampleSlow(int64_t period, int64_t step, + int64_t disabled_stride) { + if (period <= 0) { + // Back off in TLS so disabled mode stays off the slow path while still + // polling periodically in case sampling is dynamically enabled later. + // Clearing `sample_period_` marks the countdown as unarmed so expiry of + // `disabled_stride` is not mistaken for a completed sample stride. + next_sample_ = disabled_stride > 0 ? disabled_stride : (int64_t{1} << 16); + sample_period_ = 0; + return 0; + } + if (ABSL_PREDICT_FALSE(step < 1)) { + step = 1; + } + if (sample_period_ <= 0) { + // Unarmed state (thread's first event, or re-enabling from `period <= 0`): + // arm an initial stride and charge the current event's `step` against it so + // the first event on a thread is sampled with the same probability as any + // steady-state event. Fall through only if `step` already exhausted it. + sample_period_ = period; + next_sample_ = rng_.GetStride(period) - step; + if (ABSL_PREDICT_TRUE(next_sample_ > 0)) { + return 0; + } + } + + // Weight by the configured `sample_period_` active when the completed stride + // started, not the realized `GetStride()` draw: the geometric countdown is + // memoryless, so every unit has inclusion probability `1 / sample_period_` + // regardless of the random gap before it (using the draw would double + // estimator variance and undercount early-thread events). Subtracting a + // negative `next_sample_` adds any multi-unit (`step > 1`) overshoot past + // zero so `E[weight] = step` without computing `exp()`. + int64_t weight; + const int64_t max_int64 = (std::numeric_limits<int64_t>::max)(); + if (ABSL_PREDICT_FALSE(next_sample_ < 0 && + sample_period_ > max_int64 + next_sample_)) { + weight = max_int64; + } else { + weight = sample_period_ - next_sample_; + } + + // Snapshot the new `period` alongside the next countdown so a subsequent + // runtime `period` change does not retroactively reweight the new stride. + sample_period_ = period; + next_sample_ = rng_.GetStride(period); + return weight; +} + +void ExponentialSampler::DisablePermanently() { + next_sample_ = (std::numeric_limits<int64_t>::max)(); + sample_period_ = 0; +} + } // namespace profiling_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/profiling/internal/exponential_biased.h b/absl/profiling/internal/exponential_biased.h index d31f778..e5b3aa5 100644 --- a/absl/profiling/internal/exponential_biased.h +++ b/absl/profiling/internal/exponential_biased.h
@@ -17,58 +17,24 @@ #include <stdint.h> +#include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/macros.h" +#include "absl/base/optimization.h" namespace absl { ABSL_NAMESPACE_BEGIN 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. +// ExponentialBiased provides a small, fast, synchronization-free random number +// generator for a memoryless geometric distribution (the discrete analog of an +// exponential distribution): // -// 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. +// ExponentialBiased rng; +// int64_t skip = rng.GetSkipCount(mean); // in {0, 1, ...}, E[skip] ~ mean +// int64_t stride = rng.GetStride(period); // in {1, 2, ...}, P(1) ~ 1/period // -// 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 -// happen on average once every 'N' events, then we can get a random 'stride' -// counting down how long before the event to happen. For example, if we'd want -// to sample one in every 1000 'Frobber' calls, our code could look like this: -// -// Frobber::Frobber() { -// stride_ = exponential_biased_.GetStride(1000); -// } -// -// void Frobber::Frob(int arg) { -// 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; +// For periodic sampling with sample weights, prefer `ExponentialSampler`. // // This class is thread-compatible. class ExponentialBiased { @@ -92,10 +58,9 @@ // int64_t GetSkipCount(int64_t mean); - // GetStride() returns the number of events required for a specific event to - // happen. See the class comments for a usage example. `GetStride()` is - // equivalent to `GetSkipCount(mean - 1) + 1`. When to use `GetStride()` or - // `GetSkipCount()` depends mostly on what best fits the use case. + // GetStride() returns the number of events required (`>= 1`) for a specific + // event with a given mean period to happen. `GetStride(mean)` is equivalent + // to `GetSkipCount(mean - 1) + 1`. int64_t GetStride(int64_t mean); // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1] @@ -107,7 +72,6 @@ void Initialize(); uint64_t rng_{0}; - double bias_{0}; bool initialized_{false}; }; @@ -123,6 +87,87 @@ return (prng_mult * rnd + prng_add) & prng_mod_mask; } +// Per-thread periodic sampler that pairs an inline fast-path countdown with an +// out-of-line slow path returning unbiased sample weights. +// +// `ExponentialSampler` is constant-initializable and trivially destructible so +// it can be declared `thread_local` with `ABSL_CONST_INIT` (or +// `ABSL_PER_THREAD_TLS_KEYWORD`) without dynamic TLS initialization guards. +// +// Typical usage splits the fast decrement into a header and the slow path into +// a `.cc` file: +// +// // frobber.h +// ABSL_CONST_INIT extern thread_local ExponentialSampler frob_sampler; +// void SampleFrobSlow(int arg); +// +// inline void Frob(int arg) { +// if (ABSL_PREDICT_FALSE(frob_sampler.ShouldSampleNext(/*step=*/1))) { +// SampleFrobSlow(arg); +// } +// ... +// } +// +// // frobber.cc +// ABSL_CONST_INIT thread_local ExponentialSampler frob_sampler; +// +// void SampleFrobSlow(int arg) { +// int64_t weight = frob_sampler.SampleSlow( +// GetFrobSamplePeriod(), /*step=*/1, /*disabled_stride=*/1 << 16); +// if (weight > 0) { +// RecordFrobSample(arg, weight); +// } +// } +// +// This class is thread-compatible (typically one instance per thread in TLS). +class ExponentialSampler { + public: + constexpr ExponentialSampler() = default; + + // Subtracts `step` from the pending countdown and returns true when the slow + // path (`SampleSlow()`) must be called. + // + // `step` is the weight of the current event: `1` for unweighted event/object + // sampling (e.g. one Cord or hash table), or `size + 1` for size-weighted + // sampling (e.g. an allocation of `size` bytes, where `+ 1` ensures zero-byte + // events still advance the countdown). + ABSL_ATTRIBUTE_ALWAYS_INLINE bool ShouldSampleNext(int64_t step) { + next_sample_ -= step; + return ABSL_PREDICT_FALSE(next_sample_ <= 0); + } + + // Slow-path companion to `ShouldSampleNext()`, which also triggers on a + // thread's first event (since `next_sample_` is zero-initialized in TLS) and + // when `disabled_stride` expires while `period <= 0`. Pass the same `step` + // that was passed to `ShouldSampleNext()`. + // + // Returns 0 if the event is not sampled, or the positive sample weight + // (`sample_period` plus any multi-unit overshoot past zero) if it is sampled. + // + // When `period <= 0`, sampling is treated as disabled: the countdown is set + // to `disabled_stride` so the fast path skips that many units in TLS before + // re-checking `period` on the slow path, and 0 is returned. + int64_t SampleSlow(int64_t period, int64_t step, int64_t disabled_stride); + + // Permanently disables sampling on this instance by setting the countdown to + // `INT64_MAX`. + void DisablePermanently(); + + // Overrides the pending countdown and active period without reseeding `rng_`. + void SetStateForTesting(int64_t next_sample, int64_t sample_period) { + next_sample_ = next_sample; + sample_period_ = sample_period; + } + + int64_t next_sample() const { return next_sample_; } + int64_t sample_period() const { return sample_period_; } + + private: + int64_t next_sample_ = 0; + int64_t sample_period_ = 0; + ExponentialBiased rng_; +}; + } // namespace profiling_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/profiling/internal/exponential_biased_test.cc b/absl/profiling/internal/exponential_biased_test.cc index 3471b07..5d481ac 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); } } @@ -245,6 +144,129 @@ EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0)); } +TEST(ExponentialSamplerTest, InitializationModes) { + ABSL_CONST_INIT static ExponentialSampler static_sampler; + EXPECT_EQ(static_sampler.next_sample(), 0); + EXPECT_EQ(static_sampler.sample_period(), 0); + +#ifdef ABSL_HAVE_THREAD_LOCAL + ABSL_CONST_INIT thread_local ExponentialSampler thread_sampler; + EXPECT_EQ(thread_sampler.next_sample(), 0); + EXPECT_EQ(thread_sampler.sample_period(), 0); +#endif +} + +TEST(ExponentialSamplerTest, DisabledAndAlwaysOn) { + ExponentialSampler sampler; + + ASSERT_TRUE(sampler.ShouldSampleNext(/*step=*/1)); + EXPECT_EQ(sampler.SampleSlow(/*period=*/0, /*step=*/1, + /*disabled_stride=*/1234), + 0); + EXPECT_EQ(sampler.next_sample(), 1234); + EXPECT_EQ(sampler.sample_period(), 0); + + // Period 1 samples every event with weight == step, including event #1. + sampler.SetStateForTesting(0, 0); + for (int i = 0; i < 10; ++i) { + ASSERT_TRUE(sampler.ShouldSampleNext(/*step=*/1)); + EXPECT_EQ(sampler.SampleSlow(/*period=*/1, /*step=*/1, + /*disabled_stride=*/1 << 16), + 1); + } + + sampler.SetStateForTesting(0, 0); + for (int i = 0; i < 10; ++i) { + ASSERT_TRUE(sampler.ShouldSampleNext(/*step=*/65)); + EXPECT_EQ(sampler.SampleSlow(/*period=*/1, /*step=*/65, + /*disabled_stride=*/1 << 16), + 65); + } + + sampler.DisablePermanently(); + EXPECT_FALSE(sampler.ShouldSampleNext(/*step=*/1)); + EXPECT_EQ(sampler.sample_period(), 0); +} + +TEST(ExponentialSamplerTest, UnitStepConstantWeightAndUnbiasedFirstItem) { + constexpr int64_t kPeriod = 16; + constexpr int64_t kDisabledStride = 1 << 16; + constexpr int kTrials = 100000; + + // Item #1 on a fresh thread must be sampled with probability `1 / kPeriod` + // and receive weight `kPeriod` (never 1). + int64_t first_item_weight_sum = 0; + for (int i = 0; i < kTrials; ++i) { + ExponentialSampler fresh; + ASSERT_TRUE(fresh.ShouldSampleNext(/*step=*/1)); + const int64_t w = fresh.SampleSlow(kPeriod, /*step=*/1, kDisabledStride); + if (w > 0) { + ASSERT_EQ(w, kPeriod); + first_item_weight_sum += w; + } + } + EXPECT_NEAR(static_cast<double>(first_item_weight_sum), kTrials, + 0.10 * kTrials); + + // Steady-state sequential items must also carry constant weight + // `kSteadyPeriod`. + constexpr int64_t kSteadyPeriod = 32; + constexpr int kEvents = 200000; + ExponentialSampler sampler; + int64_t steady_weight_sum = 0; + for (int i = 0; i < kEvents; ++i) { + if (sampler.ShouldSampleNext(/*step=*/1)) { + const int64_t w = + sampler.SampleSlow(kSteadyPeriod, /*step=*/1, kDisabledStride); + if (w > 0) { + ASSERT_EQ(w, kSteadyPeriod); + steady_weight_sum += w; + } + } + } + EXPECT_NEAR(static_cast<double>(steady_weight_sum), kEvents, 0.10 * kEvents); +} + +TEST(ExponentialSamplerTest, PreservesInFlightPeriodAcrossRateChange) { + ExponentialSampler sampler; + sampler.SetStateForTesting(/*next_sample=*/0, /*sample_period=*/100); + + // Completed stride ran under period 100; new stride runs under period 500. + EXPECT_EQ(sampler.SampleSlow(/*period=*/500, /*step=*/1, + /*disabled_stride=*/1 << 16), + 100); + EXPECT_EQ(sampler.sample_period(), 500); + EXPECT_GT(sampler.next_sample(), 0); + + sampler.SetStateForTesting(/*next_sample=*/0, sampler.sample_period()); + EXPECT_EQ(sampler.SampleSlow(/*period=*/500, /*step=*/1, + /*disabled_stride=*/1 << 16), + 500); +} + +TEST(ExponentialSamplerTest, WeightedStepOvershootUnbiased) { + constexpr int64_t kPeriod = 4096; + // 2x period: exercises multi-period overshoot. + constexpr int64_t kSize = 8192; + constexpr int64_t kStep = kSize + 1; + constexpr int64_t kDisabledStride = 1 << 20; + constexpr int kAllocs = 100000; + + ExponentialSampler sampler; + double estimated_bytes = 0; + for (int i = 0; i < kAllocs; ++i) { + if (sampler.ShouldSampleNext(kStep)) { + const int64_t w = sampler.SampleSlow(kPeriod, kStep, kDisabledStride); + if (w > 0) { + EXPECT_GE(w, kPeriod); + estimated_bytes += static_cast<double>(w) * kSize / kStep; + } + } + } + const double exact_bytes = static_cast<double>(kAllocs) * kSize; + EXPECT_NEAR(estimated_bytes, exact_bytes, 0.05 * exact_bytes); +} + } // namespace } // namespace profiling_internal ABSL_NAMESPACE_END
diff --git a/absl/strings/internal/cordz_functions.cc b/absl/strings/internal/cordz_functions.cc index 5094817..5f774d6 100644 --- a/absl/strings/internal/cordz_functions.cc +++ b/absl/strings/internal/cordz_functions.cc
@@ -38,54 +38,27 @@ #ifdef ABSL_INTERNAL_CORDZ_ENABLED -// Special negative 'not initialized' per thread value for cordz_next_sample. -static constexpr int64_t kInitCordzNextSample = -1; - -ABSL_CONST_INIT thread_local SamplingState cordz_next_sample = { - kInitCordzNextSample, 1}; +ABSL_CONST_INIT thread_local ExponentialSampler cordz_next_sample; // kIntervalIfDisabled is the number of profile-eligible events need to occur // before the code will confirm that cordz is still disabled. constexpr int64_t kIntervalIfDisabled = 1 << 16; ABSL_ATTRIBUTE_NOINLINE int64_t -cordz_should_profile_slow(SamplingState& state) { +cordz_should_profile_slow(ExponentialSampler& sampler) { - thread_local absl::profiling_internal::ExponentialBiased - exponential_biased_generator; - int32_t mean_interval = get_cordz_mean_interval(); - - // Check if we disabled profiling. If so, set the next sample to a "large" - // number to minimize the overhead of the should_profile codepath. - if (mean_interval <= 0) { - state = {kIntervalIfDisabled, kIntervalIfDisabled}; - return 0; - } - - // Check if we're always sampling. - if (mean_interval == 1) { - state = {1, 1}; - return 1; - } - - if (cordz_next_sample.next_sample <= 0) { - // If first check on current thread, check cordz_should_profile() - // again using the created (initial) stride in cordz_next_sample. - const bool initialized = - cordz_next_sample.next_sample != kInitCordzNextSample; - auto old_stride = state.sample_stride; - auto stride = exponential_biased_generator.GetStride(mean_interval); - state = {stride, stride}; - bool should_sample = initialized || cordz_should_profile() > 0; - return should_sample ? old_stride : 0; - } - - --state.next_sample; - return 0; + return sampler.SampleSlow(get_cordz_mean_interval(), /*step=*/1, + kIntervalIfDisabled); } void cordz_set_next_sample_for_testing(int64_t next_sample) { - cordz_next_sample = {next_sample, next_sample}; + if (next_sample < 0) { + cordz_next_sample.SetStateForTesting(0, 0); + return; + } + const int32_t interval = get_cordz_mean_interval(); + cordz_next_sample.SetStateForTesting(next_sample > 1 ? next_sample : 1, + interval > 0 ? interval : 1); } #endif // ABSL_INTERNAL_CORDZ_ENABLED
diff --git a/absl/strings/internal/cordz_functions.h b/absl/strings/internal/cordz_functions.h index 84c185e..490587f 100644 --- a/absl/strings/internal/cordz_functions.h +++ b/absl/strings/internal/cordz_functions.h
@@ -20,6 +20,7 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/optimization.h" +#include "absl/profiling/internal/exponential_biased.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -41,30 +42,25 @@ #ifdef ABSL_INTERNAL_CORDZ_ENABLED -struct SamplingState { - int64_t next_sample; - int64_t sample_stride; -}; +using ExponentialSampler = ::absl::profiling_internal::ExponentialSampler; -// cordz_next_sample is the number of events until the next sample event. If -// the value is 1 or less, the code will check on the next event if cordz is -// enabled, and if so, will sample the Cord. cordz is only enabled when we can -// use thread locals. -ABSL_CONST_INIT extern thread_local SamplingState cordz_next_sample; +// cordz_next_sample holds the per-thread sampler tracking the number of events +// until the next Cord is sampled and the sampling period active when that +// countdown started. cordz is only enabled when we can use thread locals. +ABSL_CONST_INIT extern thread_local ExponentialSampler cordz_next_sample; // Determines if the next sample should be profiled. // Returns: // 0: Do not sample -// >0: Sample with the stride of the last sampling period -int64_t cordz_should_profile_slow(SamplingState& state); +// >0: Sample with the sampling period active for the completed stride +int64_t cordz_should_profile_slow(ExponentialSampler& sampler); // Determines if the next sample should be profiled. // Returns: // 0: Do not sample -// >0: Sample with the stride of the last sampling period +// >0: Sample with the sampling period active for the completed stride inline int64_t cordz_should_profile() { - if (ABSL_PREDICT_TRUE(cordz_next_sample.next_sample > 1)) { - cordz_next_sample.next_sample--; + if (ABSL_PREDICT_TRUE(!cordz_next_sample.ShouldSampleNext(/*step=*/1))) { return 0; } return cordz_should_profile_slow(cordz_next_sample);
diff --git a/absl/strings/internal/cordz_functions_test.cc b/absl/strings/internal/cordz_functions_test.cc index 3949bf3..fd7c547 100644 --- a/absl/strings/internal/cordz_functions_test.cc +++ b/absl/strings/internal/cordz_functions_test.cc
@@ -50,7 +50,7 @@ cordz_set_next_sample_for_testing(0); EXPECT_EQ(cordz_should_profile(), 0); // 1 << 16 is from kIntervalIfDisabled in cordz_functions.cc. - EXPECT_THAT(cordz_next_sample.next_sample, Eq(1 << 16)); + EXPECT_THAT(cordz_next_sample.next_sample(), Eq(1 << 16)); set_cordz_mean_interval(orig_sample_rate); } @@ -61,7 +61,7 @@ set_cordz_mean_interval(1); cordz_set_next_sample_for_testing(1); EXPECT_GT(cordz_should_profile(), 0); - EXPECT_THAT(cordz_next_sample.next_sample, Le(1)); + EXPECT_THAT(cordz_next_sample.next_sample(), Le(1)); set_cordz_mean_interval(orig_sample_rate); } @@ -92,8 +92,8 @@ // Setting next_sample to 0 will force cordz_should_profile to generate a // new value for next_sample each iteration. cordz_set_next_sample_for_testing(0); - cordz_should_profile(); - sum_of_intervals += cordz_next_sample.next_sample; + EXPECT_EQ(cordz_should_profile(), kDesiredMeanInterval); + sum_of_intervals += cordz_next_sample.next_sample(); } // The sum of independent exponential variables is an Erlang distribution,