chromium/third_party/abseil-cpp/absl/profiling/internal/exponential_biased.h

// Copyright 2019 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_
#define ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_

#include <stdint.h>

#include "absl/base/config.h"
#include "absl/base/macros.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace profiling_internal {

// ExponentialBiased provides a small and fast random number generator for a
// rounded exponential distribution. This generator manages very little state,
// and imposes no synchronization overhead. This makes it useful in specialized
// scenarios requiring minimum overhead, such as stride based periodic sampling.
//
// ExponentialBiased provides two closely related functions, GetSkipCount() and
// GetStride(), both returning a rounded integer defining a number of events
// required before some event with a given mean probability occurs.
//
// The distribution is useful to generate a random wait time or some periodic
// event with a given mean probability. For example, if an action is supposed to
// happen on average once every 'N' events, then we can get a random 'stride'
// counting down how long before the event to happen. For example, if we'd want
// to sample one in every 1000 'Frobber' calls, our code could look like this:
//
//   Frobber::Frobber() {
//     stride_ = exponential_biased_.GetStride(1000);
//   }
//
//   void Frobber::Frob(int arg) {
//     if (--stride == 0) {
//       SampleFrob(arg);
//       stride_ = exponential_biased_.GetStride(1000);
//     }
//     ...
//   }
//
// The rounding of the return value creates a bias, especially for smaller means
// where the distribution of the fraction is not evenly distributed. We correct
// this bias by tracking the fraction we rounded up or down on each iteration,
// effectively tracking the distance between the cumulative value, and the
// rounded cumulative value. For example, given a mean of 2:
//
//   raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923
//   raw = 0.14624, cumulative = 1.77701, rounded = 2, bias =  0.14624
//   raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805
//   raw = 0.24206, cumulative = 6.95101, rounded = 7, bias =  0.24206
//   etc...
//
// Adjusting with rounding bias is relatively trivial:
//
//    double value = bias_ + exponential_distribution(mean)();
//    double rounded_value = std::rint(value);
//    bias_ = value - rounded_value;
//    return rounded_value;
//
// This class is thread-compatible.
class ExponentialBiased { … };

// 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) { … }

}  // namespace profiling_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_PROFILING_INTERNAL_EXPONENTIAL_BIASED_H_