Profiling — gprof, perf, Valgrind - Callgrind: Exercises

The recurring maths tools you will use here are worth naming once, in plain words — every symbol defined, every unit stated — before any problem uses them.

Formula Tool 1 — Sample-fraction time (with units on every symbol)

A sampling profiler does not time anything directly; it takes rapid snapshots ("photos") of what the CPU is doing and counts them. Define:

$Δ t$ = the gap between two snapshots, which carries units of time (seconds). At 100 snapshots per second, $Δ t = 1/100 = 0.01 s$ .
$N$ = the total number of snapshots taken over the whole run. It is a pure count, so it is dimensionless (no units).
$n_{f}$ = the number of those snapshots in which function $f$ was "the active one", also a dimensionless count.

Each snapshot "represents" $Δ t$ seconds of real (wall-clock) time, so the whole run lasts $T_{total run} = N Δ t .$ Here $N$ is just a number and $Δ t$ carries the seconds, so multiplying them gives a result in seconds — exactly what a run time should be. The fraction of run time owned by $f$ is the fraction of photos it appears in, $n_{f} / N$ . Because it is one count divided by another, this fraction is a pure number (dimensionless), and $f$ 's self time is $T_{self} (f) \approx n_{f} Δ t = \frac{n _{f}}{N} T_{total run} (seconds) .$ The picture below makes $Δ t$ , $N$ and $n_{f}$ concrete before you meet them in the exercises.

Figure — Profiling — gprof, perf, Valgrind - Callgrind

Formula Tool 2 — Amdahl speedup, derived here (not just quoted)

Take a run of total time $1$ (measure time in "whole runs", so it is dimensionless). Split it into two pieces by what you can and cannot speed up:

the hot slice you will optimize: fraction $p$ (dimensionless, $0 \leq p \leq 1$ );
everything else, untouched: fraction $1 - p$ .

Now make the hot slice $s$ times faster ( $s$ = "how many times faster", dimensionless, so $s = 2$ means twice as fast). Its time shrinks from $p$ to $p / s$ ; the rest is unchanged at $1 - p$ . The new run time is the sum: $T_{new} = (1 - p) + \frac{p}{s} .$ Speedup is old time over new time, and old time was $1$ : $Speedup = \frac{T _{old}}{T _{new}} = \frac{1}{( 1 - p ) + \frac{p}{s}} .$ Why this exact form? The $(1 - p)$ never moves no matter how big $s$ gets — that stubborn term is the whole story of the law. The figure below shows the two blocks shrinking. See also Amdahl's Law & Scalability.

Definition Tool 3 — Sampling has statistical uncertainty (the edge case people forget)

Because sampling counts random photos, the fraction $\overset{q}{^} = n_{f} / N$ is an estimate, not the exact truth. Let us build its uncertainty from scratch rather than quote it.

Step 1 — one snapshot is a coin flip. For each snapshot ask "was $f$ active?" — answer $1$ (yes) or $0$ (no). If the true fraction is $q$ , this single yes/no value has average $q$ and variance $q (1 - q)$ . Why $q (1 - q)$ ? A $0/1$ variable is most uncertain when $q = 0.5$ (variance $0.25$ , a true coin flip) and has zero variance when $q = 0$ or $q = 1$ (the answer is always the same), and $q (1 - q)$ is exactly the curve that is $0$ at both ends and peaks in the middle.

Step 2 — average $N$ independent flips. $\overset{q}{^} = n_{f} / N$ is the average of $N$ such $0/1$ values. A basic rule of averaging independent measurements: averaging $N$ of them divides the variance by $N$ . So $variance (\overset{q}{^}) = q (1 - q) / N$ , and the standard deviation (the square root of variance) is $σ_{\overset{q}{^}} = \frac{q ( 1 - q )}{N} \approx \frac{q ^ ( 1 - q ^ )}{N} (dimensionless),$ where in practice we plug our estimate $\overset{q}{^}$ in for the unknown true $q$ .

