Repository: google/benchmark
File: test/complexity_test.cc (C++)

Code before:
}  // end namespace

// ========================================================================= //
// --------------------------- Testing BigO O(1) --------------------------- //
// ========================================================================= //

void BM_Complexity_O1(benchmark::State &state) {
  for (auto _ : state) {
    for (int i = 0; i < 1024; ++i) {
      benchmark::DoNotOptimize(i);
    }
  }
  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)
    ->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)|(N\\^2)";
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);

// Add auto enum tests
ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
                     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,
                     lambda_big_o_1, /*family_index=*/2);

// ========================================================================= //
// --------------------------- 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));

Review comment (performance):
does this mean complexity only works for manual time?  do we have any tests where we use complexity with real time?

Code after:
}  // end namespace

// ========================================================================= //
// --------------------------- Testing BigO O(1) --------------------------- //
// ========================================================================= //

void BM_Complexity_O1(benchmark::State &state) {
  for (auto _ : state) {
    // This test requires a non-zero CPU time to avoid divide-by-zero
    benchmark::DoNotOptimize(state.iterations());
    double tmp = state.iterations();
    benchmark::DoNotOptimize(tmp);
    for (benchmark::IterationCount i = 0; i < state.iterations(); ++i) {
      benchmark::DoNotOptimize(state.iterations());
      tmp *= 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)
    ->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/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_auto_big_o_1, /*family_index=*/0);

// Add auto tests
ADD_COMPLEXITY_CASES(one_test_name, big_o_1_test_name, rms_o_1_test_name,
                     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,
                     lambda_big_o_1, /*family_index=*/2);