summaryrefslogtreecommitdiff
path: root/absl/profiling/internal/exponential_biased.cc
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-10-06 17:55:30 -0700
committerGravatar rogeeff <rogeeff@google.com>2021-10-07 00:46:55 -0400
commita59b4daa07a14326d2ceb28cc6d0e079feea3338 (patch)
treedfde1cad62864dffeafd161aba4960ce0bf8aa99 /absl/profiling/internal/exponential_biased.cc
parentae0f4c266095c9003786cd571bc1fb72544104a1 (diff)
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
Diffstat (limited to 'absl/profiling/internal/exponential_biased.cc')
-rw-r--r--absl/profiling/internal/exponential_biased.cc93
1 files changed, 93 insertions, 0 deletions
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