Intuition The one core ideaA program's runtime is not spread evenly across its code — a tiny slice does almost all the work , and profiling is simply counting where the seconds actually land instead of guessing. Everything else on the parent page — samples, IPC, cache misses, call graphs — is just different rulers for measuring that same slice.
Before you can read a perf report or a gprof table, you need the vocabulary. This page builds every symbol and word the parent note leans on, starting from things a 12-year-old already knows (a clock, a tally sheet, a stopwatch) and ending exactly where the parent note begins.
Everything in profiling is about time , so we need to be precise about which time.
Definition Wall-clock timeWall-clock time is the time a real clock on the wall would show while the program runs — start to finish, including everything. The picture: a stopwatch you press at launch and stop at exit.
We write the total run's wall time as T total run name tag ; it does not mean multiplication. Whenever you see a symbol like T self self ".
Intuition Why we can't just use one stopwatchOne stopwatch tells you the whole program took 5 seconds. It does not tell you which function ate those 5 seconds. To split the 5 seconds among functions we need many tiny measurements — and that is where sampling comes in (Section 4).
A function is a named block of code you can invoke. When function main runs some code inside normalize, we say main called normalize.
Definition Caller, callee, edge
Caller = the function doing the calling (main).Callee = the function being called (normalize).Edge = the arrow caller → callee . Read the arrow as "calls".
Draw every function as a box and every "calls" relationship as an arrow, and you get a call graph — a map of who calls whom.
Definition Call graph and call countThe call graph is the whole picture of boxes-and-arrows. A call count is how many times a particular edge was travelled — e.g. main called compute_dist 1 0 6 1 0 6
Intuition Why the graph matters for timeIf a function is slow but only called once , you might not care. If it is fast but called a million times , the count is the enemy, not the per-call cost. Profiling needs both the time and the count to tell you which lever to pull (make each call cheaper vs. make fewer calls).
This distinction trips up almost everyone, so we anchor it to a picture.
The big-Σ ∑ "add up over" — here, add the total times of every function g f "total time of f = its own time, plus the sum of the total times of everything it called."
main looks slow but isn't
main almost always has the highest total time — because its subtree is the whole program . But its self time is near zero: it just calls other things. Optimize by self time ; use total time only to spot which branch of the tree to dig into.
Common mistake Reading total time as "the slow function"Why it feels right: the biggest number must be the culprit. Trap: the biggest total-time number is usually main or some coordinator that does nothing itself. Fix: sort by self time to find real hot code.
We cannot pause a program a billion times to time each line — that would change what we measure. Instead we sample .
Definition Sampling and the sampling intervalΔ t Sampling = a timer interrupts the program at a fixed rhythm and writes down which instruction is running right now . The gap between two snapshots is the sampling interval Δ t Δ
If the timer fires 100 times per second, then Δ t = 100 1 = 0.01
Each snapshot is one tally mark for whichever function was caught in the act.
Intuition The stop-motion cameraPhotograph a kitchen 1000 times a second. If the stove appears in 700 photos, the stove was busy ~70% of the time. You never timed the stove directly — you counted appearances and multiplied by the gap between photos. That is exactly the sampling estimate below.
Worked example Sampling math sanity checkTimer at 100 Hz (Δ t = 0.01 N = 500 compute_dist is caught 360 T self ≈ 360 × 0.01 = 3.6 s = 500 360 × 5 = 0.72 × 5 = 3.6 s . ✓
There are two ways to gather data, and they pull in opposite directions.
Definition InstrumentationInstrumentation = the tool inserts extra counting code into your program (e.g. -pg adds a call to mcount() at every function entry). Result: exact call counts — but the extra code costs time, so it distorts the very timing you wanted to measure.
Overhead = the extra time/work a measurement tool adds on top of the program's real work. "20–100×" overhead (Callgrind) means the program runs 20 to 100 times slower while being measured.
Intuition The unavoidable trade-offcount accuracy ↑ ⇒ overhead ↑ ⇒ measured timing drifts from true timing skipping events and guessing statistically (fast, fuzzy). No tool escapes this; each tool just picks a spot on the line. Callgrind sits at "exact + very slow"; perf sits at "statistical + ~1–5% overhead."
To read perf, you need what the CPU counts natively.
Definition Cycle and instruction
A cycle is one tick of the CPU's internal clock — the smallest unit of work a processor schedules by. A 3 GHz CPU has 3 × 1 0 9
An instruction is one machine operation (add, load, compare). "Retired " means an instruction fully completed (not just started and thrown away).
Definition Cache, reference, missA cache is a small, very fast memory near the CPU holding recently used data. A cache reference is any time the CPU asks the cache for data. A cache miss is when the data isn't there and must be fetched from far-away DRAM (~100+ cycles vs ~4 for a hit).
Profiling ends with a decision: is optimizing this worth it? That needs two symbols.
Worked example The ceilingWith p = 0.72 best possible total speedup (infinite s 1 − 0.72 1 = 0.28 1 ≈ 3.57 × first tells you this ceiling before you sink days into the code.
Instrumentation vs sampling
Cache references and misses
Profiling gprof perf Callgrind
Each foundation box feeds the profiling topic: sampling gives you self time , the call graph gives you counts , IPC and miss rate give you why a function is slow, and Amdahl tells you whether to bother .
Cover the right side and test yourself — you are ready when every line is instant.
What does T total run The whole program's wall-clock time, start to finish, including everything it calls.
Self time vs total time in one sentence? Self = seconds inside a function's own lines; total = self plus all the time in functions it calls.
Which one is main usually highest in, and why doesn't that mean it's slow? Highest in total time, because its subtree is the whole program; its own self time is near zero.
What does Δ t The sampling interval — the time gap between two consecutive PC snapshots (e.g. 0.01
Give the sampling formula for a function's self time. T self ( f ) ≈ n f Δ t = N n f T total run
Instrumentation vs sampling — the core trade? Instrumentation = exact counts but high overhead that distorts timing; sampling = low overhead but statistical estimates.
Define IPC and CPI. IPC = instructions retired ÷ cycles; CPI = 1/IPC = cycles ÷ instructions retired.
An IPC of 0.5 means what? The CPU is stalling — waiting most cycles, likely on cache misses or branch mispredictions, not doing real work.
Formula for cache miss rate? miss rate = cache-misses ÷ cache-references.
In Amdahl's Law, what do p s p s
Best possible speedup when p = 0.72 1 − 0.72 1 = 0.28 1 ≈ 3.57 ×