Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Fast is a specification

Predict, measure, change

A performance claim is a hypothesis until it is measured. The correct workflow is to predict the cost, measure it with a reliable tool, then change the code and re-measure. Only after the measurement can a claim be accepted as true.

Guessing about performance fails because modern compilers and CPUs are too clever. A statement that a piece of code is slow can be incorrect, and a statement that it is fast can be incorrect as well. The only reliable route is to turn the claim into a measurement, which is why this chapter gives you the tools rather than a list of rules of thumb.

Measuring with std::chrono

C++ provides a portable, monotonic clock in the standard library: std::chrono::steady_clock. Unlike std::chrono::system_clock, the steady clock never jumps because of adjustments to the system time. Use steady_clock::now() before and after the code region and compute the difference. The following inline example measures the time taken to execute a trivial loop.

#include <chrono>
#include <iostream>

int main() {
    auto start = std::chrono::steady_clock::now();
    volatile int sum = 0; // prevent optimisation of the loop body
    for (int i = 0; i < 10'000'000; ++i) {
        sum += i;
    }
    auto end = std::chrono::steady_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "elapsed: " << elapsed.count() << " µs\n";
    return 0;
}

The program prints a single line such as elapsed: 12345 µs. The unit is a concrete, reproducible quantity that the test harness can match. Because steady_clock is monotonic, the measurement is not affected by clock adjustments, NTP updates, or daylight-saving changes. This makes it the preferred tool for micro-benchmarking code that runs for a short period.

For more reliable numbers, run the loop several times and record each measurement. Compute the median or the minimum value. The minimum discards noise from background activity, while the median reduces the impact of outliers. Warm up the code once before timing to let the processor reach its steady frequency and to populate caches. A typical benchmarking harness therefore performs a warm-up iteration, followed by a fixed number of timed iterations, and finally reports the best or median elapsed time.

The volatile in the timing loop is important. Without it the compiler can see that the loop has no observable effect and delete it entirely under the as-if rule, making the measured time zero. volatile forces the writes to happen, so the loop measures real work. The same trick is why micro-benchmarks accumulate into a volatile sink rather than returning a value that is never used.

A single measurement is not a number you can trust. Run the workload several times and report the spread, because a two-fold difference between runs is common under system noise.

The as-if rule and optimizer levels

The C++ as-if rule permits the compiler to transform any program as long as the observable behaviour is unchanged. Observable behaviour consists of the program’s side effects on volatile objects, file I/O, and the values returned from main. Therefore a build compiled with -O2 or -O3 can reorder statements, inline functions, or eliminate dead code, provided the resulting side effects match the source semantics. A build with -O0 performs almost no optimisation. It preserves the source order but does not represent the performance of a real-world binary. Benchmarking an unoptimised build therefore yields a number that the production binary will never exhibit. The meaningful comparison is always between two programs built with the same optimisation level.

Consider a function that adds two integers and returns the result. With -O0 the compiler emits a call to the function, a load of each argument, an addition, and a return. With -O2 the compiler can inline the function, keep the arguments in registers, and avoid the call entirely. The observable result, the returned sum, is identical, so the transformation is permitted. Benchmarks that report the speed of the -O0 version therefore mislead. They measure the cost of the extra call and the lack of register allocation, not the intrinsic cost of the algorithm.

Move vs copy

Moving a value transfers ownership of its resources without allocating or copying the underlying data. Copying, by contrast, must duplicate the resources. The instrumented Counter struct below records how many copy and move constructions occur. The book_example registration verifies the printed statistics. By examining the counters you can see that a move operation incurs far less work than a copy, especially when the underlying type manages heap memory or other expensive resources. This observation underlies the design of many standard library containers that prefer move over copy when they can.

#include <iostream>
#include <utility>

struct Counter {
    static int copies;
    static int moves;
    Counter() = default;
    Counter(const Counter&) { ++copies; }
    Counter(Counter&&) noexcept { ++moves; }
    Counter& operator=(const Counter&) = delete;
    Counter& operator=(Counter&&) = delete;
    ~Counter() = default;
};

int Counter::copies = 0;
int Counter::moves = 0;

int main() {
    Counter a;
    Counter b = a; // copy
    Counter c = std::move(a); // move
    std::cout << "copy: " << Counter::copies << " move: " << Counter::moves << "\n";
    return 0;
}

Running the program yields a line such as copy: 1 move: 1. The numbers confirm that the explicit copy and explicit move each invoke a single constructor, and that the default-constructed object does not contribute to the counts. If you replace the copy with another move, the copy counter stays at zero, showing the performance advantage of move semantics in realistic code. In larger containers, moving a std::vector merely swaps its internal pointer and size, while copying allocates new storage and copies each element, an order of magnitude more work.

Move operations are noexcept for the standard containers, and that single word unlocks a real optimisation. std::vector uses the move constructor during growth only when it is guaranteed not to throw. If the move can throw, the vector has to copy instead, to keep the strong exception guarantee. Marking your own types’ move constructors noexcept is therefore not ceremony. It is what lets vector move them during reallocation rather than copy.

