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 for (int i = 0; i < 1024; ++i) {
73 benchmark::DoNotOptimize(i);
74 }
75 }
76 state.SetComplexityN(state.range(0));
77 }
78 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
79 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
80 BENCHMARK(BM_Complexity_O1)
81 ->Range(1, 1 << 18)
__anon0ce056190202(benchmark::IterationCount) 82 ->Complexity([](benchmark::IterationCount) { return 1.0; });
83
84 const char *one_test_name = "BM_Complexity_O1";
85 const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
86 const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
87 const char *enum_big_o_1 = "\\([0-9]+\\)";
88 // FIXME: Tolerate both '(1)' and 'lgN' as output when the complexity is auto
89 // deduced.
90 // See https://github.com/google/benchmark/issues/272
91 const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
92 const char *lambda_big_o_1 = "f\\(N\\)";
93
94 // Add enum tests
95 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
96 enum_big_o_1, /*family_index=*/0);
97
98 // Add auto enum tests
99 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
100 auto_big_o_1, /*family_index=*/1);
101
102 // Add lambda tests
103 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
104 lambda_big_o_1, /*family_index=*/2);
105
106 // ========================================================================= //
107 // --------------------------- Testing BigO O(N) --------------------------- //
108 // ========================================================================= //
109
ConstructRandomVector(int64_t size)110 std::vector<int> ConstructRandomVector(int64_t size) {
111 std::vector<int> v;
112 v.reserve(static_cast<size_t>(size));
113 for (int i = 0; i < size; ++i) {
114 v.push_back(static_cast<int>(std::rand() % size));
115 }
116 return v;
117 }
118
BM_Complexity_O_N(benchmark::State & state)119 void BM_Complexity_O_N(benchmark::State &state) {
120 auto v = ConstructRandomVector(state.range(0));
121 // Test worst case scenario (item not in vector)
122 const int64_t item_not_in_vector = state.range(0) * 2;
123 for (auto _ : state) {
124 auto it = std::find(v.begin(), v.end(), item_not_in_vector);
125 benchmark::DoNotOptimize(it);
126 }
127 state.SetComplexityN(state.range(0));
128 }
129 BENCHMARK(BM_Complexity_O_N)
130 ->RangeMultiplier(2)
131 ->Range(1 << 10, 1 << 16)
132 ->Complexity(benchmark::oN);
133 BENCHMARK(BM_Complexity_O_N)
134 ->RangeMultiplier(2)
135 ->Range(1 << 10, 1 << 16)
__anon0ce056190302(benchmark::IterationCount n) 136 ->Complexity([](benchmark::IterationCount n) -> double {
137 return static_cast<double>(n);
138 });
139 BENCHMARK(BM_Complexity_O_N)
140 ->RangeMultiplier(2)
141 ->Range(1 << 10, 1 << 16)
142 ->Complexity();
143
144 const char *n_test_name = "BM_Complexity_O_N";
145 const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
146 const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
147 const char *enum_auto_big_o_n = "N";
148 const char *lambda_big_o_n = "f\\(N\\)";
149
150 // Add enum tests
151 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
152 enum_auto_big_o_n, /*family_index=*/3);
153
154 // Add lambda tests
155 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
156 lambda_big_o_n, /*family_index=*/4);
157
158 // ========================================================================= //
159 // ------------------------- Testing BigO O(N*lgN) ------------------------- //
160 // ========================================================================= //
161
BM_Complexity_O_N_log_N(benchmark::State & state)162 static void BM_Complexity_O_N_log_N(benchmark::State &state) {
163 auto v = ConstructRandomVector(state.range(0));
164 for (auto _ : state) {
165 std::sort(v.begin(), v.end());
166 }
167 state.SetComplexityN(state.range(0));
168 }
169 static const double kLog2E = 1.44269504088896340736;
170 BENCHMARK(BM_Complexity_O_N_log_N)
171 ->RangeMultiplier(2)
172 ->Range(1 << 10, 1 << 16)
173 ->Complexity(benchmark::oNLogN);
174 BENCHMARK(BM_Complexity_O_N_log_N)
175 ->RangeMultiplier(2)
176 ->Range(1 << 10, 1 << 16)
__anon0ce056190402(benchmark::IterationCount n) 177 ->Complexity([](benchmark::IterationCount n) {
178 return kLog2E * static_cast<double>(n) * log(static_cast<double>(n));
179 });
180 BENCHMARK(BM_Complexity_O_N_log_N)
181 ->RangeMultiplier(2)
182 ->Range(1 << 10, 1 << 16)
183 ->Complexity();
184
185 const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N";
186 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
187 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
188 const char *enum_auto_big_o_n_lg_n = "NlgN";
189 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
190
191 // Add enum tests
192 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
193 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
194 /*family_index=*/6);
195
196 // Add lambda tests
197 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
198 rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,
199 /*family_index=*/7);
200
201 // ========================================================================= //
202 // -------- Testing formatting of Complexity with captured args ------------ //
203 // ========================================================================= //
204
BM_ComplexityCaptureArgs(benchmark::State & state,int n)205 void BM_ComplexityCaptureArgs(benchmark::State &state, int n) {
206 for (auto _ : state) {
207 // This test requires a non-zero CPU time to avoid divide-by-zero
208 auto iterations = state.iterations();
209 benchmark::DoNotOptimize(iterations);
210 }
211 state.SetComplexityN(n);
212 }
213
214 BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
215 ->Complexity(benchmark::oN)
216 ->Ranges({{1, 2}, {3, 4}});
217
218 const std::string complexity_capture_name =
219 "BM_ComplexityCaptureArgs/capture_test";
220
221 ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",
222 complexity_capture_name + "_RMS", "N", /*family_index=*/9);
223
224 // ========================================================================= //
225 // --------------------------- TEST CASES END ------------------------------ //
226 // ========================================================================= //
227
main(int argc,char * argv[])228 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
229