1 // Copyright 2019 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
16 #define ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
17
18 #include <stdint.h>
19
20 #include "absl/base/config.h"
21 #include "absl/base/macros.h"
22
23 namespace absl {
24 ABSL_NAMESPACE_BEGIN
25 namespace base_internal {
26
27 // ExponentialBiased provides a small and fast random number generator for a
28 // rounded exponential distribution. This generator manages very little state,
29 // and imposes no synchronization overhead. This makes it useful in specialized
30 // scenarios requiring minimum overhead, such as stride based periodic sampling.
31 //
32 // ExponentialBiased provides two closely related functions, GetSkipCount() and
33 // GetStride(), both returning a rounded integer defining a number of events
34 // required before some event with a given mean probability occurs.
35 //
36 // The distribution is useful to generate a random wait time or some periodic
37 // event with a given mean probability. For example, if an action is supposed to
38 // happen on average once every 'N' events, then we can get a random 'stride'
39 // counting down how long before the event to happen. For example, if we'd want
40 // to sample one in every 1000 'Frobber' calls, our code could look like this:
41 //
42 // Frobber::Frobber() {
43 // stride_ = exponential_biased_.GetStride(1000);
44 // }
45 //
46 // void Frobber::Frob(int arg) {
47 // if (--stride == 0) {
48 // SampleFrob(arg);
49 // stride_ = exponential_biased_.GetStride(1000);
50 // }
51 // ...
52 // }
53 //
54 // The rounding of the return value creates a bias, especially for smaller means
55 // where the distribution of the fraction is not evenly distributed. We correct
56 // this bias by tracking the fraction we rounded up or down on each iteration,
57 // effectively tracking the distance between the cumulative value, and the
58 // rounded cumulative value. For example, given a mean of 2:
59 //
60 // raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923
61 // raw = 0.14624, cumulative = 1.77701, rounded = 2, bias = 0.14624
62 // raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805
63 // raw = 0.24206, cumulative = 6.95101, rounded = 7, bias = 0.24206
64 // etc...
65 //
66 // Adjusting with rounding bias is relatively trivial:
67 //
68 // double value = bias_ + exponential_distribution(mean)();
69 // double rounded_value = std::round(value);
70 // bias_ = value - rounded_value;
71 // return rounded_value;
72 //
73 // This class is thread-compatible.
74 class ExponentialBiased {
75 public:
76 // The number of bits set by NextRandom.
77 static constexpr int kPrngNumBits = 48;
78
79 // `GetSkipCount()` returns the number of events to skip before some chosen
80 // event happens. For example, randomly tossing a coin, we will on average
81 // throw heads once before we get tails. We can simulate random coin tosses
82 // using GetSkipCount() as:
83 //
84 // ExponentialBiased eb;
85 // for (...) {
86 // int number_of_heads_before_tail = eb.GetSkipCount(1);
87 // for (int flips = 0; flips < number_of_heads_before_tail; ++flips) {
88 // printf("head...");
89 // }
90 // printf("tail\n");
91 // }
92 //
93 int64_t GetSkipCount(int64_t mean);
94
95 // GetStride() returns the number of events required for a specific event to
96 // happen. See the class comments for a usage example. `GetStride()` is
97 // equivalent to `GetSkipCount(mean - 1) + 1`. When to use `GetStride()` or
98 // `GetSkipCount()` depends mostly on what best fits the use case.
99 int64_t GetStride(int64_t mean);
100
101 // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1]
102 //
103 // This is public to enable testing.
104 static uint64_t NextRandom(uint64_t rnd);
105
106 private:
107 void Initialize();
108
109 uint64_t rng_{0};
110 double bias_{0};
111 bool initialized_{false};
112 };
113
114 // Returns the next prng value.
115 // pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48
116 // This is the lrand64 generator.
NextRandom(uint64_t rnd)117 inline uint64_t ExponentialBiased::NextRandom(uint64_t rnd) {
118 const uint64_t prng_mult = uint64_t{0x5DEECE66D};
119 const uint64_t prng_add = 0xB;
120 const uint64_t prng_mod_power = 48;
121 const uint64_t prng_mod_mask =
122 ~((~static_cast<uint64_t>(0)) << prng_mod_power);
123 return (prng_mult * rnd + prng_add) & prng_mod_mask;
124 }
125
126 } // namespace base_internal
127 ABSL_NAMESPACE_END
128 } // namespace absl
129
130 #endif // ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
131