See Chapter 5 for a detailed comparison of move versus copy costs.

Copy elision and RVO

When a function returns a prvalue of class type, the language permits the compiler to construct the result directly in the caller’s storage. This copy-elision eliminates both the copy and the move constructor calls. The classic case is the return value optimisation (RVO). The following example prints markers from the constructors and destructors. If elision occurs, only the constructor and destructor of the local object appear, and no copy or move messages are printed. This behaviour is guaranteed by the standard when the criteria for NRVO are met, and modern compilers perform it even at -O0.

#include <iostream>
#include <utility>

struct Marker {
    static int copies;
    static int moves;
    Marker() { std::cout << "ctor\n"; }
    Marker(const Marker&) { ++copies; std::cout << "copy\n"; }
    Marker(Marker&&) noexcept { ++moves; std::cout << "move\n"; }
    Marker& operator=(const Marker&) = delete;
    Marker& operator=(Marker&&) = delete;
    ~Marker() { std::cout << "dtor\n"; }
};

int Marker::copies = 0;
int Marker::moves = 0;

Marker make_marker() {
    Marker m; // ctor
    return m; // should be elided, no copy/move
}

int main() {
    Marker x = make_marker(); // elision expected
    (void)x;
    std::cerr << "copies=" << Marker::copies << " moves=" << Marker::moves << "\n";
    return 0;
}

The test harness expects the output to contain copies=0 moves=0. When the compiler performs RVO, the program’s output satisfies that expectation, demonstrating that the return did not incur any additional construction. If you deliberately disable copy-elision, for example by compiling with -fno-elide-constructors, the output changes to show a copy or move, which is useful for educational purposes but not representative of typical production builds.

Guaranteed copy elision, in effect since C++17, means a prvalue return does not even require the type to have a move constructor. A function that returns a prvalue of an immovable type still compiles and constructs the result in place. This is why returning a std::vector or a large struct by value is not just idiomatic but the fastest option. There is no copy and no move, only direct construction in the caller’s storage.

Chapter 18 showed that copy elision and RVO can remove all copy/move operations, making return‑by‑value the fastest way to deliver a result.

Container big-O review

Choosing the right container yields the highest performance gain in most programs. std::vector grows by amortised constant time. Each push_back is O(1) on average, but occasional reallocation costs O(n). Reserving capacity with reserve(n) eliminates those reallocations and therefore reduces the worst-case overhead. Associative containers differ. std::map provides ordered lookup in O(log n), while std::unordered_map offers average constant-time lookup, O(1), at the cost of higher memory usage and possible hash collisions. Understanding these complexities lets the programmer place the most expensive operations in the cheapest container. For example, building a large list of results is usually fastest with a vector that has been pre-reserved.

When a container holds objects that are expensive to move or copy, the cost of reallocation becomes significant. An optimisation is to store std::unique_ptr<T> in a vector and reserve enough space before filling it. This avoids repeated allocations of T and eliminates the need to move T objects during reallocation, because only the pointers are moved.

Big-O notation hides constant factors, which are real. An unordered_map is O(1) per lookup but has a large constant and high memory overhead, so for a handful of keys a linear scan of a small vector is faster. The rule is to choose by the shape of the workload, then confirm with a measurement, which brings the chapter’s central lesson back around. Choosing a container is a one-line change with large leverage, which is why it comes before micro-optimising a loop body.

Reading a hot loop

On Linux the profiler perf records CPU cycles, cache-miss events, and instruction retirements. On macOS the Instruments app provides similar metrics, including cache misses and allocations. When analysing a hot loop, look for a high proportion of cache-miss cycles, frequent allocations inside the loop body, and indirect calls such as virtual dispatch. Reducing cache misses involves improving data locality, for example by storing related objects contiguously in a vector or by using a struct-of-arrays layout. Eliminating allocations can be achieved with reserve or by reusing objects that are allocated once outside the loop. Virtual calls can be replaced by static polymorphism, by std::function_ref, or by inlining small call sites. The point is not to collect profiles but to find one or two dominant costs, because fixing the single hottest line usually beats optimising twenty small ones.

A typical workflow is:

  1. Run the program under perf record -g ./a.out or with Instruments’ time profiler.
  2. Identify the hottest functions from the flame graph.
  3. Drill into those functions to see which lines cause the most cache-miss or allocation events.
  4. Refactor the code to improve locality, pre-allocate storage, or replace virtual calls.
  5. Re-run the profiler to verify that the hot spots have diminished.

Try this

Predict whether calling reserve(n) on a std::vector<std::unique_ptr<Node>> that stores a binary tree will reduce the total runtime of a breadth-first construction loop. Measure the loop with std::chrono::steady_clock as shown earlier, print the elapsed time, and compare the two runs. Record the result as elapsed without reserve: X µs and elapsed with reserve: Y µs. The experiment demonstrates the real impact of pre-allocation on a realistic data-structure workload.