Export of internal Abseil changes

--
17141711ee419daa597a9f31e73721f80143e55a by Gennadiy Rozental <rogeeff@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 401384949

--
ac48584a7b16e8a12e26d49deb6cddec584a20b5 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 401337785

--
8a51bb7c962845e0707240c5ba12c1b80f6fbbe9 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 401047691

--
8e18024510869247f3c04c7807c93709eca2322a by Chris Kennelly <ckennelly@google.com>:

Note that SpinLock does not guarantee priorities for wakeups.

PiperOrigin-RevId: 400999238

--
75bc09b5f95fbb74b74d14c370bfb80011e8fb7f by Derek Mauro <dmauro@google.com>:

Add visibility restrictions to some internal targets

PiperOrigin-RevId: 400718253

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

Make it clear that operator<< can also be used in place of ToString when logging absl::Status.

PiperOrigin-RevId: 400248269

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

Minor cleanup

PiperOrigin-RevId: 400087535

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

Move periodic_sampler from base/internal to profiling/internal

PiperOrigin-RevId: 400038533

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

Move exponential_biased from base/internal to profiling/internal

PiperOrigin-RevId: 400020329
GitOrigin-RevId: 17141711ee419daa597a9f31e73721f80143e55a
Change-Id: I10924df7e1cc198447813dbe97a374a5cef66b49

9 files changed, 1069 insertions, 0 deletions

diff --git a/absl/profiling/BUILD.bazel b/absl/profiling/BUILD.bazel
index ba4811b3..496a06b2 100644
--- a/absl/profiling/BUILD.bazel
+++ b/absl/profiling/BUILD.bazel
@@ -16,6 +16,7 @@ load(
     "//absl:copts/configure_copts.bzl",
     "ABSL_DEFAULT_COPTS",
     "ABSL_DEFAULT_LINKOPTS",
+    "ABSL_TEST_COPTS",
 )
 
 package(default_visibility = ["//visibility:private"])
@@ -51,3 +52,75 @@ cc_test(
         "@com_google_googletest//:gtest_main",
     ],
 )
