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
11 namespace {
12
13 #define ADD_COMPLEXITY_CASES(...) \
14 int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)
15
AddComplexityTest(const std::string & test_name,const std::string & big_o_test_name,const std::string & rms_test_name,const std::string & big_o,int family_index)16 int 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 TC_ConsoleOut,
28 {{"^%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 TC_JSONOut,
33 {{"\"name\": \"%bigo_name\",$"},
34 {"\"family_index\": " + std::to_string(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(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(TC_CSVOut, {{"^\"%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
BM_Complexity_O1(benchmark::State & state)70 void 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(state.iterations());
74 double tmp = static_cast<double>(state.iterations());
75 benchmark::DoNotOptimize(tmp);
76 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
77 benchmark::DoNotOptimize(state.iterations());
78 tmp *= static_cast<double>(state.iterations());
79 benchmark::DoNotOptimize(tmp);
80 }
81
82 // always 1ns per iteration
83 state.SetIterationTime(42 * 1e-9);
84 }
85 state.SetComplexityN(state.range(0));
86 }
87 BENCHMARK(BM_Complexity_O1)
88 ->Range(1, 1 << 18)
89 ->UseManualTime()
90 ->Complexity(benchmark::o1);
91 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->UseManualTime()->Complexity();
92 BENCHMARK(BM_Complexity_O1)
93 ->Range(1, 1 << 18)
94 ->UseManualTime()
__anon692759fb0202(benchmark::IterationCount) 95 ->Complexity([](benchmark::IterationCount) { return 1.0; });
96
97 const char *one_test_name = "BM_Complexity_O1/manual_time";
98 const char *big_o_1_test_name = "BM_Complexity_O1/manual_time_BigO";
99 const char *rms_o_1_test_name = "BM_Complexity_O1/manual_time_RMS";
100 const char *enum_auto_big_o_1 = "\\([0-9]+\\)";
101 const char *lambda_big_o_1 = "f\\(N\\)";
102
103 // Add enum tests
104 ADD_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
108 ADD_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
112 ADD_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
BM_Complexity_O_N(benchmark::State & state)119 void 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(state.iterations());
123 double tmp = static_cast<double>(state.iterations());
124 benchmark::DoNotOptimize(tmp);
125 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
126 benchmark::DoNotOptimize(state.iterations());
127 tmp *= static_cast<double>(state.iterations());
128 benchmark::DoNotOptimize(tmp);
129 }
130
131 // 1ns per iteration per entry
132 state.SetIterationTime(static_cast<double>(state.range(0)) * 42 * 1e-9);
133 }
134 state.SetComplexityN(state.range(0));
135 }
136 BENCHMARK(BM_Complexity_O_N)
137 ->RangeMultiplier(2)
138 ->Range(1 << 10, 1 << 20)
139 ->UseManualTime()
140 ->Complexity(benchmark::oN);
141 BENCHMARK(BM_Complexity_O_N)
142 ->RangeMultiplier(2)
143 ->Range(1 << 10, 1 << 20)
144 ->UseManualTime()
145 ->Complexity();
146 BENCHMARK(BM_Complexity_O_N)
147 ->RangeMultiplier(2)
148 ->Range(1 << 10, 1 << 20)
149 ->UseManualTime()
__anon692759fb0302(benchmark::IterationCount n) 150 ->Complexity([](benchmark::IterationCount n) -> double {
151 return static_cast<double>(n);
152 });
153
154 const char *n_test_name = "BM_Complexity_O_N/manual_time";
155 const char *big_o_n_test_name = "BM_Complexity_O_N/manual_time_BigO";
156 const char *rms_o_n_test_name = "BM_Complexity_O_N/manual_time_RMS";
157 const char *enum_auto_big_o_n = "N";
158 const char *lambda_big_o_n = "f\\(N\\)";
159
160 // Add enum tests
161 ADD_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
165 ADD_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
169 ADD_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
176 static const double kLog2E = 1.44269504088896340736;
BM_Complexity_O_N_log_N(benchmark::State & state)177 static 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(state.iterations());
181 double tmp = static_cast<double>(state.iterations());
182 benchmark::DoNotOptimize(tmp);
183 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
184 benchmark::DoNotOptimize(state.iterations());
185 tmp *= static_cast<double>(state.iterations());
186 benchmark::DoNotOptimize(tmp);
187 }
188
189 state.SetIterationTime(static_cast<double>(state.range(0)) * kLog2E *
190 std::log(state.range(0)) * 42 * 1e-9);
191 }
192 state.SetComplexityN(state.range(0));
193 }
194 BENCHMARK(BM_Complexity_O_N_log_N)
195 ->RangeMultiplier(2)
196 ->Range(1 << 10, 1U << 24)
197 ->UseManualTime()
198 ->Complexity(benchmark::oNLogN);
199 BENCHMARK(BM_Complexity_O_N_log_N)
200 ->RangeMultiplier(2)
201 ->Range(1 << 10, 1U << 24)
202 ->UseManualTime()
203 ->Complexity();
204 BENCHMARK(BM_Complexity_O_N_log_N)
205 ->RangeMultiplier(2)
206 ->Range(1 << 10, 1U << 24)
207 ->UseManualTime()
__anon692759fb0402(benchmark::IterationCount n) 208 ->Complexity([](benchmark::IterationCount n) {
209 return kLog2E * static_cast<double>(n) * std::log(static_cast<double>(n));
210 });
211
212 const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time";
213 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_BigO";
214 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_RMS";
215 const char *enum_auto_big_o_n_lg_n = "NlgN";
216 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
217
218 // Add enum tests
219 ADD_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
224 ADD_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
229 ADD_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
BM_ComplexityCaptureArgs(benchmark::State & state,int n)237 void 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(state.iterations());
241 double tmp = static_cast<double>(state.iterations());
242 benchmark::DoNotOptimize(tmp);
243 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
244 benchmark::DoNotOptimize(state.iterations());
245 tmp *= static_cast<double>(state.iterations());
246 benchmark::DoNotOptimize(tmp);
247 }
248
249 state.SetIterationTime(static_cast<double>(state.range(0)) * 42 * 1e-9);
250 }
251 state.SetComplexityN(n);
252 }
253
254 BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
255 ->UseManualTime()
256 ->Complexity(benchmark::oN)
257 ->Ranges({{1, 2}, {3, 4}});
258
259 const std::string complexity_capture_name =
260 "BM_ComplexityCaptureArgs/capture_test/manual_time";
261
262 ADD_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
main(int argc,char * argv[])270 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
271