Why it matters: the $1/ N$ means to halve the noise you need $4 \times$ the samples — the fix for a jittery hot-list is simply a longer run. This is the profiling analogue of the pitfalls in Benchmarking & Microbenchmark Pitfalls. You will use this in L5.

Definition The 95% interval and its fine print (edge cases)

Adding up many independent $0/1$ flips, the total (and hence $\overset{q}{^}$ ) piles up into a bell-shaped normal curve — this is the Central Limit Theorem. For a normal curve about 95% of the area lies within 1.96 standard deviations of the centre, and we round $1.96 \approx 2$ for mental arithmetic, giving the rough interval $\overset{q}{^} \pm 2 σ_{\overset{q}{^}} (really \pm 1.96 σ_{\overset{q}{^}}) .$ The fine print — when this approximation breaks:

Small $N$ : the bell-curve shape has not formed yet, so the $\pm 2 σ$ interval is untrustworthy. A common rule of thumb wants both $N \overset{q}{^} \geq 5$ and $N (1 - \overset{q}{^}) \geq 5$ (i.e. at least ~5 "yes" and ~5 "no" samples) before trusting it.
$\overset{q}{^}$ near $0$ or $1$ : the interval can spill below $0$ or above $1$ , which is impossible for a fraction — a sign the normal approximation is being used outside its comfort zone; clamp to $[0, 1]$ or use an exact binomial interval.

Level 1 — Recognition

Recall Solution

(a) gprof — the -pg flag makes the compiler weave in the mcount() counter, which is instrumentation (exact call counts, but it changes timing). (b) Callgrind (a Valgrind tool) — the whole program executes on a simulated CPU, so counts are deterministic but it runs 20–100× slower. (c) perf — event-based sampling driven by real PMU counters, ~1–5% overhead.

Recall Solution

Only gprof strictly requires a recompile (you must add -pg). perf works on an existing binary (adding -g and -fno-omit-frame-pointer only improves symbol/call-graph quality). Callgrind also needs no recompile — it instruments the binary at run time via the Valgrind VM. Adding -g just gives nicer source-line attribution.

Recall Solution

main's total time = its own body plus everything it calls. A near-zero self time means main itself does almost nothing — its huge total is just the sum of its children. Do not optimize main. You optimize by self time (where the CPU actually sits); total time is only for spotting an expensive subtree to drill into.

Level 2 — Application

Recall Solution

(a) Each sample "represents" $Δ t = 10 ms = 0.010 s$ of wall time. Total run time $= N Δ t = 5000 \times 0.010 s = 50 s$ . (b) Fraction owned by the function $= n_{f} / N = 1500/5000 = 0.30$ . So $T_{self} = \frac{n _{f}}{N} T_{total} = 0.30 \times 50 s = 15 s,$ which is also just $n_{f} Δ t = 1500 \times 0.010 = 15 s$ . Both routes agree, as they must.

Recall Solution

Per-call cost $= \frac{3.60 s}{1 0 ^{6}} = 3.6 \times 1 0^{- 6} s = 3.6 μ s$ . With a call count this large, the first question is not "make each call faster" but "can I make fewer calls?" — memoize repeated inputs, hoist the call out of a loop, or vectorize. Reducing calls from $1 0^{6}$ attacks the whole $3.60$ s, whereas shaving each call only chips at the constant.

Recall Solution

IPC = Instructions Per Cycle, how many instructions the core finishes each clock tick: $IPC = \frac{instructions}{cycles} = \frac{9.0 \times 1 0 ^{9}}{3.0 \times 1 0 ^{10}} = 0.30.$ CPI = Cycles Per Instruction, the exact inverse — how many clock ticks each instruction costs on average: $CPI = \frac{1}{IPC} = \frac{1}{0.30} \approx 3.33.$ IPC of $0.30$ is far below the ~4 ceiling (equivalently CPI $3.33$ means each instruction drags on for over 3 cycles), so the core spends most cycles stalling (idle, waiting). This points at memory or branch problems — see L3 — not at needing a cleverer algorithm.

