Disciplined Optimization

Part I · Module 25 · Chapter 25.10 · Disciplined Optimization

1. The Rule, and Why Each Clause Is There

Change one thing. Measure it. Keep it only if the number moved.

Every clause earns its place:

One thing, because two changes measured together give one number and no attribution. If the pair is faster you do not know which half did it, and you will keep both — including the one that cost readability for nothing.

Measure it, because the alternative is a prediction, and §3 is five predictions that most C++ programmers would make and that are mostly wrong.

Only if the number moved, because an optimisation that does not move the number has a cost and no benefit. The cost is paid in every future reading of that code, and it is never recovered.

And one clause that is implicit and is the hardest in practice: revert it if the number did not move. The temptation after measuring a null result is to keep the change anyway — it is written, it is harmless, it might help on another compiler. That is how a codebase accumulates unreadable code with no measured justification, and Chapter 23.5 §3's hoisted ostringstream is an example from this curriculum: a plausible optimisation, measured at 1.08× with a range straddling one and an identical allocation count, which the honest conclusion requires removing rather than keeping.

2. The Harness

Every figure in this chapter comes from the same instrument, and it is worth stating because a performance claim is only as good as its measurement:

template <typename T> void sink(const T& v) { asm volatile("" : : "r,m"(v) : "memory"); }
inline void clobber() { asm volatile("" : : : "memory"); }

template <typename F> double bench(F f, int reps = 31)
{
    f();                                      // one warm-up
    double best = 1e300;
    for (int r = 0; r < reps; ++r) {
        const auto a = Clock::now();
        f();
        clobber();
        const auto z = Clock::now();
        best = std::min(best, duration_ns(z - a));
    }
    return best;                              // the MINIMUM, not the mean
}

Five properties, each of which this curriculum needed:

An assembly barrier on the result. Without sink, a loop whose result is unused is deleted entirely and you measure nothing. Chapter 22.1 §3 published a ratio of 17,280,398× from exactly that mistake before it was found.

A warm-up, so the first iteration's cold caches and lazy page faults are not in the sample.

The minimum over repetitions, not the mean. The minimum is the least-contaminated estimate of the work; the mean includes every scheduler interruption.

A median over whole-process runs, with the range. One run is not a figure — Chapter 22.9 published 136× from a single run whose absolute numbers were below the real range, and Chapter 23.7's 155× was likewise outside its own range.

A load check. The numbers below were taken at a load average of 5.5 on 8 CPUs. At load 20 this machine produced orderings that are physically impossible, which Chapter 24.9 §6 documents — a no-op make measuring slower than a four-translation-unit rebuild.

3. Five Optimisations, Measured

Each pair computes the same thing over 200,000 integers. Medians of nine runs, ranges beside them:

Read the ranges, not just the medians.

i++ against ++i on an integer: 1.00×, range 0.96–1.01. Identical to the nanosecond in the median. For a class type with a non-trivial increment the advice is sound — i++ must produce the old value and therefore a copy — but for a built-in integer the two generate the same instructions, and they have for the entire career of anyone currently working.

Hoisting .size() out of the condition: 1.00×, range 1.00–1.01. The compiler already knows std::vector::size() is a cheap accessor on an object the loop does not modify, so it hoists the load itself. The transformation is a no-op you have to read.

Index against range-for: 1.00×, range 1.00–1.01. The range-for is the one that cannot be written with an off-by-one error — Chapter 25.3 §7 — and it costs exactly nothing.

Manual 4× unrolling: 0.56×, range 0.54–0.57 — 1.8× slower. Consistently, with a tight range. The compiler's own unrolling is informed by the target's issue width and its vectoriser; a hand-unrolled loop presents a different shape that is harder to analyse, and here it defeated the better transformation. The folk optimisation actively harmed the thing it was supposed to help.

reserve before a push_back loop: 1.37×, range 1.32–1.42. A real win, with a range comfortably clear of one. And it is the only item in the table that is not folklore — it is information the compiler cannot have, because the final count is in the caller's head rather than in the code.

4. The Pattern in Which Ones Won

5. What Actually Pays, With the Figures

Collected from across this curriculum, because the point of the discipline is that the wins are known rather than guessed:

Three observations about that list.

The largest effects are all about not doing work, rather than doing the same work faster. Chapter 22.9's 145× is a branch moved earlier; Chapter 23.7's 144× is an engine not started.

Several are allocation counts rather than times, and those are the reliable ones — Chapter 25.9 §5's callout is the argument, and they reproduce exactly where timings on this machine need medians and ranges.

The algorithmic and data-structure wins dwarf everything local. Chapter 19.4's ~60× for container choice and Chapter 20.5's binary_search against a linear scan are changes of a different order from anything in §3's table, and they are the first place to look — which is the original form of the advice to profile before optimising.

6. The Failure Modes of Measurement Itself

This curriculum has made every one of these, and each produced a published figure that had to be corrected.

