Profiling and benchmarking

Performance intuition is wrong surprisingly often. The function you're sure is slow turns out to take 2% of the time; the innocent-looking std::to_string in a loop turns out to dominate. This skill is about getting numbers you can trust: how to time code honestly, which statistic to report, how to stop the optimiser from deleting the thing you're measuring, and how to ask the CPU itself where the time goes.

1. Measure before optimising

The workflow is always the same:

1. Reproduce the slow case with realistic input.
2. Measure the whole thing (wall time) to get a baseline.
3. Profile to find where the time goes — don't guess.
4. Change one thing, measure again, keep it only if it helped.

Amdahl's law keeps you honest: if a function takes 10% of the run time, making it infinitely fast saves at most 10%. Profile first so you spend effort where the time actually is.

2. Which clock?

Wall time vs CPU time answer different questions. A program that sleeps, waits for disk or blocks on a lock has wall time ≫ CPU time; a program using 8 threads can have CPU time ≈ 8 × wall time.

#include <chrono>
#include <cstdio>
#include <ctime>
#include <print>

int main() {
    auto w0 = std::chrono::steady_clock::now();
    std::clock_t c0 = std::clock();

    volatile long sink = 0;
    for (long i = 0; i < 2'000'000; ++i) sink = sink + i;  // busy: CPU ≈ wall

    auto wall = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - w0);
    double cpu = 1000.0 * static_cast<double>(std::clock() - c0) / CLOCKS_PER_SEC;
    std::println("wall {:.1f} ms, cpu {:.1f} ms", wall.count(), cpu);
}

Durations in <chrono> are typed: nanoseconds converts to milliseconds only with an explicit duration_cast (it would lose precision), while the other direction is implicit. duration<double, std::milli> is the easy way to print fractional milliseconds.

3. Repetitions, warm-up, and the right statistic

One measurement is a sample of code + noise. Noise comes from interrupts, other processes, CPU frequency changes and the cache state you happened to start in — and it only ever adds time. So:

• Warm up first: run the code once untimed so caches, page tables, branch predictors and lazily-initialised state are in their steady state.
• Repeat and summarise:
  • minimum — the best estimate of the code's intrinsic cost; ideal for comparing two versions of a small, deterministic function;
  • median — a robust "typical" run; better when the work genuinely varies (allocation, I/O, contention);
  • mean — sensitive to outliers; one 5 ms hiccup ruins a set of 100 µs samples. Report it only alongside a spread.

Worked example: best of N

#include <algorithm>
#include <chrono>
#include <print>
#include <vector>

template <class T>
inline void do_not_optimize(const T& value) {
    asm volatile("" : : "r,m"(value) : "memory");  // see §4
}

template <class F>
std::chrono::nanoseconds best_of(F&& f, int reps) {
    f();  // warm-up, not timed
    auto best = std::chrono::nanoseconds::max();
    for (int i = 0; i < reps; ++i) {
        auto t0 = std::chrono::steady_clock::now();
        f();
        auto t1 = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0));
    }
    return best;
}

