Module 14 — Debugging¶

The technique this module adds¶

Measuring instead of guessing: operation counts at two data sizes, and the invalidation audit.

The failures in this module are the quiet kind. There is no exception, no message and often no crash: a loop that produces the right answer on the sample data, a container that is merely slow, a hash that is merely unhelpful, a lambda that will be called from somewhere else tomorrow. None of them can be debugged by reading the line that is wrong, because the line that is wrong is not wrong.

Two instruments cover almost everything here. Neither is a debugger, and both produce numbers you can quote:

Operation counts — comparisons, lookups, buffer replacements — measured at two sizes, so that the shape of the growth is visible.
An audit — for invalidation and for captures, a walk through the code applying one question to each site, because the symptom is absent or delayed by design.

Move 1 — count operations, at two sizes¶

A stopwatch on one data set tells you almost nothing: the machine, the compiler's inlining, the cache and the other processes all move the number around. Counting the work is deterministic — the same number on every machine and every build — which is what makes it quotable in an argument.

n = 1000:  500500 comparison(s), total 25000
n = 10000: 50005000 comparison(s), total 250000
The data grew 10x. The work grew 99x.

The two-size rule is the whole method. At n = 1000, 500,500 comparisons is a program that feels instant. The defect only becomes visible when the data grows and the work grows faster:

Work grows by	Shape	What to do
~10x when data grows 10x	linear	nothing — this is the target
~100x	quadratic	look for a scan inside a loop
~3x	logarithmic	nothing to see here
~1x	constant	verify it is really doing the work

Make the counter part of the code while you investigate, and remove it afterwards:

struct Counted {
    int value = 0;
    static int comparisons;
};
bool operator<(const Counted& left, const Counted& right) {
    ++Counted::comparisons;
    return left.value < right.value;
}

Putting the counter in the element type is what makes it work for algorithms you did not write: std::sort, std::lower_bound and std::map::find all become measurable without a single change to the standard library. Reset before each measurement, and print both numbers — as program 03 does for four containers and program 07 does for two implementations.

Move 2 — find the scan inside the loop¶

When the count grows quadratically, the cause is almost always one of four shapes. Look for them in this order:

// 1. a scan inside a loop                       O(n * m)
for (const Loan& loan : loans)
    for (const Member& member : members)          // <-- the inner scan
        if (member.id == loan.memberId) { ... }

// 2. find_if inside a loop (the same thing, spelled as an algorithm)
for (const Loan& loan : loans)
    std::find_if(members.begin(), members.end(), sameId(loan));   // <-- still a scan

// 3. repeated erase/shift of the front, or insert at the front of a vector
while (!queue.empty()) { process(queue.front()); queue.erase(queue.begin()); }   // O(n^2)

// 4. re-sorting a container inside the loop
for (const Loan& loan : loans) { std::sort(items.begin(), items.end()); use(items); }

The fix is nearly always the same move: build the index once, before the loop, and change the inner scan into a lookup. Program 07 does it in one step and shows that the totals are unchanged — which is the evidence that the refactor did not alter behaviour:

  scan  totals: 25000 and 250000
  index totals: 25000 and 250000

Move 3 — audit for invalidation, because the symptom is absent¶

Invalidation cannot be found by testing, because the test that would reveal it depends on a reallocation the test's own size may prevent. The instrument is a question, asked at every site:

Did anything add to, or remove from, this container between obtaining this iterator (or pointer, or reference) and using it?

And the facts that answer it:

Container	Insertion	Erasure
`vector`, `string`	growth invalidates every iterator, pointer and reference	those at or after the erased element
`deque`	push at either end invalidates iterators; references survive	erase in the middle invalidates all
`list`, `forward_list`, `map`, `set`	nothing — nodes do not move	only iterators to the erased element
`unordered_*`	rehash invalidates iterators; references survive	only the erased element's iterator

What makes the audit possible — and the reason to read it rather than run it — is that the cause is observable while the bug is not:

capacity after each push_back: 1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32
buffer replaced 5 time(s) over 17 insertions, and the SIZE was never larger than 17.
with no reserve:  5 buffer replacement(s)
with reserve(17): 0 buffer replacement(s)

If you want to see the failure itself, do it in a scratch file, once, with the numbers deliberately large enough to force reallocation — and then do not draw a conclusion from what you saw. Dereferencing an invalidated iterator is undefined behaviour: the run may print the old value, print something else, or crash, and none of those outcomes is a fact about your program. The bug is proved by the rules, not by the transcript, which is exactly why this is a case where reading the code is the debugging method.

Move 4 — audit the captures and the views¶

Both of this module's lifetime bugs are found the same way, and neither will announce itself:

For every capture and every view: does the thing it refers to still exist when it is used?

lambda                             refers to                    lives until
─────────────────────────────────  ───────────────────────────  ──────────────────────
[limit, label]                     its own copies               forever (safe to store)
[&threshold] passed to count_if    threshold in this scope      end of this statement
[&count] inside a returned lambda  count in makeCounter()       already gone  ← BUG
[shared]                           a shared_ptr copy            as long as the closure
[raw = shared.get()]               the pointee                  whatever the shared_ptr says
string_view view = owned           owned's characters           until owned dies
return std::string_view(local)     a dead local's characters    already gone  ← BUG

The fix is a rule rather than a technique: capture by value when the lambda is stored, returned or called later; capture by reference only when the lambda is used within the lifetime of what it refers to; and return a string_view only when you can name the owner in the same sentence.

Move 5 — check the hash, when a container is slower than it should be¶

A hash table that is unexpectedly slow is not usually a code error; it is a distribution problem, and it is measurable on the spot:

std::cout << map.bucket_count() << ' ' << map.load_factor() << '\n';

with a hash that returns 0 for every key:
  comparisons for one lookup of the FIRST key: 632
  buckets: 1109, load factor: 0.90

Every key in one bucket, correct answers, and a lookup that walks a chain whose length depends on insertion order. The audit is short: does the hash use every field the equality uses? does it combine them (rather than +)? and does bucket(key) spread a sample of real keys over more than a handful of indices?

The escalation ladder for this module¶

Read the error. In this module it usually names a missing operation on your type — operator<, operator==, a hash — or an iterator category the container cannot provide.
Check the two common-mistakes tables, then the glossary: the remove-without-erase and capture-lifetime families are the ones that recur.
Reduce it. One container, one algorithm, one element type, twenty lines. Every error in this module reduces to that, and it compiles in a second instead of a minute.
Audit the rules — invalidation at every iterator, lifetime at every capture and view. This is this module's characteristic step, and it is reading, not running.
Measure it. Count operations at two sizes. "It feels faster" is not a measurement, and neither is one stopwatch reading; a count is, and it survives being quoted by somebody else.

Checklist before you call a query finished¶

[ ] The container's choice has a written sentence naming the dominant operation and its complexity
[ ] No container is modified while an iterator into it is held — audited, not assumed
[ ] remove/remove_if is always paired with erase
[ ] Every custom key type provides what its containers require, and any hash agrees with ==
[ ] Every stored lambda's captures outlive the lambda; every returned string_view has a named owner
[ ] Every comparator satisfies comp(a, a) == false — read each one back for it
[ ] Operation counts exist for both the before and after versions, at two data sizes
[ ] The behaviour did not change during the refactor — demonstrated by comparing the outputs

Continue¶

Previous: Misconceptions and mistakes · Next: Exercises · Module home: Module 14