Profiling — gprof, perf, Valgrind - Callgrind

WHY profile at all?

WHY two strategies? There is a tradeoff: $\text{accuracy of counts} \;\uparrow\; \implies \;\text{overhead} \;\uparrow\; \implies \;\text{measured timing distorts true timing}$

The three tools at a glance

Tool	Mechanism	Measures	Overhead	Needs recompile?
gprof	instrumentation + sampling	self/total time, call graph	medium	yes (`-pg`)
perf	hardware counters + sampling	cycles, cache misses, branches	~1–5%	no (`-g` helps)
Callgrind (Valgrind)	full CPU simulation	exact instr counts, cache sim	20–100×	no

gprof — WHAT & HOW

HOW it works (derive the model):

-pg makes the compiler insert a call to mcount() at the entry of every function. This records the caller→callee edge, building the call graph and call counts (instrumentation → exact counts).
A periodic timer (SIGPROF, ~100 Hz) samples the PC to estimate self time per function (sampling → statistical time).

Self time vs total (cumulative) time — the key distinction:

Self time = time spent inside the function's own body.
Total time = self time + time in everything it calls.

$ gcc -pg -O2 prog.c -o prog
$ ./prog            # writes gmon.out
$ gprof ./prog gmon.out > report.txt

Flat profile columns: % time | self seconds | calls | self ms/call | name.

HOW (derive the sampling logic): the PMU can be programmed to count an event (e.g. CPU cycles). After every $P$ events it raises an interrupt; perf records the PC at that moment. This is event-based sampling — denser where the program does more work.

$ perf stat ./prog              # summary counters (cycles, IPC, cache-misses)
$ perf record -g ./prog         # -g = capture call graph
$ perf report                   # interactive TUI
$ perf annotate                 # per-instruction hotness

Valgrind / Callgrind — WHAT & HOW

$ valgrind --tool=callgrind ./prog     # writes callgrind.out.<pid>
$ callgrind_annotate callgrind.out.<pid>
$ kcachegrind callgrind.out.<pid>      # GUI call graph

WHY use it despite 20–100× slowdown?

Deterministic: same input → identical counts. No timer noise, perfect for CI regression tests.
Counts instructions/calls exactly, so you can attribute cost to a single line.
--cache-sim=yes models L1/LL caches; --branch-sim=yes models branch prediction — without needing PMU access.

Figure — Profiling — gprof, perf, Valgrind - Callgrind

Worked examples

Worked example 1 — Reading a gprof flat profile

%time  self(s)  calls   name
 72.0    3.60    1e6     compute_dist
 18.0    0.90    1e6     normalize
 10.0    0.50    1       main

Q: where do you optimize? Step 1: compute_dist is 72% of self time. Why this step? By 80/20, optimizing it gives the biggest return; halving it saves ~36% of total runtime. Step 2: It's called $10^6$ times. Why this step? Per-call cost = $3.60/10^6 = 3.6\,\mu s$ ; check if calls can be reduced (memoize, vectorize), not just made faster.

Worked example 3 — perf stat diagnosis

8.0e9 instructions   #  0.45 insn per cycle
1.8e10 cycles
2.0e8 cache-misses   #  12% of all cache refs

Step 1: IPC = $8\times10^9/1.8\times10^{10}=0.44$ → stalling. Why: far below ~3–4, CPU waits a lot. Step 2: 12% miss rate is huge. Why this step: the stalls are explained by memory. Fix path: improve data locality (struct-of-arrays, blocking) — not algorithmic changes.

Recall Feynman: explain to a 12-year-old

Imagine timing yourself doing homework. Instead of guessing which subject is slowest, every minute you write down what you're doing right now. After an hour you count: "math = 40 tally marks, reading = 5." Now you know math eats your time, so that's where you should get faster. Profilers do this for programs — they keep tapping the program on the shoulder asking "what are you doing right NOW?" and tally the answers. The lazy way (perf) just peeks sometimes; the careful slow way (Callgrind) watches every single second but takes way longer.

Flashcards

What is the cardinal rule of optimization?

