Exercises — Profiling — gprof, perf, Valgrind - Callgrind

(a) gprof — -pg flag compiler ko mcount() counter weave in karne par majboor karta hai, jo instrumentation hai (exact call counts, lekin timing change ho jaati hai). (b) Callgrind (ek Valgrind tool) — poora program ek simulated CPU par execute hota hai, toh counts deterministic hain lekin yeh 20–100× slower chalata hai. (c) perf — event-based sampling real PMU counters se driven, ~1–5% overhead.

Sirf gprof strictly recompile maangta hai (tumhe -pg add karna hi hoga). perf existing binary par kaam karta hai (-g aur -fno-omit-frame-pointer add karna sirf symbol/call-graph quality improve karta hai). Callgrind ko bhi koi recompile nahi chahiye — woh binary ko run time par Valgrind VM ke through instrument karta hai. -g add karna sirf nicer source-line attribution deta hai.

main ka total time = uska apna body plus jo bhi woh call karta hai. Near-zero self time ka matlab hai main khud almost kuch nahi karta — uska bada total sirf uske children ka sum hai. main ko optimize mat karo. Tum self time se optimize karte ho (jahan CPU actually baithta hai); total time sirf ek expensive subtree dhundhne ke liye hai jisme drill in karna ho.

(a) Har sample wall time ka $\Delta t=10\text{ms}=0.010\text{s}$ "represent" karta hai. Total run time $=N\Delta t=5000\times 0.010\text{s}=50\text{s}$. (b) Function ka owned fraction $=n_f/N=1500/5000=0.30$. Toh $T_{\text{self}}=\frac{n_f}{N}{T}_{\text{total}}=0.30\times 50\text{s}=15\text{s},$ jo sirf $n_f\Delta t=1500\times 0.010=15\text{s}$ bhi hai. Dono routes agree karte hain, jaisa hona chahiye.

Per-call cost $=\frac{3.60\text{s}}{10^6}=3.6\times 10^{-6}\text{s}=3.6\mu s$. Itne bade call count ke saath, pehla sawaal "har call ko faster banao" nahi balki "kya main fewer calls kar sakta hoon?" hai — repeated inputs ko memoize karo, call ko loop se hoist karo, ya vectorize karo. Calls ko $10^6$ se reduce karna poore $3.60$ s par attack karta hai, jabki har call ko chip karna sirf constant par kaam karta hai.

IPC = Instructions Per Cycle, core har clock tick mein kitni instructions finish karta hai: $\text{IPC}=\frac{\text{instructions}}{\text{cycles}}=\frac{9.0\times 10^9}{3.0\times 10^{10}}=\mathrm{0.30.}$ CPI = Cycles Per Instruction, exact inverse — har instruction average par kitne clock ticks cost karti hai: $\text{CPI}=\frac{1}{\text{IPC}}=\frac{1}{0.30}\approx \mathrm{3.33.}$ IPC of $0.30$ is far below the ~4 ceiling (equivalently CPI $3.33$ matlab har instruction 3 se zyada cycles kheenchti hai), toh core zyaadatar cycles stalling mein spend karta hai (idle, waiting). Yeh memory ya branch problems point karta hai — L3 dekho — na ki ek cleverer algorithm ki zaroorat hai.

(a) $s\to \infty$ lene par: term $p/s\to 0$, toh ${\text{Speedup}}_{\max }=\frac{1}{1-p}=\frac{1}{0.28}\approx 3.57\times .$ No matter what, untouched $28\%$ tumhe $3.57\times$ par cap kar deta hai. (b) $s=4$ ke saath: $\text{Speedup}=\frac{1}{(1-0.72)+\frac{0.72}{4}}=\frac{1}{0.28+0.18}=\frac{1}{0.46}\approx 2.17\times .$ Toh ek 4× local win ek 2.17× global win deta hai — $3.57\times$ ceiling se kaafi kam, jo batata hai ki is ek function par aur effort ke sharply diminishing returns hain.

