| 1 |
#undef NDEBUG |
| 2 |
#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 |
|
| 11 |
namespace { |
| 12 |
|
| 13 |
#define ADD_COMPLEXITY_CASES(...) \ |
| 14 |
int CONCAT(dummy, __LINE__) = AddComplexityTest(__VA_ARGS__) |
| 15 |
|
| 16 |
int 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 namespace |
| 65 |
|
| 66 |
// ========================================================================= // |
| 67 |
// --------------------------- Testing BigO O(1) --------------------------- // |
| 68 |
// ========================================================================= // |
| 69 |
|
| 70 |
void BM_Complexity_O1(benchmark::State &state) { |
| 71 |
for (auto _ : state) { |
| 72 |
// This test requires a non-zero CPU time to avoid divide-by-zero |
| 73 |
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 iteration |
| 83 |
state.SetIterationTime(42 * 1e-9); |
| 84 |
} |
| 85 |
state.SetComplexityN(state.range(0)); |
| 86 |
} |
| 87 |
BENCHMARK(BM_Complexity_O1) |
| 88 |
->Range(1, 1 << 18) |
| 89 |
->UseManualTime() |
| 90 |
->Complexity(benchmark::o1); |
| 91 |
BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->UseManualTime()->Complexity(); |
| 92 |
BENCHMARK(BM_Complexity_O1) |
| 93 |
->Range(1, 1 << 18) |
| 94 |
->UseManualTime() |
| 95 |
->Complexity([](benchmark::IterationCount) { return 1.0; }); |
| 96 |
|
| 97 |
const char *one_test_name = "BM_Complexity_O1/manual_time"; |
| 98 |
const char *big_o_1_test_name = "BM_Complexity_O1/manual_time_BigO"; |
| 99 |
const char *rms_o_1_test_name = "BM_Complexity_O1/manual_time_RMS"; |
| 100 |
const char *enum_auto_big_o_1 = "\\([0-9]+\\)"; |
| 101 |
const char *lambda_big_o_1 = "f\\(N\\)"; |
| 102 |
|
| 103 |
// Add enum tests |
| 104 |
ADD_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 tests |
| 108 |
ADD_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 tests |
| 112 |
ADD_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 |
|
| 119 |
void BM_Complexity_O_N(benchmark::State &state) { |
| 120 |
for (auto _ : state) { |
| 121 |
// This test requires a non-zero CPU time to avoid divide-by-zero |
| 122 |
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 entry |
| 132 |
state.SetIterationTime(static_cast<double>(state.range(0)) * 42.0 * 1e-9); |
| 133 |
} |
| 134 |
state.SetComplexityN(state.range(0)); |
| 135 |
} |
| 136 |
BENCHMARK(BM_Complexity_O_N) |
| 137 |
->RangeMultiplier(2) |
| 138 |
->Range(1 << 10, 1 << 20) |
| 139 |
->UseManualTime() |
| 140 |
->Complexity(benchmark::oN); |
| 141 |
BENCHMARK(BM_Complexity_O_N) |
| 142 |
->RangeMultiplier(2) |
| 143 |
->Range(1 << 10, 1 << 20) |
| 144 |
->UseManualTime() |
| 145 |
->Complexity(); |
| 146 |
BENCHMARK(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 |
|
| 154 |
const char *n_test_name = "BM_Complexity_O_N/manual_time"; |
| 155 |
const char *big_o_n_test_name = "BM_Complexity_O_N/manual_time_BigO"; |
| 156 |
const char *rms_o_n_test_name = "BM_Complexity_O_N/manual_time_RMS"; |
| 157 |
const char *enum_auto_big_o_n = "N"; |
| 158 |
const char *lambda_big_o_n = "f\\(N\\)"; |
| 159 |
|
| 160 |
// Add enum tests |
| 161 |
ADD_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 tests |
| 165 |
ADD_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 tests |
| 169 |
ADD_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 |
|
| 176 |
static const double kLog2E = 1.44269504088896340736; |
| 177 |
static 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-zero |
| 180 |
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 |
} |
| 194 |
BENCHMARK(BM_Complexity_O_N_log_N) |
| 195 |
->RangeMultiplier(2) |
| 196 |
->Range(1 << 10, 1U << 24) |
| 197 |
->UseManualTime() |
| 198 |
->Complexity(benchmark::oNLogN); |
| 199 |
BENCHMARK(BM_Complexity_O_N_log_N) |
| 200 |
->RangeMultiplier(2) |
| 201 |
->Range(1 << 10, 1U << 24) |
| 202 |
->UseManualTime() |
| 203 |
->Complexity(); |
| 204 |
BENCHMARK(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 |
|
| 212 |
const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time"; |
| 213 |
const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_BigO"; |
| 214 |
const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_RMS"; |
| 215 |
const char *enum_auto_big_o_n_lg_n = "NlgN"; |
| 216 |
const char *lambda_big_o_n_lg_n = "f\\(N\\)"; |
| 217 |
|
| 218 |
// Add enum tests |
| 219 |
ADD_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.g |
| 224 |
ADD_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 tests |
| 229 |
ADD_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 |
|
| 237 |
void BM_ComplexityCaptureArgs(benchmark::State &state, int n) { |
| 238 |
for (auto _ : state) { |
| 239 |
// This test requires a non-zero CPU time to avoid divide-by-zero |
| 240 |
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 |
|
| 254 |
BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100) |
| 255 |
->UseManualTime() |
| 256 |
->Complexity(benchmark::oN) |
| 257 |
->Ranges({{1, 2}, {3, 4}}); |
| 258 |
|
| 259 |
const std::string complexity_capture_name = |
| 260 |
"BM_ComplexityCaptureArgs/capture_test/manual_time"; |
| 261 |
|
| 262 |
ADD_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 |
|
| 270 |
int main(int argc, char *argv[]) { RunOutputTests(argc, argv); } |