1 #undef NDEBUG
2 #include <algorithm>
3 #include <cassert>
4 #include <cmath>
5 #include <cstdlib>
6 #include <vector>
7 #include "benchmark/benchmark.h"
8 #include "output_test.h"
9
10 namespace {
11
12 #define ADD_COMPLEXITY_CASES(...) \
13 int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)
14
AddComplexityTest(std::string test_name,std::string big_o_test_name,std::string rms_test_name,std::string big_o)15 int AddComplexityTest(std::string test_name, std::string big_o_test_name,
16 std::string rms_test_name, std::string big_o) {
17 SetSubstitutions({{"%name", test_name},
18 {"%bigo_name", big_o_test_name},
19 {"%rms_name", rms_test_name},
20 {"%bigo_str", "[ ]* %float " + big_o},
21 {"%bigo", big_o},
22 {"%rms", "[ ]*[0-9]+ %"}});
23 AddCases(
24 TC_ConsoleOut,
25 {{"^%bigo_name %bigo_str %bigo_str[ ]*$"},
26 {"^%bigo_name", MR_Not}, // Assert we we didn't only matched a name.
27 {"^%rms_name %rms %rms[ ]*$", MR_Next}});
28 AddCases(TC_JSONOut, {{"\"name\": \"%bigo_name\",$"},
29 {"\"run_name\": \"%name\",$", MR_Next},
30 {"\"run_type\": \"aggregate\",$", MR_Next},
31 {"\"repetitions\": %int,$", MR_Next},
32 {"\"threads\": 1,$", MR_Next},
33 {"\"aggregate_name\": \"BigO\",$", MR_Next},
34 {"\"cpu_coefficient\": %float,$", MR_Next},
35 {"\"real_coefficient\": %float,$", MR_Next},
36 {"\"big_o\": \"%bigo\",$", MR_Next},
37 {"\"time_unit\": \"ns\"$", MR_Next},
38 {"}", MR_Next},
39 {"\"name\": \"%rms_name\",$"},
40 {"\"run_name\": \"%name\",$", MR_Next},
41 {"\"run_type\": \"aggregate\",$", MR_Next},
42 {"\"repetitions\": %int,$", MR_Next},
43 {"\"threads\": 1,$", MR_Next},
44 {"\"aggregate_name\": \"RMS\",$", MR_Next},
45 {"\"rms\": %float$", MR_Next},
46 {"}", MR_Next}});
47 AddCases(TC_CSVOut, {{"^\"%bigo_name\",,%float,%float,%bigo,,,,,$"},
48 {"^\"%bigo_name\"", MR_Not},
49 {"^\"%rms_name\",,%float,%float,,,,,,$", MR_Next}});
50 return 0;
51 }
52
53 } // end namespace
54
55 // ========================================================================= //
56 // --------------------------- Testing BigO O(1) --------------------------- //
57 // ========================================================================= //
58
BM_Complexity_O1(benchmark::State & state)59 void BM_Complexity_O1(benchmark::State& state) {
60 for (auto _ : state) {
61 for (int i = 0; i < 1024; ++i) {
62 benchmark::DoNotOptimize(&i);
63 }
64 }
65 state.SetComplexityN(state.range(0));
66 }
67 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
68 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
69 BENCHMARK(BM_Complexity_O1)
70 ->Range(1, 1 << 18)
__anon916c6fcc0202(benchmark::IterationCount) 71 ->Complexity([](benchmark::IterationCount) { return 1.0; });
72
73 const char *one_test_name = "BM_Complexity_O1";
74 const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
75 const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
76 const char *enum_big_o_1 = "\\([0-9]+\\)";
77 // FIXME: Tolerate both '(1)' and 'lgN' as output when the complexity is auto
78 // deduced.
79 // See https://github.com/google/benchmark/issues/272
80 const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
81 const char *lambda_big_o_1 = "f\\(N\\)";
82
83 // Add enum tests
84 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
85 enum_big_o_1);
86
87 // Add auto enum tests
88 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
89 auto_big_o_1);
90
91 // Add lambda tests
92 ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
93 lambda_big_o_1);
94
95 // ========================================================================= //
96 // --------------------------- Testing BigO O(N) --------------------------- //
97 // ========================================================================= //
98
ConstructRandomVector(int64_t size)99 std::vector<int> ConstructRandomVector(int64_t size) {
100 std::vector<int> v;
101 v.reserve(static_cast<int>(size));
102 for (int i = 0; i < size; ++i) {
103 v.push_back(static_cast<int>(std::rand() % size));
104 }
105 return v;
106 }
107
BM_Complexity_O_N(benchmark::State & state)108 void BM_Complexity_O_N(benchmark::State& state) {
109 auto v = ConstructRandomVector(state.range(0));
110 // Test worst case scenario (item not in vector)
111 const int64_t item_not_in_vector = state.range(0) * 2;
112 for (auto _ : state) {
113 benchmark::DoNotOptimize(std::find(v.begin(), v.end(), item_not_in_vector));
114 }
115 state.SetComplexityN(state.range(0));
116 }
117 BENCHMARK(BM_Complexity_O_N)
118 ->RangeMultiplier(2)
119 ->Range(1 << 10, 1 << 16)
120 ->Complexity(benchmark::oN);
121 BENCHMARK(BM_Complexity_O_N)
122 ->RangeMultiplier(2)
123 ->Range(1 << 10, 1 << 16)
__anon916c6fcc0302(benchmark::IterationCount n) 124 ->Complexity([](benchmark::IterationCount n) -> double {
125 return static_cast<double>(n);
126 });
127 BENCHMARK(BM_Complexity_O_N)
128 ->RangeMultiplier(2)
129 ->Range(1 << 10, 1 << 16)
130 ->Complexity();
131
132 const char *n_test_name = "BM_Complexity_O_N";
133 const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
134 const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
135 const char *enum_auto_big_o_n = "N";
136 const char *lambda_big_o_n = "f\\(N\\)";
137
138 // Add enum tests
139 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
140 enum_auto_big_o_n);
141
142 // Add lambda tests
143 ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
144 lambda_big_o_n);
145
146 // ========================================================================= //
147 // ------------------------- Testing BigO O(N*lgN) ------------------------- //
148 // ========================================================================= //
149
BM_Complexity_O_N_log_N(benchmark::State & state)150 static void BM_Complexity_O_N_log_N(benchmark::State& state) {
151 auto v = ConstructRandomVector(state.range(0));
152 for (auto _ : state) {
153 std::sort(v.begin(), v.end());
154 }
155 state.SetComplexityN(state.range(0));
156 }
157 static const double kLog2E = 1.44269504088896340736;
158 BENCHMARK(BM_Complexity_O_N_log_N)
159 ->RangeMultiplier(2)
160 ->Range(1 << 10, 1 << 16)
161 ->Complexity(benchmark::oNLogN);
162 BENCHMARK(BM_Complexity_O_N_log_N)
163 ->RangeMultiplier(2)
164 ->Range(1 << 10, 1 << 16)
__anon916c6fcc0402(benchmark::IterationCount n) 165 ->Complexity([](benchmark::IterationCount n) {
166 return kLog2E * n * log(static_cast<double>(n));
167 });
168 BENCHMARK(BM_Complexity_O_N_log_N)
169 ->RangeMultiplier(2)
170 ->Range(1 << 10, 1 << 16)
171 ->Complexity();
172
173 const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N";
174 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
175 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
176 const char *enum_auto_big_o_n_lg_n = "NlgN";
177 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
178
179 // Add enum tests
180 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
181 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n);
182
183 // Add lambda tests
184 ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
185 rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n);
186
187 // ========================================================================= //
188 // -------- Testing formatting of Complexity with captured args ------------ //
189 // ========================================================================= //
190
BM_ComplexityCaptureArgs(benchmark::State & state,int n)191 void BM_ComplexityCaptureArgs(benchmark::State& state, int n) {
192 for (auto _ : state) {
193 // This test requires a non-zero CPU time to avoid divide-by-zero
194 benchmark::DoNotOptimize(state.iterations());
195 }
196 state.SetComplexityN(n);
197 }
198
199 BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
200 ->Complexity(benchmark::oN)
201 ->Ranges({{1, 2}, {3, 4}});
202
203 const std::string complexity_capture_name =
204 "BM_ComplexityCaptureArgs/capture_test";
205
206 ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",
207 complexity_capture_name + "_RMS", "N");
208
209 // ========================================================================= //
210 // --------------------------- TEST CASES END ------------------------------ //
211 // ========================================================================= //
212
main(int argc,char * argv[])213 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
214