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
10namespace {
11
12#define ADD_COMPLEXITY_CASES(...) \
13  int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)
14
15int 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
48void 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}
56BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
57BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
58BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity([](int) {
59  return 1.0;
60});
61
62const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
63const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
64const 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
68const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
69const char *lambda_big_o_1 = "f\\(N\\)";
70
71// Add enum tests
72ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, enum_big_o_1);
73
74// Add auto enum tests
75ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, auto_big_o_1);
76
77// Add lambda tests
78ADD_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
84std::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
93void 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}
102BENCHMARK(BM_Complexity_O_N)
103    ->RangeMultiplier(2)
104    ->Range(1 << 10, 1 << 16)
105    ->Complexity(benchmark::oN);
106BENCHMARK(BM_Complexity_O_N)
107    ->RangeMultiplier(2)
108    ->Range(1 << 10, 1 << 16)
109    ->Complexity([](int n) -> double { return n; });
110BENCHMARK(BM_Complexity_O_N)
111    ->RangeMultiplier(2)
112    ->Range(1 << 10, 1 << 16)
113    ->Complexity();
114
115const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
116const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
117const char *enum_auto_big_o_n = "N";
118const char *lambda_big_o_n = "f\\(N\\)";
119
120// Add enum tests
121ADD_COMPLEXITY_CASES(big_o_n_test_name, rms_o_n_test_name, enum_auto_big_o_n);
122
123// Add lambda tests
124ADD_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
130static 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}
137BENCHMARK(BM_Complexity_O_N_log_N)
138    ->RangeMultiplier(2)
139    ->Range(1 << 10, 1 << 16)
140    ->Complexity(benchmark::oNLogN);
141BENCHMARK(BM_Complexity_O_N_log_N)
142    ->RangeMultiplier(2)
143    ->Range(1 << 10, 1 << 16)
144    ->Complexity([](int n) { return n * log2(n); });
145BENCHMARK(BM_Complexity_O_N_log_N)
146    ->RangeMultiplier(2)
147    ->Range(1 << 10, 1 << 16)
148    ->Complexity();
149
150const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
151const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
152const char *enum_auto_big_o_n_lg_n = "NlgN";
153const char *lambda_big_o_n_lg_n = "f\\(N\\)";
154
155// Add enum tests
156ADD_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
160ADD_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
167int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }
168