Level 3 — Analysis

Recall Solution

(a) Let $s \to \infty$ : the term $p / s \to 0$ , so $Speedup_{m a x} = \frac{1}{1 - p} = \frac{1}{0.28} \approx 3.57 \times .$ No matter what, the untouched $28%$ caps you at $3.57 \times$ . (b) With $s = 4$ : $Speedup = \frac{1}{( 1 - 0.72 ) + \frac{0.72}{4}} = \frac{1}{0.28 + 0.18} = \frac{1}{0.46} \approx 2.17 \times .$ So a 4× local win buys a 2.17× global win — well short of the 3.57× ceiling, telling you further effort on this one function has sharply diminishing returns.

Recall Solution

$cache miss rate = \frac{1.8 \times 1 0 ^{8}}{1.5 \times 1 0 ^{9}} = 0.12 = 12%.$ $branch miss rate = \frac{2.0 \times 1 0 ^{7}}{2.0 \times 1 0 ^{9}} = 0.01 = 1%.$ The branch predictor is doing fine (1%). A 12% cache miss rate is the culprit: a DRAM miss costs ~100+ cycles vs ~4 for an L1 hit, so those misses easily explain the low IPC. The fix lives in Cache Hierarchy & Locality of Reference — improve locality (struct-of-arrays, loop blocking) — not algorithmic complexity. Contrast with Branch Prediction & Pipelining, which is not the problem here.

Recall Solution

Cycles lost to misses $\approx 1.8 \times 1 0^{8} \times 120 = 2.16 \times 1 0^{10}$ cycles. Fraction of all cycles $= \frac{2.16 \times 1 0 ^{10}}{3.0 \times 1 0 ^{10}} = 0.72 = 72%$ . With ~72% of cycles plausibly consumed by memory stalls, cache behaviour alone accounts for the vast majority of the slowdown — memory is indeed a sufficient explanation, and locality work is the right lever. The figure below turns this arithmetic into a picture of where the cycle budget goes.

Level 4 — Synthesis

Recall Solution

(a) Callgrind — it is deterministic (same input → identical instruction counts), so a >2% threshold is stable across machines with no timer noise. Slowness (20–100×) is acceptable in CI. (b) gprof — quick and classic; a -pg rebuild plus one command gives a flat profile good enough for "roughly which function". (c) perf — real PMU hardware counters at ~1–5% overhead, no recompile of the release binary, and it reports true cache misses on the real CPU. Callgrind is disqualified because its simulated timing is not real-hardware timing.

Recall Solution

(a) $p = n_{f} / N = 2000/4000 = 0.50$ . (Sanity: $N Δ t = 4000 \times 0.010 = 40$ s ✓ matches the stated run.) (b) $Speedup = \frac{1}{( 1 - 0.5 ) + \frac{0.5}{3}} = \frac{1}{0.5 + 0.1 6} = \frac{1}{0.6 6} = 1.5 \times .$ (c) New time $= \frac{40 s}{1.5} \approx 26.7 s$ . This is the forecast-then-verify discipline: predict $26.7$ s before editing, then re-profile to confirm — if the measured time isn't near $26.7$ s, your model (or your assumption that only serialize changed) is wrong. See Benchmarking & Microbenchmark Pitfalls.

Recall Solution

Apply the Amdahl formula to each candidate separately. A ( $p_{A} = 0.50$ , $s_{A} = 1.6$ ): $Speedup_{A} = \frac{1}{( 1 - 0.50 ) + \frac{0.50}{1.6}} = \frac{1}{0.50 + 0.3125} = \frac{1}{0.8125} \approx 1.231 \times .$ B ( $p_{B} = 0.30$ , $s_{B} = 5$ ): $Speedup_{B} = \frac{1}{( 1 - 0.30 ) + \frac{0.30}{5}} = \frac{1}{0.70 + 0.06} = \frac{1}{0.76} \approx 1.316 \times .$ Pick B ( $1.316 \times > 1.231 \times$ ). The lesson: a smaller slice with a bigger achievable speedup can beat a larger slice you can barely improve — Amdahl rewards $p / s$ shrinking, so both $p$ and $s$ matter, not $p$ alone.

