diff options
| -rw-r--r-- | absl/base/internal/exponential_biased.cc | 52 | ||||
| -rw-r--r-- | absl/base/internal/exponential_biased.h | 6 | ||||
| -rw-r--r-- | absl/container/internal/hashtablez_sampler.cc | 6 | ||||
| -rw-r--r-- | absl/strings/substitute.cc | 6 | ||||
| -rw-r--r-- | absl/strings/substitute_test.cc | 6 |
5 files changed, 18 insertions, 58 deletions
diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc index 3007f9b46b86..7786c303cdd1 100644 --- a/absl/base/internal/exponential_biased.cc +++ b/absl/base/internal/exponential_biased.cc @@ -27,7 +27,16 @@ namespace absl { namespace base_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 int64_t ExponentialBiased::GetSkipCount(int64_t mean) { if (ABSL_PREDICT_FALSE(!initialized_)) { Initialize(); @@ -63,47 +72,6 @@ int64_t ExponentialBiased::GetStride(int64_t mean) { return GetSkipCount(mean - 1) + 1; } -// 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 -int64_t ExponentialBiased::Get(int64_t mean) { - if (ABSL_PREDICT_FALSE(!initialized_)) { - Initialize(); - } - - uint64_t rng = NextRandom(rng_); - rng_ = 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; - } - int64_t value = std::max<int64_t>(1, std::round(interval)); - bias_ = interval - value; - return value; -} - void ExponentialBiased::Initialize() { // We don't get well distributed numbers from `this` so we call NextRandom() a // bunch to mush the bits around. We use a global_rand to handle the case diff --git a/absl/base/internal/exponential_biased.h b/absl/base/internal/exponential_biased.h index 571505d32677..6701e695ef0e 100644 --- a/absl/base/internal/exponential_biased.h +++ b/absl/base/internal/exponential_biased.h @@ -96,12 +96,6 @@ class ExponentialBiased { // `GetSkipCount()` depends mostly on what best fits the use case. int64_t GetStride(int64_t mean); - // Generates a rounded exponentially distributed random variable - // by rounding the value to the nearest integer. - // The result will be in the range [0, int64_t max / 2]. - ABSL_DEPRECATED("Use GetSkipCount() or GetStride() instead") - int64_t Get(int64_t mean); - // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1] // // This is public to enable testing. diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 4aec0a07ffb3..6deeca44d97b 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc @@ -196,12 +196,10 @@ HashtablezInfo* SampleSlow(int64_t* next_sample) { return nullptr; #else bool first = *next_sample < 0; - *next_sample = g_exponential_biased_generator.Get( + *next_sample = g_exponential_biased_generator.GetStride( g_hashtablez_sample_parameter.load(std::memory_order_relaxed)); // Small values of interval are equivalent to just sampling next time. - if (*next_sample < 1) { - *next_sample = 1; - } + ABSL_ASSERT(*next_sample >= 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 diff --git a/absl/strings/substitute.cc b/absl/strings/substitute.cc index 36dbfe7d42ff..5d28c5286cf5 100644 --- a/absl/strings/substitute.cc +++ b/absl/strings/substitute.cc @@ -35,7 +35,7 @@ void SubstituteAndAppendArray(std::string* output, absl::string_view format, if (i + 1 >= format.size()) { #ifndef NDEBUG ABSL_RAW_LOG(FATAL, - "Invalid strings::Substitute() format std::string: \"%s\".", + "Invalid absl::Substitute() format std::string: \"%s\".", absl::CEscape(format).c_str()); #endif return; @@ -45,7 +45,7 @@ void SubstituteAndAppendArray(std::string* output, absl::string_view format, #ifndef NDEBUG ABSL_RAW_LOG( FATAL, - "Invalid strings::Substitute() format std::string: asked for \"$" + "Invalid absl::Substitute() format std::string: asked for \"$" "%d\", but only %d args were given. Full format std::string was: " "\"%s\".", index, static_cast<int>(num_args), absl::CEscape(format).c_str()); @@ -60,7 +60,7 @@ void SubstituteAndAppendArray(std::string* output, absl::string_view format, } else { #ifndef NDEBUG ABSL_RAW_LOG(FATAL, - "Invalid strings::Substitute() format std::string: \"%s\".", + "Invalid absl::Substitute() format std::string: \"%s\".", absl::CEscape(format).c_str()); #endif return; diff --git a/absl/strings/substitute_test.cc b/absl/strings/substitute_test.cc index e27abb177274..b005f0f47caa 100644 --- a/absl/strings/substitute_test.cc +++ b/absl/strings/substitute_test.cc @@ -189,14 +189,14 @@ TEST(SubstituteTest, VectorBoolRef) { TEST(SubstituteDeathTest, SubstituteDeath) { EXPECT_DEBUG_DEATH( static_cast<void>(absl::Substitute(absl::string_view("-$2"), "a", "b")), - "Invalid strings::Substitute\\(\\) format std::string: asked for \"\\$2\", " + "Invalid absl::Substitute\\(\\) format std::string: asked for \"\\$2\", " "but only 2 args were given."); EXPECT_DEBUG_DEATH( static_cast<void>(absl::Substitute("-$z-")), - "Invalid strings::Substitute\\(\\) format std::string: \"-\\$z-\""); + "Invalid absl::Substitute\\(\\) format std::string: \"-\\$z-\""); EXPECT_DEBUG_DEATH( static_cast<void>(absl::Substitute("-$")), - "Invalid strings::Substitute\\(\\) format std::string: \"-\\$\""); + "Invalid absl::Substitute\\(\\) format std::string: \"-\\$\""); } #endif // GTEST_HAS_DEATH_TEST |