No barrier, so the work was deleted. The always-failing loops in Chapter 22.1 §3 were constant-folded away, producing 0.00 ns and a ratio of 17,280,398×.

A single run. Chapter 22.9 published 45.01 ms / 136× from one run; nine runs put both absolutes below the real range. Chapter 23.7's 155× was likewise outside its own seven-run range.

An experiment whose arms are indistinguishable. Chapter 24.2 §5's header-only comparison reported header-only as 0.67× — faster — because one-line function bodies made both sides preprocess to the same 412 lines. Chapter 25.9 §3's first version used short map keys and measured the missing & as free.

The wrong instrument for the claim. Chapter 23.5 §3 timed a hoisted ostringstream at an apparent 8% win; the allocation counter showed identical counts, and the timing ratio's range straddled one.

A loaded machine. Chapter 24.9 §6 measured a no-op make as slower than a four-file rebuild at load 20. An impossible ordering is evidence about the harness, not the subject.

A gate that reads the wrong thing. Chapter 24.7 §5 and Chapter 25.6 §5: UBSan reports a defect and exits 0, so a status-only check passes.

The checklist those produce, before believing any performance number:

• Is the result consumed, through a barrier?
• Is this a median over runs, with a range?
• Does the range exclude 1.0?
• Can the experiment distinguish its two arms at all?
• Is the instrument measuring the quantity my explanation is about?
• Is the ordering of my results physically possible?
• What was the load?

7. When Not to Optimise

Before it is correct. An optimisation applied to code with a defect optimises the defect, and Chapter 25.1's measurements show that undefined behaviour's observable value changes with the optimisation level — so you may be tuning a program whose answer is about to change.

Before you have measured where the time goes. Chapter 25.8 §3 measured one program reporting three different hot spots under three builds. Optimising the function you suspect is a coin flip.

When the code is not hot. A 2× improvement in code holding 1% of the run time is a 0.5% improvement, and it is permanent damage to the readability of that code.

When the readability cost is large and the measured win is small. This is a judgement, and the discipline is to make it with the number in hand. 1.37× for reserve(n) costs one line and is obviously worth it; 1.37× for an unreadable rewrite of a central function may not be.

When you have not written the test that will catch the regression. An optimisation is a behaviour-preserving transformation and the obligation to prove the behaviour was preserved is yours. Chapter 23.8 §3's measurement is the sharpest version of that: one of five test vectors separated a correct saturating add from a broken one, and it was the one at the boundary.

8. The Order to Work In

Each step is cheaper than the one after it and finds larger effects:

1. Make it correct, with the sanitizers on. Chapter 25.6's configuration.

2. Time the phases. Chapter 25.8 §7's three-bucket wall-clock measurement, five minutes and no tooling.

3. Count the allocations and copies. Chapter 25.9 §1's two instruments. In a C++ model this is where the answer usually is, and the counts are exact.

4. Check the algorithm and the data structure. Chapter 19.4 and Chapter 20.5 — the ~60× changes.

5. Profile the optimised build. Chapter 25.8 §5, reading the aggregate rather than the top row.

6. Only then make local changes, one at a time, each measured, each reverted if the number did not move.

Most work stops at step 3 or 4, which is the point. By the time you reach step 6, §3's table says the expected value of a local transformation is approximately zero unless it supplies a fact the compiler cannot derive.

9. The Table

10. What to Actually Do

• Change one thing, measure it, and revert it if the number did not move. The reverting is the clause people skip.
• Use a harness with a barrier, a warm-up, a minimum over repetitions, a median over runs, and a reported range. Without the barrier the work is deleted.
• Require the ratio's range to exclude 1.0 before claiming an effect. Three of §3's five do not.
• Ask whether the change supplies a fact the compiler cannot derive. If not, expect nothing — and expect harm in the unrolling case.
• Prefer counting to timing where the quantity is deterministic; Chapter 25.9's counts reproduce exactly.
• Work in order: correctness with sanitizers, phase timing, allocation counts, algorithm and container, profile, then local changes.
• Check the load before measuring, and treat an impossible ordering as a broken harness.
• Confirm the experiment can distinguish its arms before interpreting it.
• Write the test that proves behaviour was preserved, with a boundary case — one vector in five was the one that discriminated.
• Never optimise code that is not hot, and never before the sanitizers are clean.

11. Mistakes Worth Making Once

No barrier. A published ratio of 17,280,398× from a loop that was deleted.

One run. Two figures in this curriculum were published outside their own ranges.

Keeping a null result because it is already written. That is how unreadable code accumulates without justification.

Manual unrolling. 1.8× slower here, consistently.

Rewriting i++ as ++i for integers. 1.00×, to the nanosecond.

Hoisting .size(). 1.00×, and a longer loop to read.

Timing a claim about allocations. Chapter 23.5 §3's 8% that the counter showed was nothing.

An experiment whose arms are identical. Chapter 24.2 §5 reported the wrong direction entirely.

Measuring at load 20. A no-op build slower than a four-file rebuild.

Optimising before the sanitizers are clean. Chapter 25.1 §3 — the answer itself may change with the optimisation level.

