| // 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. | |
| namespace absl { | |
| ABSL_NAMESPACE_BEGIN | |
| namespace profiling_internal { | |
| // ExponentialBiased provides a small and fast random number generator for a | |
| // rounded exponential distribution. This generator manages very little state, | |
| // and imposes no synchronization overhead. This makes it useful in specialized | |
| // scenarios requiring minimum overhead, such as stride based periodic sampling. | |
| // | |
| // ExponentialBiased provides two closely related functions, GetSkipCount() and | |
| // GetStride(), both returning a rounded integer defining a number of events | |
| // required before some event with a given mean probability occurs. | |
| // | |
| // The distribution is useful to generate a random wait time or some periodic | |
| // event with a given mean probability. For example, if an action is supposed to | |
| // happen on average once every 'N' events, then we can get a random 'stride' | |
| // counting down how long before the event to happen. For example, if we'd want | |
| // to sample one in every 1000 'Frobber' calls, our code could look like this: | |
| // | |
| // Frobber::Frobber() { | |
| // stride_ = exponential_biased_.GetStride(1000); | |
| // } | |
| // | |
| // void Frobber::Frob(int arg) { | |
| // if (--stride == 0) { | |
| // SampleFrob(arg); | |
| // stride_ = exponential_biased_.GetStride(1000); | |
| // } | |
| // ... | |
| // } | |
| // | |
| // The rounding of the return value creates a bias, especially for smaller means | |
| // where the distribution of the fraction is not evenly distributed. We correct | |
| // this bias by tracking the fraction we rounded up or down on each iteration, | |
| // effectively tracking the distance between the cumulative value, and the | |
| // rounded cumulative value. For example, given a mean of 2: | |
| // | |
| // raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923 | |
| // raw = 0.14624, cumulative = 1.77701, rounded = 2, bias = 0.14624 | |
| // raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805 | |
| // raw = 0.24206, cumulative = 6.95101, rounded = 7, bias = 0.24206 | |
| // etc... | |
| // | |
| // Adjusting with rounding bias is relatively trivial: | |
| // | |
| // double value = bias_ + exponential_distribution(mean)(); | |
| // double rounded_value = std::rint(value); | |
| // bias_ = value - rounded_value; | |
| // return rounded_value; | |
| // | |
| // This class is thread-compatible. | |
| class ExponentialBiased { | |
| public: | |
| // The number of bits set by NextRandom. | |
| static constexpr int kPrngNumBits = 48; | |
| // `GetSkipCount()` returns the number of events to skip before some chosen | |
| // event happens. For example, randomly tossing a coin, we will on average | |
| // throw heads once before we get tails. We can simulate random coin tosses | |
| // using GetSkipCount() as: | |
| // | |
| // ExponentialBiased eb; | |
| // for (...) { | |
| // int number_of_heads_before_tail = eb.GetSkipCount(1); | |
| // for (int flips = 0; flips < number_of_heads_before_tail; ++flips) { | |
| // printf("head..."); | |
| // } | |
| // printf("tail\n"); | |
| // } | |
| // | |
| int64_t GetSkipCount(int64_t mean); | |
| // GetStride() returns the number of events required for a specific event to | |
| // happen. See the class comments for a usage example. `GetStride()` is | |
| // equivalent to `GetSkipCount(mean - 1) + 1`. When to use `GetStride()` or | |
| // `GetSkipCount()` depends mostly on what best fits the use case. | |
| int64_t GetStride(int64_t mean); | |
| // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1] | |
| // | |
| // This is public to enable testing. | |
| static uint64_t NextRandom(uint64_t rnd); | |
| private: | |
| void Initialize(); | |
| uint64_t rng_{0}; | |
| double bias_{0}; | |
| bool initialized_{false}; | |
| }; | |
| // Returns the next prng value. | |
| // pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48 | |
| // This is the lrand64 generator. | |
| inline uint64_t ExponentialBiased::NextRandom(uint64_t rnd) { | |
| const uint64_t prng_mult = uint64_t{0x5DEECE66D}; | |
| const uint64_t prng_add = 0xB; | |
| const uint64_t prng_mod_power = 48; | |
| const uint64_t prng_mod_mask = | |
| ~((~static_cast<uint64_t>(0)) << prng_mod_power); | |
| return (prng_mult * rnd + prng_add) & prng_mod_mask; | |
| } | |
| } // namespace profiling_internal | |
| ABSL_NAMESPACE_END | |
| } // namespace absl | |