1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <cstddef>
18 #include <random>
19 #include <vector>
20
21 #include <benchmark/benchmark.h>
22
23 #include <audio_utils/Statistics.h>
24
25 template <typename T>
initUniform(std::vector<T> & data,T rangeMin,T rangeMax)26 static void initUniform(std::vector<T> &data, T rangeMin, T rangeMax) {
27 const size_t count = data.capacity();
28 std::minstd_rand gen(count);
29 std::uniform_real_distribution<T> dis(rangeMin, rangeMax);
30 for (auto &datum : data) {
31 datum = dis(gen);
32 }
33 }
34
35 template <typename Stats>
BM_MeanVariance(benchmark::State & state,int iterlimit,int alphalimit)36 static void BM_MeanVariance(benchmark::State& state, int iterlimit, int alphalimit) {
37 const float alpha = 1. - alphalimit * std::numeric_limits<float>::epsilon();
38 Stats stat(alpha);
39 using T = decltype(stat.getMin());
40 constexpr size_t count = 1 << 20; // exactly one "mega" samples from the distribution.
41 constexpr T range = 1.;
42 std::vector<T> data(count);
43 initUniform(data, -range, range);
44
45 // Run the test
46 int iters = 0;
47 while (state.KeepRunning()) {
48 benchmark::DoNotOptimize(data.data());
49 for (const auto &datum : data) {
50 stat.add(datum);
51 }
52 benchmark::ClobberMemory();
53 if (++iters % iterlimit == 0) {
54 printf("%d> alpha:%f mean:%.17g variance:%.17g\n",
55 iters, alpha, (double)stat.getMean(), (double)stat.getPopVariance());
56 stat.reset();
57 }
58 }
59 state.SetComplexityN(count);
60 }
61
62
63 // Test case:
64 // Do we work correctly within the capacity of float statistics when alpha == 1?
65 //
66 // 1 << 23 samples is the mantissa limited capacity of float statistics if alpha == 1.
67 static constexpr int float_iterlimit = 8;
68 // alphalimit of 0 means alpha exactly equals one.
69 static constexpr int alpha_equals_one_alphalimit = 0;
70
71 // benchmark running float
BM_MeanVariance_float_float_float(benchmark::State & state)72 static void BM_MeanVariance_float_float_float(benchmark::State &state) {
73 BM_MeanVariance<android::audio_utils::Statistics<float, float, float>>(state,
74 float_iterlimit, alpha_equals_one_alphalimit);
75 }
76
77 BENCHMARK(BM_MeanVariance_float_float_float);
78
79 // benchmark reference float
BM_RefMeanVariance_float_float(benchmark::State & state)80 static void BM_RefMeanVariance_float_float(benchmark::State &state) {
81 BM_MeanVariance<android::audio_utils::ReferenceStatistics<float, float>>(state,
82 float_iterlimit, alpha_equals_one_alphalimit);
83 }
84
85 BENCHMARK(BM_RefMeanVariance_float_float);
86
87 // benchmark running double
BM_MeanVariance_float_double_double(benchmark::State & state)88 static auto BM_MeanVariance_float_double_double(benchmark::State &state) {
89 BM_MeanVariance<android::audio_utils::Statistics<float, double, double>>(state,
90 float_iterlimit, alpha_equals_one_alphalimit);
91 }
92
93 BENCHMARK(BM_MeanVariance_float_double_double);
94
95 // benchmark reference double
BM_RefMeanVariance_float_double(benchmark::State & state)96 static auto BM_RefMeanVariance_float_double(benchmark::State &state) {
97 BM_MeanVariance<android::audio_utils::ReferenceStatistics<float, double>>(state,
98 float_iterlimit, alpha_equals_one_alphalimit);
99 }
100
101 BENCHMARK(BM_RefMeanVariance_float_double);
102
103 // benchmark running float + kahan
BM_MeanVariance_float_float_Kahan(benchmark::State & state)104 static auto BM_MeanVariance_float_float_Kahan(benchmark::State &state) {
105 BM_MeanVariance<android::audio_utils::Statistics<float, float,
106 android::audio_utils::KahanSum<float>>>(state,
107 float_iterlimit, alpha_equals_one_alphalimit);
108 }
109
110 BENCHMARK(BM_MeanVariance_float_float_Kahan);
111
112 // benchmark running float + Neumaier
BM_MeanVariance_float_float_Neumaier(benchmark::State & state)113 static auto BM_MeanVariance_float_float_Neumaier(benchmark::State &state) {
114 BM_MeanVariance<android::audio_utils::Statistics<float, float,
115 android::audio_utils::NeumaierSum<float>>>(state,
116 float_iterlimit, alpha_equals_one_alphalimit);
117 }
118
119 BENCHMARK(BM_MeanVariance_float_float_Neumaier);
120
121 // Test case:
122 // Do we work correctly for very large N statistics when alpha is 1 - 32 * epsilon?
123 // This simulates long term statistics collection, where the alpha weighted windowing
124 // permits us to exceed 1 << 23 samples reliably.
125 //
126 // 1 << 25 samples exceeds the mantissa limited capacity of float statistics if alpha == 1...
127 static constexpr int float_overflow_iterlimit = 32;
128 // but we use an alphalimit of 32, means 1. - (alphalimit * epsilon) approx = 0.999996.
129 // This should allow statistics collection indefinitely.
130 static constexpr int alpha_safe_upperbound_iterlimit = 32;
131
132 // benchmark running float at alpha
BM_MeanVariance_float_float_float_alpha(benchmark::State & state)133 static auto BM_MeanVariance_float_float_float_alpha(benchmark::State &state) {
134 BM_MeanVariance<android::audio_utils::Statistics<float, float, float>>(state,
135 float_overflow_iterlimit, alpha_safe_upperbound_iterlimit);
136 }
137
138 BENCHMARK(BM_MeanVariance_float_float_float_alpha);
139
140 // benchmark running double
BM_MeanVariance_float_double_double_alpha(benchmark::State & state)141 static auto BM_MeanVariance_float_double_double_alpha(benchmark::State &state) {
142 BM_MeanVariance<android::audio_utils::Statistics<float, double, double>>(state,
143 float_overflow_iterlimit, alpha_safe_upperbound_iterlimit);
144 }
145
146 BENCHMARK(BM_MeanVariance_float_double_double_alpha);
147
148 BENCHMARK_MAIN();
149