utils/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 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\": %float,$", MR_Next},
  29                         {"\"real_coefficient\": %float,$", 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
  48 void BM_Complexity_O1(benchmark::State& state) {
  49   for (auto _ : state) {
  50     for (int i = 0; i < 1024; ++i) {
  51       benchmark::DoNotOptimize(&i);
  52     }
  53   }
  54   state.SetComplexityN(state.range(0));
  55 }
  56 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
  57 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
  58 BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity([](int64_t) {
  59   return 1.0;
  60 });
  61
  62 const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
  63 const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
  64 const 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
  68 const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
  69 const char *lambda_big_o_1 = "f\\(N\\)";
  70
  71 // Add enum tests
  72 ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, enum_big_o_1);
  73
  74 // Add auto enum tests
  75 ADD_COMPLEXITY_CASES(big_o_1_test_name, rms_o_1_test_name, auto_big_o_1);
  76
  77 // Add lambda tests
  78 ADD_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
  84 std::vector<int> ConstructRandomVector(int64_t size) {
  85   std::vector<int> v;
  86   v.reserve(static_cast<int>(size));
  87   for (int i = 0; i < size; ++i) {
  88     v.push_back(std::rand() % size);
  89   }
  90   return v;
  91 }
  92
  93 void BM_Complexity_O_N(benchmark::State& state) {
  94   auto v = ConstructRandomVector(state.range(0));
  95   // Test worst case scenario (item not in vector)
  96   const int64_t item_not_in_vector = state.range(0) * 2;
  97   for (auto _ : state) {
  98     benchmark::DoNotOptimize(std::find(v.begin(), v.end(), item_not_in_vector));
  99   }
 100   state.SetComplexityN(state.range(0));
 101 }
 102 BENCHMARK(BM_Complexity_O_N)
 103     ->RangeMultiplier(2)
 104     ->Range(1 << 10, 1 << 16)
 105     ->Complexity(benchmark::oN);
 106 BENCHMARK(BM_Complexity_O_N)
 107     ->RangeMultiplier(2)
 108     ->Range(1 << 10, 1 << 16)
 109     ->Complexity([](int64_t n) -> double { return n; });
 110 BENCHMARK(BM_Complexity_O_N)
 111     ->RangeMultiplier(2)
 112     ->Range(1 << 10, 1 << 16)
 113     ->Complexity();
 114
 115 const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
 116 const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
 117 const char *enum_auto_big_o_n = "N";
 118 const char *lambda_big_o_n = "f\\(N\\)";
 119
 120 // Add enum tests
 121 ADD_COMPLEXITY_CASES(big_o_n_test_name, rms_o_n_test_name, enum_auto_big_o_n);
 122
 123 // Add lambda tests
 124 ADD_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
 130 static void BM_Complexity_O_N_log_N(benchmark::State& state) {
 131   auto v = ConstructRandomVector(state.range(0));
 132   for (auto _ : state) {
 133     std::sort(v.begin(), v.end());
 134   }
 135   state.SetComplexityN(state.range(0));
 136 }
 137 BENCHMARK(BM_Complexity_O_N_log_N)
 138     ->RangeMultiplier(2)
 139     ->Range(1 << 10, 1 << 16)
 140     ->Complexity(benchmark::oNLogN);
 141 BENCHMARK(BM_Complexity_O_N_log_N)
 142     ->RangeMultiplier(2)
 143     ->Range(1 << 10, 1 << 16)
 144     ->Complexity([](int64_t n) { return n * log2(n); });
 145 BENCHMARK(BM_Complexity_O_N_log_N)
 146     ->RangeMultiplier(2)
 147     ->Range(1 << 10, 1 << 16)
 148     ->Complexity();
 149
 150 const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
 151 const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
 152 const char *enum_auto_big_o_n_lg_n = "NlgN";
 153 const char *lambda_big_o_n_lg_n = "f\\(N\\)";
 154
 155 // Add enum tests
 156 ADD_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
 160 ADD_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
 167 int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }