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 #include "absl/profiling/internal/exponential_biased.h"
16
17 #include <stddef.h>
18
19 #include <cmath>
20 #include <cstdint>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "gtest/gtest.h"
25 #include "absl/strings/str_cat.h"
26
27 using ::testing::Ge;
28
29 namespace absl {
30 ABSL_NAMESPACE_BEGIN
31 namespace profiling_internal {
32 namespace {
33
34 MATCHER_P2(IsBetween, a, b,
35 absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a,
36 " and ", b)) {
37 return a <= arg && arg <= b;
38 }
39
40 // Tests of the quality of the random numbers generated
41 // This uses the Anderson Darling test for uniformity.
42 // See "Evaluating the Anderson-Darling Distribution" by Marsaglia
43 // for details.
44
45 // Short cut version of ADinf(z), z>0 (from Marsaglia)
46 // This returns the p-value for Anderson Darling statistic in
47 // the limit as n-> infinity. For finite n, apply the error fix below.
AndersonDarlingInf(double z)48 double AndersonDarlingInf(double z) {
49 if (z < 2) {
50 return exp(-1.2337141 / z) / sqrt(z) *
51 (2.00012 +
52 (0.247105 -
53 (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) *
54 z) *
55 z);
56 }
57 return exp(
58 -exp(1.0776 -
59 (2.30695 -
60 (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) *
61 z));
62 }
63
64 // Corrects the approximation error in AndersonDarlingInf for small values of n
65 // Add this to AndersonDarlingInf to get a better approximation
66 // (from Marsaglia)
AndersonDarlingErrFix(int n,double x)67 double AndersonDarlingErrFix(int n, double x) {
68 if (x > 0.8) {
69 return (-130.2137 +
70 (745.2337 -
71 (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) *
72 x) /
73 n;
74 }
75 double cutoff = 0.01265 + 0.1757 / n;
76 if (x < cutoff) {
77 double t = x / cutoff;
78 t = sqrt(t) * (1 - t) * (49 * t - 102);
79 return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n;
80 } else {
81 double t = (x - cutoff) / (0.8 - cutoff);
82 t = -0.00022633 +
83 (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) *
84 t;
85 return t * (0.04213 + 0.01365 / n) / n;
86 }
87 }
88
89 // Returns the AndersonDarling p-value given n and the value of the statistic
AndersonDarlingPValue(int n,double z)90 double AndersonDarlingPValue(int n, double z) {
91 double ad = AndersonDarlingInf(z);
92 double errfix = AndersonDarlingErrFix(n, ad);
93 return ad + errfix;
94 }
95
AndersonDarlingStatistic(const std::vector<double> & random_sample)96 double AndersonDarlingStatistic(const std::vector<double>& random_sample) {
97 size_t n = random_sample.size();
98 double ad_sum = 0;
99 for (size_t i = 0; i < n; i++) {
100 ad_sum += (2 * i + 1) *
101 std::log(random_sample[i] * (1 - random_sample[n - 1 - i]));
102 }
103 const auto n_as_double = static_cast<double>(n);
104 double ad_statistic = -n_as_double - 1 / n_as_double * ad_sum;
105 return ad_statistic;
106 }
107
108 // Tests if the array of doubles is uniformly distributed.
109 // Returns the p-value of the Anderson Darling Statistic
110 // for the given set of sorted random doubles
111 // See "Evaluating the Anderson-Darling Distribution" by
112 // Marsaglia and Marsaglia for details.
AndersonDarlingTest(const std::vector<double> & random_sample)113 double AndersonDarlingTest(const std::vector<double>& random_sample) {
114 double ad_statistic = AndersonDarlingStatistic(random_sample);
115 double p = AndersonDarlingPValue(static_cast<int>(random_sample.size()),
116 ad_statistic);
117 return p;
118 }
119
TEST(ExponentialBiasedTest,CoinTossDemoWithGetSkipCount)120 TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) {
121 ExponentialBiased eb;
122 for (int runs = 0; runs < 10; ++runs) {
123 for (int64_t flips = eb.GetSkipCount(1); flips > 0; --flips) {
124 printf("head...");
125 }
126 printf("tail\n");
127 }
128 int heads = 0;
129 for (int i = 0; i < 10000000; i += 1 + eb.GetSkipCount(1)) {
130 ++heads;
131 }
132 printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000);
133 }
134
TEST(ExponentialBiasedTest,SampleDemoWithStride)135 TEST(ExponentialBiasedTest, SampleDemoWithStride) {
136 ExponentialBiased eb;
137 int64_t stride = eb.GetStride(10);
138 int samples = 0;
139 for (int i = 0; i < 10000000; ++i) {
140 if (--stride == 0) {
141 ++samples;
142 stride = eb.GetStride(10);
143 }
144 }
145 printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000);
146 }
147
148
149 // Testing that NextRandom generates uniform random numbers. Applies the
150 // Anderson-Darling test for uniformity
TEST(ExponentialBiasedTest,TestNextRandom)151 TEST(ExponentialBiasedTest, TestNextRandom) {
152 for (auto n : std::vector<size_t>({
153 10, // Check short-range correlation
154 100, 1000,
155 10000 // Make sure there's no systemic error
156 })) {
157 uint64_t x = 1;
158 // This assumes that the prng returns 48 bit numbers
159 uint64_t max_prng_value = static_cast<uint64_t>(1) << 48;
160 // Initialize.
161 for (int i = 1; i <= 20; i++) {
162 x = ExponentialBiased::NextRandom(x);
163 }
164 std::vector<uint64_t> int_random_sample(n);
165 // Collect samples
166 for (size_t i = 0; i < n; i++) {
167 int_random_sample[i] = x;
168 x = ExponentialBiased::NextRandom(x);
169 }
170 // First sort them...
171 std::sort(int_random_sample.begin(), int_random_sample.end());
172 std::vector<double> random_sample(n);
173 // Convert them to uniform randoms (in the range [0,1])
174 for (size_t i = 0; i < n; i++) {
175 random_sample[i] =
176 static_cast<double>(int_random_sample[i]) / max_prng_value;
177 }
178 // Now compute the Anderson-Darling statistic
179 double ad_pvalue = AndersonDarlingTest(random_sample);
180 EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001)
181 << "prng is not uniform: n = " << n << " p = " << ad_pvalue;
182 }
183 }
184
185 // The generator needs to be available as a thread_local and as a static
186 // variable.
TEST(ExponentialBiasedTest,InitializationModes)187 TEST(ExponentialBiasedTest, InitializationModes) {
188 ABSL_CONST_INIT static ExponentialBiased eb_static;
189 EXPECT_THAT(eb_static.GetSkipCount(2), Ge(0));
190
191 #ifdef ABSL_HAVE_THREAD_LOCAL
192 thread_local ExponentialBiased eb_thread;
193 EXPECT_THAT(eb_thread.GetSkipCount(2), Ge(0));
194 #endif
195
196 ExponentialBiased eb_stack;
197 EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0));
198 }
199
200 } // namespace
201 } // namespace profiling_internal
202 ABSL_NAMESPACE_END
203 } // namespace absl
204