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