Profiling & Benchmarking

By the end of this lesson you'll be able to time C++ code accurately with std::chrono, avoid the traps that make micro-benchmarks lie, reach for the right profiler to find real hotspots, and reason about whether an optimisation is even worth doing — so you optimise what matters instead of guessing.

1. Measure, Don't Guess — Timing with std::chrono

The single most expensive habit in performance work is guessing. Your intuition about which line is slow is almost always wrong, because the CPU's caches, branch predictor, and the optimiser reshape your code in ways you can't see. The cure is to measure. The simplest tool is std::chrono: take a timestamp before the work, another after, and subtract. high_resolution_clock is the finest-grained clock the standard library offers — perfect for small benchmarks.

The pattern is always the same: auto start = Clock::now(); → do the work → auto end = Clock::now(); → duration_cast the gap into the unit you want (microseconds here). Read the worked example, run it, and notice it checks both answers match before comparing speed — a fast wrong answer is worthless.

#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>   // accumulate, iota
using namespace std;

// chrono is the standard timing toolkit. high_resolution_clock is the
// finest-grained clock available, good for micro-benchmarks.
using Clock = chrono::high_resolution_clock;

// APPROACH A: sum with a hand-written loop.
long long sumLoop(const vector<int>& v) {
    long long total = 0;
    for (int x : v) total += x;   // visit every element once -> O(n)
    return total;
}

...

Your turn. The program below times how long it takes to build a big vector — fill in the two timestamp blanks and the conversion, then run it.

#include <iostream>
#include <chrono>
#include <vector>
using namespace std;

using Clock = chrono::high_resolution_clock;

int main() {
    // 🎯 YOUR TURN — time how long it takes to build a big vector.
    // Replace each ___ then press "Try it Yourself".

    const int N = 500000;
    vector<long long> v;

    // 1) Take a timestamp BEFORE the work
    auto start = ___;        // 👉 Clock::now()

    long long sum = 0;
    for (int i = 1; i <= N; i++) { v.push_back(i); sum += i; }

    // 2)
...

2. Micro-Benchmark Pitfalls

A micro-benchmark times a tiny isolated snippet — and tiny snippets lie more than any other kind of measurement. The most infamous trap: if you compute a result and never use it, an optimising compiler is allowed to delete the entire calculation. Your benchmark then reports near-zero time and you celebrate a speed-up that never happened. The fix is to make the result observable — print it, or store it in a volatile so the compiler must actually do the work.

#include <iostream>
#include <chrono>
using namespace std;

using Clock = chrono::high_resolution_clock;

int main() {
    const int N = 100000000;

    // PITFALL: this loop computes a sum that is NEVER USED.
    // With -O2 the optimiser deletes the whole loop -> ~0 us. The
    // "blazing fast" result is an illusion: nothing actually ran.
    {
        auto start = Clock::now();
        long long sum = 0;
        for (int i = 0; i < N; i++) sum += i;   // result discarded
        auto end = C
...

3. Profilers — Find the Real Hotspot

chrono answers "how long does this take?". A profiler answers the more important question: "across my whole program, where is the time going?". It runs your program and reports a breakdown by function. A hotspot is a function with a large share of the total — that's where optimisation pays off. There are two flavours: sampling profilers (like perf) interrupt the program thousands of times a second and record where it is, giving low overhead and realistic numbers; instrumenting profilers (like Callgrind) count every call exactly, giving precise call graphs but running much slower.

Whatever the tool, reading a profile is the same skill: look at the top of the sorted list, ignore the long tail. A function eating 60% of the run time is your target; a hundred functions at 0.2% each are not worth touching. This is where your effort multiplies.

4. Is It Even Worth It? Amdahl's Law & Big-O

Before you optimise, ask what the payoff can be. Amdahl's law says your overall speed-up is capped by the part you don't improve. If a function is 90% of the run time, making it infinitely fast still only makes the whole program 10× faster — and optimising a 10% slice can never beat 1.11× no matter what. This is the maths behind "optimise the biggest slice the profiler shows you."

#include <iostream>
#include <iomanip>
using namespace std;

// Amdahl's law: if a fraction p of the program can be sped up by factor s,
// the WHOLE program speeds up by only:  1 / ((1 - p) + p / s)
// The (1 - p) part you did NOT optimise puts a hard ceiling on your gains.
double amdahl(double p, double s) {
    return 1.0 / ((1.0 - p) + p / s);
}

int main() {
    cout << fixed << setprecision(2);

    // Suppose a function is 90% of total run time (p = 0.90).
    // Even if you make THAT fun
...

The other lens is big-O vs constant factors. Big-O tells you how cost grows as the input grows — O(n) doubles when the input doubles, O(n²) quadruples. It is the most reliable performance lever you have, because a better big-O wins by ever-larger margins as data scales. But big-O hides the constant factor: for small inputs a "worse" algorithm with a tiny constant can win. Below, replace the blank so you can watch an O(1) hash lookup demolish an O(n) linear scan as soon as the data is non-trivial.

#include <iostream>
#include <chrono>
#include <vector>
#include <unordered_set>
using namespace std;

using Clock = chrono::high_resolution_clock;

int main() {
    // 🎯 YOUR TURN — big-O vs constant factors.
    // Looking a value up in a vector is O(n) (scan every element).
    // Looking it up in an unordered_set is O(1) average (hash jump).
    const int N = 20000;
    vector<int> vec;
    unordered_set<int> set;
    for (int i = 0; i < N; i++) { vec.push_back(i); set.insert(i); }

    int
...

#include <iostream>
#include <chrono>
#include <string>
using namespace std;

using Clock = chrono::high_resolution_clock;

int main() {
    // 🎯 MINI-CHALLENGE: benchmark string building
    // Compare two ways to build one big string of 100000 "x" characters.
    //
    // 1. APPROACH A — naive concatenation in a loop:
    //      string a;
    //      for (...) a = a + "x";     // each += may COPY the whole string
    //    Time it with Clock::now() before and after.
    //
    // 2. APPROAC
...