Optimising a function holding 1% of the time. A 2× win is 0.5%, permanently.

12. Interview Relevance

The frozen curriculum marks this chapter High, and the question is usually a request for an opinion — "how would you make this faster?" — where the strongest answer declines to give one until it has a measurement.

The sequence to give is the one in §8: correctness with sanitizers first, then phase timing, then allocation and copy counts, then the algorithm and the container, then a profile of the optimised build, and only then local changes one at a time.

The measurement to quote is §3's table, because it is concrete and it contradicts advice the interviewer may hold: i++ against ++i, hoisting .size(), and index against range-for all came out at 1.00× with ranges straddling one, manual 4× unrolling was 1.8× slower, and reserve was the only real win at 1.37×.

The observation that lifts it from a list of results to a principle is §4's: the only transformation that paid is the only one supplying a fact the compiler could not derive — the final size. That gives a test applicable before any measurement, and it explains why this module's largest wins (145× from not formatting a discarded line, 144× from not starting a regex engine) are all about not doing work rather than doing the same work faster.

13. What You Should Be Able to Say Now

• The rule and why each clause is there, including the clause people skip: revert it if the number did not move.
• What a trustworthy harness needs — barrier, warm-up, minimum over reps, median over runs, a reported range, and a load check — and the specific published error each element prevents.
• That three of five folk optimisations measured exactly 1.00× with ranges straddling one, and manual unrolling was 1.8× slower with a tight range.
• That reserve was the only win, at 1.37× [1.32–1.42], and that it is the only item supplying a fact the compiler cannot derive.
• The test that follows: does this change tell the compiler something it could not have worked out? If not, expect nothing.
• That the module's largest wins are all "do not do the work" — ~145×, 144×, 17.1×, 1,978 allocations to 1 — and that counts are more reliable than times.
• The six ways a measurement can lie, each of which produced a corrected figure in this curriculum.
• When not to optimise: before correctness, before measurement, when the code is not hot, when the readability cost exceeds a measured win, and before the regression test exists.
• The order to work in, and that most problems are solved by step 3 or 4.

14. Exercises

Exercise 1 — reproduce the table. Build §3's five pairs with the §2 harness and produce medians of nine runs with ranges. Note your load average. Report which ranges exclude 1.0.

Exercise 2 — break the harness deliberately. Remove sink from one arm and re-measure. Then use the mean instead of the minimum. Then report a single run. Record how wrong each version is.

Exercise 3 — the unrolling. Dump the assembly for the plain and hand-unrolled loops at -O2 and find what the compiler did to the plain one that it did not do to yours.

Exercise 4 — the test. Apply §4's test to five optimisations you have been told to make. Predict which supply a fact the compiler cannot derive, then measure all five and check your predictions.

Exercise 5 — your own code. Work §8's order on a real program. Record where you stopped, and whether you reached step 6 at all.

Exercise 6 — the regression test. Take an optimisation you have made and write the test that would catch it breaking. Include a boundary case, and confirm the test fails against a deliberately broken version.

15. Summary

• Change one thing, measure it, keep it only if the number moved — and revert it otherwise. The last clause is the one that keeps a codebase readable.
• The harness matters as much as the result: an assembly barrier (without it, a measured ratio of 17,280,398× from deleted code), a warm-up, the minimum over repetitions, a median over whole-process runs, a reported range, and a load check.
• Measured, five optimisations people are taught: i++ vs ++i 1.00× [0.96–1.01]; hoisting .size() 1.00× [1.00–1.01]; index vs range-for 1.00× [1.00–1.01]; manual 4× unrolling 0.56× — 1.8× slower [0.54–0.57]; reserve before a growth loop 1.37× [1.32–1.42].
• Four of the five do nothing or harm, and the one that pays is the only one that is not folklore.
• The line through the table: the four that failed all tell the compiler something it already derives, so they change the source and not the program — and the unrolling changed it into a shape the optimiser handles worse. reserve supplies a fact that is not in the code, which is why it is the one that works.
• That gives a pre-measurement test: does this change give the compiler information it could not derive? If not, the expected value is zero.
• The module's largest wins are all "do not do the work" — ~145× from not formatting a discarded log line, 144× from not starting a regex engine, 17.1× from not flushing per line, 1,978 allocations to 1 from knowing the final length — and the counts among them are the most reliable figures in this curriculum.
• Six ways a measurement lies, each of which produced a corrected figure here: no barrier, a single run, indistinguishable arms, the wrong instrument, a loaded machine, and a gate reading the wrong artefact.
• Work in order: sanitizers, phase timing, allocation counts, algorithm and container, profile the shipped build, then local changes. Most problems are solved before the last step.

That closes Module 25. Its through-line is the one this chapter ends on: the defects in the first half are invisible precisely because no single observation distinguishes them from correct behaviour, and the performance work in the second half fails for the same reason — a number you did not measure, or measured with the wrong instrument, is indistinguishable from the number you hoped for.