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