commit b6c5177e9033c2f2240fe03f2093cb500b033444
parent dc4a6b86a9e69010438db1b6d5131b3432879320
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 11:11:42 -0700
doc(perf): refocus PERF.md on the tcc bar + sqlite reproduction recipe
Lead with tcc as the explicit target and the real-world sqlite benchmark with a
copy-pasteable measurement recipe (instr/cycles via /usr/bin/time -l, phase
decomposition, sample-based hotspot profiling, tcc build). Record the
frontend-bound finding (codegen is ~10%/~1% on real code, not the dominant
bucket the synthetic axes suggested) and Lever 1 (de-quadratic type caches).
Remove the copy-and-patch references.
Diffstat:
| M | doc/plan/PERF.md | | | 538 | +++++++++++++++++++++++++++++++++++++++++-------------------------------------- |
1 file changed, 281 insertions(+), 257 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -1,274 +1,298 @@
# 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".
+is irrelevant; only correctness and **compile+link throughput** matter. The bar
+is **tcc** — the fastest mainstream C compiler. The structural bet is already in
+place (a single-pass, no-AST C frontend, single-pass code emission with
+patch-ups, a format-neutral linker), so the work is measurement-driven: profile a
+real workload, find where the time goes, and remove it.
+
+Two rules hold everywhere below:
+
+- **A superlinear axis is a bug.** It means some inner step is O(n²)-ish — a
+ linear scan run once per item, a table that rebuilds, a list re-walked. The
+ type-cache work in "Current state" was exactly this class.
+- **Gate on byte-identical output.** A perf change must produce a bit-for-bit
+ identical object (and `-E` / `-g` / diagnostics) vs a snapshot of the
+ pre-change binary, unless it deliberately changes output (then the gate is
+ run-correctness + determinism). ASan can't see a premature arena reuse or an
+ uninit read; the output diff can.
+
+## The bar: tcc on sqlite
+
+The real workload is the **sqlite amalgamation** — one ~9 MB / 263 K-line C file
+(`tmp/projects/sqlite-amalg/sqlite3.c`, v3.50.2). It is the right benchmark
+because it is real, huge, declaration/macro/type-heavy (not a synthetic shape),
+and doubles as a correctness test (compile + link the shell, run a query).
+
+### Current standings (compile to object, `-c`, default `-O0`, best-of-N)
+
+Apple-silicon arm64 / macOS. `instructions`/`cycles` from `/usr/bin/time -l`
+(see below); both are **load-independent**, so they are the metrics to trust —
+wall time is only meaningful on a quiet machine.
+
+| compiler | wall | instructions | cycles | object |
+|---|--:|--:|--:|--:|
+| **tcc 0.9.28** | 0.06 s | 0.67 B | 0.22 B | 2.11 MB |
+| **kit (current)** | 0.28 s | 3.36 B | 0.89 B | 5.12 MB |
+| kit (pre-Lever-1) | 0.47 s | 5.25 B | 1.96 B | 5.12 MB |
+| clang 22 | 0.81 s | 8.63 B | 2.57 B | 1.50 MB |
+
+kit beats clang on compile speed and is the fastest *general* backend here, but
+**tcc is the bar**: ~4.7× wall / ~4.0× cycles / ~5.0× instructions ahead. Closing
+that is the whole game. (kit's object is larger because `-O0` codegen is
+deliberately unoptimized — irrelevant to this goal.)
+
+### Reproducing the detailed measurements
+
+All commands assume `SDK=$(xcrun --sdk macosx --show-sdk-path)` and a release
+kit at `build/release/kit` (`make bin RELEASE=1`).
+
+**1. Build tcc** (the bar) from the mob mirror, as an optimized binary:
+
+```sh
+git clone --depth 1 https://github.com/tinycc/tinycc tmp/tinycc
+cd tmp/tinycc
+export SDKROOT=$(xcrun --sdk macosx --show-sdk-path) # REQUIRED: Homebrew
+ # clang guesses a non-existent SDK; without this, "stdio.h not found"
+sed -i 's|^CFLAGS=.*|CFLAGS=-Wall -O3 -DNDEBUG -Wdeclaration-after-statement|' config.mak
+./configure ; make clean ; make CC=cc # CC=cc = Apple clang (xcrun-aware)
+# binary at tmp/tinycc/tcc ; compile with: tcc -c sqlite3.c -o x.o
+```
+
+**2. Instructions / cycles / wall** — `/usr/bin/time -l` is the macOS analog of
+`perf stat`; it reports `instructions retired` and `cycles elapsed`. Best-of-N
+filters scheduling noise. Helper:
+
+```sh
+m(){ local bi=9e18 bc=9e18 br=9e18; for i in $(seq 1 7); do
+ /usr/bin/time -l "$@" >/dev/null 2>/tmp/m.txt
+ local I=$(awk '/instructions retired/{print $1}' /tmp/m.txt)
+ local C=$(awk '/cycles elapsed/{print $1}' /tmp/m.txt)
+ local R=$(awk '/real/{print $1}' /tmp/m.txt)
+ awk "BEGIN{exit !($I<$bi)}"&&bi=$I; awk "BEGIN{exit !($C<$bc)}"&&bc=$C
+ awk "BEGIN{exit !($R<$br)}"&&br=$R; done
+ echo "instr=$bi cycles=$bc real=${br}s"; }
+cd tmp/projects/sqlite-amalg
+m build/release/kit cc -c sqlite3.c -o /tmp/k.o --sysroot "$SDK"
+m tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o
+```
+
+Caveat: Apple clang spawns a separate `cc1` that `/usr/bin/time` does **not**
+count — measure it with `cc -fintegrated-cc1 -c …`. Homebrew clang and kit are
+single-process, so their counters are exact. Check `sysctl -n vm.loadavg` before
+trusting wall time; instructions/cycles are fine under load.
+
+**3. Phase decomposition** — where the frontend vs codegen time goes, by
+subtraction (instruction counts are cleanest):
+
+```sh
+m build/release/kit cc -E -o /dev/null sqlite3.c --sysroot "$SDK" # pp + lex
+m build/release/kit cc -fsyntax-only sqlite3.c --sysroot "$SDK" # + parse/sema/types
+m build/release/kit cc -c -o /tmp/k.o sqlite3.c --sysroot "$SDK" # + codegen + emit
+```
+
+`-fsyntax-only` still drives the full CG value-stack and type lowering (routed to
+the no-op check backend), so `(-c) − (-fsyntax-only)` isolates **native emit +
+object write** only. On the pre-Lever-1 binary that delta was ~0.54 B / ~10 % —
+i.e. **codegen+emit is a small slice; the frontend is ~90 %.**
+
+**4. Hotspot profile** (self-time per function). The single run is too fast for
+`sample`, so merge the `Sort by top of stack` sections across many runs:
+
+```sh
+make RELEASE=1 PROFILE=1 CC=clang BUILD_DIR=build/bench bin # profileable kit
+cd tmp/projects/sqlite-amalg ; KIT=build/bench/kit ; rm -f /tmp/p_*.txt
+for i in $(seq 1 24); do
+ $KIT cc -c sqlite3.c -o /tmp/kk.o --sysroot "$SDK" 2>/dev/null & pid=$!
+ sample $pid 5 1 -file /tmp/p_$i.txt -mayDie >/dev/null 2>&1 ; wait $pid; done
+for f in /tmp/p_*.txt; do awk '/Sort by top of stack/{f=1;next}/Binary Images/{f=0}f' "$f"; done \
+ | sed -E 's/\(in [^)]*\)//' | grep -oE '[A-Za-z_][A-Za-z0-9_]*[[:space:]]+[0-9]+' \
+ | awk '{c[$1]+=$2} END{for(k in c) print c[k],k}' | sort -rn | head -25
+```
+
+`PROFILE=1` keeps `-g` + frame pointers and skips the strip, so codegen matches
+the shipped release and arm64 stacks are reliable.
+
+**5. End-to-end correctness** (sqlite as a correctness test):
+
+```sh
+build/release/kit cc sqlite3.c shell.c -o /tmp/sq --sysroot "$SDK" -lc
+/tmp/sq :memory: "create table t(a,b); insert into t values(2,40),(10,32);
+ select sum(a)+sum(b), count(*) from t;" # -> 84|2
+```
+
+## Current state (2026-06-12)
+
+**The headline finding: real-world compilation is frontend-bound, not
+codegen-bound.** The phase split above puts native codegen+emit at ~10 % of a
+real `-c` and ~1 % of self-time. The frontend — preprocessor, lexer, interner,
+parser, semantic analysis, and the CG value-stack/type-lowering it drives — is
+~90 %. (The synthetic `bench-cc` axes below over-weight codegen by construction;
+trust the sqlite profile for where to spend effort.)
+
+**Lever 1 — de-quadratic type-lowering caches (done; commit `dc4a6b86`).** The
+derived-type dedup paths each linearly scanned a growing table on *every* type
+use, making type-heavy compilation O(n²). On sqlite this was ~70 % of frontend
+self-time, dominated by `find_ptr_type_id` (the function `kit_cg_type_ptr`, 47 %
+of all self-time). Fixed, all O(n)→O(1), all byte-identical:
+
+- `find_ptr_type_id` / `find_array_type_id`: linear scan of all CG types → packed
+ u64-keyed hashmaps (`CgPtrMap`/`CgArrayMap` on `CgApiState`).
+- `find_func_type_id`: linear scan → structural hashset of `CgApiType*`
+ (`CgFuncSet`); each entry carries its `self_id` so the set returns the id.
+ SEGVEC entries have stable addresses, so storing pointers is sound.
+- `abi_cg_func_info` / `abi_cg_record_layout`: linearly-scanned linked-list
+ caches → type-id-keyed hashmaps (`AbiFnInfoMap`/`AbiRecLayoutMap`); cached
+ values stay arena-backed.
+
+Result: **1.68× wall / 2.20× cycles / 1.56× instructions** whole-compile,
+byte-identical. The cycle win exceeds the instruction win because the scans were
+cache-miss-heavy pointer chases. Gap to tcc: ~7.8× → ~4.7× wall.
+
+### Where the time goes now (self-time, real sqlite `-c`, post Lever 1)
+
+24-run merged `sample`. After Lever 1 the profile is flat — no single dominant
+hotspot, and the type system has dropped out entirely.
+
+| function | self | stage |
+|---|--:|---|
+| `lex_next` | 487 | lexer (the scanner) |
+| `hs_add` | 384 | **preprocessor hideset** (macro-recursion tracking) |
+| `pool_intern_slice` | 158 | identifier interning |
+| `pp_next_raw_into` | 118 | preprocessor token pump |
+| `_platform_memset` | 108 | zeroing |
+| `type_unqual` | 100 | frontend type query |
+| `src_next_raw_into` | 38 | preprocessor source |
+| `nd_dst_reg`/`m_emit_bytes`/`aa_emit_mem` | ~20 | native codegen+emit (**~1 %**) |
+| `scope_lookup` | 10 | symbol lookup (already cheap — lazy scope index) |
+
+The next frontier is the **lexer + preprocessor + interner** pipeline (≈40 % of
+self-time combined). sqlite is macro-heavy, so the hideset (`hs_add`) and the
+token pump are large; the lexer interns *every* token spelling including
+punctuators, which tcc avoids (operators are bare token codes there).
+
+### Remaining levers (ranked)
+
+1. **Lever 2 — lexer / preprocessor diet.** Stop interning punctuator spellings;
+ trim the per-token 24-byte `Tok` copies across the lex→pp→parse layers; lighten
+ the macro-expansion hideset (`hs_add`/`hs_contains`) which sqlite leans on
+ heavily. This is the current ~40 % bucket.
+2. **Frontend type construction** (`hs_add`'s sibling cost, `type_unqual`,
+ `TypeInternSet`). Lever 1 killed the *CG-layer* re-lowering; the *frontend*
+ `Type` hash-cons still runs per construction. Caching the lowered
+ `KitCgTypeId` on the canonical `Type` would remove the remaining per-use
+ re-walk (watch record-completeness: incomplete records must not be memoized).
+3. **Sym-centric bindings** (tcc's core trick). tcc resolves identifier→decl,
+ macro, keyword, and typedef-ness with O(1) pointer loads off the interned
+ token; kit still pays a keyword-map probe per identifier and a scope probe per
+ level. `scope_lookup` is already cheap (lazy index), so this is lower-priority
+ now, but it removes the residual per-identifier probes.
+
+## The synthetic scaling benchmark (`make bench-cc`)
+
+A complement to the sqlite profile: it isolates *one input dimension at a time*
+and proves each scales **linearly**. Use it to catch a re-introduced O(n²); use
+the sqlite profile to decide where to optimize (the synthetic axes over-weight
+codegen relative to real code).
+
+`make bench-cc` builds a `PROFILE=1` kit and runs `scripts/cc_bench.sh`, which:
+
+1. **Sweeps each axis** over a geometric size series, timing `kit cc -O0 -c` /
+ `-E` and `kit ld` best-of-N (link axes pre-build objects untimed).
+2. **Fits a scaling exponent** (`cc_bench_report.py`): least-squares
+ `log t = log a + p·log n` on overhead-subtracted times; `p ≈ 1.0` is the goal,
+ `p ≥ 1.4` is flagged `SUPERLINEAR` (treat as a bug).
+3. **Samples hotspots** on the largest input of each axis.
+4. Records a **clang `-O0` reference** for each axis.
### 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_gen.py` | Axis catalog + synthetic source/object generator (`--list` prints axes). **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_hot.sh` | Hotspot sampler: drives one axis at a time at a size tuned for a ~1.5–3 s run (the normal sweep is now too fast to sample), so `sample` captures a real call graph. Writes `build/bench/hot/<axis>/`. |
+| `scripts/cc_bench_hot.sh` | Hotspot sampler: drives one axis at a size tuned for a ~1.5–3 s run so `sample` captures a real call graph. |
| `scripts/cc_bench_report.py` | Exponent fit + verdicts + clang ratios → `scaling.md`; parses `sample` call-trees → `hotspots.md`. |
-| `scripts/cc_bench_stages.py` | Buckets each function's self-time (from `build/bench/hot/<axis>/raw/`) into a pipeline **stage** (lexer / pp / intern / parser / types-abi / codegen / emit / arena / libc) so the breakdown is per-stage, not per-function. |
+| `scripts/cc_bench_stages.py` | Buckets each function's self-time into a pipeline **stage** (lexer/pp/intern/parser/types-abi/codegen/emit/arena/libc). |
| `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`.
-
-## Current state
-
-Every axis scales **linearly** and kit is faster than clang `-O0` on all of them.
-kit/clang at the largest measured size (lower = faster):
-
-| axis | kit/clang | axis | kit/clang |
-|---|--:|---|--:|
-| locals-per-fn | 0.01× | type-decl | 0.45× |
-| ref-density | 0.06× | pp-macro `-E` | 0.32× |
-| fn-count | 0.09× | global-decl | 0.32× |
-| obj-count (link) | 0.25× | pp-include `-E` | 0.88× |
-| body-size | 0.25× | symbol-count (link) | 0.76× |
-
-**Round 6 (constant-factor sprint, gate: `scripts/perf_identity_gate.sh`).** A
-byte-identical pass across all nine segments cut **+10–13%** off the major
-compile axes (paired best-of-15 vs the pre-sprint binary: type-decl +13.3%,
-pp-macro `-E` +10.8%, fn-count +10.1%, body-size +9.6%, ref-density +7%,
-global-decl +4.8%), plus a non-byte-identical linker win of **−27%** on large
-links. What landed, by segment: **intern** — inline `sym_eq`/miss-copy to drop
-the freestanding `memcmp`/`memcpy` libcalls; **codegen** — a 1-byte `wide_kind`
-tag cached on the value-stack node collapses the per-binop type-query gauntlet to
-a load+compare, plus a flat `reg_last_use` regcache mirror; **parser** — fused
-redefinition+define into one hash probe + O(1) keyword classification; **lexer**
-— dropped the per-token `memset` + a splice-free fast-path scan; **pp** —
-out-pointer token readers killing the 24B sret round-trip; **emit** — inlined
-`buf_write` fast path + cached section `Buf*`; **abi** — right-sized the
-`NativeCallPlanRet` scratch; **link** — HW-SHA image-id (the one non-byte-id
-change: only the UUID/build-id bytes move). New tooling:
-`scripts/perf_identity_gate.sh` (60-category byte-identical gate) and
-`scripts/perf_axis_time.py` (focused A/B axis timer).
-
-**Round 7 (value-stack frontend, byte-identical).** Three structural wins on the
-value-stack layer that sits *above* the `CgTarget` seam, all gated on the same
-60-category identity gate: **(b) per-type classification memo** — R6 cached the
-`wide_kind` result on each node but `api_push` still re-derived it (a string of
-`cg_type_get` + alias-chase + ABI round trips) on every operand; the wide/soft
-class and the aggregate-place bit are now computed once per type id (builtins
-precomputed at `cg_api` init, user types filled lazily in the `CgApiType` slack)
-and `api_push` reads both from one packed byte. **(c) designated-init value nodes**
-— the `api_op_*` / `api_make_*` constructors drop their `memset` for a compound
-literal, so the compiler stores only live fields. **(d) off-node delayed payload**
-— the 64-byte delayed cmp/arith union moves off `ApiSValue` behind a pointer
-(node **112 → 56 bytes**); payloads live in a per-function arena pool on `KitCg`
-(reset at `func_begin`, freelist-recycled within a function), and fold's
-`*out = *a` chain-fold becomes a pointer *move* (`out` takes `a`'s payload,
-`a->delayed = NULL`) so no shared payload is double-freed.
-
-Measured **on a RELEASE build** (paired best-of-9 vs the pre-Round-7 binary;
-`perf_axis_time.py`): body-size **+9.5%**, locals-per-fn **+6.9%**, fn-count
-**+2.8%**, ref-density **+2.5%**. The win is essentially all (b) — the compute
-saved by killing the per-operand type gauntlet. (c) reclaims only the memset
-*call* (the delayed zeroing survives `-ftrivial-auto-var-init=zero`), and (d) is
-**perf-neutral** (the per-delayed-node alloc/free cancels the smaller-node
-savings; the value stack is small and L1-hot regardless) — it is kept for the
-structural cleanup (the cold payload no longer rides every hot node), not speed.
-
-> Methodology note: measure perf on a **RELEASE** build (`make … RELEASE=1
-> BUILD_DIR=build/release`), never the default `make bin` (which is
-> `RELEASE=0` → ASan/UBSan-instrumented). ASan amplifies *memory*-op savings and
-> dilutes *compute* savings, which inverts the apparent ranking: under ASan (d)
-> looked like a big win and (b) small; on RELEASE it is the reverse. The
-> byte-identity gate is build-mode-independent, but the timer is not.
-
-The structural bet is fully in place: a single-pass no-AST C frontend, single-pass
-code emission with patch-ups, and a format-neutral linker. The scaling bugs are
-gone (no axis is superlinear) and the big constant factors with them — per-unit
-allocation churn, per-token IO syscalls, the per-byte line-splice tax, full-struct
-descriptor zeroing, and the O(n)/O(n²) symbol/scope/type/section table scans are
-all eliminated. Every per-pool table (parser scope/tag/extern indexes, the type
-intern + ABI/record memos) runs on one shared open-addressed hashmap facility
-(`KIT_HASHMAP_DEFINE` / `KIT_HASHSET_DEFINE`) over an arena-heap facade
-(`Pool.arena_heap`), so there is no teardown. The linker beats ld64 across both
-link axes (its output hashing uses the ARMv8 SHA extension).
-
-### Where the time goes (self-time by stage, `scripts/cc_bench_stages.py`)
-
-Current self-time % by stage (post Round-6; `build/bench/kit`, well-sampled axes):
-
-| stage | body-size | locals | fn-count | pp-macro `-E` | top frames |
-|---|--:|--:|--:|--:|---|
-| **codegen** | **38** | **35** | 19 | – | `nd_dst_reg` (regcache), `cg_type_get`/`api_unalias_type`, `nd_binop` |
-| **parser** | 9 | 12 | 14 | – | `declare_function`, `scope_define_checked`, `parse_decl_specs` |
-| **libc mem** (memset/memmove) | 9 | 12 | 12 | 9 | per-fn/node zeroing + payload copies |
-| **libc io** (`write`) | 8 | 8 | **12** | 2 | **writing the `.o` output** |
-| **lexer** (`lex_next`) | 8 | 5 | 6 | **12** | the scanner |
-| **pp** (`pp_next_raw_into`, `subst_phase2`) | 5 | 5 | 5 | **66** | the token pump (the 66% *is* `-E`'s work) |
-| **intern** (`pool_intern_slice`) | 3 | 6 | 9 | 8 | identifier interning |
-| **emit** (`obj_symbol_find`, `aa_emit_*`) | 6 | 5 | 12 | – | per-instruction emit |
-| **types/abi** | 7 | 5 | 3 | – | `c_abi_*`, `type_cg_*` |
-
-**Codegen is the dominant bucket** — the `-O0` regcache scan (`nd_dst_reg`) and the
-per-operand type queries (`cg_type_get`/`api_unalias_type`) are the top frames, and
-only copy-and-patch (above) would structurally lower them. Newly notable:
-**`write()` of the object file is 8–12%** — as the compute shrank ~10–15%, the
-output-write became a real fraction. It is *not* an easy lever: the writer is
-already buffered and flattens each section into **one big `write()`** (minimal
-syscalls); streaming the section's `Buf` chunks instead measured **−2.4 %**
-(N×64 KB syscalls beat one big write only in theory). The visible `write%` is
-mostly irreducible kernel I/O; the only further lever is `writev` (one
-scatter-gather syscall, no flatten copy) — marginal (~0.2–0.5 %) and needs a new
-writer vtable method. **`pp-include` is ~95 % `open`+`read` syscalls** (header-cache
-territory, helps real re-include graphs not the single-include axis).
-
-### Where link time goes (flat self-time, forced 1M-symbol link ≈ 1 s)
-
-The linker won't sample at normal bench sizes (sub-ms/unit; beats ld64). At 1M
-symbols, no single hotspot: **content hash `sha256_update` ~20 %** (the HW-SHA
-build-id/UUID over all output bytes — irreducible: a deterministic build-id must
-hash the whole image), **symbol table + resolve ~20 %** (`obj_symbol_make`,
-`link_resolve_symbols`, `link_assign_symbol_vaddrs`), **mem ~15 %**
-(`__bzero`/memset/memmove), **object ingest ~12 %** (`link_ingest_archives`,
-`read_macho`), **output emit ~6 %** (`link_emit_macho`, relocations), **intern +
-hashmap resize ~6 %**. The one cheap link lever left is pre-sizing the symbol
-hashmaps (`SymNameIndex_resize`/`SymHash_resize`, ~3 %).
-
-### Invariants (hold these)
-
-- **No axis may be superlinear.** A superlinear fit means some inner step is
- O(n²)-ish — a per-item linear scan, a rebuilding table, a re-walked list. The
- benchmark exists to surface those; treat a `SUPERLINEAR` verdict as a bug.
-- **Gate changes on byte-identical output** (object / `-E` / `-g` / diagnostics)
- vs a snapshot of the pre-change binary. ASan can't see a premature arena reuse
- or an uninit read, so the output diff — not the sanitizer — is the gate. The
- two latent-O(n²) fixes are the only changes that legitimately alter *timing*
- without altering output. For the lexer, the diff must include a line-splice
- battery (mid-token / mid-string / leading / trailing / consecutive
- continuations) plus a diagnostic whose line number falls across a splice.
+Compile (`kit cc -O0 -c`, or `-E` for the pp axes): `fn-count` · `body-size` ·
+`global-decl` · `type-decl` · `locals-per-fn` · `pp-macro` · `pp-include` ·
+`ref-density`. Link (`kit ld`, objects pre-built untimed): `obj-count` ·
+`symbol-count`.
+
+### Output + env knobs
+
+Output in `build/bench/cc/`: `scaling.md` (linearity summary + kit/clang ratios),
+`hotspots.md` (top self-time per axis), `scaling.csv`, `raw/<axis>.sample.txt`.
+
+Env: `KIT` · `CLANG` · `KIT_CC_BENCH_AXES` · `KIT_CC_BENCH_SIZES` ·
+`KIT_CC_BENCH_REPEATS` (3) · `KIT_CC_BENCH_MAX_MS` (4000) ·
+`KIT_CC_BENCH_SKIP_CLANG` · `KIT_CC_BENCH_SAMPLE` (1) · `KIT_CC_BENCH_DTRACE`
+(needs sudo) · `KIT_CC_BENCH_OUT`. Quick wire-check:
+`KIT_CC_BENCH_SIZES='8 16 32' KIT_CC_BENCH_SAMPLE=0 make bench-cc`.
+
+Every axis currently scales **linearly** and kit is faster than clang `-O0` on
+all of them; that guarantee is the floor this benchmark defends.
+
+## Methodology notes
+
+- **Measure on a RELEASE build** (`make bin RELEASE=1`, or `PROFILE=1` for
+ sampling), never the default `make bin` (`RELEASE=0` → ASan/UBSan). ASan
+ amplifies *memory*-op savings and dilutes *compute* savings, which can invert
+ the apparent ranking. The byte-identity gate is build-mode-independent; the
+ timer is not.
- **`memset` is explicit zero-init, not `-ftrivial-auto-var-init`.** Proven by
rebuilding with the auto-init flag off and re-sampling (self-time unchanged).
- So attack `memset` at the call sites (designated initializers, right-sized
+ Attack `memset` at call sites (designated initializers, right-sized
allocations) — the hardening flag stays.
-
-## Forward-looking — the remaining levers
-
-The Round-6 sprint took the constant-factor wins (the four levers previously
-listed here — the type-query gauntlet, the regcache scan, the per-function
-`memset`, and the token-pump sret tax — all landed). What remains is
-**structural**: byte-identity now caps the compile axes at constant-factor
-shaving, and **codegen is the dominant bucket** (27–42 % of every per-statement
-axis). The remaining levers were each prototyped/measured (the gate for these is
-run-correctness + determinism, not byte-identity, since they change output by
-design). Ranked by (impact × confidence) / risk:
-
-1. **Copy-and-patch codegen** (the structural ceiling-raiser — biggest potential,
- biggest effort). Precompiled per-IR-op machine-code stencils emitted by
- `memcpy` + hole-patching, replacing the value-stack / regcache / type-query /
- MC-emit path. A narrow aa64 spike (load/store/add/mov-imm/ret) measured
- **~24× faster per op** (~175 ns/op → ~7 ns/op), cross-validated: the spike's
- CG-region cost is 41 % of marginal whole-compile cost, matching the profiler's
- 42 % codegen self-time. But whole-compile is **Amdahl-capped at ~1.66×** on the
- most codegen-heavy axis (body-size) and less elsewhere — it cannot touch the
- ~59 % frontend. A full backend is a large multi-arch investment (a stencil-
- generation toolchain — harvest `.text`+relocs from compiled snippets — plus
- reloc/ABI handling and variable-length x86 encoding). Worth it only as a
- deliberate big bet on the dominant bucket. (Spike + numbers persisted under
- `build/perf-nonbid-analysis/codegen-copypatch-spike.md`.)
-2. **16-byte `Tok` (register return)** — *implemented, byte-identical, and
- rejected on measurement.* The lossless 32-bit `LocId` side-table makes `Tok`
- 16 B (exact diagnostics, passes the full byte-id gate) and achieves the
- `x0:x1` register-return ABI. But on a **quiet** machine (best-of-15; the
- earlier "neutral" was load-noise) it **splits**: pp-macro `-E` **+3.3 %** but
- type-decl **−7.1 %**, body-size **−3.4 %**, fn-count **−2.8 %**. Reason: the
- compile path is loc-heavy (a loc per statement + `.loc` on every AST node), so
- each token pays the `LocId` indirection on *both* ends — the lexer interns
- each loc (a 12 B store into the table) and the parser resolves it (a table
- lookup + a cross-TU `kit_loc_resolve`) — which costs more than the smaller-`Tok`
- copy saves; `-E` wins only because the pp passes tokens through without
- resolving. The planned "inline the loc append into the lexer" does **not** fix
- this: it removes only the intern *call overhead*, not the per-token store work
- or the parser-side resolve cost, which are the regression. And the clean inline
- is blocked anyway — it would require exposing libkit's loc-table layout to the
- `lang/cpp` frontend, a boundary violation. `Tok` is one type shared by `-c` and
- `-E`, so it is all-or-nothing, and `-c` dominates → net loss. **Dead end; do
- not revive.**
-3. **Keyword classify-once** — *partly landed.* The real residual the `KwMap`
- missed was `parse_decl_specs` re-deciding keyword-ness ~27×/token (26 `is_kw`
- + a trailing `ident_kw`); a single alias-aware `classify_kw()` at the loop top
- captured it byte-identically: **+7.4 % type-decl** (cumulative type-decl now
- +15.6 % vs pre-Round-6). The same CSE on the *statement* dispatch measured
- **neutral** — that chain was already 13 cheap direct compares with no alias
- keywords, so routing it through one `classify_kw` (a hashmap probe) just trades
- compares for a probe. The full invariant (one classification per token, cached
- on the parser at `advance`-time so every site reads a field) would dedup the
- remaining label-check + dispatch probes, but measured not worth the refactor at
- the cheap sites. The deeper keyword-id-on-`Sym` table is **not** needed — the
- classify-once CSE captured the win without it.
-
-**Deliberately not pursued** (measured dead ends, keep them dead):
-**fused lex→pp→parse** (a pull pipeline that never materializes a `Tok` array) —
-measured: the pure pull-wrapper layers are only ~5 % of frontend self-time and
-`pp_next_raw`'s cost is mostly macro/directive decision logic a pull pipeline
-still runs, so the payoff doesn't justify the rewrite. **`nd_grow_*` non-zeroing**
-has an uninit-read risk no available sanitizer catches. A **word-at-a-time intern
-hash**, a **lower hash load factor**, and an **inline-prefix entry cache** all
-measured *slower* or negligible for the short identifiers real code uses.
-(Done since this list last named it: **image-id FNV→HW-SHA** — landed, −27 % on
-large links; it was fenced off only for changing UUID/build-id bytes.)
+- **Byte-identity gate tooling.** `scripts/perf_identity_gate.sh` (60-category
+ byte-identical gate) and `scripts/perf_axis_time.py` (focused A/B axis timer).
+ For lexer changes the diff must include a line-splice battery (mid-token /
+ mid-string / leading / trailing / consecutive continuations) plus a diagnostic
+ whose line number falls across a splice.
+
+## History — constant-factor rounds (byte-identical)
+
+Context for what is already wrung out; all gated on `perf_identity_gate.sh`.
+
+**Round 5/6 (constant-factor sprint).** Byte-identical passes across all segments:
+**intern** inlined `sym_eq`/miss-copy (dropped freestanding `memcmp`/`memcpy`);
+**parser** fused redefinition+define into one probe + O(1) keyword classify;
+**lexer** dropped per-token `memset` + splice-free fast-path scan (the line-splice
+fold is a single up-front pass); **pp** out-pointer token readers killing the 24 B
+sret round-trip; **emit** inlined `buf_write` + cached section `Buf*`; **link**
+HW-SHA image-id (−27 % large links — the one non-byte-id change, only UUID bytes
+move). The per-pool tables (scope/tag/extern indexes, type intern + ABI/record
+memos) all run on one open-addressed hashmap facility
+(`KIT_HASHMAP_DEFINE`/`KIT_HASHSET_DEFINE`) over an arena-heap facade
+(`Pool.arena_heap`), so there is no teardown. The linker beats ld64 on both link
+axes.
+
+**Round 7 (value-stack).** Per-type classification memo (the win): the wide/soft
+class + aggregate-place bit are computed once per type id and read from one packed
+byte in `api_push`, instead of a `cg_type_get` + alias-chase + ABI round-trip per
+operand. Plus designated-init value nodes (drop a `memset`) and an off-node
+delayed cmp/arith payload (`ApiSValue` 112→56 B; kept for the structural cleanup,
+perf-neutral). Measured on RELEASE: body-size +9.5 %, locals-per-fn +6.9 %.
+
+## Dead ends (measured; keep them dead)
+
+- **16-byte `Tok` (register return).** Implemented, byte-identical, rejected on
+ measurement: the lossless 32-bit `LocId` side-table makes `Tok` 16 B and gets
+ the `x0:x1` return ABI, but the compile path is loc-heavy (a loc per statement),
+ so each token pays the `LocId` store (lexer) + resolve (parser) on both ends,
+ costing more than the smaller-copy saves. `-E` gains (+3.3 %) but `-c` regresses
+ (type-decl −7.1 %, body-size −3.4 %); `Tok` is shared and `-c` dominates → net
+ loss. Inlining the loc append doesn't fix the store/resolve cost and would
+ violate the `lang/cpp`↔libkit boundary. **Do not revive.**
+- **Fused lex→pp→parse pull pipeline.** The pure pull-wrapper layers are only
+ ~5 % of frontend self-time and `pp_next_raw`'s cost is mostly macro/directive
+ decision logic a pull pipeline still runs — payoff doesn't justify the rewrite.
+- **`nd_grow_*` non-zeroing** — uninit-read risk no available sanitizer catches.
+- **Word-at-a-time intern hash, lower hash load factor, inline-prefix entry
+ cache** — all measured slower or negligible for the short identifiers real code
+ uses.
