Export of internal Abseil changes

--
e54b9c7bbb0c58475676c268e2e19c69f4bce48a by Jorg Brown <jorg@google.com>:

Tweak ABSL_PREDICT_TRUE slightly, for better code on some platforms and/or
optimization levels.  "false || (x)" is more verbose than "!!(x)", but
ultimately more efficient.

For example, given this code:

void InitIfNecessary() {
  if (ABSL_PREDICT_TRUE(NeedsInit())) {
    SlowInitIfNecessary();
  }
}

Clang with default optimization level will produce:

Before this CL              After this CL
InitIfNecessary:            InitIfNecessary:
  push rbp                    push rbp
  mov  rbp, rsp               mov  rbp, rsp
  call NeedsInit              call NeedsInit
  xor  al, -1
  xor  al, -1
  test al, 1                  test al, 1
  jne  .LBB2_1                jne  .LBB3_1
  jmp  .LBB2_2                jmp  .LBB3_2
.LBB2_1:                    .LBB3_1:
  call SlowInitIfNecessary    call SlowInitIfNecessary
.LBB2_2:                    .LBB3_2:
  pop  rbp                    pop  rbp
  ret                         ret
PiperOrigin-RevId: 276401386

--
0a3c4dfd8342bf2b1b11a87f1c662c883f73cab7 by Abseil Team <absl-team@google.com>:

Fix comment nit: sem_open => sem_init.

The code calls sem_init, not sem_open, to initialize an unnamed semaphore.
(sem_open creates or opens a named semaphore.)

PiperOrigin-RevId: 276344072

--
b36a664e9459057509a90e83d3482e1d3a4c44c7 by Abseil Team <absl-team@google.com>:

Fix typo in flat_hash_map.h: exchaged -> exchanged

PiperOrigin-RevId: 276295792

--
7bbd8d18276eb110c8335743e35fceb662ddf3d6 by Samuel Benzaquen <sbenza@google.com>:

Add assertions to verify use of iterators.

PiperOrigin-RevId: 276283300

--
677398a8ffcb1f59182cffe57a4fe7ff147a0404 by Laramie Leavitt <lar@google.com>:

Migrate distribution_impl.h/cc to generate_real.h/cc.

Combine the methods RandU64To<Float,Double> into a single method:
GenerateRealFromBits().

Remove rejection sampling from absl::uniform_real_distribution.

PiperOrigin-RevId: 276158675

--
c60c9d11d24b0c546329d998e78e15a84b3153f5 by Abseil Team <absl-team@google.com>:

Internal change

PiperOrigin-RevId: 276126962

--
4c840cab6a8d86efa29b397cafaf7520eece68cc by Andy Soffer <asoffer@google.com>:

Update CMakeLists.txt to address https://github.com/abseil/abseil-cpp/issues/365.
This does not cover every platform, but it does at least address the
first-order issue of assuming gcc implies x86.

PiperOrigin-RevId: 276116253

--
98da366e6b5d51afe5d7ac6722126aca23d85ee6 by Abseil Team <absl-team@google.com>:

Internal change

PiperOrigin-RevId: 276097452
GitOrigin-RevId: e54b9c7bbb0c58475676c268e2e19c69f4bce48a
Change-Id: I02d84454bb71ab21ad3d39650acf6cc6e36f58d7

1 files changed, 12 insertions, 71 deletions

diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc
index 054e8981..0a7ef61c 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