Level 5 — Mastery

Recall Solution

At -O2 the optimizer inlined tiny_helper into its callers (see Compiler Optimization Flags (-O2, -O3, inlining)). Once inlined, it is no longer a distinct function with an entry point, so gprof's mcount()/sample attribution has nothing to pin time to — its cost is now fused into the caller's self time. Your -O0 profile pointed at code that does not exist in the shipped binary. Correct method: profile the same optimization level you ship (-O2/-O3), add -g for source symbols, and -fno-omit-frame-pointer so perf can still build call graphs. Never draw conclusions from a -O0 profile.

Recall Solution

No contradiction — they measure different things.

Callgrind counts instructions executed: f runs few instructions (8%).
But perf shows f triggers 90% of cache misses; each miss stalls the core ~100+ cycles doing no instructions, crushing IPC to 0.4.
gprof measures wall-clock self time, which includes those stall cycles, so f eats 40% of real time despite few instructions. Coherent story: f is memory-bound — cheap in instructions, expensive in time because it waits on DRAM. This is exactly why the mistake "Callgrind tells me real seconds" is dangerous: low instruction count hid a real-time hog. Use perf for the timing truth here.

Recall Solution

(a) $\overset{q}{^} = n_{g} / N = 40/400 = 0.10$ (10%). (b) $σ_{\overset{q}{^}} = \frac{q ^ ( 1 - q ^ )}{N} = \frac{0.10 \times 0.90}{400} = \frac{0.09}{400} = 2.25 \times 1 0^{- 4} = 0.015.$ So $\overset{q}{^} \pm 2 σ_{\overset{q}{^}} = 0.10 \pm 0.03$ , i.e. the true fraction plausibly lies in $[0.07, 0.13]$ . (Check the normal-approximation conditions first: $N \overset{q}{^} = 40 \geq 5$ and $N (1 - \overset{q}{^}) = 360 \geq 5$ , so the bell-curve interval is trustworthy here.) (c) The whole interval sits above 5%, so even at the pessimistic end g exceeds the budget — $N = 400$ is enough to conclude "over budget". Had the interval straddled 5% you would run longer: $σ_{\overset{q}{^}}$ falls like $1/ N$ , so to halve the error you need $4 \times$ the samples. This is why short profiling runs give jittery hot-lists.

Recall Solution

(a) With instruction count fixed, run time of q $\propto$ cycles $= instructions / IPC$ , so speedup of q $= \frac{IPC _{new}}{IPC _{old}} = \frac{2.8}{0.35} = 8 \times$ . (b) $Speedup = \frac{1}{( 1 - 0.60 ) + \frac{0.60}{8}} = \frac{1}{0.40 + 0.075} = \frac{1}{0.475} \approx 2.11 \times .$ (c) After the rewrite, re-run perf and confirm q's measured self time actually dropped ~8× (equivalently its cycles/miss-rate fell as modelled). If the whole-program speedup isn't near $2.11 \times$ , either IPC didn't reach 2.8 or another function became the new bottleneck — profile again. This closes the measure → model → change → re-measure loop.

Recall Quick self-quiz (cloze)

Amdahl's speedup formula ::: $Speedup = 1/ ((1 - p) + p / s)$ Self time from samples ::: $T_{self} = (n_{f} / N) T_{total} = n_{f} Δ t$ Standard deviation of a sampled fraction ::: $σ_{\overset{q}{^}} = \overset{q}{^} (1 - \overset{q}{^}) / N$ IPC of 0.3 on a 4-wide core means the CPU is mostly ::: stalling (waiting), likely on cache misses What does CPI stand for and equal? ::: Cycles Per Instruction, $= 1/ IPC$ The tool with deterministic, machine-independent counts ::: Callgrind The tool with ~1–5% overhead on real hardware ::: perf You must optimize by which time column, not total? ::: self time