From a59b4daa07a14326d2ceb28cc6d0e079feea3338 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 6 Oct 2021 17:55:30 -0700 Subject: Export of internal Abseil changes -- 17141711ee419daa597a9f31e73721f80143e55a by Gennadiy Rozental : Import of CCTZ from GitHub. PiperOrigin-RevId: 401384949 -- ac48584a7b16e8a12e26d49deb6cddec584a20b5 by Derek Mauro : Internal change PiperOrigin-RevId: 401337785 -- 8a51bb7c962845e0707240c5ba12c1b80f6fbbe9 by Derek Mauro : Internal change PiperOrigin-RevId: 401047691 -- 8e18024510869247f3c04c7807c93709eca2322a by Chris Kennelly : Note that SpinLock does not guarantee priorities for wakeups. PiperOrigin-RevId: 400999238 -- 75bc09b5f95fbb74b74d14c370bfb80011e8fb7f by Derek Mauro : Add visibility restrictions to some internal targets PiperOrigin-RevId: 400718253 -- 1de5061016bc42cd7be009c9725ed2343ce12e3d by Abseil Team : Make it clear that operator<< can also be used in place of ToString when logging absl::Status. PiperOrigin-RevId: 400248269 -- cda15d9dc6e5cd569de7e5e73f409b72a3caed51 by Abseil Team : Minor cleanup PiperOrigin-RevId: 400087535 -- b001375ec47da3a0434be9ca9a45c0df510e7dda by Abseil Team : Move periodic_sampler from base/internal to profiling/internal PiperOrigin-RevId: 400038533 -- e7e02e686abc3900e723080849a3607d190ef57f by Abseil Team : Move exponential_biased from base/internal to profiling/internal PiperOrigin-RevId: 400020329 GitOrigin-RevId: 17141711ee419daa597a9f31e73721f80143e55a Change-Id: I10924df7e1cc198447813dbe97a374a5cef66b49 --- CMake/AbseilDll.cmake | 8 +- absl/base/BUILD.bazel | 69 ------- absl/base/CMakeLists.txt | 54 ------ absl/base/internal/exponential_biased.cc | 93 --------- absl/base/internal/exponential_biased.h | 130 ------------- absl/base/internal/exponential_biased_test.cc | 199 ------------------- absl/base/internal/periodic_sampler.cc | 53 ------ absl/base/internal/periodic_sampler.h | 211 --------------------- absl/base/internal/periodic_sampler_benchmark.cc | 79 -------- absl/base/internal/periodic_sampler_test.cc | 177 ----------------- absl/base/internal/spinlock.h | 4 +- absl/base/internal/spinlock_wait.h | 2 + absl/container/BUILD.bazel | 2 +- absl/container/internal/hashtablez_sampler.cc | 4 +- absl/debugging/BUILD.bazel | 2 + absl/profiling/BUILD.bazel | 73 +++++++ absl/profiling/CMakeLists.txt | 54 ++++++ absl/profiling/internal/exponential_biased.cc | 93 +++++++++ absl/profiling/internal/exponential_biased.h | 130 +++++++++++++ absl/profiling/internal/exponential_biased_test.cc | 199 +++++++++++++++++++ absl/profiling/internal/periodic_sampler.cc | 53 ++++++ absl/profiling/internal/periodic_sampler.h | 211 +++++++++++++++++++++ .../internal/periodic_sampler_benchmark.cc | 79 ++++++++ absl/profiling/internal/periodic_sampler_test.cc | 177 +++++++++++++++++ absl/status/status.h | 2 +- absl/strings/BUILD.bazel | 2 +- absl/strings/internal/cordz_functions.cc | 4 +- absl/synchronization/mutex_test.cc | 55 +++--- absl/time/internal/cctz/src/cctz_benchmark.cc | 1 + .../internal/cctz/src/time_zone_lookup_test.cc | 1 + absl/time/internal/cctz/testdata/version | 2 +- .../cctz/testdata/zoneinfo/Atlantic/Jan_Mayen | Bin 705 -> 676 bytes 32 files changed, 1118 insertions(+), 1105 deletions(-) delete mode 100644 absl/base/internal/exponential_biased.cc delete mode 100644 absl/base/internal/exponential_biased.h delete mode 100644 absl/base/internal/exponential_biased_test.cc delete mode 100644 absl/base/internal/periodic_sampler.cc delete mode 100644 absl/base/internal/periodic_sampler.h delete mode 100644 absl/base/internal/periodic_sampler_benchmark.cc delete mode 100644 absl/base/internal/periodic_sampler_test.cc create mode 100644 absl/profiling/internal/exponential_biased.cc create mode 100644 absl/profiling/internal/exponential_biased.h create mode 100644 absl/profiling/internal/exponential_biased_test.cc create mode 100644 absl/profiling/internal/periodic_sampler.cc create mode 100644 absl/profiling/internal/periodic_sampler.h create mode 100644 absl/profiling/internal/periodic_sampler_benchmark.cc create mode 100644 absl/profiling/internal/periodic_sampler_test.cc diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 056343e5..fa323ff8 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -17,8 +17,6 @@ set(ABSL_INTERNAL_DLL_FILES "base/internal/dynamic_annotations.h" "base/internal/endian.h" "base/internal/errno_saver.h" - "base/internal/exponential_biased.cc" - "base/internal/exponential_biased.h" "base/internal/fast_type_id.h" "base/internal/hide_ptr.h" "base/internal/identity.h" @@ -28,8 +26,6 @@ set(ABSL_INTERNAL_DLL_FILES "base/internal/low_level_alloc.h" "base/internal/low_level_scheduling.h" "base/internal/per_thread_tls.h" - "base/internal/periodic_sampler.cc" - "base/internal/periodic_sampler.h" "base/internal/pretty_function.h" "base/internal/raw_logging.cc" "base/internal/raw_logging.h" @@ -133,6 +129,10 @@ set(ABSL_INTERNAL_DLL_FILES "numeric/int128.h" "numeric/internal/bits.h" "numeric/internal/representation.h" + "profiling/internal/exponential_biased.cc" + "profiling/internal/exponential_biased.h" + "profiling/internal/periodic_sampler.cc" + "profiling/internal/periodic_sampler.h" "profiling/internal/sample_recorder.h" "random/bernoulli_distribution.h" "random/beta_distribution.h" diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 65ff0dde..8b09b6e3 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -593,75 +593,6 @@ cc_test( ], ) -cc_library( - name = "exponential_biased", - srcs = ["internal/exponential_biased.cc"], - hdrs = ["internal/exponential_biased.h"], - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = [ - "//absl:__subpackages__", - ], - deps = [ - ":config", - ":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, - deps = [ - ":core_headers", - ":exponential_biased", - ], -) - -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 = [ - ":core_headers", - ":periodic_sampler", - "@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 = [ - ":core_headers", - ":periodic_sampler", - "@com_github_google_benchmark//:benchmark_main", - ], -) - cc_library( name = "scoped_set_env", testonly = 1, diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 7d56aa13..c7233cb3 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -519,60 +519,6 @@ absl_cc_test( GTest::gtest_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 -) - absl_cc_library( NAME scoped_set_env diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc deleted file mode 100644 index 05aeea56..00000000 --- a/absl/base/internal/exponential_biased.cc +++ /dev/null @@ -1,93 +0,0 @@ -// 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/base/internal/exponential_biased.h" - -#include - -#include -#include -#include -#include - -#include "absl/base/attributes.h" -#include "absl/base/optimization.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -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(); - } - - 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(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(std::numeric_limits::max() / 2)) { - // Assume huge values are bias neutral, retain bias for next call. - return std::numeric_limits::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 global_rand(0); - uint64_t r = reinterpret_cast(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 base_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/base/internal/exponential_biased.h b/absl/base/internal/exponential_biased.h deleted file mode 100644 index a81f10e2..00000000 --- a/absl/base/internal/exponential_biased.h +++ /dev/null @@ -1,130 +0,0 @@ -// 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_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ -#define ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ - -#include - -#include "absl/base/config.h" -#include "absl/base/macros.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_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(0)) << prng_mod_power); - return (prng_mult * rnd + prng_add) & prng_mod_mask; -} - -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_ diff --git a/absl/base/internal/exponential_biased_test.cc b/absl/base/internal/exponential_biased_test.cc deleted file mode 100644 index 075583ca..00000000 --- a/absl/base/internal/exponential_biased_test.cc +++ /dev/null @@ -1,199 +0,0 @@ -// 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/base/internal/exponential_biased.h" - -#include - -#include -#include -#include - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/strings/str_cat.h" - -using ::testing::Ge; - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_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& 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(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& 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({ - 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(1) << 48; - // Initialize. - for (int i = 1; i <= 20; i++) { - x = ExponentialBiased::NextRandom(x); - } - std::vector 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 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(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 base_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/base/internal/periodic_sampler.cc b/absl/base/internal/periodic_sampler.cc deleted file mode 100644 index 520dabba..00000000 --- a/absl/base/internal/periodic_sampler.cc +++ /dev/null @@ -1,53 +0,0 @@ -// 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/base/internal/periodic_sampler.h" - -#include - -#include "absl/base/internal/exponential_biased.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_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(-GetExponentialBiased(current_period)); - if (static_cast(stride_) < -1) { - ++stride_; - return false; - } - } - - stride_ = static_cast(-GetExponentialBiased(current_period)); - return true; -} - -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/base/internal/periodic_sampler.h b/absl/base/internal/periodic_sampler.h deleted file mode 100644 index f8a86796..00000000 --- a/absl/base/internal/periodic_sampler.h +++ /dev/null @@ -1,211 +0,0 @@ -// 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_BASE_INTERNAL_PERIODIC_SAMPLER_H_ -#define ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_ - -#include - -#include - -#include "absl/base/internal/exponential_biased.h" -#include "absl/base/optimization.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_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(++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; - ExponentialBiased rng_; -}; - -inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept { - // See comments on `stride_` for the unsigned increment / signed compare. - if (ABSL_PREDICT_TRUE(static_cast(++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 -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 period_; -}; - -template -std::atomic PeriodicSampler::period_(default_period); - -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_ diff --git a/absl/base/internal/periodic_sampler_benchmark.cc b/absl/base/internal/periodic_sampler_benchmark.cc deleted file mode 100644 index 5ad469ce..00000000 --- a/absl/base/internal/periodic_sampler_benchmark.cc +++ /dev/null @@ -1,79 +0,0 @@ -// 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 "benchmark/benchmark.h" -#include "absl/base/internal/periodic_sampler.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_internal { -namespace { - -template -void BM_Sample(Sampler* sampler, benchmark::State& state) { - for (auto _ : state) { - benchmark::DoNotOptimize(sampler); - benchmark::DoNotOptimize(sampler->Sample()); - } -} - -template -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 sampler; - BM_Sample(&sampler, state); -} -BENCHMARK(BM_PeriodicSampler_TinySample); - -void BM_PeriodicSampler_ShortSample(benchmark::State& state) { - struct Tag {}; - PeriodicSampler sampler; - BM_Sample(&sampler, state); -} -BENCHMARK(BM_PeriodicSampler_ShortSample); - -void BM_PeriodicSampler_LongSample(benchmark::State& state) { - struct Tag {}; - PeriodicSampler sampler; - BM_Sample(&sampler, state); -} -BENCHMARK(BM_PeriodicSampler_LongSample); - -void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) { - struct Tag {}; - PeriodicSampler sampler; - BM_SampleMinunumInlined(&sampler, state); -} -BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined); - -void BM_PeriodicSampler_Disabled(benchmark::State& state) { - struct Tag {}; - PeriodicSampler sampler; - BM_Sample(&sampler, state); -} -BENCHMARK(BM_PeriodicSampler_Disabled); - -} // namespace -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/base/internal/periodic_sampler_test.cc b/absl/base/internal/periodic_sampler_test.cc deleted file mode 100644 index 3b301e37..00000000 --- a/absl/base/internal/periodic_sampler_test.cc +++ /dev/null @@ -1,177 +0,0 @@ -// 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/base/internal/periodic_sampler.h" - -#include // 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 base_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 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 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 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 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 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 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 sampler; - (void)sampler; -} - -TEST(PeriodicSamplerTest, DefaultPeriod0) { - struct Tag {}; - PeriodicSampler sampler; - EXPECT_THAT(sampler.period(), Eq(0)); -} - -TEST(PeriodicSamplerTest, DefaultPeriod) { - struct Tag {}; - PeriodicSampler sampler; - EXPECT_THAT(sampler.period(), Eq(100)); -} - -TEST(PeriodicSamplerTest, SetGlobalPeriod) { - struct Tag1 {}; - struct Tag2 {}; - PeriodicSampler sampler1; - PeriodicSampler sampler2; - - EXPECT_THAT(sampler1.period(), Eq(25)); - EXPECT_THAT(sampler2.period(), Eq(50)); - - std::thread thread([] { - PeriodicSampler sampler1; - PeriodicSampler 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 base_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h index c73b5e09..ac40daff 100644 --- a/absl/base/internal/spinlock.h +++ b/absl/base/internal/spinlock.h @@ -16,13 +16,15 @@ // Most users requiring mutual exclusion should use Mutex. // SpinLock is provided for use in two situations: -// - for use in code that Mutex itself depends on +// - for use by Abseil internal code that Mutex itself depends on // - for async signal safety (see below) // SpinLock is async signal safe. If a spinlock is used within a signal // handler, all code that acquires the lock must ensure that the signal cannot // arrive while they are holding the lock. Typically, this is done by blocking // the signal. +// +// Threads waiting on a SpinLock may be woken in an arbitrary order. #ifndef ABSL_BASE_INTERNAL_SPINLOCK_H_ #define ABSL_BASE_INTERNAL_SPINLOCK_H_ diff --git a/absl/base/internal/spinlock_wait.h b/absl/base/internal/spinlock_wait.h index 579bd09f..9a1adcda 100644 --- a/absl/base/internal/spinlock_wait.h +++ b/absl/base/internal/spinlock_wait.h @@ -39,6 +39,8 @@ struct SpinLockWaitTransition { // satisfying 0<=i *w, int n, const SpinLockWaitTransition trans[], SchedulingMode scheduling_mode); diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index c9d387d6..9e3bc06a 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -510,9 +510,9 @@ cc_library( ":have_sse", "//absl/base", "//absl/base:core_headers", - "//absl/base:exponential_biased", "//absl/debugging:stacktrace", "//absl/memory", + "//absl/profiling:exponential_biased", "//absl/profiling:sample_recorder", "//absl/synchronization", "//absl/utility", diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 4b133705..7070912e 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc @@ -21,10 +21,10 @@ #include #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" +#include "absl/profiling/internal/exponential_biased.h" #include "absl/profiling/internal/sample_recorder.h" #include "absl/synchronization/mutex.h" @@ -40,7 +40,7 @@ ABSL_CONST_INIT std::atomic g_hashtablez_enabled{ ABSL_CONST_INIT std::atomic g_hashtablez_sample_parameter{1 << 10}; #if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) -ABSL_PER_THREAD_TLS_KEYWORD absl::base_internal::ExponentialBiased +ABSL_PER_THREAD_TLS_KEYWORD absl::profiling_internal::ExponentialBiased g_exponential_biased_generator; #endif diff --git a/absl/debugging/BUILD.bazel b/absl/debugging/BUILD.bazel index b536a044..b503da51 100644 --- a/absl/debugging/BUILD.bazel +++ b/absl/debugging/BUILD.bazel @@ -183,6 +183,7 @@ cc_library( ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = ["//visibility:private"], deps = [ "//absl/base:config", "//absl/base:core_headers", @@ -197,6 +198,7 @@ cc_library( srcs = ["internal/demangle.cc"], hdrs = ["internal/demangle.h"], copts = ABSL_DEFAULT_COPTS, + visibility = ["//visibility:private"], deps = [ "//absl/base", "//absl/base:config", 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 + +#include +#include +#include +#include + +#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(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(std::numeric_limits::max() / 2)) { + // Assume huge values are bias neutral, retain bias for next call. + return std::numeric_limits::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 global_rand(0); + uint64_t r = reinterpret_cast(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 + +#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(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 + +#include +#include +#include + +#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& 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(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& 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({ + 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(1) << 48; + // Initialize. + for (int i = 1; i <= 20; i++) { + x = ExponentialBiased::NextRandom(x); + } + std::vector 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 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(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 + +#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(-GetExponentialBiased(current_period)); + if (static_cast(stride_) < -1) { + ++stride_; + return false; + } + } + + stride_ = static_cast(-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 + +#include + +#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(++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(++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 +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 period_; +}; + +template +std::atomic PeriodicSampler::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 +void BM_Sample(Sampler* sampler, benchmark::State& state) { + for (auto _ : state) { + benchmark::DoNotOptimize(sampler); + benchmark::DoNotOptimize(sampler->Sample()); + } +} + +template +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 sampler; + BM_Sample(&sampler, state); +} +BENCHMARK(BM_PeriodicSampler_TinySample); + +void BM_PeriodicSampler_ShortSample(benchmark::State& state) { + struct Tag {}; + PeriodicSampler sampler; + BM_Sample(&sampler, state); +} +BENCHMARK(BM_PeriodicSampler_ShortSample); + +void BM_PeriodicSampler_LongSample(benchmark::State& state) { + struct Tag {}; + PeriodicSampler sampler; + BM_Sample(&sampler, state); +} +BENCHMARK(BM_PeriodicSampler_LongSample); + +void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) { + struct Tag {}; + PeriodicSampler sampler; + BM_SampleMinunumInlined(&sampler, state); +} +BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined); + +void BM_PeriodicSampler_Disabled(benchmark::State& state) { + struct Tag {}; + PeriodicSampler 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 // 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 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 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 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 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 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 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 sampler; + (void)sampler; +} + +TEST(PeriodicSamplerTest, DefaultPeriod0) { + struct Tag {}; + PeriodicSampler sampler; + EXPECT_THAT(sampler.period(), Eq(0)); +} + +TEST(PeriodicSamplerTest, DefaultPeriod) { + struct Tag {}; + PeriodicSampler sampler; + EXPECT_THAT(sampler.period(), Eq(100)); +} + +TEST(PeriodicSamplerTest, SetGlobalPeriod) { + struct Tag1 {}; + struct Tag2 {}; + PeriodicSampler sampler1; + PeriodicSampler sampler2; + + EXPECT_THAT(sampler1.period(), Eq(25)); + EXPECT_THAT(sampler2.period(), Eq(50)); + + std::thread thread([] { + PeriodicSampler sampler1; + PeriodicSampler 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 diff --git a/absl/status/status.h b/absl/status/status.h index 638b9ca4..9bb45382 100644 --- a/absl/status/status.h +++ b/absl/status/status.h @@ -494,7 +494,7 @@ class Status final { // Returns the error message associated with this error code, if available. // Note that this message rarely describes the error code. It is not unusual // for the error message to be the empty string. As a result, prefer - // `Status::ToString()` for debug logging. + // `operator<<` or `Status::ToString()` for debug logging. absl::string_view message() const; friend bool operator==(const Status&, const Status&); diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index f9735b4b..c45a671e 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -508,8 +508,8 @@ cc_library( deps = [ "//absl/base:config", "//absl/base:core_headers", - "//absl/base:exponential_biased", "//absl/base:raw_logging_internal", + "//absl/profiling:exponential_biased", ], ) diff --git a/absl/strings/internal/cordz_functions.cc b/absl/strings/internal/cordz_functions.cc index 48369933..20d314f0 100644 --- a/absl/strings/internal/cordz_functions.cc +++ b/absl/strings/internal/cordz_functions.cc @@ -21,8 +21,8 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/base/internal/exponential_biased.h" #include "absl/base/internal/raw_logging.h" +#include "absl/profiling/internal/exponential_biased.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -48,7 +48,7 @@ constexpr int64_t kIntervalIfDisabled = 1 << 16; ABSL_ATTRIBUTE_NOINLINE bool cordz_should_profile_slow() { - thread_local absl::base_internal::ExponentialBiased + thread_local absl::profiling_internal::ExponentialBiased exponential_biased_generator; int32_t mean_interval = get_cordz_mean_interval(); diff --git a/absl/synchronization/mutex_test.cc b/absl/synchronization/mutex_test.cc index f8fbf948..4f403176 100644 --- a/absl/synchronization/mutex_test.cc +++ b/absl/synchronization/mutex_test.cc @@ -26,6 +26,7 @@ #include #include #include // NOLINT(build/c++11) +#include #include #include "gtest/gtest.h" @@ -870,33 +871,6 @@ TEST(Mutex, LockedMutexDestructionBug) ABSL_NO_THREAD_SAFETY_ANALYSIS { } } -// -------------------------------------------------------- -// Test for bug with pattern of readers using a condvar. The bug was that if a -// reader went to sleep on a condition variable while one or more other readers -// held the lock, but there were no waiters, the reader count (held in the -// mutex word) would be lost. (This is because Enqueue() had at one time -// always placed the thread on the Mutex queue. Later (CL 4075610), to -// tolerate re-entry into Mutex from a Condition predicate, Enqueue() was -// changed so that it could also place a thread on a condition-variable. This -// introduced the case where Enqueue() returned with an empty queue, and this -// case was handled incorrectly in one place.) - -static void ReaderForReaderOnCondVar(absl::Mutex *mu, absl::CondVar *cv, - int *running) { - std::random_device dev; - std::mt19937 gen(dev()); - std::uniform_int_distribution random_millis(0, 15); - mu->ReaderLock(); - while (*running == 3) { - absl::SleepFor(absl::Milliseconds(random_millis(gen))); - cv->WaitWithTimeout(mu, absl::Milliseconds(random_millis(gen))); - } - mu->ReaderUnlock(); - mu->Lock(); - (*running)--; - mu->Unlock(); -} - struct True { template bool operator()(Args...) const { @@ -945,6 +919,33 @@ TEST(Mutex, FunctorCondition) { } } +// -------------------------------------------------------- +// Test for bug with pattern of readers using a condvar. The bug was that if a +// reader went to sleep on a condition variable while one or more other readers +// held the lock, but there were no waiters, the reader count (held in the +// mutex word) would be lost. (This is because Enqueue() had at one time +// always placed the thread on the Mutex queue. Later (CL 4075610), to +// tolerate re-entry into Mutex from a Condition predicate, Enqueue() was +// changed so that it could also place a thread on a condition-variable. This +// introduced the case where Enqueue() returned with an empty queue, and this +// case was handled incorrectly in one place.) + +static void ReaderForReaderOnCondVar(absl::Mutex *mu, absl::CondVar *cv, + int *running) { + std::random_device dev; + std::mt19937 gen(dev()); + std::uniform_int_distribution random_millis(0, 15); + mu->ReaderLock(); + while (*running == 3) { + absl::SleepFor(absl::Milliseconds(random_millis(gen))); + cv->WaitWithTimeout(mu, absl::Milliseconds(random_millis(gen))); + } + mu->ReaderUnlock(); + mu->Lock(); + (*running)--; + mu->Unlock(); +} + static bool IntIsZero(int *x) { return *x == 0; } // Test for reader waiting condition variable when there are other readers diff --git a/absl/time/internal/cctz/src/cctz_benchmark.cc b/absl/time/internal/cctz/src/cctz_benchmark.cc index 4e39188f..6770ad6b 100644 --- a/absl/time/internal/cctz/src/cctz_benchmark.cc +++ b/absl/time/internal/cctz/src/cctz_benchmark.cc @@ -648,6 +648,7 @@ const char* const kTimeZoneNames[] = {"Africa/Abidjan", "Pacific/Guam", "Pacific/Honolulu", "Pacific/Johnston", + "Pacific/Kanton", "Pacific/Kiritimati", "Pacific/Kosrae", "Pacific/Kwajalein", diff --git a/absl/time/internal/cctz/src/time_zone_lookup_test.cc b/absl/time/internal/cctz/src/time_zone_lookup_test.cc index 6948c3ea..8751b346 100644 --- a/absl/time/internal/cctz/src/time_zone_lookup_test.cc +++ b/absl/time/internal/cctz/src/time_zone_lookup_test.cc @@ -579,6 +579,7 @@ const char* const kTimeZoneNames[] = {"Africa/Abidjan", "Pacific/Guam", "Pacific/Honolulu", "Pacific/Johnston", + "Pacific/Kanton", "Pacific/Kiritimati", "Pacific/Kosrae", "Pacific/Kwajalein", diff --git a/absl/time/internal/cctz/testdata/version b/absl/time/internal/cctz/testdata/version index ba5601ef..51191b57 100644 --- a/absl/time/internal/cctz/testdata/version +++ b/absl/time/internal/cctz/testdata/version @@ -1 +1 @@ -2021b +2021c diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Atlantic/Jan_Mayen b/absl/time/internal/cctz/testdata/zoneinfo/Atlantic/Jan_Mayen index 465546bd..dfc50957 100644 Binary files a/absl/time/internal/cctz/testdata/zoneinfo/Atlantic/Jan_Mayen and b/absl/time/internal/cctz/testdata/zoneinfo/Atlantic/Jan_Mayen differ -- cgit v1.2.3