1 files changed, 12 insertions, 71 deletions
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index 054e898..0a7ef61 100644
--- a/absl/container/internal/hashtablez_sampler.cc
+++ b/absl/container/internal/hashtablez_sampler.cc
@@ -21,6 +21,7 @@
 #include <limits>
 
 #include "absl/base/attributes.h"
+#include "absl/base/internal/exponential_biased.h"
 #include "absl/container/internal/have_sse.h"
 #include "absl/debugging/stacktrace.h"
 #include "absl/memory/memory.h"
@@ -37,77 +38,13 @@ ABSL_CONST_INIT std::atomic<bool> g_hashtablez_enabled{
 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_sample_parameter{1 << 10};
 ABSL_CONST_INIT std::atomic<int32_t> g_hashtablez_max_samples{1 << 20};
 
-// Returns the next pseudo-random value.
-// pRNG is: aX+b mod c with a = 0x5DEECE66D, b =  0xB, c = 1<<48
-// This is the lrand64 generator.
-uint64_t NextRandom(uint64_t rnd) {
-  const uint64_t prng_mult = uint64_t{0x5DEECE66D};
-  const uint64_t prng_add = 0xB;
-  const uint64_t prng_mod_power = 48;
-  const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power);
-  return (prng_mult * rnd + prng_add) & prng_mod_mask;
-}
-
-// Generates a geometric variable with the specified mean.
-// This is done by generating a random number between 0 and 1 and applying
-// 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 GetGeometricVariable(int64_t mean) {
 #if ABSL_HAVE_THREAD_LOCAL
-  thread_local
-#else   // ABSL_HAVE_THREAD_LOCAL
-  // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when
-  // there are not thread locals.  Thus, a single global rng is acceptable for
-  // that case.
-  static
-#endif  // ABSL_HAVE_THREAD_LOCAL
-      uint64_t rng = []() {
-        // 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 where the same thread (by memory address) gets
-        // created and destroyed repeatedly.
-        ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
-        uint64_t r = reinterpret_cast<uint64_t>(&rng) +
-                   global_rand.fetch_add(1, std::memory_order_relaxed);
-        for (int i = 0; i < 20; ++i) {
-          r = NextRandom(r);
-        }
-        return r;
-      }();
-
-  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.)
-  const uint64_t prng_mod_power = 48;  // Number of bits in prng
-  // 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 >> (prng_mod_power - 26)) + 1.0;
-  // Put the computed p-value through the CDF of a geometric.
-  double interval = (log2(q) - 26) * (-std::log(2.0) * mean);
-
-  // Very large values of interval overflow int64_t. If we happen to
-  // hit such improbable condition, we simply cheat and clamp interval
-  // to largest supported value.
-  if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
-    return std::numeric_limits<int64_t>::max() / 2;
-  }
-
-  // Small values of interval are equivalent to just sampling next time.
-  if (interval < 1) {
-    return 1;
-  }
-  return static_cast<int64_t>(interval);
-}
+thread_local absl::base_internal::ExponentialBiased
+    g_exponential_biased_generator;
+#else
+ABSL_CONST_INIT static absl::base_internal::ExponentialBiased
+    g_exponential_biased_generator;
+#endif
 
 }  // namespace
 
@@ -253,8 +190,12 @@ HashtablezInfo* SampleSlow(int64_t* next_sample) {
   }
 
   bool first = *next_sample < 0;
-  *next_sample = GetGeometricVariable(
+  *next_sample = g_exponential_biased_generator.Get(
       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;
+  }
 
   // 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