Benchmarking the STL

Building and Running Benchmarks

Read our README's Benchmarking section.

Writing a New Benchmark

• Read Google Benchmark's User Guide.
• Review the existing benchmarks and follow our conventions.
  • Please avoid shadowing Standard Library names. For example, the benchmark for std::sort() shouldn't be called sort().
• Decide whether you should create a new file or extend an existing file.
  • If you create a new file, you'll need to add it to the build. At the bottom of benchmarks/CMakeLists.txt, insert add_benchmark(MEOW src/MEOW.cpp), where MEOW is the name of your file. Keep the list of benchmarks in sorted order.
• Your benchmark function should take (benchmark::State& state) and return void. A basic benchmark example:

  void meow(benchmark::State& state) {
      // setup code
      for (auto _ : state) {
          benchmark::DoNotOptimize(/* input */);
          // code that you want to benchmark
          benchmark::DoNotOptimize(/* output */);
      }
  }

• Use benchmark::DoNotOptimize(...) to prevent the compiler from optimizing away what you're trying to measure.
• Call your benchmark with BENCHMARK(meow);.
  • If you're creating a new file, you'll also need BENCHMARK_MAIN(); at the end.
• More advanced usage can call your benchmark function with varying arguments.
  • See examples where BENCHMARK(meow) is followed by ->Apply, ->Range, and so forth, where state.range(0) gets the varying arguments (and state.range(1) can get a second varying argument, etc.).

Calculating Speedups

Read What We Talk About When We Talk About Performance by Bruce Dawson.

• Always calculate speedups as Old Time / New Time. Never present them in any other way.
  • For example, if something previously took 22 seconds, and now takes 7 seconds, that's a 3.14x speedup.
• To get your New Times, ensure that you've merged main into your branch (git merge main should report "Already up to date."), then build and run your benchmarks.
• To get your Old Times, you can temporarily revert your product code changes, then build and run your benchmarks. This will create a throwaway branch:

  git switch -c REVERT-PRODUCT-CODE
  git restore --source=main stl
  git add stl
  git commit -m "Temporarily revert product code"
  

• Then you can prepare a Markdown table with Old Time, New Time, and Speedup columns.