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