1#undef NDEBUG
2#include <algorithm>
3#include <cassert>
4#include <cmath>
5#include <cstdlib>
6#include <vector>
7
8#include "benchmark/benchmark.h"
9#include "output_test.h"
10
11namespace {
12
13#define ADD_COMPLEXITY_CASES(...) \
14 int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)
15
16int AddComplexityTest(const std::string &test_name,
17 const std::string &big_o_test_name,
18 const std::string &rms_test_name,
19 const std::string &big_o, int family_index) {
20 SetSubstitutions({{"%name", test_name},
21 {"%bigo_name", big_o_test_name},
22 {"%rms_name", rms_test_name},
23 {"%bigo_str", "[ ]* %float " + big_o},
24 {"%bigo", big_o},
25 {"%rms", "[ ]*[0-9]+ %"}});
26 AddCases(
27 ID: TC_ConsoleOut,
28 il: {{"^%bigo_name %bigo_str %bigo_str[ ]*$"},
29 {"^%bigo_name", MR_Not}, // Assert we we didn't only matched a name.
30 {"^%rms_name %rms %rms[ ]*$", MR_Next}});
31 AddCases(
32 ID: TC_JSONOut,
33 il: {{"\"name\": \"%bigo_name\",$"},
34 {"\"family_index\": " + std::to_string(val: family_index) + ",$", MR_Next},
35 {"\"per_family_instance_index\": 0,$", MR_Next},
36 {"\"run_name\": \"%name\",$", MR_Next},
37 {"\"run_type\": \"aggregate\",$", MR_Next},
38 {"\"repetitions\": %int,$", MR_Next},
39 {"\"threads\": 1,$", MR_Next},
40 {"\"aggregate_name\": \"BigO\",$", MR_Next},
41 {"\"aggregate_unit\": \"time\",$", MR_Next},
42 {"\"cpu_coefficient\": %float,$", MR_Next},
43 {"\"real_coefficient\": %float,$", MR_Next},
44 {"\"big_o\": \"%bigo\",$", MR_Next},
45 {"\"time_unit\": \"ns\"$", MR_Next},
46 {"}", MR_Next},
47 {"\"name\": \"%rms_name\",$"},
48 {"\"family_index\": " + std::to_string(val: family_index) + ",$", MR_Next},
49 {"\"per_family_instance_index\": 0,$", MR_Next},
50 {"\"run_name\": \"%name\",$", MR_Next},
51 {"\"run_type\": \"aggregate\",$", MR_Next},
52 {"\"repetitions\": %int,$", MR_Next},
53 {"\"threads\": 1,$", MR_Next},
54 {"\"aggregate_name\": \"RMS\",$", MR_Next},
55 {"\"aggregate_unit\": \"percentage\",$", MR_Next},
56 {"\"rms\": %float$", MR_Next},
57 {"}", MR_Next}});
58 AddCases(ID: TC_CSVOut, il: {{"^\"%bigo_name\",,%float,%float,%bigo,,,,,$"},
59 {"^\"%bigo_name\"", MR_Not},
60 {"^\"%rms_name\",,%float,%float,,,,,,$", MR_Next}});
61 return 0;
62}
63
64} // end namespace
65
66// ========================================================================= //
67// --------------------------- Testing BigO O(1) --------------------------- //
68// ========================================================================= //
69
70void BM_Complexity_O1(benchmark::State &state) {
71 for (auto _ : state) {
72 // This test requires a non-zero CPU time to avoid divide-by-zero
73 benchmark::DoNotOptimize(value: state.iterations());
74 long tmp = state.iterations();
75 benchmark::DoNotOptimize(value&: tmp);
76 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
77 benchmark::DoNotOptimize(value: state.iterations());
78 tmp *= state.iterations();
79 benchmark::DoNotOptimize(value&: tmp);
80 }
81
82 // always 1ns per iteration
83 state.SetIterationTime(42 * 1e-9);
84 }
85 state.SetComplexityN(state.range(pos: 0));
86}
87BENCHMARK(BM_Complexity_O1)
88 ->Range(start: 1, limit: 1 << 18)
89 ->UseManualTime()
90 ->Complexity(complexity: benchmark::o1);
91BENCHMARK(BM_Complexity_O1)->Range(start: 1, limit: 1 << 18)->UseManualTime()->Complexity();
92BENCHMARK(BM_Complexity_O1)
93 ->Range(start: 1, limit: 1 << 18)
94 ->UseManualTime()
95 ->Complexity(complexity: [](benchmark::IterationCount) { return 1.0; });
96
97const char *one_test_name = "BM_Complexity_O1/manual_time";
98const char *big_o_1_test_name = "BM_Complexity_O1/manual_time_BigO";
99const char *rms_o_1_test_name = "BM_Complexity_O1/manual_time_RMS";
100const char *enum_auto_big_o_1 = "\\([0-9]+\\)";
101const char *lambda_big_o_1 = "f\\(N\\)";
102
103// Add enum tests
104ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
105 enum_auto_big_o_1, /*family_index=*/0);
106
107// Add auto tests
108ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
109 enum_auto_big_o_1, /*family_index=*/1);
110
111// Add lambda tests
112ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
113 lambda_big_o_1, /*family_index=*/2);
114
115// ========================================================================= //
116// --------------------------- Testing BigO O(N) --------------------------- //
117// ========================================================================= //
118
119void BM_Complexity_O_N(benchmark::State &state) {
120 for (auto _ : state) {
121 // This test requires a non-zero CPU time to avoid divide-by-zero
122 benchmark::DoNotOptimize(value: state.iterations());
123 long tmp = state.iterations();
124 benchmark::DoNotOptimize(value&: tmp);
125 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
126 benchmark::DoNotOptimize(value: state.iterations());
127 tmp *= state.iterations();
128 benchmark::DoNotOptimize(value&: tmp);
129 }
130
131 // 1ns per iteration per entry
132 state.SetIterationTime(static_cast<double>(state.range(pos: 0)) * 42.0 * 1e-9);
133 }
134 state.SetComplexityN(state.range(pos: 0));
135}
136BENCHMARK(BM_Complexity_O_N)
137 ->RangeMultiplier(multiplier: 2)
138 ->Range(start: 1 << 10, limit: 1 << 20)
139 ->UseManualTime()
140 ->Complexity(complexity: benchmark::oN);
141BENCHMARK(BM_Complexity_O_N)
142 ->RangeMultiplier(multiplier: 2)
143 ->Range(start: 1 << 10, limit: 1 << 20)
144 ->UseManualTime()
145 ->Complexity();
146BENCHMARK(BM_Complexity_O_N)
147 ->RangeMultiplier(multiplier: 2)
148 ->Range(start: 1 << 10, limit: 1 << 20)
149 ->UseManualTime()
150 ->Complexity(complexity: [](benchmark::IterationCount n) -> double {
151 return static_cast<double>(n);
152 });
153
154const char *n_test_name = "BM_Complexity_O_N/manual_time";
155const char *big_o_n_test_name = "BM_Complexity_O_N/manual_time_BigO";
156const char *rms_o_n_test_name = "BM_Complexity_O_N/manual_time_RMS";
157const char *enum_auto_big_o_n = "N";
158const char *lambda_big_o_n = "f\\(N\\)";
159
160// Add enum tests
161ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
162 enum_auto_big_o_n, /*family_index=*/3);
163
164// Add auto tests
165ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
166 enum_auto_big_o_n, /*family_index=*/4);
167
168// Add lambda tests
169ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
170 lambda_big_o_n, /*family_index=*/5);
171
172// ========================================================================= //
173// ------------------------- Testing BigO O(NlgN) ------------------------- //
174// ========================================================================= //
175
176static const double kLog2E = 1.44269504088896340736;
177static void BM_Complexity_O_N_log_N(benchmark::State &state) {
178 for (auto _ : state) {
179 // This test requires a non-zero CPU time to avoid divide-by-zero
180 benchmark::DoNotOptimize(value: state.iterations());
181 long tmp = state.iterations();
182 benchmark::DoNotOptimize(value&: tmp);
183 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
184 benchmark::DoNotOptimize(value: state.iterations());
185 tmp *= state.iterations();
186 benchmark::DoNotOptimize(value&: tmp);
187 }
188
189 state.SetIterationTime(static_cast<double>(state.range(pos: 0)) * kLog2E *
190 std::log(x: state.range(pos: 0)) * 42.0 * 1e-9);
191 }
192 state.SetComplexityN(state.range(pos: 0));
193}
194BENCHMARK(BM_Complexity_O_N_log_N)
195 ->RangeMultiplier(multiplier: 2)
196 ->Range(start: 1 << 10, limit: 1U << 24)
197 ->UseManualTime()
198 ->Complexity(complexity: benchmark::oNLogN);
199BENCHMARK(BM_Complexity_O_N_log_N)
200 ->RangeMultiplier(multiplier: 2)
201 ->Range(start: 1 << 10, limit: 1U << 24)
202 ->UseManualTime()
203 ->Complexity();
204BENCHMARK(BM_Complexity_O_N_log_N)
205 ->RangeMultiplier(multiplier: 2)
206 ->Range(start: 1 << 10, limit: 1U << 24)
207 ->UseManualTime()
208 ->Complexity(complexity: [](benchmark::IterationCount n) {
209 return kLog2E * static_cast<double>(n) * std::log(x: static_cast<double>(n));
210 });
211
212const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time";
213const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_BigO";
214const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_RMS";
215const char *enum_auto_big_o_n_lg_n = "NlgN";
216const char *lambda_big_o_n_lg_n = "f\\(N\\)";
217
218// Add enum tests
219ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
220 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
221 /*family_index=*/6);
222
223// NOTE: auto big-o is wron.g
224ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
225 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
226 /*family_index=*/7);
227
228//// Add lambda tests
229ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
230 rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,
231 /*family_index=*/8);
232
233// ========================================================================= //
234// -------- Testing formatting of Complexity with captured args ------------ //
235// ========================================================================= //
236
237void BM_ComplexityCaptureArgs(benchmark::State &state, int n) {
238 for (auto _ : state) {
239 // This test requires a non-zero CPU time to avoid divide-by-zero
240 benchmark::DoNotOptimize(value: state.iterations());
241 long tmp = state.iterations();
242 benchmark::DoNotOptimize(value&: tmp);
243 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
244 benchmark::DoNotOptimize(value: state.iterations());
245 tmp *= state.iterations();
246 benchmark::DoNotOptimize(value&: tmp);
247 }
248
249 state.SetIterationTime(static_cast<double>(state.range(pos: 0)) * 42.0 * 1e-9);
250 }
251 state.SetComplexityN(n);
252}
253
254BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
255 ->UseManualTime()
256 ->Complexity(complexity: benchmark::oN)
257 ->Ranges(ranges: {{1, 2}, {3, 4}});
258
259const std::string complexity_capture_name =
260 "BM_ComplexityCaptureArgs/capture_test/manual_time";
261
262ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",
263 complexity_capture_name + "_RMS", "N",
264 /*family_index=*/9);
265
266// ========================================================================= //
267// --------------------------- TEST CASES END ------------------------------ //
268// ========================================================================= //
269
270int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
271

source code of third-party/benchmark/test/complexity_test.cc