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\": [0-9]+,$", MR_Next}, 29 {"\"real_coefficient\": [0-9]{1,5},$", 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 while (state.KeepRunning()) { 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([](int) { 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(int size) { 85 std::vector<int> v; 86 v.reserve(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 const int item_not_in_vector = 96 state.range(0) * 2; // Test worst case scenario (item not in vector) 97 while (state.KeepRunning()) { 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([](int 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 while (state.KeepRunning()) { 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([](int n) { return n * std::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); } 168