+
+cc_library(
+    name = "exponential_biased",
+    srcs = ["internal/exponential_biased.cc"],
+    hdrs = ["internal/exponential_biased.h"],
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    visibility = [
+        "//absl:__subpackages__",
+    ],
+    deps = [
+        "//absl/base:config",
+        "//absl/base:core_headers",
+    ],
+)
+
+cc_test(
+    name = "exponential_biased_test",
+    size = "small",
+    srcs = ["internal/exponential_biased_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    visibility = ["//visibility:private"],
+    deps = [
+        ":exponential_biased",
+        "//absl/strings",
+        "@com_google_googletest//:gtest_main",
+    ],
+)
+
+cc_library(
+    name = "periodic_sampler",
+    srcs = ["internal/periodic_sampler.cc"],
+    hdrs = ["internal/periodic_sampler.h"],
+    copts = ABSL_DEFAULT_COPTS,
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    visibility = [
+        "//absl:__subpackages__",
+    ],
+    deps = [
+        ":exponential_biased",
+        "//absl/base:core_headers",
+    ],
+)
+
+cc_test(
+    name = "periodic_sampler_test",
+    size = "small",
+    srcs = ["internal/periodic_sampler_test.cc"],
+    copts = ABSL_TEST_COPTS,
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    visibility = ["//visibility:private"],
+    deps = [
+        ":periodic_sampler",
+        "//absl/base:core_headers",
+        "@com_google_googletest//:gtest_main",
+    ],
+)
+
+cc_binary(
+    name = "periodic_sampler_benchmark",
+    testonly = 1,
+    srcs = ["internal/periodic_sampler_benchmark.cc"],
+    copts = ABSL_TEST_COPTS,
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    tags = ["benchmark"],
+    visibility = ["//visibility:private"],
+    deps = [
+        ":periodic_sampler",
+        "//absl/base:core_headers",
+        "@com_github_google_benchmark//:benchmark_main",
+    ],
+)
diff --git a/absl/profiling/CMakeLists.txt b/absl/profiling/CMakeLists.txt
index 7b6a7780..9b3a7102 100644
--- a/absl/profiling/CMakeLists.txt
+++ b/absl/profiling/CMakeLists.txt
@@ -37,3 +37,57 @@ absl_cc_test(
     GTest::gmock_main
 )
 
+absl_cc_library(
+  NAME
+    exponential_biased
+  SRCS
+    "internal/exponential_biased.cc"
+  HDRS
+    "internal/exponential_biased.h"
+  COPTS
+    ${ABSL_DEFAULT_COPTS}
+  DEPS
+    absl::config
+    absl::core_headers
+)
+
+absl_cc_test(
+  NAME
+    exponential_biased_test
+  SRCS
+    "internal/exponential_biased_test.cc"
+  COPTS
+    ${ABSL_TEST_COPTS}
+  DEPS
+    absl::exponential_biased
+    absl::strings
+    GTest::gmock_main
+)
+
+absl_cc_library(
+  NAME
+    periodic_sampler
+  SRCS
+    "internal/periodic_sampler.cc"
+  HDRS
+    "internal/periodic_sampler.h"
+  COPTS
+    ${ABSL_DEFAULT_COPTS}
+  DEPS
+    absl::core_headers
+    absl::exponential_biased
+)
+
+absl_cc_test(
+  NAME
+    periodic_sampler_test
+  SRCS
+    "internal/periodic_sampler_test.cc"
+  COPTS
+    ${ABSL_TEST_COPTS}
+  DEPS
+    absl::core_headers
+    absl::periodic_sampler
+    GTest::gmock_main
+)
+
diff --git a/absl/profiling/internal/exponential_biased.cc b/absl/profiling/internal/exponential_biased.cc
new file mode 100644
index 00000000..81d9a757
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased.cc
@@ -0,0 +1,93 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+#include <stdint.h>
+
+#include <algorithm>
+#include <atomic>
+#include <cmath>
+#include <limits>
+
+#include "absl/base/attributes.h"
+#include "absl/base/optimization.h"
+
+namespace absl {
+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
+int64_t ExponentialBiased::GetSkipCount(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;
+  }
+  double value = std::rint(interval);
+  bias_ = interval - value;
+  return value;
+}
+
+int64_t ExponentialBiased::GetStride(int64_t mean) {
+  return GetSkipCount(mean - 1) + 1;
+}
+
+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
+  // 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>(this) +
+               global_rand.fetch_add(1, std::memory_order_relaxed);
+  for (int i = 0; i < 20; ++i) {
+    r = NextRandom(r);
+  }
+  rng_ = r;
+  initialized_ = true;
+}
+
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/profiling/internal/exponential_biased.h b/absl/profiling/internal/exponential_biased.h
new file mode 100644
index 00000000..d31f7782
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased.h
@@ -0,0 +1,130 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
+#define ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
+
+#include <stdint.h>
+
+#include "absl/base/config.h"
+#include "absl/base/macros.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 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.
+//
+// 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;
+//
+// This class is thread-compatible.
+class ExponentialBiased {
+ public:
+  // The number of bits set by NextRandom.
+  static constexpr int kPrngNumBits = 48;
+
+  // `GetSkipCount()` returns the number of events to skip before some chosen
+  // event happens. For example, randomly tossing a coin, we will on average
+  // throw heads once before we get tails. We can simulate random coin tosses
+  // using GetSkipCount() as:
+  //
+  //   ExponentialBiased eb;
+  //   for (...) {
+  //     int number_of_heads_before_tail = eb.GetSkipCount(1);
+  //     for (int flips = 0; flips < number_of_heads_before_tail; ++flips) {
+  //       printf("head...");
+  //     }
+  //     printf("tail\n");
+  //   }
+  //
+  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.
+  int64_t GetStride(int64_t mean);
+
+  // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1]
+  //
+  // This is public to enable testing.
+  static uint64_t NextRandom(uint64_t rnd);
+
+ private:
+  void Initialize();
+
+  uint64_t rng_{0};
+  double bias_{0};
+  bool initialized_{false};
+};
+
+// Returns the next prng value.
+// pRNG is: aX+b mod c with a = 0x5DEECE66D, b =  0xB, c = 1<<48
+// This is the lrand64 generator.
+inline uint64_t ExponentialBiased::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 =
+      ~((~static_cast<uint64_t>(0)) << prng_mod_power);
+  return (prng_mult * rnd + prng_add) & prng_mod_mask;
+}
+
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
diff --git a/absl/profiling/internal/exponential_biased_test.cc b/absl/profiling/internal/exponential_biased_test.cc
new file mode 100644
index 00000000..5675001d
--- /dev/null
+++ b/absl/profiling/internal/exponential_biased_test.cc
@@ -0,0 +1,199 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+#include <stddef.h>
+
+#include <cmath>
+#include <cstdint>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/str_cat.h"
+
+using ::testing::Ge;
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+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) {
+  int n = random_sample.size();
+  double ad_sum = 0;
+  for (int i = 0; i < n; i++) {
+    ad_sum += (2 * i + 1) *
+              std::log(random_sample[i] * (1 - random_sample[n - 1 - i]));
+  }
+  double ad_statistic = -n - 1 / static_cast<double>(n) * 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(random_sample.size(), ad_statistic);
+  return p;
+}
+
+TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) {
+  ExponentialBiased eb;
+  for (int runs = 0; runs < 10; ++runs) {
+    for (int 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);
+}
+
+TEST(ExponentialBiasedTest, SampleDemoWithStride) {
+  ExponentialBiased eb;
+  int stride = eb.GetStride(10);
+  int samples = 0;
+  for (int i = 0; i < 10000000; ++i) {
+    if (--stride == 0) {
+      ++samples;
+      stride = eb.GetStride(10);
+    }
+  }
+  printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000);
+}
+
+
+// Testing that NextRandom generates uniform random numbers. Applies the
+// Anderson-Darling test for uniformity
+TEST(ExponentialBiasedTest, TestNextRandom) {
+  for (auto n : std::vector<int>({
+           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 (int 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 (int 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;
+  }
+}
+
+// The generator needs to be available as a thread_local and as a static
+// variable.
+TEST(ExponentialBiasedTest, InitializationModes) {
+  ABSL_CONST_INIT static ExponentialBiased eb_static;
+  EXPECT_THAT(eb_static.GetSkipCount(2), Ge(0));
+
+#ifdef ABSL_HAVE_THREAD_LOCAL
+  thread_local ExponentialBiased eb_thread;
+  EXPECT_THAT(eb_thread.GetSkipCount(2), Ge(0));
+#endif
+
+  ExponentialBiased eb_stack;
+  EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0));
+}
+
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler.cc b/absl/profiling/internal/periodic_sampler.cc
new file mode 100644
index 00000000..a738a82c
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler.cc
@@ -0,0 +1,53 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+
+#include <atomic>
+
+#include "absl/profiling/internal/exponential_biased.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+int64_t PeriodicSamplerBase::GetExponentialBiased(int period) noexcept {
+  return rng_.GetStride(period);
+}
+
+bool PeriodicSamplerBase::SubtleConfirmSample() noexcept {
+  int current_period = period();
+
+  // Deal with period case 0 (always off) and 1 (always on)
+  if (ABSL_PREDICT_FALSE(current_period < 2)) {
+    stride_ = 0;
+    return current_period == 1;
+  }
+
+  // Check if this is the first call to Sample()
+  if (ABSL_PREDICT_FALSE(stride_ == 1)) {
+    stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
+    if (static_cast<int64_t>(stride_) < -1) {
+      ++stride_;
+      return false;
+    }
+  }
+
+  stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
+  return true;
+}
+
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler.h b/absl/profiling/internal/periodic_sampler.h
new file mode 100644
index 00000000..54f0af45
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler.h
@@ -0,0 +1,211 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
+#define ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
+
+#include <stdint.h>
+
+#include <atomic>
+
+#include "absl/base/optimization.h"
+#include "absl/profiling/internal/exponential_biased.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+
+// PeriodicSamplerBase provides the basic period sampler implementation.
+//
+// This is the base class for the templated PeriodicSampler class, which holds
+// a global std::atomic value identified by a user defined tag, such that
+// each specific PeriodSampler implementation holds its own global period.
+//
+// PeriodicSamplerBase is thread-compatible except where stated otherwise.
+class PeriodicSamplerBase {
+ public:
+  // PeriodicSamplerBase is trivial / copyable / movable / destructible.
+  PeriodicSamplerBase() = default;
+  PeriodicSamplerBase(PeriodicSamplerBase&&) = default;
+  PeriodicSamplerBase(const PeriodicSamplerBase&) = default;
+
+  // Returns true roughly once every `period` calls. This is established by a
+  // randomly picked `stride` that is counted down on each call to `Sample`.
+  // This stride is picked such that the probability of `Sample()` returning
+  // true is 1 in `period`.
+  inline bool Sample() noexcept;
+
+  // The below methods are intended for optimized use cases where the
+  // size of the inlined fast path code is highly important. Applications
+  // should use the `Sample()` method unless they have proof that their
+  // specific use case requires the optimizations offered by these methods.
+  //
+  // An example of such a use case is SwissTable sampling. All sampling checks
+  // are in inlined SwissTable methods, and the number of call sites is huge.
+  // In this case, the inlined code size added to each translation unit calling
+  // SwissTable methods is non-trivial.
+  //
+  // The `SubtleMaybeSample()` function spuriously returns true even if the
+  // function should not be sampled, applications MUST match each call to
+  // 'SubtleMaybeSample()' returning true with a `SubtleConfirmSample()` call,
+  // and use the result of the latter as the sampling decision.
+  // In other words: the code should logically be equivalent to:
+  //
+  //    if (SubtleMaybeSample() && SubtleConfirmSample()) {
+  //      // Sample this call
+  //    }
+  //
+  // In the 'inline-size' optimized case, the `SubtleConfirmSample()` call can
+  // be placed out of line, for example, the typical use case looks as follows:
+  //
+  //   // --- frobber.h -----------
+  //   void FrobberSampled();
+  //
+  //   inline void FrobberImpl() {
+  //     // ...
+  //   }
+  //
+  //   inline void Frobber() {
+  //     if (ABSL_PREDICT_FALSE(sampler.SubtleMaybeSample())) {
+  //       FrobberSampled();
+  //     } else {
+  //       FrobberImpl();
+  //     }
+  //   }
+  //
+  //   // --- frobber.cc -----------
+  //   void FrobberSampled() {
+  //     if (!sampler.SubtleConfirmSample())) {
+  //       // Spurious false positive
+  //       FrobberImpl();
+  //       return;
+  //     }
+  //
+  //     // Sampled execution
+  //     // ...
+  //   }
+  inline bool SubtleMaybeSample() noexcept;
+  bool SubtleConfirmSample() noexcept;
+
+ protected:
+  // We explicitly don't use a virtual destructor as this class is never
+  // virtually destroyed, and it keeps the class trivial, which avoids TLS
+  // prologue and epilogue code for our TLS instances.
+  ~PeriodicSamplerBase() = default;
+
+  // Returns the next stride for our sampler.
+  // This function is virtual for testing purposes only.
+  virtual int64_t GetExponentialBiased(int period) noexcept;
+
+ private:
+  // Returns the current period of this sampler. Thread-safe.
+  virtual int period() const noexcept = 0;
+
+  // Keep and decrement stride_ as an unsigned integer, but compare the value
+  // to zero casted as a signed int. clang and msvc do not create optimum code
+  // if we use signed for the combined decrement and sign comparison.
+  //
+  // Below 3 alternative options, all compiles generate the best code
+  // using the unsigned increment <---> signed int comparison option.
+  //
+  // Option 1:
+  //   int64_t stride_;
+  //   if (ABSL_PREDICT_TRUE(++stride_ < 0)) { ... }
+  //
+  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/R5MzzA
+  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/z7NZAt
+  //   Clang x64 (BAD): https://gcc.godbolt.org/z/t4gPsd
+  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/rE6s8W
+  //   MSVC  x64 (OK) : https://gcc.godbolt.org/z/ARMXqS
+  //
+  // Option 2:
+  //   int64_t stride_ = 0;
+  //   if (ABSL_PREDICT_TRUE(--stride_ >= 0)) { ... }
+  //
+  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/jSQxYK
+  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/VJdYaA
+  //   Clang x64 (BAD): https://gcc.godbolt.org/z/Xm4NjX
+  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/4snaFd
+  //   MSVC  x64 (BAD): https://gcc.godbolt.org/z/BgnEKE
+  //
+  // Option 3:
+  //   uint64_t stride_;
+  //   if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) { ... }
+  //
+  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/bFbfPy
+  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/S9KkUE
+  //   Clang x64 (OK) : https://gcc.godbolt.org/z/UYzRb4
+  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/ptTNfD
+  //   MSVC  x64 (OK) : https://gcc.godbolt.org/z/76j4-5
+  uint64_t stride_ = 0;
+  absl::profiling_internal::ExponentialBiased rng_;
+};
+
+inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept {
+  // See comments on `stride_` for the unsigned increment / signed compare.
+  if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) {
+    return false;
+  }
+  return true;
+}
+
+inline bool PeriodicSamplerBase::Sample() noexcept {
+  return ABSL_PREDICT_FALSE(SubtleMaybeSample()) ? SubtleConfirmSample()
+                                                 : false;
+}
+
+// PeriodicSampler is a concreted periodic sampler implementation.
+// The user provided Tag identifies the implementation, and is required to
+// isolate the global state of this instance from other instances.
+//
+// Typical use case:
+//
+//   struct HashTablezTag {};
+//   thread_local PeriodicSampler sampler;
+//
+//   void HashTableSamplingLogic(...) {
+//     if (sampler.Sample()) {
+//       HashTableSlowSamplePath(...);
+//     }
+//   }
+//
+template <typename Tag, int default_period = 0>
+class PeriodicSampler final : public PeriodicSamplerBase {
+ public:
+  ~PeriodicSampler() = default;
+
+  int period() const noexcept final {
+    return period_.load(std::memory_order_relaxed);
+  }
+
+  // Sets the global period for this sampler. Thread-safe.
+  // Setting a period of 0 disables the sampler, i.e., every call to Sample()
+  // will return false. Setting a period of 1 puts the sampler in 'always on'
+  // mode, i.e., every call to Sample() returns true.
+  static void SetGlobalPeriod(int period) {
+    period_.store(period, std::memory_order_relaxed);
+  }
+
+ private:
+  static std::atomic<int> period_;
+};
+
+template <typename Tag, int default_period>
+std::atomic<int> PeriodicSampler<Tag, default_period>::period_(default_period);
+
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_PROFILING_INTERNAL_PERIODIC_SAMPLER_H_
diff --git a/absl/profiling/internal/periodic_sampler_benchmark.cc b/absl/profiling/internal/periodic_sampler_benchmark.cc
new file mode 100644
index 00000000..8f0e5574
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler_benchmark.cc
@@ -0,0 +1,79 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+#include "benchmark/benchmark.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+namespace {
+
+template <typename Sampler>
+void BM_Sample(Sampler* sampler, benchmark::State& state) {
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(sampler);
+    benchmark::DoNotOptimize(sampler->Sample());
+  }
+}
+
+template <typename Sampler>
+void BM_SampleMinunumInlined(Sampler* sampler, benchmark::State& state) {
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(sampler);
+    if (ABSL_PREDICT_FALSE(sampler->SubtleMaybeSample())) {
+      benchmark::DoNotOptimize(sampler->SubtleConfirmSample());
+    }
+  }
+}
+
+void BM_PeriodicSampler_TinySample(benchmark::State& state) {
+  struct Tag {};
+  PeriodicSampler<Tag, 10> sampler;
+  BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_TinySample);
+
+void BM_PeriodicSampler_ShortSample(benchmark::State& state) {
+  struct Tag {};
+  PeriodicSampler<Tag, 1024> sampler;
+  BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_ShortSample);
+
+void BM_PeriodicSampler_LongSample(benchmark::State& state) {
+  struct Tag {};
+  PeriodicSampler<Tag, 1024 * 1024> sampler;
+  BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSample);
+
+void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) {
+  struct Tag {};
+  PeriodicSampler<Tag, 1024 * 1024> sampler;
+  BM_SampleMinunumInlined(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined);
+
+void BM_PeriodicSampler_Disabled(benchmark::State& state) {
+  struct Tag {};
+  PeriodicSampler<Tag, 0> sampler;
+  BM_Sample(&sampler, state);
+}
+BENCHMARK(BM_PeriodicSampler_Disabled);
+
+}  // namespace
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
diff --git a/absl/profiling/internal/periodic_sampler_test.cc b/absl/profiling/internal/periodic_sampler_test.cc
new file mode 100644
index 00000000..ef986f38
--- /dev/null
+++ b/absl/profiling/internal/periodic_sampler_test.cc
@@ -0,0 +1,177 @@
+// Copyright 2019 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/profiling/internal/periodic_sampler.h"
+
+#include <thread>  // NOLINT(build/c++11)
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/attributes.h"
+#include "absl/base/macros.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace profiling_internal {
+namespace {
+
+using testing::Eq;
+using testing::Return;
+using testing::StrictMock;
+
+class MockPeriodicSampler : public PeriodicSamplerBase {
+ public:
+  virtual ~MockPeriodicSampler() = default;
+
+  MOCK_METHOD(int, period, (), (const, noexcept));
+  MOCK_METHOD(int64_t, GetExponentialBiased, (int), (noexcept));
+};
+
+TEST(PeriodicSamplerBaseTest, Sample) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(16));
+  EXPECT_CALL(sampler, GetExponentialBiased(16))
+      .WillOnce(Return(2))
+      .WillOnce(Return(3))
+      .WillOnce(Return(4));
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, ImmediatelySample) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+  EXPECT_CALL(sampler, GetExponentialBiased(16))
+      .WillOnce(Return(1))
+      .WillOnce(Return(2))
+      .WillOnce(Return(3));
+
+  EXPECT_TRUE(sampler.Sample());
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disabled) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(0));
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, AlwaysOn) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(1));
+
+  EXPECT_TRUE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Disable) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).WillOnce(Return(16));
+  EXPECT_CALL(sampler, GetExponentialBiased(16)).WillOnce(Return(3));
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+
+  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(0));
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerBaseTest, Enable) {
+  StrictMock<MockPeriodicSampler> sampler;
+
+  EXPECT_CALL(sampler, period()).WillOnce(Return(0));
+  EXPECT_FALSE(sampler.Sample());
+
+  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
+  EXPECT_CALL(sampler, GetExponentialBiased(16))
+      .Times(2)
+      .WillRepeatedly(Return(3));
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_TRUE(sampler.Sample());
+
+  EXPECT_FALSE(sampler.Sample());
+  EXPECT_FALSE(sampler.Sample());
+}
+
+TEST(PeriodicSamplerTest, ConstructConstInit) {
+  struct Tag {};
+  ABSL_CONST_INIT static PeriodicSampler<Tag> sampler;
+  (void)sampler;
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod0) {
+  struct Tag {};
+  PeriodicSampler<Tag> sampler;
+  EXPECT_THAT(sampler.period(), Eq(0));
+}
+
+TEST(PeriodicSamplerTest, DefaultPeriod) {
+  struct Tag {};
+  PeriodicSampler<Tag, 100> sampler;
+  EXPECT_THAT(sampler.period(), Eq(100));
+}
+
+TEST(PeriodicSamplerTest, SetGlobalPeriod) {
+  struct Tag1 {};
+  struct Tag2 {};
+  PeriodicSampler<Tag1, 25> sampler1;
+  PeriodicSampler<Tag2, 50> sampler2;
+
+  EXPECT_THAT(sampler1.period(), Eq(25));
+  EXPECT_THAT(sampler2.period(), Eq(50));
+
+  std::thread thread([] {
+    PeriodicSampler<Tag1, 25> sampler1;
+    PeriodicSampler<Tag2, 50> sampler2;
+    EXPECT_THAT(sampler1.period(), Eq(25));
+    EXPECT_THAT(sampler2.period(), Eq(50));
+    sampler1.SetGlobalPeriod(10);
+    sampler2.SetGlobalPeriod(20);
+  });
+  thread.join();
+
+  EXPECT_THAT(sampler1.period(), Eq(10));
+  EXPECT_THAT(sampler2.period(), Eq(20));
+}
+
+}  // namespace
+}  // namespace profiling_internal
+ABSL_NAMESPACE_END
+}  // namespace absl