5

I would like to benchmark various sorting algorithms using Google Benchmark. If I use

static void StdSort(benchmark::State& state) {
  auto v = generate_random_vector(state.range(0));
  for (auto _ : state)
    std::sort(std::begin(v), std::end(v));
}
BENCHMARK(StdSort)->Arg(10)->Arg(1000)->Arg(1'000'000);

I will end up sorting a pre-sorted vector most of the time. I read in the manual that I could use manual timing to only benchmark the sections I care about:

static void StdSort(benchmark::State& state) {
  auto v = generate_random_vector(state.range(0));
  std::default_random_engine gen;
  for (auto _ : state) {
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(std::begin(v), std::end(v));
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed_seconds =
        std::chrono::duration_cast<std::chrono::duration<double>>(end - start);

    state.SetIterationTime(elapsed_seconds.count());
    std::shuffle(std::begin(v), std::end(v), gen);
  }
}
BENCHMARK(StdSort)->Arg(10)->Arg(1000)->Arg(1'000'000)->UseManualTime();

Is this the right way to benchmark sorting algorithms using Google Benchmark? Is there a better approach?

Touloudou
  • 2,079
  • 1
  • 17
  • 28
  • Is there any risk the compiler will optimize away the whole code since I am not actually reading from the vector? Should I just add one superfluous read after the benchmarking loop? – Touloudou Sep 15 '21 at 09:43
  • 1
    There is such a risk. Take a look at `benchmark::DoNotOptimize()`. – Evg Sep 15 '21 at 09:48
  • 1
    It seems that measuring with `choro` is indeed more accurate. Here is a related question: [Google benchmark `state.PauseTiming()` and `state.ResumeTiming()` take a long time](https://stackoverflow.com/q/56660845). – Evg Sep 15 '21 at 10:11
  • Instead of doing a random shuffle, you could memcpy (or std::copy) the same unsorted data which is much cheaper. Especially for small sorts, branch prediction might learn the patterns of branching and give unrealistic perf numbers. Or if there's an API for producing a sorted copy of an array, instead of an in-place sort, that would be nice... – Peter Cordes Sep 16 '21 at 03:09

0 Answers0