aboutsummaryrefslogtreecommitdiff
path: root/test/complexity_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'test/complexity_test.cc')
-rw-r--r--test/complexity_test.cc160
1 files changed, 101 insertions, 59 deletions
diff --git a/test/complexity_test.cc b/test/complexity_test.cc
index 76891e0..0729d15 100644
--- a/test/complexity_test.cc
+++ b/test/complexity_test.cc
@@ -69,35 +69,44 @@ int AddComplexityTest(const std::string &test_name,
void BM_Complexity_O1(benchmark::State &state) {
for (auto _ : state) {
- for (int i = 0; i < 1024; ++i) {
- benchmark::DoNotOptimize(i);
+ // This test requires a non-zero CPU time to avoid divide-by-zero
+ benchmark::DoNotOptimize(state.iterations());
+ double tmp = static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
+ benchmark::DoNotOptimize(state.iterations());
+ tmp *= static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
}
+
+ // always 1ns per iteration
+ state.SetIterationTime(42 * 1e-9);
}
state.SetComplexityN(state.range(0));
}
-BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity(benchmark::o1);
-BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->Complexity();
BENCHMARK(BM_Complexity_O1)
->Range(1, 1 << 18)
+ ->UseManualTime()
+ ->Complexity(benchmark::o1);
+BENCHMARK(BM_Complexity_O1)->Range(1, 1 << 18)->UseManualTime()->Complexity();
+BENCHMARK(BM_Complexity_O1)
+ ->Range(1, 1 << 18)
+ ->UseManualTime()
->Complexity([](benchmark::IterationCount) { return 1.0; });
-const char *one_test_name = "BM_Complexity_O1";
-const char *big_o_1_test_name = "BM_Complexity_O1_BigO";
-const char *rms_o_1_test_name = "BM_Complexity_O1_RMS";
-const char *enum_big_o_1 = "\\([0-9]+\\)";
-// FIXME: Tolerate both '(1)' and 'lgN' as output when the complexity is auto
-// deduced.
-// See https://github.com/google/benchmark/issues/272
-const char *auto_big_o_1 = "(\\([0-9]+\\))|(lgN)";
+const char *one_test_name = "BM_Complexity_O1/manual_time";
+const char *big_o_1_test_name = "BM_Complexity_O1/manual_time_BigO";
+const char *rms_o_1_test_name = "BM_Complexity_O1/manual_time_RMS";
+const char *enum_auto_big_o_1 = "\\([0-9]+\\)";
const char *lambda_big_o_1 = "f\\(N\\)";
// Add enum tests
ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
- enum_big_o_1, /*family_index=*/0);
+ enum_auto_big_o_1, /*family_index=*/0);
-// Add auto enum tests
+// Add auto tests
ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
- auto_big_o_1, /*family_index=*/1);
+ enum_auto_big_o_1, /*family_index=*/1);
// Add lambda tests
ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
@@ -107,43 +116,44 @@ ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
// --------------------------- Testing BigO O(N) --------------------------- //
// ========================================================================= //
-std::vector<int> ConstructRandomVector(int64_t size) {
- std::vector<int> v;
- v.reserve(static_cast<size_t>(size));
- for (int i = 0; i < size; ++i) {
- v.push_back(static_cast<int>(std::rand() % size));
- }
- return v;
-}
-
void BM_Complexity_O_N(benchmark::State &state) {
- auto v = ConstructRandomVector(state.range(0));
- // Test worst case scenario (item not in vector)
- const int64_t item_not_in_vector = state.range(0) * 2;
for (auto _ : state) {
- auto it = std::find(v.begin(), v.end(), item_not_in_vector);
- benchmark::DoNotOptimize(it);
+ // This test requires a non-zero CPU time to avoid divide-by-zero
+ benchmark::DoNotOptimize(state.iterations());
+ double tmp = static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
+ benchmark::DoNotOptimize(state.iterations());
+ tmp *= static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ }
+
+ // 1ns per iteration per entry
+ state.SetIterationTime(static_cast<double>(state.range(0)) * 42 * 1e-9);
}
state.SetComplexityN(state.range(0));
}
BENCHMARK(BM_Complexity_O_N)
->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
+ ->Range(1 << 10, 1 << 20)
+ ->UseManualTime()
->Complexity(benchmark::oN);
BENCHMARK(BM_Complexity_O_N)
->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
+ ->Range(1 << 10, 1 << 20)
+ ->UseManualTime()
+ ->Complexity();
+BENCHMARK(BM_Complexity_O_N)
+ ->RangeMultiplier(2)
+ ->Range(1 << 10, 1 << 20)
+ ->UseManualTime()
->Complexity([](benchmark::IterationCount n) -> double {
return static_cast<double>(n);
});
-BENCHMARK(BM_Complexity_O_N)
- ->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
- ->Complexity();
-const char *n_test_name = "BM_Complexity_O_N";
-const char *big_o_n_test_name = "BM_Complexity_O_N_BigO";
-const char *rms_o_n_test_name = "BM_Complexity_O_N_RMS";
+const char *n_test_name = "BM_Complexity_O_N/manual_time";
+const char *big_o_n_test_name = "BM_Complexity_O_N/manual_time_BigO";
+const char *rms_o_n_test_name = "BM_Complexity_O_N/manual_time_RMS";
const char *enum_auto_big_o_n = "N";
const char *lambda_big_o_n = "f\\(N\\)";
@@ -151,40 +161,57 @@ const char *lambda_big_o_n = "f\\(N\\)";
ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
enum_auto_big_o_n, /*family_index=*/3);
+// Add auto tests
+ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
+ enum_auto_big_o_n, /*family_index=*/4);
+
// Add lambda tests
ADD_COMPLEXITY_CASES(n_test_name, big_o_n_test_name, rms_o_n_test_name,
- lambda_big_o_n, /*family_index=*/4);
+ lambda_big_o_n, /*family_index=*/5);
// ========================================================================= //
-// ------------------------- Testing BigO O(N*lgN) ------------------------- //
+// ------------------------- Testing BigO O(NlgN) ------------------------- //
// ========================================================================= //
+static const double kLog2E = 1.44269504088896340736;
static void BM_Complexity_O_N_log_N(benchmark::State &state) {
- auto v = ConstructRandomVector(state.range(0));
for (auto _ : state) {
- std::sort(v.begin(), v.end());
+ // This test requires a non-zero CPU time to avoid divide-by-zero
+ benchmark::DoNotOptimize(state.iterations());
+ double tmp = static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
+ benchmark::DoNotOptimize(state.iterations());
+ tmp *= static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ }
+
+ state.SetIterationTime(static_cast<double>(state.range(0)) * kLog2E *
+ std::log(state.range(0)) * 42 * 1e-9);
}
state.SetComplexityN(state.range(0));
}
-static const double kLog2E = 1.44269504088896340736;
BENCHMARK(BM_Complexity_O_N_log_N)
->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
+ ->Range(1 << 10, 1U << 24)
+ ->UseManualTime()
->Complexity(benchmark::oNLogN);
BENCHMARK(BM_Complexity_O_N_log_N)
->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
- ->Complexity([](benchmark::IterationCount n) {
- return kLog2E * static_cast<double>(n) * log(static_cast<double>(n));
- });
+ ->Range(1 << 10, 1U << 24)
+ ->UseManualTime()
+ ->Complexity();
BENCHMARK(BM_Complexity_O_N_log_N)
->RangeMultiplier(2)
- ->Range(1 << 10, 1 << 16)
- ->Complexity();
+ ->Range(1 << 10, 1U << 24)
+ ->UseManualTime()
+ ->Complexity([](benchmark::IterationCount n) {
+ return kLog2E * static_cast<double>(n) * std::log(static_cast<double>(n));
+ });
-const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N";
-const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_BigO";
-const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N_RMS";
+const char *n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time";
+const char *big_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_BigO";
+const char *rms_o_n_lg_n_test_name = "BM_Complexity_O_N_log_N/manual_time_RMS";
const char *enum_auto_big_o_n_lg_n = "NlgN";
const char *lambda_big_o_n_lg_n = "f\\(N\\)";
@@ -193,11 +220,16 @@ ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
/*family_index=*/6);
-// Add lambda tests
+// NOTE: auto big-o is wron.g
ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
- rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,
+ rms_o_n_lg_n_test_name, enum_auto_big_o_n_lg_n,
/*family_index=*/7);
+//// Add lambda tests
+ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
+ rms_o_n_lg_n_test_name, lambda_big_o_n_lg_n,
+ /*family_index=*/8);
+
// ========================================================================= //
// -------- Testing formatting of Complexity with captured args ------------ //
// ========================================================================= //
@@ -205,21 +237,31 @@ ADD_COMPLEXITY_CASES(n_lg_n_test_name, big_o_n_lg_n_test_name,
void BM_ComplexityCaptureArgs(benchmark::State &state, int n) {
for (auto _ : state) {
// This test requires a non-zero CPU time to avoid divide-by-zero
- auto iterations = state.iterations();
- benchmark::DoNotOptimize(iterations);
+ benchmark::DoNotOptimize(state.iterations());
+ double tmp = static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
+ benchmark::DoNotOptimize(state.iterations());
+ tmp *= static_cast<double>(state.iterations());
+ benchmark::DoNotOptimize(tmp);
+ }
+
+ state.SetIterationTime(static_cast<double>(state.range(0)) * 42 * 1e-9);
}
state.SetComplexityN(n);
}
BENCHMARK_CAPTURE(BM_ComplexityCaptureArgs, capture_test, 100)
+ ->UseManualTime()
->Complexity(benchmark::oN)
->Ranges({{1, 2}, {3, 4}});
const std::string complexity_capture_name =
- "BM_ComplexityCaptureArgs/capture_test";
+ "BM_ComplexityCaptureArgs/capture_test/manual_time";
ADD_COMPLEXITY_CASES(complexity_capture_name, complexity_capture_name + "_BigO",
- complexity_capture_name + "_RMS", "N", /*family_index=*/9);
+ complexity_capture_name + "_RMS", "N",
+ /*family_index=*/9);
// ========================================================================= //
// --------------------------- TEST CASES END ------------------------------ //
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-20 22:25:47 +0000