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)
__anon6d5cfdec0202(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<int>(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 benchmark::DoNotOptimize(std::find(v.begin(), v.end(), item_not_in_vector));
125 }
126 state.SetComplexityN(state.range(0));
127 }
128 BENCHMARK(BM_Complexity_O_N)
129 ->RangeMultiplier(2)
130 ->Range(1 << 10, 1 << 16)
131 ->Complexity(benchmark::oN);
132 BENCHMARK(BM_Complexity_O_N)
133 ->RangeMultiplier(2)
134 ->Range(1 << 10, 1 << 16)
__anon6d5cfdec0302(benchmark::IterationCount n) 135 ->Complexity([](benchmark::IterationCount n) -> double {
136 return static_cast<double>(n);
137 });
138 BENCHMARK(BM_Complexity_O_N)
139 ->RangeMultiplier(2)
140 ->Range(1 << 10, 1 << 16)
141 ->Complexity();
142
143 const char *n_test_name = "BM_Complexity_O_N";
144 const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
145 const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
146 const char *enum_auto_big_o_n = "N";
147 const char *lambda_big_o_n = "f\\(N\\)";
148
149 // Add enum tests
150 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
151 enum_auto_big_o_n, /*family_index=*/3);
152
153 // Add lambda tests
154 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
155 lambda_big_o_n, /*family_index=*/4);
156
157 // ========================================================================= //
158 // ------------------------- Testing BigO O(N*lgN) ------------------------- //
159 // ========================================================================= //
160
BM_Complexity_O_N_log_N(benchmark::State & state)161 static void BM_Complexity_O_N_log_N(benchmark::State &state) {
162 auto v = ConstructRandomVector(state.range(0));
163 for (auto _ : state) {
164 std::sort(v.begin(), v.end());
165 }
166 state.SetComplexityN(state.range(0));
167 }
168 static const double kLog2E = 1.44269504088896340736;
169 BENCHMARK(BM_Complexity_O_N_log_N)
170 ->RangeMultiplier(2)
171 ->Range(1 << 10, 1 << 16)
172 ->Complexity(benchmark::oNLogN);
173 BENCHMARK(BM_Complexity_O_N_log_N)
174 ->RangeMultiplier(2)
175 ->Range(1 << 10, 1 << 16)
__anon6d5cfdec0402(benchmark::IterationCount n) 176 ->Complexity([](benchmark::IterationCount n) {
177 return kLog2E * n * log(static_cast<double>(n));
178 });
179 BENCHMARK(BM_Complexity_O_N_log_N)
180 ->RangeMultiplier(2)
181 ->Range(1 << 10, 1 << 16)
182 ->Complexity();
183
184 const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N";
185 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
186 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
187 const char *enum_auto_big_o_n_lg_n = "NlgN";
188 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
189
190 // Add enum tests
191 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
192 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
193 /*family_index=*/6);
194
195 // Add lambda tests
196 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
197 rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,
198 /*family_index=*/7);
199
200 // ========================================================================= //
201 // -------- Testing formatting of Complexity with captured args ------------ //
202 // ========================================================================= //
203
BM_ComplexityCaptureArgs(benchmark::State & state,int n)204 void BM_ComplexityCaptureArgs(benchmark::State &state, int n) {
205 for (auto _ : state) {
206 // This test requires a non-zero CPU time to avoid divide-by-zero
207 benchmark::DoNotOptimize(state.iterations());
208 }
209 state.SetComplexityN(n);
210 }
211
212 BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
213 ->Complexity(benchmark::oN)
214 ->Ranges({{1, 2}, {3, 4}});
215
216 const std::string complexity_capture_name =
217 "BM_ComplexityCaptureArgs/capture_test";
218
219 ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",
220 complexity_capture_name + "_RMS", "N", /*family_index=*/9);
221
222 // ========================================================================= //
223 // --------------------------- TEST CASES END ------------------------------ //
224 // ========================================================================= //
225
main(int argc,char * argv[])226 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
227