summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-11-25 10:40:20 -0800
committerGravatar Gennadiy Rozental <rogeeff@google.com>2019-11-25 14:57:06 -0500
commit7f4fe64af80fe3c84db8ea938276c3690573c45e (patch)
tree8a88ab00a8c2210edd1be109ec00a83586ad03c1 /absl
parent16d9fd58a51c6083234e2e9f8f50e49ed5ed02e4 (diff)
Export of internal Abseil changes
-- 44efc1bb0e0a47eabf0569eaab81c66710d5b9c3 by Mark Barolak <mbar@google.com>: Update "strings::Substitute" to "absl::Substitute" in the absl::Substitute error messages. PiperOrigin-RevId: 282388042 -- 9ec7e9385f5469473f76857dc5b067d869bbc65b by Abseil Team <absl-team@google.com>: Remove deprecated ExponentialBiased::Get() PiperOrigin-RevId: 282045123 GitOrigin-RevId: 44efc1bb0e0a47eabf0569eaab81c66710d5b9c3 Change-Id: I915bf0ff5fa7ac2bd5f9fb653d1fbd9ece6af9fc
Diffstat (limited to 'absl')
-rw-r--r--absl/base/internal/exponential_biased.cc52
-rw-r--r--absl/base/internal/exponential_biased.h6
-rw-r--r--absl/container/internal/hashtablez_sampler.cc6
-rw-r--r--absl/strings/substitute.cc6
-rw-r--r--absl/strings/substitute_test.cc6
5 files changed, 18 insertions, 58 deletions
diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc
index 3007f9b4..7786c303 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 571505d3..6701e695 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 4aec0a07..6deeca44 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 36dbfe7d..5d28c528 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 e27abb17..b005f0f4 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