$\text{cache miss rate}=\frac{1.8\times 10^8}{1.5\times 10^9}=0.12=12\%.$ $\text{branch miss rate}=\frac{2.0\times 10^7}{2.0\times 10^9}=0.01=1\%.$ Branch predictor theek kaam kar raha hai (1%). 12% cache miss rate culprit hai: ek DRAM miss ~100+ cycles cost karta hai vs L1 hit ke ~4 cycles, toh woh misses low IPC easily explain kar dete hain. Fix Cache Hierarchy & Locality of Reference mein rehta hai — locality improve karo (struct-of-arrays, loop blocking) — na ki algorithmic complexity mein. Branch Prediction & Pipelining se compare karo, jo yahan problem nahi hai.

Misses se lost cycles $\approx 1.8\times 10^8\times 120=2.16\times 10^{10}$ cycles. Sab cycles ka fraction $=\frac{2.16\times 10^{10}}{3.0\times 10^{10}}=0.72=72\%$. ~72% cycles plausibly memory stalls se consume ho rahe hain, toh cache behaviour akele slowdown ki vast majority account karta hai — memory waqai ek sufficient explanation hai, aur locality work sahi lever hai. Neeche di gayi figure yeh arithmetic cycle budget kaahan jaata hai iska picture banati hai.

(a) Callgrind — yeh deterministic hai (same input → identical instruction counts), toh ek >2% threshold machines across stable hai bina kisi timer noise ke. Slowness (20–100×) CI mein acceptable hai. (b) gprof — quick aur classic; ek -pg rebuild plus ek command ek flat profile deta hai jo "roughly kaun sa function" ke liye kaafi hai. (c) perf — real PMU hardware counters ~1–5% overhead par, release binary ka koi recompile nahi, aur yeh real CPU par true cache misses report karta hai. Callgrind disqualify hai kyunki uska simulated timing real-hardware timing nahi hai.

(a) $p=n_f/N=2000/4000=0.50$. (Sanity: $N\Delta t=4000\times 0.010=40$ s ✓ stated run se match karta hai.) (b) $\text{Speedup}=\frac{1}{(1-0.5)+\frac{0.5}{3}}=\frac{1}{0.5+0.1\overline{6}}=\frac{1}{0.6\overline{6}}=1.5\times .$ (c) Naya time $=\frac{40\text{s}}{1.5}\approx 26.7\text{s}$. Yeh forecast-then-verify discipline hai: edit karne se pehle $26.7$ s predict karo, phir confirm karne ke liye re-profile karo — agar measured time $26.7$ s ke paas nahi hai, toh tumhara model (ya tumhari assumption ki sirf serialize badla) galat hai. Dekho Benchmarking & Microbenchmark Pitfalls.

