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 big_o_test_name,std::string rms_test_name,std::string big_o)15 int AddComplexityTest(std::string big_o_test_name, std::string rms_test_name,
16 std::string big_o) {
17 SetSubstitutions({{"%bigo_name", big_o_test_name},
18 {"%rms_name", rms_test_name},
19 {"%bigo_str", "[ ]* %float " + big_o},
20 {"%bigo", big_o},
21 {"%rms", "[ ]*[0-9]+ %"}});
22 AddCases(
23 TC_ConsoleOut,
24 {{"^%bigo_name %bigo_str %bigo_str[ ]*$"},
25 {"^%bigo_name", MR_Not}, // Assert we we didn't only matched a name.
26 {"^%rms_name %rms %rms[ ]*$", MR_Next}});
27 AddCases(TC_JSONOut, {{"\"name\": \"%bigo_name\",$"},
28 {"\"cpu_coefficient\": [0-9]+,$", MR_Next},
29 {"\"real_coefficient\": [0-9]{1,5},$", MR_Next},
30 {"\"big_o\": \"%bigo\",$", MR_Next},
31 {"\"time_unit\": \"ns\"$", MR_Next},
32 {"}", MR_Next},
33 {"\"name\": \"%rms_name\",$"},
34 {"\"rms\": %float$", MR_Next},
35 {"}", MR_Next}});
36 AddCases(TC_CSVOut, {{"^\"%bigo_name\",,%float,%float,%bigo,,,,,$"},
37 {"^\"%bigo_name\"", MR_Not},
38 {"^\"%rms_name\",,%float,%float,,,,,,$", MR_Next}});
39 return 0;
40 }
41
42 } // end namespace
43
44 // ========================================================================= //
45 // --------------------------- Testing BigO O(1) --------------------------- //
46 // ========================================================================= //
47
BM_Complexity_O1(benchmark::State & state)48 void BM_Complexity_O1(benchmark::State& state) {
49 while (state.KeepRunning()) {
50 for (int i = 0; i < 1024; ++i) {
51 benchmark::DoNotOptimize(&i);
52 }
53 }
54 state.SetComplexityN(state.range(0));
55 }
56 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
57 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
__anon3310dde40202(int) 58 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity([](int) {
59 return 1.0;
60 });
61
62 const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
63 const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
64 const char *enum_big_o_1 = "\\([0-9]+\\)";
65 // FIXME: Tolerate both '(1)' and 'lgN' as output when the complexity is auto
66 // deduced.
67 // See https://github.com/google/benchmark/issues/272
68 const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
69 const char *lambda_big_o_1 = "f\\(N\\)";
70
71 // Add enum tests
72 ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, enum_big_o_1);
73
74 // Add auto enum tests
75 ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, auto_big_o_1);
76
77 // Add lambda tests
78 ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, lambda_big_o_1);
79
80 // ========================================================================= //
81 // --------------------------- Testing BigO O(N) --------------------------- //
82 // ========================================================================= //
83
ConstructRandomVector(int size)84 std::vector<int> ConstructRandomVector(int size) {
85 std::vector<int> v;
86 v.reserve(size);
87 for (int i = 0; i < size; ++i) {
88 v.push_back(std::rand() % size);
89 }
90 return v;
91 }
92
BM_Complexity_O_N(benchmark::State & state)93 void BM_Complexity_O_N(benchmark::State& state) {
94 auto v = ConstructRandomVector(state.range(0));
95 const int item_not_in_vector =
96 state.range(0) * 2; // Test worst case scenario (item not in vector)
97 while (state.KeepRunning()) {
98 benchmark::DoNotOptimize(std::find(v.begin(), v.end(), item_not_in_vector));
99 }
100 state.SetComplexityN(state.range(0));
101 }
102 BENCHMARK(BM_Complexity_O_N)
103 ->RangeMultiplier(2)
104 ->Range(1 << 10, 1 << 16)
105 ->Complexity(benchmark::oN);
106 BENCHMARK(BM_Complexity_O_N)
107 ->RangeMultiplier(2)
108 ->Range(1 << 10, 1 << 16)
__anon3310dde40302(int n) 109 ->Complexity([](int n) -> double { return n; });
110 BENCHMARK(BM_Complexity_O_N)
111 ->RangeMultiplier(2)
112 ->Range(1 << 10, 1 << 16)
113 ->Complexity();
114
115 const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
116 const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
117 const char *enum_auto_big_o_n = "N";
118 const char *lambda_big_o_n = "f\\(N\\)";
119
120 // Add enum tests
121 ADD_COMPLEXITY_CASES(big_o_n_test_name, rms_o_n_test_name, enum_auto_big_o_n);
122
123 // Add lambda tests
124 ADD_COMPLEXITY_CASES(big_o_n_test_name, rms_o_n_test_name, lambda_big_o_n);
125
126 // ========================================================================= //
127 // ------------------------- Testing BigO O(N*lgN) ------------------------- //
128 // ========================================================================= //
129
BM_Complexity_O_N_log_N(benchmark::State & state)130 static void BM_Complexity_O_N_log_N(benchmark::State& state) {
131 auto v = ConstructRandomVector(state.range(0));
132 while (state.KeepRunning()) {
133 std::sort(v.begin(), v.end());
134 }
135 state.SetComplexityN(state.range(0));
136 }
137 BENCHMARK(BM_Complexity_O_N_log_N)
138 ->RangeMultiplier(2)
139 ->Range(1 << 10, 1 << 16)
140 ->Complexity(benchmark::oNLogN);
141 BENCHMARK(BM_Complexity_O_N_log_N)
142 ->RangeMultiplier(2)
143 ->Range(1 << 10, 1 << 16)
__anon3310dde40402(int n) 144 ->Complexity([](int n) { return n * log2(n); });
145 BENCHMARK(BM_Complexity_O_N_log_N)
146 ->RangeMultiplier(2)
147 ->Range(1 << 10, 1 << 16)
148 ->Complexity();
149
150 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
151 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
152 const char *enum_auto_big_o_n_lg_n = "NlgN";
153 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
154
155 // Add enum tests
156 ADD_COMPLEXITY_CASES(big_o_n_lg_n_test_name, rms_o_n_lg_n_test_name,
157 enum_auto_big_o_n_lg_n);
158
159 // Add lambda tests
160 ADD_COMPLEXITY_CASES(big_o_n_lg_n_test_name, rms_o_n_lg_n_test_name,
161 lambda_big_o_n_lg_n);
162
163 // ========================================================================= //
164 // --------------------------- TEST CASES END ------------------------------ //
165 // ========================================================================= //
166
main(int argc,char * argv[])167 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
168