about summary refs log tree commit diff
path: root/third_party/abseil_cpp/absl/base/internal/exponential_biased.h
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/abseil_cpp/absl/base/internal/exponential_biased.h')
-rw-r--r--third_party/abseil_cpp/absl/base/internal/exponential_biased.h130
1 files changed, 0 insertions, 130 deletions
diff --git a/third_party/abseil_cpp/absl/base/internal/exponential_biased.h b/third_party/abseil_cpp/absl/base/internal/exponential_biased.h
deleted file mode 100644
index 94f79a3378db..000000000000
--- a/third_party/abseil_cpp/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 <stdint.h>
-
-#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::round(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 base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
-
-#endif  // ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_