cc_bench_report.py (13483B)
1 #!/usr/bin/env python3 2 """Reporter for the -O0 compile+link scaling benchmark. 3 4 Reads <out>/scaling.csv (written by cc_bench.sh) and produces: 5 6 <out>/scaling.md per-axis scaling exponent + verdict + clang ratio 7 <out>/hotspots.md flat self-time hotspot table per axis, parsed from the 8 `sample` call-trees in <out>/raw/<axis>.sample.txt 9 10 Scaling model: for each axis we fit log(t_net) = log(a) + p*log(n), where t_net 11 is best-of-N wall time minus the fixed per-invocation overhead (empty-TU compile 12 / preprocess / trivial link). The exponent p is the headline: 13 14 p < 1.15 LINEAR (the goal) 15 p < 1.40 NEAR-LINEAR 16 p >= 1.40 SUPERLINEAR (an O(n^2)-ish trap -> a hotspot to fix) 17 18 A low R^2 (<0.9) tags the fit NOISY (rerun with more repeats / bigger sizes). 19 """ 20 import csv 21 import math 22 import os 23 import re 24 import sys 25 from collections import defaultdict, OrderedDict 26 27 28 # --------------------------------------------------------------------------- 29 # CSV loading 30 # --------------------------------------------------------------------------- 31 def fnum(v): 32 try: 33 return float(v) 34 except (TypeError, ValueError): 35 return None 36 37 38 def load(csv_path): 39 with open(csv_path, newline="") as f: 40 return list(csv.DictReader(f)) 41 42 43 # --------------------------------------------------------------------------- 44 # Power-law fit 45 # --------------------------------------------------------------------------- 46 def linfit(xs, ys): 47 """Least-squares slope/intercept/R^2 of ys ~ a + b*xs.""" 48 npt = len(xs) 49 if npt < 2: 50 return None 51 mx = sum(xs) / npt 52 my = sum(ys) / npt 53 sxx = sum((x - mx) ** 2 for x in xs) 54 sxy = sum((x - mx) * (y - my) for x, y in zip(xs, ys)) 55 if sxx == 0: 56 return None 57 b = sxy / sxx 58 a = my - b * mx 59 syy = sum((y - my) ** 2 for y in ys) 60 ss_res = sum((y - (a + b * x)) ** 2 for x, y in zip(xs, ys)) 61 r2 = 1.0 - ss_res / syy if syy > 0 else 1.0 62 return a, b, r2 63 64 65 def fmt(v, spec="%.1f", na="NA"): 66 return (spec % v) if v is not None else na 67 68 69 def verdict(p, r2): 70 if p is None: 71 return "NA" 72 tag = "LINEAR" if p < 1.15 else ("NEAR-LINEAR" if p < 1.40 else "SUPERLINEAR") 73 if r2 is not None and r2 < 0.9: 74 tag += " (noisy)" 75 return tag 76 77 78 def fit_axis(points, overhead): 79 """points: list of (n, ms). Returns dict with exponent/r2/used info.""" 80 pts = sorted((n, t) for n, t in points if t is not None and t > 0) 81 # Net time after subtracting fixed overhead. 82 net = [(n, t - overhead) for n, t in pts] 83 # Prefer points where the signal clears the overhead noise floor. 84 strong = [(n, d) for n, d in net if d > max(2 * overhead, 1e-6)] 85 used = strong if len(strong) >= 3 else [(n, d) for n, d in net if d > 0] 86 low_conf = len(strong) < 3 87 if len(used) < 2: 88 return {"p": None, "r2": None, "used": used, "low_conf": True, 89 "double": None, "pts": pts, "net": net} 90 fit = linfit([math.log(n) for n, _ in used], [math.log(d) for _, d in used]) 91 p = fit[1] if fit else None 92 r2 = fit[2] if fit else None 93 # Doubling ratio sanity check: t(2n)/t(n) ~ 2 linear, ~4 quadratic. 94 dbl = None 95 for (n1, d1), (n2, d2) in zip(used, used[1:]): 96 if d1 > 0 and 1.7 <= n2 / n1 <= 2.3: 97 r = (d2 / d1) / (n2 / n1) # normalize to a pure 2x step 98 dbl = r if dbl is None else max(dbl, r) 99 return {"p": p, "r2": r2, "used": used, "low_conf": low_conf, 100 "double": dbl, "pts": pts, "net": net} 101 102 103 # --------------------------------------------------------------------------- 104 # scaling.md 105 # --------------------------------------------------------------------------- 106 def write_scaling(out_dir, rows): 107 overhead = {"compile": 0.0, "preprocess": 0.0, "link": 0.0} 108 for r in rows: 109 if r["axis"] == "__overhead__" and r["status"] == "OK": 110 overhead[r["mode"]] = fnum(r["time_ms"]) or 0.0 111 112 # axis -> tool -> mode/phase/unit + list of (n, ms) 113 axes = OrderedDict() 114 for r in rows: 115 if r["axis"] == "__overhead__": 116 continue 117 a = r["axis"] 118 ax = axes.setdefault(a, {"phase": r["phase"], "mode": r["mode"], 119 "unit": r["unit"], "kit": [], "clang": []}) 120 ms = fnum(r["time_ms"]) if r["status"] == "OK" else None 121 if r["tool"] == "kit": 122 ax["kit"].append((int(r["n"]), ms)) 123 elif r["tool"] == "clang": 124 ax["clang"].append((int(r["n"]), ms)) 125 126 L = [] 127 L.append("# kit -O0 compile + link scaling") 128 L.append("") 129 L.append("Goal: **linear scaling** on every axis (exponent ~1.0). " 130 "`SUPERLINEAR` (exponent >= 1.4) marks an O(n^2)-ish hotspot to fix.") 131 L.append("") 132 L.append(f"Fixed per-invocation overhead (subtracted before fitting): " 133 f"compile **{overhead['compile']:.2f} ms**, preprocess " 134 f"**{overhead['preprocess']:.2f} ms**, link " 135 f"**{overhead['link']:.2f} ms**.") 136 L.append("") 137 L.append("## Linearity summary") 138 L.append("") 139 L.append("| axis | phase | unit | pts | exponent | R² | 2x-ratio | verdict " 140 "| kit @maxN | clang @maxN | kit/clang |") 141 L.append("| --- | --- | --- | ---: | ---: | ---: | ---: | --- | ---: | ---: | ---: |") 142 143 details = [] 144 for a, ax in axes.items(): 145 ov = overhead.get(ax["mode"], 0.0) 146 fit = fit_axis(ax["kit"], ov) 147 kit_by_n = {n: t for n, t in ax["kit"]} 148 clang_by_n = {n: t for n, t in ax["clang"]} 149 maxn = max(kit_by_n) if kit_by_n else None 150 kit_max = kit_by_n.get(maxn) 151 clang_max = clang_by_n.get(maxn) 152 ratio = (kit_max / clang_max) if (kit_max and clang_max) else None 153 p_s = fmt(fit["p"], "%.2f") 154 r2_s = fmt(fit["r2"], "%.3f") 155 d_s = fmt(fit["double"], "%.2f") 156 v = verdict(fit["p"], fit["r2"]) + (" *low-n*" if fit["low_conf"] else "") 157 L.append(f"| {a} | {ax['phase']} | {ax['unit']} | {len(fit['used'])} | " 158 f"{p_s} | {r2_s} | {d_s} | {v} | " 159 f"{fmt(kit_max)} | {fmt(clang_max)} | {fmt(ratio, '%.2fx')} |") 160 161 # Per-axis detail block 162 d = [f"### {a} ({ax['phase']}, per {ax['unit'][:-1] if ax['unit'].endswith('s') else ax['unit']})", "", 163 f"overhead {ov:.2f} ms subtracted. exponent **{p_s}** ({verdict(fit['p'], fit['r2'])}).", "", 164 f"| n | kit ms | kit net ms | kit ns/{ax['unit'][:-1] if ax['unit'].endswith('s') else ax['unit']} | clang ms | kit/clang |", 165 "| ---: | ---: | ---: | ---: | ---: | ---: |"] 166 net_by_n = {n: v for n, v in fit["net"]} 167 for n in sorted(kit_by_n): 168 kt = kit_by_n[n] 169 ct = clang_by_n.get(n) 170 net = net_by_n.get(n) 171 per = (net * 1e6 / n) if (net and net > 0 and n) else None 172 rr = (kt / ct) if (kt and ct) else None 173 d.append(f"| {n} | {('%.2f' % kt) if kt else 'FAIL'} | " 174 f"{('%.2f' % net) if net is not None else 'NA'} | " 175 f"{('%.1f' % per) if per else 'NA'} | " 176 f"{('%.2f' % ct) if ct else 'NA'} | " 177 f"{('%.2fx' % rr) if rr else 'NA'} |") 178 d.append("") 179 details.append("\n".join(d)) 180 181 L.append("") 182 L.append("kit/clang > 1 means kit is **slower** than the clang -O0 reference " 183 "at the largest size (lower is better; <1 means kit is faster).") 184 L.append("") 185 L.append("## Per-axis detail") 186 L.append("") 187 L.extend(details) 188 L.append(f"Raw data: `{os.path.relpath(os.path.join(out_dir, 'scaling.csv'))}` " 189 f"· hotspots: `{os.path.relpath(os.path.join(out_dir, 'hotspots.md'))}`") 190 191 path = os.path.join(out_dir, "scaling.md") 192 with open(path, "w") as f: 193 f.write("\n".join(L) + "\n") 194 return path, axes 195 196 197 # --------------------------------------------------------------------------- 198 # sample call-tree -> self-time per function 199 # --------------------------------------------------------------------------- 200 FRAME_RE = re.compile(r"^(?P<indent>[ |+!:]*)(?P<count>\d+)\s+(?P<rest>.*\S)\s*$") 201 202 203 def parse_sample(text): 204 """Return (self_by_func dict, total_samples) from a `sample` report, or 205 (None, 0) if the file isn't a parseable call graph. 206 207 Each call-graph line is `<indent><count> <symbol> (in <image>) ...`. A 208 node's count is the samples that passed through it; its direct children sum 209 to <= that, and the difference is the samples whose stack *ended* there — 210 i.e. self time. We reconstruct the tree via an indent stack and accumulate 211 self time per (symbol, image).""" 212 lines = text.splitlines() 213 start = None 214 for i, ln in enumerate(lines): 215 if ln.strip() == "Call graph:": 216 start = i + 1 217 break 218 if start is None: 219 return None, 0 220 221 indents = [] # per node: indentation width 222 counts = [] # per node: total sample count 223 child_sum = [] # per node: summed direct-children counts 224 names = [] # per node: (symbol, image) 225 stack = [] # node indices, increasing indent 226 started = False 227 for ln in lines[start:]: 228 if not ln.strip(): 229 if started: 230 break 231 continue 232 m = FRAME_RE.match(ln) 233 if not m: 234 if started: 235 break 236 continue 237 started = True 238 indent = len(m.group("indent")) 239 cnt = int(m.group("count")) 240 rest = m.group("rest") 241 if " (in " in rest: 242 sym = rest.split(" (in ", 1)[0].strip() 243 img = rest.split(" (in ", 1)[1].split(")", 1)[0].strip() 244 else: # thread/root header or unresolved frame 245 sym = rest.split(" ")[0].strip() 246 img = "" 247 idx = len(counts) 248 indents.append(indent) 249 counts.append(cnt) 250 child_sum.append(0) 251 names.append((sym, img)) 252 while stack and indent <= indents[stack[-1]]: 253 stack.pop() 254 if stack: 255 child_sum[stack[-1]] += cnt 256 stack.append(idx) 257 258 self_by = defaultdict(float) 259 total = 0.0 260 for i in range(len(counts)): 261 self_t = max(0, counts[i] - child_sum[i]) 262 sym, img = names[i] 263 if not sym: 264 continue 265 self_by[(sym, img)] += self_t 266 total += self_t 267 return self_by, total 268 269 270 def parse_dtrace(text): 271 """Flat `ufunc count` histogram from a dtrace profile run.""" 272 self_by = defaultdict(float) 273 total = 0.0 274 for ln in text.splitlines(): 275 s = ln.strip() 276 if not s: 277 continue 278 parts = s.split() 279 if len(parts) < 2 or not parts[-1].isdigit(): 280 continue 281 cnt = float(parts[-1]) 282 sym = " ".join(parts[:-1]) 283 img = "" 284 if "`" in sym: 285 img, sym = sym.split("`", 1) 286 self_by[(sym, img)] += cnt 287 total += cnt 288 return self_by, total 289 290 291 def write_hotspots(out_dir, axes): 292 raw_dir = os.path.join(out_dir, "raw") 293 L = ["# kit -O0 compile + link hotspots", "", 294 "Flat **self-time** per function (samples whose stack *ends* in that " 295 "function), from `sample` on the largest input of each axis. Use these " 296 "to see where time goes when an axis is stressed — especially axes the " 297 "linearity summary flagged SUPERLINEAR.", ""] 298 if not os.path.isdir(raw_dir): 299 L.append("_No sample data._") 300 with open(os.path.join(out_dir, "hotspots.md"), "w") as f: 301 f.write("\n".join(L) + "\n") 302 return 303 for a in axes: 304 raw = os.path.join(raw_dir, f"{a}.sample.txt") 305 if not os.path.exists(raw): 306 continue 307 text = open(raw, errors="replace").read() 308 if text.startswith("skipped:"): 309 L.append(f"## {a}") 310 L.append("") 311 L.append("_" + text.strip() + "_") 312 L.append("") 313 continue 314 if text.lstrip().startswith("Analysis of sampling"): 315 self_by, total = parse_sample(text) 316 else: 317 self_by, total = parse_dtrace(text) 318 L.append(f"## {a}") 319 L.append("") 320 if not self_by or total <= 0: 321 L.append("_No parseable samples._") 322 L.append("") 323 continue 324 L.append(f"{int(total)} samples.") 325 L.append("") 326 L.append("| self % | samples | function | image |") 327 L.append("| ---: | ---: | --- | --- |") 328 top = sorted(self_by.items(), key=lambda kv: kv[1], reverse=True)[:30] 329 for (sym, img), s in top: 330 if s <= 0: 331 continue 332 L.append(f"| {100.0 * s / total:.1f}% | {int(s)} | `{sym}` | {img} |") 333 L.append("") 334 with open(os.path.join(out_dir, "hotspots.md"), "w") as f: 335 f.write("\n".join(L) + "\n") 336 337 338 def main(): 339 out_dir = sys.argv[1] if len(sys.argv) > 1 else os.path.join( 340 os.path.dirname(os.path.dirname(os.path.abspath(__file__))), 341 "build", "bench", "cc") 342 csv_path = os.path.join(out_dir, "scaling.csv") 343 if not os.path.exists(csv_path): 344 sys.exit(f"cc_bench_report: no CSV at {csv_path}") 345 rows = load(csv_path) 346 scaling_path, axes = write_scaling(out_dir, rows) 347 write_hotspots(out_dir, axes) 348 print(f"cc_bench_report: wrote {scaling_path}") 349 print(f"cc_bench_report: wrote {os.path.join(out_dir, 'hotspots.md')}") 350 351 352 if __name__ == "__main__": 353 main()