Measure (profile) before you optimize — intuition about bottlenecks is usually wrong.

Instrumentation vs sampling profiling?

Instrumentation inserts counters (exact counts, high overhead, distorts timing); sampling interrupts periodically to record the PC (low overhead, statistical estimate).

What flag compiles for gprof and what file does running produce?

-pg; running produces gmon.out.

gprof self time vs total/cumulative time?

Self = time inside the function's own body; total = self + time in everything it calls.

Formula to estimate a function's self time from samples?

T_{self}\approx n_f \Delta t = (n_f/N)\,T_{total}

— fraction of samples × total runtime.

What does perf use to measure events?

The kernel perf_events subsystem driving the CPU's hardware PMU (performance counters), via event-based sampling.

Define IPC and what a low IPC implies.

IPC = instructions retired / CPU cycles; low IPC (e.g. <1) means the CPU is stalling, often on cache misses or branch mispredictions.

Why is a 1% L1 cache miss potentially dominant?

A miss to DRAM costs ~100+ cycles vs ~4 for an L1 hit, so even few misses add huge time.

Main downside of Callgrind and main upside?

Downside: 20–100× slowdown and it simulates (not real wall-clock). Upside: deterministic, bit-exact instruction/call counts, reproducible for CI.

Amdahl's law for speedup with fraction p sped up s×?

\text{Speedup}=1/((1-p)+p/s)

; ceiling is

1/(1-p)

Why must you profile an optimized (-O2) build, not -O0?

The optimizer inlines/vectorizes; a -O0 profile points at code that doesn't exist in the release binary.

perf command for a quick counter summary vs a call-graph record?

perf stat ./prog for summary; perf record -g ./prog then perf report for call graph.

Connections

Build Systems & Toolchain
Compiler Optimization Flags (-O2, -O3, inlining)
Cache Hierarchy & Locality of Reference
Amdahl's Law & Scalability
Branch Prediction & Pipelining
Debugging with gdb
Benchmarking & Microbenchmark Pitfalls

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, optimization ka pehla rule simple hai: pehle measure karo, phir optimize karo. Hum sabko lagta hai ki "yeh nested loop slow hoga" — but 90% baar humari guess galat hoti hai. Asli time kisi aur function mein ja raha hota hai, jaise ek chhota sa log() jo million baar call ho raha hai. Profiling tools yahi batate hain ki time actually kahan kharch ho raha hai.

Teen main tools hain. gprof classic hai — -pg se compile karo, program chalao, gmon.out banta hai, phir report dekho. Yeh self time (function ke apne andar) aur total time (uske callees samet) dono deta hai. perf Linux ka powerful tool hai jo CPU ke hardware counters (PMU) use karta hai — overhead sirf 1-5%, aur yeh IPC, cache misses, branch mispredicts dikha deta hai. Agar IPC bahut low hai (jaise 0.5), matlab CPU stall ho raha hai — usually cache miss ki wajah se. Callgrind (Valgrind ka part) sab kuch ek simulated CPU pe chalata hai, har instruction exact count karta hai — 20-100x slow hota hai, but deterministic hai, CI testing ke liye perfect.

Ek important cheez: self time vs total time confuse mat karna. main ka total time sabse zyada dikhega kyunki usme sab kuch include hai, but main khud kuch nahi karta. Optimize karne ke liye self time dekho. Aur ek aur trap — kabhi -O0 debug build profile mat karna, kyunki optimizer inlining aur vectorization se code badal deta hai; release build (-O2 -g) hi profile karo.

Last mein Amdahl's law yaad rakho: agar koi function total ka 72% hai aur usse 4x fast kar do, total speedup sirf 2.17x hoga, ceiling 3.57x hai. Isliye profiling pehle batata hai ki effort worth hai ya nahi — yahi hai smart 80/20 thinking.

Profiling — gprof, perf, Valgrind - Callgrind

WHY profile at all?

The three tools at a glance

gprof — WHAT & HOW

perf — WHAT & HOW

Valgrind / Callgrind — WHAT & HOW

Worked examples

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Build Systems & Toolchain

Connections