C++ Performance Quiz: Undefined Behavior, Cache and Padding
Test your C++ with 14 questions and three programs on undefined behaviour, overflow checks, copy and allocation costs, cache lines, padding and benchmarks.
- Course: C++ study plan
- Module: Performance and undefined behaviour
- Kind: Checkpoint — cleared at 70%
- Reading time: 25 min
- Runtime: Clang 18 · C++20
Checkpoint — Performance and undefined behaviour is the checkpoint that closes the Performance and undefined behaviour module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
This checkpoint covers the whole module: the undefined behaviour catalogue and the well-defined detectors for it, the cost model of copies, allocations and calls, cache lines, struct padding and traversal order, what the optimiser does under the as-if rule, and how to measure without being lied to.
How it works. Fourteen questions and three programs. You need 70% on the questions and every program accepted to clear the module. You can retake it as often as you like; your best score counts.
Before you start, make sure you can answer these from memory:
- Why does
if (x + 1 < x)never detect an overflow at-O2, and what do you write instead? - What does passing a
std::vector<int>by value cost, and byconst&? - How many elements are moved over a thousand
push_backs into a doubling vector, and what doesreservechange? - What is the size of
struct { char a; double b; char c; }on this platform, and what does reordering do? - Why does a column-major inner loop over a wide matrix load a cache line per element?
- What does the as-if rule permit, and why does it make an unprinted benchmark result worthless?
- Which statistic of a set of benchmark runs should you report, and why not the mean?
The three programs are an overflow-safe statistics report over long long values, an array-of-structs against struct-of-arrays cache-line audit built on the padding rule, and an operation counter that runs insertion sort and selection sort on the same input and reports the work each did. Every one of them counts; none of them times.
Common questions
Why does if (x + 1 < x) never detect an overflow at -O2?
Signed overflow is undefined behaviour, so the compiler assumes x + 1 cannot overflow and folds the test to false. Test before the operation instead: x > std::numeric_limits<int>::max() - 1, a wider type, or __builtin_add_overflow.
What is the size of struct { char a; double b; char c; }?
24 bytes on x86-64: seven bytes of padding after a align b to 8, and seven more after c round the size up to a multiple of 8. Reordering the members as double b; char a; char c; removes the interior padding and makes it 16.
Why is an unprinted benchmark result worthless?
Under the as-if rule the compiler only has to preserve observable behaviour, and a value that never reaches an output is not observable. Dead-code elimination can therefore remove the whole computation, and the benchmark times nothing at all.
Exercises
Overflow-safe statistics
Report statistics over long long values without ever computing a sum, difference or product that does not fit. Read n and n values (each fits in a long long). Print count n; if n is 0 print empty and stop. Otherwise print, one per line: min, max, range (max − min), sum, mean (the integer quotient sum / n, truncated toward zero) and squares (the sum of every value squared). Any figure that would overflow prints the word overflow in its place — the mean too, when the sum did. Use __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow on long long operands; once an accumulation has overflowed it stays overflowed.
Input: n, then n integers. Output: count, then either empty or the six statistic lines.
4
-3 9 2 6prints
count 4
min -3
max 9
range 12
sum 14
mean 3
squares 130AoS against SoA: a cache-line audit
Audit the cache lines two layouts touch, built on the padding rule from lesson 3. Read a struct as m type names (char/bool 1, short 2, int/float 4, long/double/ptr 8; each aligns to its size, the struct rounds up to its largest alignment), then n (≥ 1) elements and the 0-based index hot of the member a hot loop reads. Lines are 64 bytes and both layouts start at offset 0.
- Array of structs: element
i's hot member starts at bytei * size + offset; count the distinct lines those bytes fall in (a member never straddles a line here, since every width divides 64 and every offset is a multiple of its width). - Struct of arrays: the hot member alone is a contiguous array of
n × widthbytes:ceil(bytes / 64)lines. - All fields: AoS is
ceil(n × size / 64); SoA is the sum ofceil(n × width / 64)over every member.
Print struct size S hot offset O width W, hot field: aos A soa B, all fields: aos C soa D, and hot ratio A/B fixed to two decimals.
Input: m, m type names, n, hot. Output: four lines.
4
double double double float
32
3prints
struct size 32 hot offset 24 width 4
hot field: aos 16 soa 2
all fields: aos 16 soa 14
hot ratio 8.00Insertion against selection: the work each did
Run two sorts on the same input and report the work each did, counted, never timed. Read n integers. Insertion sort: for i from 1, take key = a[i] and walk j down from i; each evaluation of a[j - 1] > key is one comparison; each a[j] = a[j - 1] is one shift; stop when the comparison fails or j reaches 0, then store the key. Selection sort: for each i from 0 to n − 2, scan j from i + 1 to the end, one comparison per a[j] < a[best]; if the best index differs from i, std::swap and count one swap.
Print sorted: followed by the sorted values (one space before each), then insertion comparisons C shifts S, selection comparisons C swaps S, and cheaper insertion, cheaper selection or cheaper tie comparing comparisons + shifts against comparisons + swaps.
Input: n, then n integers. Output: four lines.
6
5 2 4 6 1 3prints
sorted: 1 2 3 4 5 6
insertion comparisons 12 shifts 9
selection comparisons 15 swaps 3
cheaper selectionIn this module: Performance and undefined behaviour
- The undefined behaviour catalogue — what the compiler is allowed to assume
- The cost model — counting copies, allocations and calls
- Memory layout and the cache — contiguity, padding and traversal order
- Compiler optimisation — what -O2 does for you and what it cannot
- Measuring — clocks, benchmarks that lie and the tools that tell the truth
- Checkpoint — Performance and undefined behaviour (this lesson)
← Measuring — clocks, benchmarks that lie and the tools that tell the truth · The interview template — the contest idioms and what they cost →