commit 7336010e1c2df57fdc23b794f497d361843c796a
parent bd148cea9313867a40abbbf442aaa29591a41d9c
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 17:05:19 -0700
perf(bench): add -O0 compile+link scaling benchmark + hotspot sampler
make bench-cc builds a profileable release kit (new PROFILE=1: -O2 with -g and
no -Wl,-S strip, so codegen is unchanged but `sample` can attribute hotspots)
and sweeps each input axis over a geometric size series, fitting a scaling
exponent per axis (~1.0 = linear goal, >=1.4 = O(n^2) hotspot) against a
clang -O0 reference, with macOS `sample` self-time hotspot tables.
- scripts/cc_bench_gen.py: axis catalog + synthetic C generator (single source
of truth for the axes).
- scripts/cc_bench.sh: harness -- overhead baseline, best-of-N timing, adaptive
wall-time cap, clang/system-ld reference, per-axis sampling.
- scripts/cc_bench_report.py: power-law fit + sample call-tree -> self-time.
- mk/maint.mk: bench-cc target. mk/flags.mk: PROFILE=1 switch.
- doc/plan/PERF.md (+ README index): methodology and the findings that drove the
O(n^2) -> O(1) fixes.
Output lands under build/bench/cc/ (gitignored).
Diffstat:
7 files changed, 1177 insertions(+), 3 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -0,0 +1,144 @@
+# Performance: the fastest C compiler
+
+**Goal.** kit should be *the fastest* C compiler at `-O0`. Generated code quality
+is irrelevant; only correctness and **compile+link throughput** matter. The
+structural bet is already in place — a single-pass, no-AST C frontend with
+single-pass code emission and patch-ups, and a format-neutral linker — so the
+remaining work is measurement-driven: find where the time goes and keep every
+input dimension scaling **linearly**.
+
+A superlinear axis is never acceptable here: it means some inner step is
+O(n²)-ish (a linear scan that runs once per item, a table that rebuilds, a list
+that is re-walked). Those are the bugs this benchmark exists to surface.
+
+## The benchmark
+
+`make bench-cc` builds a profileable release kit (clang, `-O2`, but `PROFILE=1`
+keeps `-g` + frame pointers and skips the `-Wl,-S` strip — codegen is identical
+to the shipped release, so timings are representative) and runs
+`scripts/cc_bench.sh`, which:
+
+1. **Sweeps each input axis** over a geometric size series, timing `kit cc -O0
+ -c` / `-E` (compile) and `kit ld` (link) best-of-N. Link axes pre-build the
+ object set untimed, so only the linker is on the clock.
+2. **Fits a scaling exponent** per axis (`scripts/cc_bench_report.py`): on
+ overhead-subtracted times, least-squares `log t = log a + p·log n`. `p ≈ 1.0`
+ is the goal; `p ≥ 1.4` is flagged `SUPERLINEAR`.
+3. **Samples hotspots** on the largest input of each axis with macOS `sample`
+ (no sudo; arm64 frame pointers make `-O2` stacks reliable), reduced to a flat
+ **self-time per function** table.
+4. Records a **clang `-O0` reference** (same sources for compile; the same kit
+ objects through the system linker for link) to quantify the gap to "fastest".
+
+### Components (single source of truth)
+
+| File | Role |
+|------|------|
+| `scripts/cc_bench_gen.py` | Axis catalog + synthetic source/object generator. `--list` prints the axes; `--axis/--n/--out` writes an instance + JSON manifest. **All axis definitions live here.** |
+| `scripts/cc_bench.sh` | Harness: build/locate kit, measure overhead, sweep, time kit + clang, correctness-check, sample. Writes `scaling.csv`. |
+| `scripts/cc_bench_report.py` | Exponent fit + verdicts + clang ratios → `scaling.md`; parses `sample` call-trees → `hotspots.md`. |
+| `mk/maint.mk: bench-cc` | Builds the `PROFILE=1` kit and runs the harness. |
+
+### Axes
+
+Each varies *one* dimension; the rest are held fixed.
+
+**Compile** (`kit cc -O0 -c`, or `-E` for the preprocessor axes):
+`fn-count` (functions) · `body-size` (statements in one function) · `global-decl`
+(file-scope globals) · `type-decl` (distinct struct typedefs) · `locals-per-fn`
+(locals in one function) · `pp-macro` (macro expansions) · `pp-include` (distinct
+headers) · `ref-density` (distinct extern calls in one function).
+
+**Link** (`kit ld`, objects pre-built untimed):
+`obj-count` (object files) · `symbol-count` (total symbols/relocs, object count
+fixed).
+
+### Output (`build/bench/cc/`)
+
+- `scaling.md` — linearity summary (exponent + verdict + kit/clang ratio per
+ axis) and per-axis detail (per-unit time, net-of-overhead, clang comparison).
+- `hotspots.md` — top self-time functions per axis. Read these for the axes
+ flagged `SUPERLINEAR`: the dominant function *is* the O(n²).
+- `scaling.csv` — raw rows; `raw/<axis>.sample.txt` — full `sample` reports;
+ `logs/` — per-run stdout/stderr.
+
+### Env knobs
+
+`KIT` (binary) · `CLANG` · `KIT_CC_BENCH_AXES` (subset) · `KIT_CC_BENCH_SIZES`
+(override series) · `KIT_CC_BENCH_REPEATS` (default 3) · `KIT_CC_BENCH_MAX_MS`
+(adaptive cap: stop growing an axis past this wall-time, default 4000 — keeps the
+run bounded even when an axis is badly superlinear) · `KIT_CC_BENCH_SKIP_CLANG` ·
+`KIT_CC_BENCH_SAMPLE` (default 1) · `KIT_CC_BENCH_DTRACE` (flat histogram; needs
+sudo) · `KIT_CC_BENCH_OUT`.
+
+Quick wire-check: `KIT_CC_BENCH_SIZES='8 16 32' KIT_CC_BENCH_SAMPLE=0 make bench-cc`.
+
+## Findings
+
+> 2026-06-10, M1 (8-core), clang-built `PROFILE=1` release kit, best-of-3.
+> **All superlinear axes have been fixed** — every axis is now LINEAR. The table
+> shows the exponent before → after the fixes below, and kit's speed vs clang
+> `-O0` at the largest measured size.
+
+| axis | exponent before → after | kit/clang before → after | was |
+|------|:-----------------------:|:------------------------:|-----|
+| type-decl | 2.14 → **1.09** | 70.1× slower → **0.62× (1.6× faster)** | `parse_c` typedef intern |
+| fn-count | 1.92 → **1.04** | 7.5× slower → **0.33× (3× faster)** | `declare_function` scan |
+| ref-density | 1.90 → **1.04** | 6.0× slower → **0.16× (6× faster)** | `declare_function`+`scope_lookup` |
+| locals-per-fn | 1.45 → **0.96** | → **0.04× (25× faster)** | `make_local_aligned` scan |
+| global-decl | 1.44 → **1.01** | 24.4× → 5.3× slower (linear) | global-scope scan |
+| pp-include | 1.25 → **1.06** | 1.8× slower | file-I/O bound |
+| body-size | 0.98 → **1.03** | 1.30× slower | (already linear) |
+| pp-macro | 1.00 → **1.01** | 0.05× (22× faster) | `-E` output I/O |
+| obj-count | linear | **0.27× (3.7× faster than ld64)** | linker |
+| symbol-count | 1.03 → **1.03** | 1.45× slower (linear) | linker |
+
+The remaining axes where kit is slower than clang (global-decl 5.3×, symbol-count
+1.45×, body-size 1.3×, pp-include 1.8×) are all **linear** — constant-factor
+codegen/IO differences, not scaling problems. On every axis that was O(n²), kit
+went from 6–70× slower to **as fast as or faster than clang**.
+
+### Fixes applied (all landed)
+
+The root cause was systemic: every place that added N entries to a *symbol /
+scope / type* table did a **linear scan per item**. Three changes:
+
+1. **C-frontend scope/tag/external indexes** (`lang/c/parse/parse.c`,
+ `parse_priv.h`). `Scope.entries`, `Scope.tags`, and the file-scope
+ `external_funcs` list were LIFO linked lists scanned linearly by
+ `scope_lookup` / `scope_lookup_current` / `tag_lookup` / `external_func_*`
+ (and `make_local_aligned`'s redefinition check). Each now carries a generated
+ `KIT_HASHMAP_DEFINE` index keyed on the interned `Sym`. Scopes keep the list
+ for ordering and only build the index past a small threshold (tiny block
+ scopes pay nothing); indexes allocate through an arena-heap facade so there is
+ no teardown. → fixed type-decl, fn-count, ref-density, global-decl, locals.
+2. **Chunked-buffer random access** (`src/core/buf.c`, `buf.h`). `buf_patch` /
+ `buf_read` walked the chunk list from the head — O(N_chunks) — so single-pass
+ emission patch-ups over a multi-MB `.text` were O(n²) (this was the residual
+ that kept fn-count at 1.18 after fix #1, 70% of its self-time). Added a sorted
+ chunk-start directory + binary search → O(log N_chunks); append stays O(1).
+3. **Object section find-or-create** (`src/obj/obj.c`). `obj_section` linearly
+ scanned all sections to dedup by `(name, kind)`; added a composite-key
+ `SecKeyIndex` so the find is O(1). Latent today (kit's `cc` emits one `.text`)
+ but O(n²) under `-ffunction-sections` / many distinct sections.
+
+Verified: `test-parse` 3880×4 modes, `toy` 1392, all `cg_*`, `test-link`,
+`test-elf`/`macho`, `test-debug`/`dwarf`, `test-smoke-x64`/`rv64` — all pass
+under ASan/UBSan; benchmark exponents all ≤ ~1.1.
+
+### Deliberately left (genuinely bounded, not O(n²) in practice)
+
+- **COFF weak-alias** lookup (`obj_set/get_weak_alias`): a linear scan, but only
+ over the handful of `WEAK_EXTERNAL`s in an import-archive member — does not
+ scale with compiler input.
+- **Linker COMDAT atom fallback** (`link_resolve.c`): O(natom) only for
+ COMDAT/GROUP symbols (rare in C); the normal path is already an O(1) hash hit.
+
+### Resolved out-of-band
+
+The macOS system linker (`ld64`) previously rejected kit's Mach-O objects
+(`empty CIE`); it now accepts them since kit stops emitting a raw `__eh_frame` on
+Mach-O (`KitTargetSpec.emits_eh_frame`, `src/api/core.c`). The benchmark's link
+axes therefore now carry a real system-`ld` reference: **kit's linker is ~3.7×
+faster than ld64** at 1024 objects (40 ms vs 146 ms; ld64 has ~123 ms of fixed
+overhead).
diff --git a/doc/plan/README.md b/doc/plan/README.md
@@ -10,6 +10,7 @@ shrinks to whatever remains open.
|---------|-------|------------|
| [RELEASE.md](RELEASE.md) | Cross-cutting initial-release punchlist: release scope, deferred features, and per-subsystem completion/validation items. | — |
| [OPTIMIZER.md](OPTIMIZER.md) | Completing the O2 SSA mid-end, expanded inlining, -O0/-O1 performance work, machine register-constraint improvements. | [../OPT.md](../OPT.md) |
+| [PERF.md](PERF.md) | Making kit the fastest `-O0` C compiler: the compile+link scaling benchmark (`make bench-cc`), per-axis linearity goals, hotspot sampling, and the open superlinear-axis fixes. | — |
| [LINKER.md](LINKER.md) | Incremental linking: the file-based object-link redesign and remaining non-ELF format coverage. | [../LINK.md](../LINK.md) |
| [JIT.md](JIT.md) | Function-level hot reload, Go-runtime-style codegen support, and remaining JIT host-portability work. | [../JIT.md](../JIT.md) |
| [DEBUG.md](DEBUG.md) | The Windows debugger host adapter, x64/rv64 displaced single-step, profiling, and DWARF gaps. | [../DBG.md](../DBG.md), [../DWARF.md](../DWARF.md) |
diff --git a/mk/flags.mk b/mk/flags.mk
@@ -11,10 +11,20 @@ ifeq ($(RELEASE),1)
HOST_OPTFLAGS ?= -O2
HOST_MODE_CPPFLAGS = -DNDEBUG
HOST_MODE_CFLAGS = -ffunction-sections -fdata-sections
+# PROFILE=1: an optimized build that stays profileable. Keeps -g/DWARF + frame
+# pointers and skips the -Wl,-S debug strip so sampling profilers (e.g.
+# `make bench-cc`) can attribute hotspots to functions and source lines. Codegen
+# is unchanged (-O2), so timings still reflect the shipped release.
+ifeq ($(PROFILE),1)
+HOST_MODE_CFLAGS += -g -fno-omit-frame-pointer
+endif
ifeq ($(HOST_OS),darwin)
-HOST_MODE_LDFLAGS = -Wl,-dead_strip -Wl,-S
+HOST_MODE_LDFLAGS = -Wl,-dead_strip
else
-HOST_MODE_LDFLAGS = -Wl,--gc-sections -Wl,-S
+HOST_MODE_LDFLAGS = -Wl,--gc-sections
+endif
+ifneq ($(PROFILE),1)
+HOST_MODE_LDFLAGS += -Wl,-S
endif
else
HOST_OPTFLAGS ?= -O0
diff --git a/mk/maint.mk b/mk/maint.mk
@@ -3,7 +3,7 @@
# Developer maintenance targets: source formatting, the clangd compilation
# database, optimizer benchmarking, and clean.
-.PHONY: format compile-commands bench-opt code-size clean
+.PHONY: format compile-commands bench-opt bench-cc code-size clean
# Format only the .c/.h files changed in the working tree (staged, unstaged, or
# new/untracked), restricted to the formatted roots and excluding test/pp. When
@@ -32,6 +32,14 @@ bench-opt:
$(MAKE) RELEASE=1 bin
@KIT='$(abspath build/release/kit)' bash scripts/opt_bench.sh
+# -O0 C compile+link throughput/scaling benchmark + hotspot sampling. Builds a
+# release kit with clang (-O2, but with -g and without the symbol strip so
+# `sample` can attribute hotspots) into build/bench/kit, then sweeps each input
+# axis and fits a scaling exponent. Design + findings: doc/plan/PERF.md.
+bench-cc:
+ $(MAKE) RELEASE=1 PROFILE=1 CC=clang BUILD_DIR=build/bench bin
+ @KIT='$(abspath build/bench/kit)' bash scripts/cc_bench.sh
+
# Regenerate doc/CODE_SIZE.md: per-component cloc line counts plus a binary
# code-size section attributed from the release linker map. Requires cloc.
# The map step relinks the release objects explicitly (not via libkit.a) so the
diff --git a/scripts/cc_bench.sh b/scripts/cc_bench.sh
@@ -0,0 +1,349 @@
+#!/usr/bin/env bash
+# -O0 C compile + link scaling benchmark for kit.
+#
+# Goal: kit is meant to be the *fastest* C compiler. This harness sweeps each
+# input axis (see scripts/cc_bench_gen.py --list) over a geometric size series,
+# times `kit cc -O0 -c/-E` (compile) and `kit ld` (link) best-of-N, records a
+# clang -O0 reference for context, and samples the largest input per axis to
+# produce a flat self-time hotspot table. The reporter (cc_bench_report.py) fits
+# a scaling exponent per axis: ~1.0 is the linear goal, >=1.4 is an O(n^2) trap.
+#
+# Output under build/bench/cc/: scaling.csv (raw), plus scaling.md + hotspots.md
+# written by the reporter.
+#
+# Env knobs:
+# KIT kit binary (default build/bench/kit, else build/release/kit)
+# CLANG clang binary (default clang)
+# KIT_CC_BENCH_AXES space-separated subset of axes (default: all)
+# KIT_CC_BENCH_SIZES override size series for ALL axes (default: per-axis)
+# KIT_CC_BENCH_REPEATS best-of-N timing repeats (default 3)
+# KIT_CC_BENCH_SKIP_CLANG 1 to skip the clang reference (default 0)
+# KIT_CC_BENCH_SAMPLE 1 to sample hotspots (default 1)
+# KIT_CC_BENCH_SAMPLE_AXES subset of axes to sample (default: all run)
+# KIT_CC_BENCH_SAMPLE_MIN_MS skip sampling if max-size run is faster (default 400)
+# KIT_CC_BENCH_DTRACE 1 to use dtrace flat histogram instead of sample (needs sudo)
+# KIT_CC_BENCH_OUT output root (default build/bench/cc)
+# KIT_SYSROOT sysroot passed to kit (default: macOS SDK via xcrun)
+set -uo pipefail
+
+ROOT="$(cd "$(dirname "$0")/.." && pwd)"
+GEN="$ROOT/scripts/cc_bench_gen.py"
+REPORT="$ROOT/scripts/cc_bench_report.py"
+
+KIT="${KIT:-}"
+if [ -z "$KIT" ]; then
+ if [ -x "$ROOT/build/bench/kit" ]; then KIT="$ROOT/build/bench/kit"
+ else KIT="$ROOT/build/release/kit"; fi
+fi
+CLANG="${CLANG:-clang}"
+OUT_DIR="${KIT_CC_BENCH_OUT:-$ROOT/build/bench/cc}"
+REPEATS="${KIT_CC_BENCH_REPEATS:-3}"
+SKIP_CLANG="${KIT_CC_BENCH_SKIP_CLANG:-0}"
+DO_SAMPLE="${KIT_CC_BENCH_SAMPLE:-1}"
+SAMPLE_MIN_MS="${KIT_CC_BENCH_SAMPLE_MIN_MS:-400}"
+USE_DTRACE="${KIT_CC_BENCH_DTRACE:-0}"
+# Adaptive cap: once a size's kit time exceeds this, stop growing that axis. Keeps
+# the run bounded even when an axis is badly superlinear (we still collect the
+# smaller points needed to fit + flag the exponent). 0 disables.
+MAX_MS="${KIT_CC_BENCH_MAX_MS:-4000}"
+
+# kit needs a sysroot to find the host libc for linking. Match opt_bench.sh.
+KIT_SYSROOT="${KIT_SYSROOT:-}"
+if [ -z "$KIT_SYSROOT" ] && [ "$(uname -s)" = "Darwin" ] && command -v xcrun >/dev/null 2>&1; then
+ KIT_SYSROOT="$(xcrun --show-sdk-path 2>/dev/null || true)"
+fi
+KIT_SYSROOT_ARGS=()
+[ -n "$KIT_SYSROOT" ] && KIT_SYSROOT_ARGS=(--sysroot "$KIT_SYSROOT")
+# Homebrew clang ships a default config pointing at a (often nonexistent) SDK;
+# pass the real one so the reference build is clean. Compile needs no headers
+# (generated sources have none), but this silences the stale-sysroot warning.
+CLANG_SYSROOT_ARGS=()
+[ -n "$KIT_SYSROOT" ] && CLANG_SYSROOT_ARGS=(-isysroot "$KIT_SYSROOT")
+
+CSV="$OUT_DIR/scaling.csv"
+GEN_DIR="$OUT_DIR/gen"
+RAW_DIR="$OUT_DIR/raw"
+LOG_DIR="$OUT_DIR/logs"
+
+if [ ! -x "$KIT" ]; then
+ printf 'cc-bench: kit binary not found/executable: %s\n' "$KIT" >&2
+ printf 'cc-bench: run `make bench-cc` (builds a profiling kit) or set KIT=...\n' >&2
+ exit 2
+fi
+
+rm -rf "$GEN_DIR" "$RAW_DIR" "$LOG_DIR"
+mkdir -p "$OUT_DIR" "$GEN_DIR" "$RAW_DIR" "$LOG_DIR"
+
+# ---------------------------------------------------------------------------
+# Timing: run a command, capturing rc + wall-clock ms of exactly the child.
+# python times only the subprocess, so its own startup is not counted.
+# ---------------------------------------------------------------------------
+time_cmd() { # $1=out $2=err ; rest=cmd ; sets TIME_RC, TIME_MS
+ local out="$1" err="$2"; shift 2
+ local line
+ line=$(python3 - "$out" "$err" "$@" <<'PY'
+import subprocess, sys, time
+out, err = sys.argv[1], sys.argv[2]
+cmd = sys.argv[3:]
+with open(out, "wb") as o, open(err, "wb") as e:
+ t0 = time.monotonic_ns()
+ rc = subprocess.call(cmd, stdout=o, stderr=e)
+ t1 = time.monotonic_ns()
+print("%d %.3f" % (rc, (t1 - t0) / 1e6))
+PY
+)
+ TIME_RC="${line%% *}"
+ TIME_MS="${line#* }"
+}
+
+min_ms() { # echo min of $1,$2 (either may be "" meaning unset)
+ awk -v a="$1" -v b="$2" 'BEGIN{
+ if (a=="") {print b; exit}
+ if (b=="") {print a; exit}
+ print (b+0 < a+0) ? b : a
+ }'
+}
+
+csv_field() { printf '%s' "$1" | sed 's/"/""/g; s/^/"/; s/$/"/'; }
+record() { # axis phase tool mode n unit time_ms status exit note
+ { csv_field "$1"; printf ','; csv_field "$2"; printf ','; csv_field "$3"; printf ',';
+ csv_field "$4"; printf ','; csv_field "$5"; printf ','; csv_field "$6"; printf ',';
+ csv_field "$7"; printf ','; csv_field "$8"; printf ','; csv_field "$9"; printf ',';
+ csv_field "${10}"; printf '\n'; } >>"$CSV"
+}
+
+# best-of-N: run "$@" REPEATS times, set BEST_MS (min over reps) + LAST_RC.
+best_of() { # out_base, cmd...
+ local out_base="$1"; shift
+ local rep best=""
+ LAST_RC=0
+ for rep in $(seq 1 "$REPEATS"); do
+ time_cmd "$out_base.$rep.out" "$out_base.$rep.err" "$@"
+ LAST_RC="$TIME_RC"
+ [ "$TIME_RC" -ne 0 ] && { best=""; return 1; }
+ best="$(min_ms "$best" "$TIME_MS")"
+ done
+ BEST_MS="$best"
+ return 0
+}
+
+# ---------------------------------------------------------------------------
+# kit / clang command builders (mode -> argv). kit links via `kit ld ... -l c`.
+# ---------------------------------------------------------------------------
+kit_compile_cmd() { KIT_CMD=("$KIT" cc -O0 -c "$1" -o "$2"); }
+kit_preprocess_cmd() { KIT_CMD=("$KIT" cc -O0 -E "$@"); } # args: [-I dir] src -o out
+kit_link_cmd() { KIT_CMD=("$KIT" ld "$@" -l c "${KIT_SYSROOT_ARGS[@]}"); } # args: objs... -o app
+clang_compile_cmd() { CLANG_CMD=("$CLANG" "${CLANG_SYSROOT_ARGS[@]}" -O0 -c "$1" -o "$2"); }
+clang_preprocess_cmd() { CLANG_CMD=("$CLANG" "${CLANG_SYSROOT_ARGS[@]}" -O0 -E "$@"); }
+clang_link_cmd() { CLANG_CMD=("$CLANG" "${CLANG_SYSROOT_ARGS[@]}" "$@"); } # kit objs... -o app
+
+# ---------------------------------------------------------------------------
+# Axis runners. Each generates the instance, times kit (+clang ref), checks
+# correctness, records rows. Sets KIT_BEST_MS for the sampling gate.
+# ---------------------------------------------------------------------------
+read_manifest() { # $1=manifest.json $2=key -> echo value (python)
+ python3 -c 'import json,sys; v=json.load(open(sys.argv[1])).get(sys.argv[2],""); print(v if not isinstance(v,list) else " ".join(map(str,v)))' "$1" "$2"
+}
+
+run_compile_axis() { # axis mode unit n dir
+ local axis="$1" mode="$2" unit="$3" n="$4" dir="$5"
+ local src="$dir/gen.c" incdir status="OK"
+ incdir="$(read_manifest "$dir/manifest.json" incdir)"
+ local inc_args=(); [ -n "$incdir" ] && inc_args=(-I "$dir/$incdir")
+ local logb="$LOG_DIR/$axis.n$n.kit"
+
+ # kit
+ if [ "$mode" = preprocess ]; then
+ kit_preprocess_cmd "${inc_args[@]}" "$src" -o "$dir/gen.i"
+ else
+ kit_compile_cmd "$src" "$dir/gen.o"
+ fi
+ KIT_BEST_MS=""
+ if best_of "$logb" "${KIT_CMD[@]}"; then
+ # correctness: output produced
+ local artifact="$dir/gen.o"; [ "$mode" = preprocess ] && artifact="$dir/gen.i"
+ [ -s "$artifact" ] || status="OUTPUT_FAIL"
+ KIT_BEST_MS="$BEST_MS"
+ else
+ status="KIT_FAIL"
+ fi
+ record "$axis" compile kit "$mode" "$n" "$unit" "${BEST_MS:-NA}" "$status" "$LAST_RC" "$logb.1.err"
+
+ # clang reference
+ if [ "$SKIP_CLANG" != 1 ]; then
+ local clogb="$LOG_DIR/$axis.n$n.clang" cstatus="OK"
+ if [ "$mode" = preprocess ]; then
+ clang_preprocess_cmd "${inc_args[@]}" "$src" -o "$dir/gen.clang.i"
+ else
+ clang_compile_cmd "$src" "$dir/gen.clang.o"
+ fi
+ if best_of "$clogb" "${CLANG_CMD[@]}"; then :; else cstatus="CLANG_FAIL"; fi
+ record "$axis" compile clang "$mode" "$n" "$unit" "${BEST_MS:-NA}" "$cstatus" "$LAST_RC" "$clogb.1.err"
+ fi
+}
+
+run_link_axis() { # axis unit n dir
+ local axis="$1" unit="$2" n="$3" dir="$4" status="OK"
+ local prebuild link_order expected logb="$LOG_DIR/$axis.n$n.kit"
+ prebuild="$(read_manifest "$dir/manifest.json" prebuild)"
+ link_order="$(read_manifest "$dir/manifest.json" link_order)"
+ expected="$(read_manifest "$dir/manifest.json" expected_exit)"
+
+ # Pre-build kit objects (UNTIMED). Shared by both linkers.
+ local s o objs=()
+ for s in $prebuild; do
+ o="$dir/${s%.c}.o"
+ if ! "$KIT" cc -O0 -c "$dir/$s" -o "$o" 2>"$LOG_DIR/$axis.n$n.prebuild.err"; then
+ record "$axis" link kit link "$n" "$unit" NA PREBUILD_FAIL 1 "$LOG_DIR/$axis.n$n.prebuild.err"
+ KIT_BEST_MS=""; return
+ fi
+ done
+ for o in $link_order; do objs+=("$dir/$o"); done
+
+ # kit ld (TIMED): relink the prebuilt objects best-of-N.
+ kit_link_cmd "${objs[@]}" -o "$dir/app"
+ KIT_BEST_MS=""
+ if best_of "$logb" "${KIT_CMD[@]}"; then
+ "$dir/app" >/dev/null 2>&1; local got=$?
+ [ "$got" = "$expected" ] || status="OUTPUT_FAIL($got!=$expected)"
+ KIT_BEST_MS="$BEST_MS"
+ else
+ status="KIT_FAIL"
+ fi
+ record "$axis" link kit link "$n" "$unit" "${BEST_MS:-NA}" "$status" "$LAST_RC" "$logb.1.err"
+
+ # System-ld reference: link the SAME kit objects through the clang driver.
+ # (kit's Mach-O objects no longer carry a raw __eh_frame, so ld64 accepts
+ # them.) If the system linker still rejects an object, it's recorded N/A and
+ # the run continues.
+ if [ "$SKIP_CLANG" != 1 ]; then
+ local clogb="$LOG_DIR/$axis.n$n.clang" cstatus="OK"
+ clang_link_cmd "${objs[@]}" -o "$dir/app.clang"
+ if best_of "$clogb" "${CLANG_CMD[@]}"; then
+ "$dir/app.clang" >/dev/null 2>&1
+ local cgot=$?
+ [ "$cgot" = "$expected" ] || cstatus="OUTPUT_FAIL($cgot!=$expected)"
+ else
+ cstatus="CLANG_LINK_NA"
+ fi
+ record "$axis" link clang link "$n" "$unit" "${BEST_MS:-NA}" "$cstatus" \
+ "$LAST_RC" "$clogb.1.err"
+ fi
+}
+
+# ---------------------------------------------------------------------------
+# Hotspot sampling: run kit on the largest input in the background, sample by
+# PID until it exits. No sudo. dtrace path (flat histogram) is opt-in.
+# ---------------------------------------------------------------------------
+sample_cmd() { # axis raw_path cmd...
+ local axis="$1" raw="$2"; shift 2
+ if [ "$USE_DTRACE" = 1 ]; then
+ # Flat user-function histogram for exactly the target process.
+ sudo dtrace -x ustackframes=64 -o "$raw" \
+ -n 'profile-997 /pid == $target/ { @[ufunc(arg1)] = count(); } END { printa(@); }' \
+ -c "$(printf '%q ' "$@")" >/dev/null 2>"$raw.dtrace.err" || \
+ printf 'cc-bench: dtrace sample failed for %s (see %s.dtrace.err)\n' "$axis" "$raw" >&2
+ return
+ fi
+ "$@" >/dev/null 2>"$RAW_DIR/$axis.sample.cmd.err" &
+ local pid=$!
+ # Attach and sample at 1ms until the process dies (-mayDie). 3600s upper bound.
+ sample "$pid" 3600 1 -mayDie -file "$raw" >/dev/null 2>"$RAW_DIR/$axis.sample.err"
+ wait "$pid" 2>/dev/null
+}
+
+# ===========================================================================
+printf 'axis,phase,tool,mode,n,unit,time_ms,status,exit_code,note\n' >"$CSV"
+
+printf 'cc-bench: kit: %s\n' "$KIT"
+"$KIT" --version 2>/dev/null | head -1 | sed 's/^/cc-bench: /' || true
+printf 'cc-bench: clang: %s (skip=%s)\n' "$CLANG" "$SKIP_CLANG"
+printf 'cc-bench: out: %s\n' "$OUT_DIR"
+printf 'cc-bench: repeats=%s sample=%s dtrace=%s\n' "$REPEATS" "$DO_SAMPLE" "$USE_DTRACE"
+
+# Fixed per-invocation overhead: empty TU compile, empty TU preprocess, and a
+# trivial 1-object link. Subtracted by the reporter so process startup doesn't
+# masquerade as sub-linear scaling.
+OV_DIR="$GEN_DIR/__overhead__"; mkdir -p "$OV_DIR"
+printf 'int kit_bench_empty(void){return 0;}\n' >"$OV_DIR/empty.c"
+printf 'int main(void){return 0;}\n' >"$OV_DIR/main.c"
+# Warm up: the very first kit invocation pays dyld/page-in cold-start cost that
+# would inflate the overhead baseline. Discard one run first.
+"$KIT" cc -O0 -c "$OV_DIR/empty.c" -o "$OV_DIR/empty.o" >/dev/null 2>&1
+best_of "$LOG_DIR/ov.compile" "$KIT" cc -O0 -c "$OV_DIR/empty.c" -o "$OV_DIR/empty.o" && \
+ record __overhead__ compile kit compile 0 functions "$BEST_MS" OK 0 ""
+best_of "$LOG_DIR/ov.pp" "$KIT" cc -O0 -E "$OV_DIR/empty.c" -o "$OV_DIR/empty.i" && \
+ record __overhead__ compile kit preprocess 0 headers "$BEST_MS" OK 0 ""
+"$KIT" cc -O0 -c "$OV_DIR/main.c" -o "$OV_DIR/main.o" 2>/dev/null
+best_of "$LOG_DIR/ov.link" "$KIT" ld "$OV_DIR/main.o" -l c "${KIT_SYSROOT_ARGS[@]}" -o "$OV_DIR/app" && \
+ record __overhead__ link kit link 0 objects "$BEST_MS" OK 0 ""
+
+# Axis catalog (JSON) -> drive the sweep.
+AXES_JSON="$(python3 "$GEN" --list)"
+ALL_AXES="$(printf '%s' "$AXES_JSON" | python3 -c 'import json,sys; print(" ".join(a["axis"] for a in json.load(sys.stdin)))')"
+SEL_AXES="${KIT_CC_BENCH_AXES:-$ALL_AXES}"
+SAMPLE_AXES="${KIT_CC_BENCH_SAMPLE_AXES:-$SEL_AXES}"
+
+declare -A AXIS_MAXMS AXIS_MAXN AXIS_PHASE AXIS_MODE AXIS_UNIT
+for axis in $SEL_AXES; do
+ phase="$(printf '%s' "$AXES_JSON" | python3 -c 'import json,sys; a={x["axis"]:x for x in json.load(sys.stdin)}["'"$axis"'"]; print(a["phase"])')"
+ mode="$(printf '%s' "$AXES_JSON" | python3 -c 'import json,sys; a={x["axis"]:x for x in json.load(sys.stdin)}["'"$axis"'"]; print(a["mode"])')"
+ unit="$(printf '%s' "$AXES_JSON" | python3 -c 'import json,sys; a={x["axis"]:x for x in json.load(sys.stdin)}["'"$axis"'"]; print(a["unit"])')"
+ sizes="${KIT_CC_BENCH_SIZES:-$(printf '%s' "$AXES_JSON" | python3 -c 'import json,sys; a={x["axis"]:x for x in json.load(sys.stdin)}["'"$axis"'"]; print(" ".join(map(str,a["sizes"])))')}"
+ AXIS_PHASE[$axis]="$phase"; AXIS_MODE[$axis]="$mode"; AXIS_UNIT[$axis]="$unit"
+ maxn=0
+ printf '\n===== %s (%s, %s) sizes: %s =====\n' "$axis" "$phase" "$mode" "$sizes"
+ for n in $sizes; do
+ dir="$GEN_DIR/$axis/n$n"; mkdir -p "$dir"
+ python3 "$GEN" --axis "$axis" --n "$n" --out "$dir" >"$dir/manifest.json"
+ if [ "$phase" = link ]; then
+ run_link_axis "$axis" "$unit" "$n" "$dir"
+ else
+ run_compile_axis "$axis" "$mode" "$unit" "$n" "$dir"
+ fi
+ printf ' n=%-7s kit=%-10s\n' "$n" "${KIT_BEST_MS:-FAIL}"
+ [ "$n" -gt "$maxn" ] && { maxn="$n"; AXIS_MAXMS[$axis]="${KIT_BEST_MS:-}"; }
+ # Adaptive cap: stop growing this axis once a run blows past the ceiling.
+ if [ "$MAX_MS" != 0 ] && [ -n "${KIT_BEST_MS:-}" ] && \
+ awk -v m="$KIT_BEST_MS" -v c="$MAX_MS" 'BEGIN{exit !(m+0 > c+0)}'; then
+ printf ' (cap: %.0fms > %sms -> stop growing %s)\n' "$KIT_BEST_MS" "$MAX_MS" "$axis"
+ break
+ fi
+ done
+ AXIS_MAXN[$axis]="$maxn"
+done
+
+# ---- sampling pass: largest input per axis ----
+if [ "$DO_SAMPLE" = 1 ]; then
+ printf '\ncc-bench: sampling hotspots (largest input per axis)\n'
+ for axis in $SAMPLE_AXES; do
+ [ -n "${AXIS_PHASE[$axis]:-}" ] || continue
+ maxn="${AXIS_MAXN[$axis]}"; maxms="${AXIS_MAXMS[$axis]:-0}"
+ raw="$RAW_DIR/$axis.sample.txt"
+ if [ -z "$maxms" ]; then printf ' %-14s SKIP (run failed)\n' "$axis"; continue; fi
+ if awk -v m="$maxms" -v t="$SAMPLE_MIN_MS" 'BEGIN{exit !(m+0 < t+0)}'; then
+ printf ' %-14s SKIP (%.0fms < %sms)\n' "$axis" "$maxms" "$SAMPLE_MIN_MS"
+ printf 'skipped: %s ran in %sms (< %sms), too short to sample\n' "$axis" "$maxms" "$SAMPLE_MIN_MS" >"$raw"
+ continue
+ fi
+ dir="$GEN_DIR/$axis/n$maxn"
+ if [ "${AXIS_PHASE[$axis]}" = link ]; then
+ link_order="$(read_manifest "$dir/manifest.json" link_order)"
+ objs=(); for o in $link_order; do objs+=("$dir/$o"); done # objects already built in sweep
+ printf ' %-14s sampling kit ld (n=%s, ~%.0fms)\n' "$axis" "$maxn" "$maxms"
+ sample_cmd "$axis" "$raw" "$KIT" ld "${objs[@]}" -l c "${KIT_SYSROOT_ARGS[@]}" -o "$dir/app.sample"
+ else
+ incdir="$(read_manifest "$dir/manifest.json" incdir)"
+ inc_args=(); [ -n "$incdir" ] && inc_args=(-I "$dir/$incdir")
+ printf ' %-14s sampling kit cc (n=%s, ~%.0fms)\n' "$axis" "$maxn" "$maxms"
+ if [ "${AXIS_MODE[$axis]}" = preprocess ]; then
+ sample_cmd "$axis" "$raw" "$KIT" cc -O0 -E "${inc_args[@]}" "$dir/gen.c" -o "$dir/gen.sample.i"
+ else
+ sample_cmd "$axis" "$raw" "$KIT" cc -O0 -c "$dir/gen.c" -o "$dir/gen.sample.o"
+ fi
+ fi
+ done
+fi
+
+printf '\ncc-bench: wrote %s\n' "$CSV"
+python3 "$REPORT" "$OUT_DIR" || true
diff --git a/scripts/cc_bench_gen.py b/scripts/cc_bench_gen.py
@@ -0,0 +1,309 @@
+#!/usr/bin/env python3
+"""Synthetic C input generator for the -O0 compile+link scaling benchmark.
+
+This is the single source of truth for the benchmark's *axes*: each axis varies
+one input dimension (function count, statement count, object-file count, ...) so
+the harness can sweep it over a geometric size series and the reporter can fit a
+scaling exponent. The goal is linear scaling on every axis; a superlinear axis
+points straight at an O(n^2) trap in the single-pass frontend or the linker.
+
+Two modes:
+
+ cc_bench_gen.py --list
+ Print a JSON array describing every axis: name, phase (compile|link),
+ unit label, timed mode (compile=-c, preprocess=-E, link), and the default
+ geometric size series. The harness drives the sweep from this.
+
+ cc_bench_gen.py --axis AXIS --n N --out DIR
+ Write the source/header files for AXIS at size N into DIR and print a JSON
+ manifest describing how to build/time/check this instance. The manifest
+ names *intent* (mode, source, prebuild list, link order, expected exit),
+ never tool-specific flags -- the harness turns that into kit/clang command
+ lines so the axis definitions stay tool-neutral.
+
+Generated code is dead-simple C11 with no platform headers (integer arithmetic
++ a deterministic main return % 256), so compile time is frontend/codegen-bound
+and identical for kit and the clang reference.
+"""
+import argparse
+import json
+import os
+import sys
+
+# ---------------------------------------------------------------------------
+# Axis catalog. Each entry: phase, unit label, timed mode, default size series.
+# Sizes are tuned per axis: large where the work is cheap per unit (statements,
+# macro expansions), smaller where an O(n^2) trap would blow up fast (locals,
+# decls) or where each unit is its own file (objects, headers).
+# ---------------------------------------------------------------------------
+AXES = {
+ # ---- compile axes (kit cc -O0 -c, or -E for the preprocessor axes) ----
+ "fn-count": {
+ "phase": "compile", "unit": "functions", "mode": "compile",
+ "sizes": [1000, 2000, 4000, 8000, 16000, 32000],
+ "blurb": "N tiny functions -> symbol-table inserts, per-fn codegen+emit",
+ },
+ "body-size": {
+ "phase": "compile", "unit": "statements", "mode": "compile",
+ "sizes": [4000, 8000, 16000, 32000, 64000, 128000],
+ "blurb": "one function, N statements -> per-stmt codegen, value stack, "
+ "BB patch-ups, const-tracker",
+ },
+ "global-decl": {
+ "phase": "compile", "unit": "globals", "mode": "compile",
+ "sizes": [2000, 4000, 8000, 16000, 32000, 64000],
+ "blurb": "N file-scope globals -> global scope table inserts",
+ },
+ "type-decl": {
+ "phase": "compile", "unit": "types", "mode": "compile",
+ "sizes": [2000, 4000, 8000, 16000, 32000, 64000],
+ "blurb": "N distinct struct typedefs -> type/typedef interning",
+ },
+ "locals-per-fn": {
+ "phase": "compile", "unit": "locals", "mode": "compile",
+ "sizes": [1000, 2000, 4000, 8000, 16000, 32000],
+ "blurb": "one function, N locals -> local scope table, frame slots",
+ },
+ "pp-macro": {
+ "phase": "compile", "unit": "expansions", "mode": "preprocess",
+ "sizes": [4000, 8000, 16000, 32000, 64000, 128000],
+ "blurb": "N function-like macro expansions -> macro expander, token buf",
+ },
+ "pp-include": {
+ "phase": "compile", "unit": "headers", "mode": "preprocess",
+ "sizes": [500, 1000, 2000, 4000, 8000],
+ "blurb": "N distinct headers included once -> lexer/pp file handling",
+ },
+ "ref-density": {
+ "phase": "compile", "unit": "calls", "mode": "compile",
+ "sizes": [2000, 4000, 8000, 16000, 32000, 64000],
+ "blurb": "one function, N calls to N distinct externs -> call lowering, "
+ "relocation emission",
+ },
+ # ---- link axes (objects pre-built untimed; only kit ld is timed) ----
+ "obj-count": {
+ "phase": "link", "unit": "objects", "mode": "link",
+ "sizes": [32, 64, 128, 256, 512, 1024],
+ "blurb": "N objects linked to one exe -> input handling, symbol resolve "
+ "map, layout/section merge",
+ },
+ "symbol-count": {
+ "phase": "link", "unit": "symbols", "mode": "link",
+ "sizes": [2000, 4000, 8000, 16000, 32000, 64000],
+ "blurb": "fixed object count, N total symbols/relocs -> global symbol "
+ "hash map + reloc apply",
+ },
+}
+
+
+def _write(path, lines):
+ """Write a file from an iterable of lines (joined, single write)."""
+ with open(path, "w") as f:
+ f.write("\n".join(lines))
+ f.write("\n")
+
+
+# ---------------------------------------------------------------------------
+# Per-axis source generators. Each returns the manifest dict (minus axis/n/unit/
+# phase, which the caller fills in) after writing files into `out`.
+# ---------------------------------------------------------------------------
+def gen_fn_count(n, out):
+ lines = ["/* fn-count n=%d */" % n]
+ for i in range(n):
+ lines.append("int f_%d(int x){return x + %d;}" % (i, i % 251))
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_body_size(n, out):
+ lines = ["/* body-size n=%d */" % n, "int body(int x){", " int acc = x;"]
+ for i in range(n):
+ lines.append(" acc = acc * 1000003 + %d;" % (i % 1000))
+ lines += [" return acc;", "}"]
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_global_decl(n, out):
+ lines = ["/* global-decl n=%d */" % n]
+ for i in range(n):
+ lines.append("int g_%d = %d;" % (i, i % 257))
+ # Touch the first and last so the TU is unambiguously meaningful.
+ lines.append("int gd_use(void){return g_0 + g_%d;}" % (n - 1))
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_type_decl(n, out):
+ lines = ["/* type-decl n=%d */" % n]
+ for i in range(n):
+ lines.append("typedef struct { int a; int b; } T_%d;" % i)
+ # Use the last type so the table is actually consulted, not just filled.
+ lines.append("T_%d g_last;" % (n - 1))
+ lines.append("int td_use(void){return g_last.a + g_last.b;}")
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_locals_per_fn(n, out):
+ lines = ["/* locals-per-fn n=%d */" % n, "int locals(int x){"]
+ lines.append(" int v0 = x;")
+ for i in range(1, n):
+ lines.append(" int v%d = v%d + %d;" % (i, i - 1, i % 251))
+ lines.append(" return v0 ^ v%d;" % (n - 1))
+ lines.append("}")
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_pp_macro(n, out):
+ lines = ["/* pp-macro n=%d */" % n,
+ "#define SQ(x) ((x)*(x))",
+ "#define MIX(a,b) (SQ(a) + SQ(b) - (a)*(b))",
+ "int pp_macro(int x){", " int a = 0;"]
+ for i in range(n):
+ lines.append(" a += MIX(x + %d, x - %d);" % (i % 997, i % 991))
+ lines += [" return a;", "}"]
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "preprocess", "source": "gen.c"}
+
+
+def gen_pp_include(n, out):
+ for i in range(n):
+ guard = "H_%d_H" % i
+ _write(os.path.join(out, "h_%d.h" % i), [
+ "#ifndef %s" % guard, "#define %s" % guard,
+ "typedef int hi_%d_t;" % i,
+ "extern hi_%d_t hv_%d;" % (i, i),
+ "#endif",
+ ])
+ lines = ["/* pp-include n=%d */" % n]
+ for i in range(n):
+ lines.append('#include "h_%d.h"' % i)
+ lines.append("int pp_include(void){return 0;}")
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "preprocess", "source": "gen.c", "incdir": "."}
+
+
+def gen_ref_density(n, out):
+ lines = ["/* ref-density n=%d */" % n]
+ for i in range(n):
+ lines.append("extern int rf_%d(void);" % i)
+ lines += ["int hub(void){", " int s = 0;"]
+ for i in range(n):
+ lines.append(" s += rf_%d();" % i)
+ lines += [" return s;", "}"]
+ _write(os.path.join(out, "gen.c"), lines)
+ return {"mode": "compile", "source": "gen.c"}
+
+
+def gen_obj_count(n, out):
+ # N leaf objects, each defining leaf_i returning i. A main sums them all and
+ # returns the total % 256. Objects are pre-built untimed; only the link of
+ # all N+1 objects is timed.
+ prebuild = []
+ link_order = []
+ for i in range(n):
+ _write(os.path.join(out, "obj_%d.c" % i),
+ ["int leaf_%d(void){return %d;}" % (i, i % 256)])
+ prebuild.append("obj_%d.c" % i)
+ link_order.append("obj_%d.o" % i)
+ main = ["/* obj-count main n=%d */" % n]
+ for i in range(n):
+ main.append("extern int leaf_%d(void);" % i)
+ main += ["int main(void){", " long s = 0;"]
+ for i in range(n):
+ main.append(" s += leaf_%d();" % i)
+ expected = (sum(i % 256 for i in range(n))) % 256
+ main += [" return (int)(s % 256);", "}"]
+ _write(os.path.join(out, "main.c"), main)
+ prebuild.append("main.c")
+ link_order.append("main.o")
+ return {"mode": "link", "prebuild": prebuild, "link_order": link_order,
+ "expected_exit": expected}
+
+
+def gen_symbol_count(n, out):
+ # Fixed object count (2): defs.c defines N functions, main.c references all
+ # N. Link must resolve N symbols and apply N relocations -> stresses the
+ # global symbol hash map + reloc apply with object count held constant.
+ defs = ["/* symbol-count defs n=%d */" % n]
+ for i in range(n):
+ defs.append("int s_%d(void){return %d;}" % (i, i % 256))
+ _write(os.path.join(out, "defs.c"), defs)
+ main = ["/* symbol-count main n=%d */" % n]
+ for i in range(n):
+ main.append("extern int s_%d(void);" % i)
+ main += ["int main(void){", " long s = 0;"]
+ for i in range(n):
+ main.append(" s += s_%d();" % i)
+ main += [" return (int)(s % 256);", "}"]
+ _write(os.path.join(out, "main.c"), main)
+ expected = (sum(i % 256 for i in range(n))) % 256
+ return {"mode": "link", "prebuild": ["defs.c", "main.c"],
+ "link_order": ["defs.o", "main.o"], "expected_exit": expected}
+
+
+GENERATORS = {
+ "fn-count": gen_fn_count,
+ "body-size": gen_body_size,
+ "global-decl": gen_global_decl,
+ "type-decl": gen_type_decl,
+ "locals-per-fn": gen_locals_per_fn,
+ "pp-macro": gen_pp_macro,
+ "pp-include": gen_pp_include,
+ "ref-density": gen_ref_density,
+ "obj-count": gen_obj_count,
+ "symbol-count": gen_symbol_count,
+}
+
+
+def cmd_list():
+ out = []
+ for name, spec in AXES.items():
+ out.append({
+ "axis": name,
+ "phase": spec["phase"],
+ "unit": spec["unit"],
+ "mode": spec["mode"],
+ "sizes": spec["sizes"],
+ "blurb": spec["blurb"],
+ })
+ json.dump(out, sys.stdout, indent=2)
+ sys.stdout.write("\n")
+
+
+def cmd_gen(axis, n, out):
+ if axis not in GENERATORS:
+ sys.exit("cc_bench_gen: unknown axis %r" % axis)
+ if n < 1:
+ sys.exit("cc_bench_gen: n must be >= 1")
+ os.makedirs(out, exist_ok=True)
+ spec = AXES[axis]
+ manifest = GENERATORS[axis](n, out)
+ manifest.update({
+ "axis": axis, "n": n, "phase": spec["phase"], "unit": spec["unit"],
+ })
+ json.dump(manifest, sys.stdout)
+ sys.stdout.write("\n")
+
+
+def main():
+ ap = argparse.ArgumentParser(description=__doc__)
+ ap.add_argument("--list", action="store_true",
+ help="print the axis catalog as JSON and exit")
+ ap.add_argument("--axis", help="axis name (see --list)")
+ ap.add_argument("--n", type=int, help="size for this axis")
+ ap.add_argument("--out", help="output directory for generated files")
+ args = ap.parse_args()
+
+ if args.list:
+ cmd_list()
+ return
+ if not (args.axis and args.n is not None and args.out):
+ ap.error("need --axis, --n and --out (or --list)")
+ cmd_gen(args.axis, args.n, args.out)
+
+
+if __name__ == "__main__":
+ main()
diff --git a/scripts/cc_bench_report.py b/scripts/cc_bench_report.py
@@ -0,0 +1,353 @@
+#!/usr/bin/env python3
+"""Reporter for the -O0 compile+link scaling benchmark.
+
+Reads <out>/scaling.csv (written by cc_bench.sh) and produces:
+
+ <out>/scaling.md per-axis scaling exponent + verdict + clang ratio
+ <out>/hotspots.md flat self-time hotspot table per axis, parsed from the
+ `sample` call-trees in <out>/raw/<axis>.sample.txt
+
+Scaling model: for each axis we fit log(t_net) = log(a) + p*log(n), where t_net
+is best-of-N wall time minus the fixed per-invocation overhead (empty-TU compile
+/ preprocess / trivial link). The exponent p is the headline:
+
+ p < 1.15 LINEAR (the goal)
+ p < 1.40 NEAR-LINEAR
+ p >= 1.40 SUPERLINEAR (an O(n^2)-ish trap -> a hotspot to fix)
+
+A low R^2 (<0.9) tags the fit NOISY (rerun with more repeats / bigger sizes).
+"""
+import csv
+import math
+import os
+import re
+import sys
+from collections import defaultdict, OrderedDict
+
+
+# ---------------------------------------------------------------------------
+# CSV loading
+# ---------------------------------------------------------------------------
+def fnum(v):
+ try:
+ return float(v)
+ except (TypeError, ValueError):
+ return None
+
+
+def load(csv_path):
+ with open(csv_path, newline="") as f:
+ return list(csv.DictReader(f))
+
+
+# ---------------------------------------------------------------------------
+# Power-law fit
+# ---------------------------------------------------------------------------
+def linfit(xs, ys):
+ """Least-squares slope/intercept/R^2 of ys ~ a + b*xs."""
+ npt = len(xs)
+ if npt < 2:
+ return None
+ mx = sum(xs) / npt
+ my = sum(ys) / npt
+ sxx = sum((x - mx) ** 2 for x in xs)
+ sxy = sum((x - mx) * (y - my) for x, y in zip(xs, ys))
+ if sxx == 0:
+ return None
+ b = sxy / sxx
+ a = my - b * mx
+ syy = sum((y - my) ** 2 for y in ys)
+ ss_res = sum((y - (a + b * x)) ** 2 for x, y in zip(xs, ys))
+ r2 = 1.0 - ss_res / syy if syy > 0 else 1.0
+ return a, b, r2
+
+
+def fmt(v, spec="%.1f", na="NA"):
+ return (spec % v) if v is not None else na
+
+
+def verdict(p, r2):
+ if p is None:
+ return "NA"
+ tag = "LINEAR" if p < 1.15 else ("NEAR-LINEAR" if p < 1.40 else "SUPERLINEAR")
+ if r2 is not None and r2 < 0.9:
+ tag += " (noisy)"
+ return tag
+
+
+def fit_axis(points, overhead):
+ """points: list of (n, ms). Returns dict with exponent/r2/used info."""
+ pts = sorted((n, t) for n, t in points if t is not None and t > 0)
+ # Net time after subtracting fixed overhead.
+ net = [(n, t - overhead) for n, t in pts]
+ # Prefer points where the signal clears the overhead noise floor.
+ strong = [(n, d) for n, d in net if d > max(2 * overhead, 1e-6)]
+ used = strong if len(strong) >= 3 else [(n, d) for n, d in net if d > 0]
+ low_conf = len(strong) < 3
+ if len(used) < 2:
+ return {"p": None, "r2": None, "used": used, "low_conf": True,
+ "double": None, "pts": pts, "net": net}
+ fit = linfit([math.log(n) for n, _ in used], [math.log(d) for _, d in used])
+ p = fit[1] if fit else None
+ r2 = fit[2] if fit else None
+ # Doubling ratio sanity check: t(2n)/t(n) ~ 2 linear, ~4 quadratic.
+ dbl = None
+ for (n1, d1), (n2, d2) in zip(used, used[1:]):
+ if d1 > 0 and 1.7 <= n2 / n1 <= 2.3:
+ r = (d2 / d1) / (n2 / n1) # normalize to a pure 2x step
+ dbl = r if dbl is None else max(dbl, r)
+ return {"p": p, "r2": r2, "used": used, "low_conf": low_conf,
+ "double": dbl, "pts": pts, "net": net}
+
+
+# ---------------------------------------------------------------------------
+# scaling.md
+# ---------------------------------------------------------------------------
+def write_scaling(out_dir, rows):
+ overhead = {"compile": 0.0, "preprocess": 0.0, "link": 0.0}
+ for r in rows:
+ if r["axis"] == "__overhead__" and r["status"] == "OK":
+ overhead[r["mode"]] = fnum(r["time_ms"]) or 0.0
+
+ # axis -> tool -> mode/phase/unit + list of (n, ms)
+ axes = OrderedDict()
+ for r in rows:
+ if r["axis"] == "__overhead__":
+ continue
+ a = r["axis"]
+ ax = axes.setdefault(a, {"phase": r["phase"], "mode": r["mode"],
+ "unit": r["unit"], "kit": [], "clang": []})
+ ms = fnum(r["time_ms"]) if r["status"] == "OK" else None
+ if r["tool"] == "kit":
+ ax["kit"].append((int(r["n"]), ms))
+ elif r["tool"] == "clang":
+ ax["clang"].append((int(r["n"]), ms))
+
+ L = []
+ L.append("# kit -O0 compile + link scaling")
+ L.append("")
+ L.append("Goal: **linear scaling** on every axis (exponent ~1.0). "
+ "`SUPERLINEAR` (exponent >= 1.4) marks an O(n^2)-ish hotspot to fix.")
+ L.append("")
+ L.append(f"Fixed per-invocation overhead (subtracted before fitting): "
+ f"compile **{overhead['compile']:.2f} ms**, preprocess "
+ f"**{overhead['preprocess']:.2f} ms**, link "
+ f"**{overhead['link']:.2f} ms**.")
+ L.append("")
+ L.append("## Linearity summary")
+ L.append("")
+ L.append("| axis | phase | unit | pts | exponent | R² | 2x-ratio | verdict "
+ "| kit @maxN | clang @maxN | kit/clang |")
+ L.append("| --- | --- | --- | ---: | ---: | ---: | ---: | --- | ---: | ---: | ---: |")
+
+ details = []
+ for a, ax in axes.items():
+ ov = overhead.get(ax["mode"], 0.0)
+ fit = fit_axis(ax["kit"], ov)
+ kit_by_n = {n: t for n, t in ax["kit"]}
+ clang_by_n = {n: t for n, t in ax["clang"]}
+ maxn = max(kit_by_n) if kit_by_n else None
+ kit_max = kit_by_n.get(maxn)
+ clang_max = clang_by_n.get(maxn)
+ ratio = (kit_max / clang_max) if (kit_max and clang_max) else None
+ p_s = fmt(fit["p"], "%.2f")
+ r2_s = fmt(fit["r2"], "%.3f")
+ d_s = fmt(fit["double"], "%.2f")
+ v = verdict(fit["p"], fit["r2"]) + (" *low-n*" if fit["low_conf"] else "")
+ L.append(f"| {a} | {ax['phase']} | {ax['unit']} | {len(fit['used'])} | "
+ f"{p_s} | {r2_s} | {d_s} | {v} | "
+ f"{fmt(kit_max)} | {fmt(clang_max)} | {fmt(ratio, '%.2fx')} |")
+
+ # Per-axis detail block
+ d = [f"### {a} ({ax['phase']}, per {ax['unit'][:-1] if ax['unit'].endswith('s') else ax['unit']})", "",
+ f"overhead {ov:.2f} ms subtracted. exponent **{p_s}** ({verdict(fit['p'], fit['r2'])}).", "",
+ f"| n | kit ms | kit net ms | kit ns/{ax['unit'][:-1] if ax['unit'].endswith('s') else ax['unit']} | clang ms | kit/clang |",
+ "| ---: | ---: | ---: | ---: | ---: | ---: |"]
+ net_by_n = {n: v for n, v in fit["net"]}
+ for n in sorted(kit_by_n):
+ kt = kit_by_n[n]
+ ct = clang_by_n.get(n)
+ net = net_by_n.get(n)
+ per = (net * 1e6 / n) if (net and net > 0 and n) else None
+ rr = (kt / ct) if (kt and ct) else None
+ d.append(f"| {n} | {('%.2f' % kt) if kt else 'FAIL'} | "
+ f"{('%.2f' % net) if net is not None else 'NA'} | "
+ f"{('%.1f' % per) if per else 'NA'} | "
+ f"{('%.2f' % ct) if ct else 'NA'} | "
+ f"{('%.2fx' % rr) if rr else 'NA'} |")
+ d.append("")
+ details.append("\n".join(d))
+
+ L.append("")
+ L.append("kit/clang > 1 means kit is **slower** than the clang -O0 reference "
+ "at the largest size (lower is better; <1 means kit is faster).")
+ L.append("")
+ L.append("## Per-axis detail")
+ L.append("")
+ L.extend(details)
+ L.append(f"Raw data: `{os.path.relpath(os.path.join(out_dir, 'scaling.csv'))}` "
+ f"· hotspots: `{os.path.relpath(os.path.join(out_dir, 'hotspots.md'))}`")
+
+ path = os.path.join(out_dir, "scaling.md")
+ with open(path, "w") as f:
+ f.write("\n".join(L) + "\n")
+ return path, axes
+
+
+# ---------------------------------------------------------------------------
+# sample call-tree -> self-time per function
+# ---------------------------------------------------------------------------
+FRAME_RE = re.compile(r"^(?P<indent>[ |+!:]*)(?P<count>\d+)\s+(?P<rest>.*\S)\s*$")
+
+
+def parse_sample(text):
+ """Return (self_by_func dict, total_samples) from a `sample` report, or
+ (None, 0) if the file isn't a parseable call graph.
+
+ Each call-graph line is `<indent><count> <symbol> (in <image>) ...`. A
+ node's count is the samples that passed through it; its direct children sum
+ to <= that, and the difference is the samples whose stack *ended* there —
+ i.e. self time. We reconstruct the tree via an indent stack and accumulate
+ self time per (symbol, image)."""
+ lines = text.splitlines()
+ start = None
+ for i, ln in enumerate(lines):
+ if ln.strip() == "Call graph:":
+ start = i + 1
+ break
+ if start is None:
+ return None, 0
+
+ indents = [] # per node: indentation width
+ counts = [] # per node: total sample count
+ child_sum = [] # per node: summed direct-children counts
+ names = [] # per node: (symbol, image)
+ stack = [] # node indices, increasing indent
+ started = False
+ for ln in lines[start:]:
+ if not ln.strip():
+ if started:
+ break
+ continue
+ m = FRAME_RE.match(ln)
+ if not m:
+ if started:
+ break
+ continue
+ started = True
+ indent = len(m.group("indent"))
+ cnt = int(m.group("count"))
+ rest = m.group("rest")
+ if " (in " in rest:
+ sym = rest.split(" (in ", 1)[0].strip()
+ img = rest.split(" (in ", 1)[1].split(")", 1)[0].strip()
+ else: # thread/root header or unresolved frame
+ sym = rest.split(" ")[0].strip()
+ img = ""
+ idx = len(counts)
+ indents.append(indent)
+ counts.append(cnt)
+ child_sum.append(0)
+ names.append((sym, img))
+ while stack and indent <= indents[stack[-1]]:
+ stack.pop()
+ if stack:
+ child_sum[stack[-1]] += cnt
+ stack.append(idx)
+
+ self_by = defaultdict(float)
+ total = 0.0
+ for i in range(len(counts)):
+ self_t = max(0, counts[i] - child_sum[i])
+ sym, img = names[i]
+ if not sym:
+ continue
+ self_by[(sym, img)] += self_t
+ total += self_t
+ return self_by, total
+
+
+def parse_dtrace(text):
+ """Flat `ufunc count` histogram from a dtrace profile run."""
+ self_by = defaultdict(float)
+ total = 0.0
+ for ln in text.splitlines():
+ s = ln.strip()
+ if not s:
+ continue
+ parts = s.split()
+ if len(parts) < 2 or not parts[-1].isdigit():
+ continue
+ cnt = float(parts[-1])
+ sym = " ".join(parts[:-1])
+ img = ""
+ if "`" in sym:
+ img, sym = sym.split("`", 1)
+ self_by[(sym, img)] += cnt
+ total += cnt
+ return self_by, total
+
+
+def write_hotspots(out_dir, axes):
+ raw_dir = os.path.join(out_dir, "raw")
+ L = ["# kit -O0 compile + link hotspots", "",
+ "Flat **self-time** per function (samples whose stack *ends* in that "
+ "function), from `sample` on the largest input of each axis. Use these "
+ "to see where time goes when an axis is stressed — especially axes the "
+ "linearity summary flagged SUPERLINEAR.", ""]
+ if not os.path.isdir(raw_dir):
+ L.append("_No sample data._")
+ with open(os.path.join(out_dir, "hotspots.md"), "w") as f:
+ f.write("\n".join(L) + "\n")
+ return
+ for a in axes:
+ raw = os.path.join(raw_dir, f"{a}.sample.txt")
+ if not os.path.exists(raw):
+ continue
+ text = open(raw, errors="replace").read()
+ if text.startswith("skipped:"):
+ L.append(f"## {a}")
+ L.append("")
+ L.append("_" + text.strip() + "_")
+ L.append("")
+ continue
+ if text.lstrip().startswith("Analysis of sampling"):
+ self_by, total = parse_sample(text)
+ else:
+ self_by, total = parse_dtrace(text)
+ L.append(f"## {a}")
+ L.append("")
+ if not self_by or total <= 0:
+ L.append("_No parseable samples._")
+ L.append("")
+ continue
+ L.append(f"{int(total)} samples.")
+ L.append("")
+ L.append("| self % | samples | function | image |")
+ L.append("| ---: | ---: | --- | --- |")
+ top = sorted(self_by.items(), key=lambda kv: kv[1], reverse=True)[:30]
+ for (sym, img), s in top:
+ if s <= 0:
+ continue
+ L.append(f"| {100.0 * s / total:.1f}% | {int(s)} | `{sym}` | {img} |")
+ L.append("")
+ with open(os.path.join(out_dir, "hotspots.md"), "w") as f:
+ f.write("\n".join(L) + "\n")
+
+
+def main():
+ out_dir = sys.argv[1] if len(sys.argv) > 1 else os.path.join(
+ os.path.dirname(os.path.dirname(os.path.abspath(__file__))),
+ "build", "bench", "cc")
+ csv_path = os.path.join(out_dir, "scaling.csv")
+ if not os.path.exists(csv_path):
+ sys.exit(f"cc_bench_report: no CSV at {csv_path}")
+ rows = load(csv_path)
+ scaling_path, axes = write_scaling(out_dir, rows)
+ write_hotspots(out_dir, axes)
+ print(f"cc_bench_report: wrote {scaling_path}")
+ print(f"cc_bench_report: wrote {os.path.join(out_dir, 'hotspots.md')}")
+
+
+if __name__ == "__main__":
+ main()
