271 lines · plain
1#undef NDEBUG2#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 11namespace {12 13#define ADD_COMPLEXITY_CASES(...) \14 int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__)15 16int 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 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 namespace65 66// ========================================================================= //67// --------------------------- Testing BigO O(1) --------------------------- //68// ========================================================================= //69 70void BM_Complexity_O1(benchmark::State &state) {71 for (auto _ : state) {72 // This test requires a non-zero CPU time to avoid divide-by-zero73 benchmark::DoNotOptimize(state.iterations());74 long tmp = state.iterations();75 benchmark::DoNotOptimize(tmp);76 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {77 benchmark::DoNotOptimize(state.iterations());78 tmp *= state.iterations();79 benchmark::DoNotOptimize(tmp);80 }81 82 // always 1ns per iteration83 state.SetIterationTime(42 * 1e-9);84 }85 state.SetComplexityN(state.range(0));86}87BENCHMARK(BM_Complexity_O1)88 ->Range(1, 1 << 18)89 ->UseManualTime()90 ->Complexity(benchmark::o1);91BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->UseManualTime()->Complexity();92BENCHMARK(BM_Complexity_O1)93 ->Range(1, 1 << 18)94 ->UseManualTime()95 ->Complexity([](benchmark::IterationCount) { return 1.0; });96 97const char *one_test_name = "BM_Complexity_O1/manual_time";98const char *big_o_1_test_name = "BM_Complexity_O1/manual_time_BigO";99const char *rms_o_1_test_name = "BM_Complexity_O1/manual_time_RMS";100const char *enum_auto_big_o_1 = "\\([0-9]+\\)";101const char *lambda_big_o_1 = "f\\(N\\)";102 103// Add enum tests104ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,105 enum_auto_big_o_1, /*family_index=*/0);106 107// Add auto tests108ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,109 enum_auto_big_o_1, /*family_index=*/1);110 111// Add lambda tests112ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,113 lambda_big_o_1, /*family_index=*/2);114 115// ========================================================================= //116// --------------------------- Testing BigO O(N) --------------------------- //117// ========================================================================= //118 119void BM_Complexity_O_N(benchmark::State &state) {120 for (auto _ : state) {121 // This test requires a non-zero CPU time to avoid divide-by-zero122 benchmark::DoNotOptimize(state.iterations());123 long tmp = state.iterations();124 benchmark::DoNotOptimize(tmp);125 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {126 benchmark::DoNotOptimize(state.iterations());127 tmp *= state.iterations();128 benchmark::DoNotOptimize(tmp);129 }130 131 // 1ns per iteration per entry132 state.SetIterationTime(static_cast<double>(state.range(0)) * 42.0 * 1e-9);133 }134 state.SetComplexityN(state.range(0));135}136BENCHMARK(BM_Complexity_O_N)137 ->RangeMultiplier(2)138 ->Range(1 << 10, 1 << 20)139 ->UseManualTime()140 ->Complexity(benchmark::oN);141BENCHMARK(BM_Complexity_O_N)142 ->RangeMultiplier(2)143 ->Range(1 << 10, 1 << 20)144 ->UseManualTime()145 ->Complexity();146BENCHMARK(BM_Complexity_O_N)147 ->RangeMultiplier(2)148 ->Range(1 << 10, 1 << 20)149 ->UseManualTime()150 ->Complexity([](benchmark::IterationCount n) -> double {151 return static_cast<double>(n);152 });153 154const char *n_test_name = "BM_Complexity_O_N/manual_time";155const char *big_o_n_test_name = "BM_Complexity_O_N/manual_time_BigO";156const char *rms_o_n_test_name = "BM_Complexity_O_N/manual_time_RMS";157const char *enum_auto_big_o_n = "N";158const char *lambda_big_o_n = "f\\(N\\)";159 160// Add enum tests161ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,162 enum_auto_big_o_n, /*family_index=*/3);163 164// Add auto tests165ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,166 enum_auto_big_o_n, /*family_index=*/4);167 168// Add lambda tests169ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,170 lambda_big_o_n, /*family_index=*/5);171 172// ========================================================================= //173// ------------------------- Testing BigO O(NlgN) ------------------------- //174// ========================================================================= //175 176static const double kLog2E = 1.44269504088896340736;177static void BM_Complexity_O_N_log_N(benchmark::State &state) {178 for (auto _ : state) {179 // This test requires a non-zero CPU time to avoid divide-by-zero180 benchmark::DoNotOptimize(state.iterations());181 long tmp = state.iterations();182 benchmark::DoNotOptimize(tmp);183 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {184 benchmark::DoNotOptimize(state.iterations());185 tmp *= state.iterations();186 benchmark::DoNotOptimize(tmp);187 }188 189 state.SetIterationTime(static_cast<double>(state.range(0)) * kLog2E *190 std::log(state.range(0)) * 42.0 * 1e-9);191 }192 state.SetComplexityN(state.range(0));193}194BENCHMARK(BM_Complexity_O_N_log_N)195 ->RangeMultiplier(2)196 ->Range(1 << 10, 1U << 24)197 ->UseManualTime()198 ->Complexity(benchmark::oNLogN);199BENCHMARK(BM_Complexity_O_N_log_N)200 ->RangeMultiplier(2)201 ->Range(1 << 10, 1U << 24)202 ->UseManualTime()203 ->Complexity();204BENCHMARK(BM_Complexity_O_N_log_N)205 ->RangeMultiplier(2)206 ->Range(1 << 10, 1U << 24)207 ->UseManualTime()208 ->Complexity([](benchmark::IterationCount n) {209 return kLog2E * static_cast<double>(n) * std::log(static_cast<double>(n));210 });211 212const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time";213const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_BigO";214const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_RMS";215const char *enum_auto_big_o_n_lg_n = "NlgN";216const char *lambda_big_o_n_lg_n = "f\\(N\\)";217 218// Add enum tests219ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,220 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,221 /*family_index=*/6);222 223// NOTE: auto big-o is wron.g224ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,225 rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,226 /*family_index=*/7);227 228//// Add lambda tests229ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,230 rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,231 /*family_index=*/8);232 233// ========================================================================= //234// -------- Testing formatting of Complexity with captured args ------------ //235// ========================================================================= //236 237void BM_ComplexityCaptureArgs(benchmark::State &state, int n) {238 for (auto _ : state) {239 // This test requires a non-zero CPU time to avoid divide-by-zero240 benchmark::DoNotOptimize(state.iterations());241 long tmp = state.iterations();242 benchmark::DoNotOptimize(tmp);243 for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {244 benchmark::DoNotOptimize(state.iterations());245 tmp *= state.iterations();246 benchmark::DoNotOptimize(tmp);247 }248 249 state.SetIterationTime(static_cast<double>(state.range(0)) * 42.0 * 1e-9);250 }251 state.SetComplexityN(n);252}253 254BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)255 ->UseManualTime()256 ->Complexity(benchmark::oN)257 ->Ranges({{1, 2}, {3, 4}});258 259const std::string complexity_capture_name =260 "BM_ComplexityCaptureArgs/capture_test/manual_time";261 262ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",263 complexity_capture_name + "_RMS", "N",264 /*family_index=*/9);265 266// ========================================================================= //267// --------------------------- TEST CASES END ------------------------------ //268// ========================================================================= //269 270int main(int argc, char *argv[]) { RunOutputTests(argc, argv); }271