int main() {
    std::vector<int> v(100'000, 1);
    auto t = best_of([&] {
        long s = 0;
        for (int x : v) s += x;
        do_not_optimize(s);
    }, 9);
    std::println("best of 9: {} us", t.count() / 1000);
}

Each sample brackets exactly one call with two now() reads. Taking now() once before the loop and once after would also time the loop overhead and smear the samples together, so you'd lose the minimum.

Faded example: the median

Collect every sample instead of only the best, then fill in the median — including the even-count case:

std::ranges::sort(samples);
std::size_t mid = samples.size() / 2;
auto median = /* ??? */;

4. The optimiser will delete your benchmark

At -O2, code whose result is never used is dead, and the compiler removes it. Measured on this machine (1M-element sum, best of 7):

                       -O1        -O2        -O3
sum, result unused     282 µs     0.02 µs    0.02 µs
sum, result kept       284 µs     284 µs     142 µs

The "0.02 µs" isn't a fast sum — there's no sum. Open the Playground's Compiler tab at -O2 and the loop has vanished from the assembly.

Benchmark libraries prevent this with two compiler barriers, which you can write yourself with GCC/Clang inline assembly:

// "value is used by something you can't see": the computation must happen.
template <class T>
inline void do_not_optimize(const T& value) {
    asm volatile("" : : "r,m"(value) : "memory");
}

// "all memory may have been read or written": stores can't be dropped or
// moved across this point.
inline void clobber_memory() {
    asm volatile("" : : : "memory");
}

The harness this app uses has the same tool: crucible::do_not_optimize.

Two more optimiser tricks to watch for:

• Hoisting. Calling a pure function with the same arguments in a timing loop lets the compiler compute it once and reuse the result, even when you pass the result to do_not_optimize. Vary an input every iteration.
• Constant folding. If the input is a compile-time constant, the whole computation may happen at compile time. Generate inputs at run time (from a seed, or argv), never from literals.

5. Microbenchmark pitfalls

• Cache warmth. Timing the same 4 KB array a thousand times measures L1 cache speed. If production data doesn't fit in cache, benchmark with production-sized data (or flush between runs).

• Branch predictor training. Repeating identical input trains the predictor perfectly. Measured here, a loop that adds only the elements ≥ 128 of a million random bytes:

  GCC -O2 (branchless cmov)            unsorted 568 µs   sorted 564 µs
  GCC -O2 -fno-if-conversion (branch)  unsorted 3472 µs  sorted 434 µs
  

  With a real branch, unsorted data is 8× slower — every other branch is mispredicted. GCC normally avoids the branch altogether, which is why the classic "sorted is faster" demo often shows nothing. Always look at the asm before explaining a timing.

• Frequency scaling and turbo. CPUs change clock speed with load and temperature. Warm up, keep runs short and repeated, and compare versions in the same session (interleave A, B, A, B).

• Noisy neighbours. Other processes, other agents, a browser. Use the minimum, pin to a core (taskset -c 3 ./bench) on a quiet machine, and distrust differences under ~5%.

6. Benchmarks at scale: Google Benchmark, and this app's probe

Google Benchmark (#include <benchmark/benchmark.h>) packages all of the above. A benchmark is a function with a State loop; the library decides how many iterations to run, repeats, and reports statistics:

static void BM_dedupe(benchmark::State& state) {
    auto v = make_input(state.range(0));
    for (auto _ : state) {
        benchmark::DoNotOptimize(dedupe_keep_first(v));
    }
    state.SetComplexityN(state.range(0));
}
BENCHMARK(BM_dedupe)->RangeMultiplier(2)->Range(1 << 10, 1 << 16)->Complexity();

->Complexity() fits the times against O(1), O(n), O(n log n), O(n²)… This app's complexity probe does something similar and simpler:

1. Run your code at several sizes n (say 2048, 4096, 8192, 16384), keeping the minimum of a few repetitions at each size.
2. Fit a straight line to log(time) vs log(n). Its slope is the exponent: ≈ 1 for O(n), ≈ 2 for O(n²), a little over 1 for O(n log n).
3. Compare with the reference solution measured the same way, and flag yours only if the slope is clearly steeper and it's at least 3× slower at the largest size — so timing noise alone can't fail you.

7. Asking the CPU: perf

Timers tell you how long; hardware counters tell you why. On Linux, perf reads them. (It isn't available inside this app's sandbox; run it on your own machine. If it refuses, lower /proc/sys/kernel/perf_event_paranoid or run as root.)

perf stat — whole-program counters (illustrative output):

$ perf stat -e cycles,instructions,cache-misses,branch-misses ./analyse big.log

 Performance counter stats for './analyse big.log':

     4,812,330,117      cycles
     1,402,118,905      instructions        #  0.29  insn per cycle
        61,903,224      cache-misses
         1,208,447      branch-misses

       1.271 seconds time elapsed

Read it top-down. IPC (instructions per cycle) of 0.29 on a core that can retire 4+ per cycle means it's mostly waiting — here on memory, given 62M cache misses. Pointer-chasing data structures look like this. A high branch-miss count with good cache behaviour points at unpredictable branches instead.

perf record / perf report — where the time goes (illustrative output):

$ perf record -g ./analyse big.log
$ perf report --stdio
  Children  Self  Symbol
    92.1%   0.4%  main
    71.3%  45.2%  count_by_user
    25.8%  25.8%  __memcmp_avx2_movbe
    14.6%  14.6%  malloc

Self is time in the function itself; Children includes its callees. Here count_by_user and the memcmp/malloc it triggers are the whole story — that's where to look. Build with -g (and -fno-omit-frame-pointer for reliable call stacks) so the report has names and lines.

Flame graphs (perf script | stackcollapse-perf.pl | flamegraph.pl) draw the same call stacks as nested bars whose width is time — the fastest way to spot the one wide tower in a big program.

8. Compiler flags that matter

• -O2 is the sane default for release builds; -O3 adds more aggressive inlining and vectorisation (it halved the sum above), sometimes at the cost of code size. Measure both.
• -march=native lets the compiler use every instruction your CPU has (AVX2, AVX-512…). The binary may not run on older machines.
• LTO (-flto) optimises across translation units — inlining a function from another .cpp file.
• PGO (-fprofile-generate, run a representative workload, -fprofile-use) tells the compiler which branches are hot. Typical wins: 10–30% on branchy code.

The Playground's Compiler tab shows the assembly for each of these flags side by side — the quickest way to see what a flag actually changed.

Summary

• Measure, profile, change one thing, measure again.
• Time intervals with steady_clock; know whether you want wall or CPU time.
• Warm up; report the minimum for deterministic code, the median for noisy work; distrust the mean.
• Keep results alive (do_not_optimize), vary inputs, and check the asm.
• Use perf stat to learn why (IPC, cache and branch misses) and perf record to learn where.