Har candidate par Amdahl formula alag apply karo. A ($p_A=0.50$, $s_A=1.6$): ${\text{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$): ${\text{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 .$ B choose karo ($1.316\times >1.231\times$). Lesson: ek chota slice ek bade achievable speedup ke saath ek bade slice ko beat kar sakta hai jise tum mushkil se improve kar sako — Amdahl $p/s$ shrink hone se reward karta hai, toh $p$ aur $s$ dono matter karte hain, sirf $p$ nahi.

-O2 par optimizer ne tiny_helper ko uske callers mein inline kar diya (dekho Compiler Optimization Flags (-O2, -O3, inlining)). Ek baar inline hone par, woh ek distinct function nahi raha jiske paas ek entry point ho, toh gprof ka mcount()/sample attribution usse time pin karne ki koi jagah nahi tha — uska cost ab caller ke self time mein fused ho gaya hai. Tumhara -O0 profile us code ki taraf point kar raha tha jo shipped binary mein exist hi nahi karta. Sahi method: wahi optimization level profile karo jo tum ship karte ho (-O2/-O3), source symbols ke liye -g add karo, aur -fno-omit-frame-pointer taaki perf abhi bhi call graphs build kar sake. Kabhi -O0 profile se conclusions mat nikalo.

Koi contradiction nahi — woh alag alag cheezein measure karte hain.

• Callgrind instructions executed count karta hai: f few instructions chalata hai (8%).
• Lekin perf dikhata hai f 90% cache misses trigger karta hai; har miss core ko ~100+ cycles stall karta hai bina kisi instructions ke, IPC ko 0.4 tak crush karta hai.
• gprof wall-clock self time measure karta hai, jismein woh stall cycles bhi hain, toh f few instructions ke bawajood real time ka 40% khaata hai. Coherent story: f memory-bound hai — instructions mein cheap, time mein expensive kyunki woh DRAM ka intezaar karta hai. Yahi wajah hai ki mistake "Callgrind real seconds batata hai" dangerous hai: low instruction count ne ek real-time hog chhupaaya. Yahan timing truth ke liye perf use karo.

(a) $\hat{q}=n_g/N=40/400=0.10$ (10%). (b) ${\sigma }_{\hat{q}}=\sqrt{\frac{\hat{q}(1-\hat{q})}{N}}=\sqrt{\frac{0.10\times 0.90}{400}}=\sqrt{\frac{0.09}{400}}=\sqrt{2.25\times 10^{-4}}=\mathrm{0.015.}$ Toh $\hat{q}\pm 2{\sigma }_{\hat{q}}=0.10\pm 0.03$, yaani true fraction plausibly $[0.07,0.13]$ mein hai. (Pehle normal-approximation conditions check karo: $N\hat{q}=40\ge 5$ aur $N(1-\hat{q})=360\ge 5$, toh bell-curve interval yahan trustworthy hai.) (c) Poora interval 5% se upar baitha hai, toh pessimistic end par bhi g budget exceed karta hai — $N=400$ yeh conclude karne ke liye enough hai "over budget". Agar interval 5% ke aas paas hota toh tum longer run karte: ${\sigma }_{\hat{q}}$ $1/\sqrt{N}$ ki tarah girta hai, toh error halve karne ke liye tumhe $4\times$ samples chahiye. Isliye short profiling runs jittery hot-lists dete hain.

(a) Instruction count fixed hone par, q ka run time $\propto$ cycles $=\text{instructions}/\text{IPC}$, toh q ka speedup $=\frac{{\text{IPC}}_{\text{new}}}{{\text{IPC}}_{\text{old}}}=\frac{2.8}{0.35}=8\times$. (b) $\text{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) Rewrite ke baad, perf re-run karo aur confirm karo ki q ka measured self time waqai ~8× drop kiya (equivalently uske cycles/miss-rate ne model ke anusaar giraavat dekhi). Agar whole-program speedup $2.11\times$ ke paas nahi aaya, toh ya toh IPC 2.8 tak nahi pahuncha ya koi aur function naya bottleneck ban gaya — dobara profile karo. Yeh measure → model → change → re-measure loop close karta hai.

Amdahl's speedup formula ::: $\text{Speedup}=1/((1-p)+p/s)$ Self time from samples ::: $T_{\text{self}}=(n_f/N)T_{\text{total}}=n_f\Delta t$ Standard deviation of a sampled fraction ::: ${\sigma }_{\hat{q}}=\sqrt{\hat{q}(1-\hat{q})/N}$ IPC of 0.3 on a 4-wide core ka matlab CPU mostly ::: stalling (waiting) hai, likely cache misses par CPI kya stand karta hai aur kya equal hai? ::: Cycles Per Instruction, $=1/\text{IPC}$ Deterministic, machine-independent counts wala tool ::: Callgrind Real hardware par ~1–5% overhead wala tool ::: perf Tum kaun se time column se optimize karte ho, total se nahi? ::: self time