third-party/benchmark/test/complexity_test.cc

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