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