commit 2cd7230758eac2d58870f15f88b9a3b389961c6d
parent 15ebd192facfde7db02a13c2a01fbe86a9bfa913
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 18:50:27 -0700
doc(perf): structural map to close the tcc gap (PERF-TCC-GAP.md)
Measurement-grounded investigation of the 2.22B vs 0.66B (3.35x) instruction gap
to tcc on sqlite, with a four-strand code-path audit (kit token pipeline, kit
codegen, tcc baseline, kit memory density).
Headline findings (overturn the wall-clock "scanner is THE frontier" framing):
- kit IPC 3.70 > tcc IPC 3.48: the gap is INSTRUCTION COUNT, not cache stalls.
Density helps by cutting instructions (copies/indirections/recompute), not by
recovering memory stalls. RSS 70MB vs 14MB but no IPC penalty.
- Instruction-grounded phase split (by subtraction + preprocessed-.c isolation):
lex+pp ~0.97B (~2.8x tcc), parse+sema+types+CG-drive ~0.87B (~3.5x), native
emit+objwrite 0.37B (~7x). The gap is ~uniform ~3x across phases.
- Post-PP work alone (>= -c minus -E = 1.24B) is already ~1.87x tcc's ENTIRE
compile, and kit -E already beats tcc -E. So the lexer is NOT the sole
frontier; the post-PP pipeline must be attacked. The wall-clock 62% lex_next
is a single-peaked-leaf artifact.
Per-phase structural diagnosis (file:line grounded) + tcc's single-pass model
(token=int+globals, SValue[] vtop++, direct backend calls, bytes into the final
section, int[] macro replay), then a ranked roadmap:
- Track 1 (biggest): collapse the CgTarget->NativeTarget->MCEmitter vtable stack
at -O0, drop the NDT mini-RA, gate the fold ladder off, memoize size/align on
the type id, shrink ApiSValue 56->24B.
- Track 2: token relay density (defer/cache interning, Tok 24->16B via packed
SrcLoc, collapse the 4-frame pull).
- Track 3: interner slot self-sufficiency (hash+len+SSO inline).
- Track 4: end-state = adopt tcc's single-pass data-flow shape.
Updates PERF.md: adds a wall-vs-instruction warning callout under the self-time
table and re-ranks Next levers (codegen density #1), pointing to the new doc.
Diffstat:
2 files changed, 290 insertions(+), 15 deletions(-)
diff --git a/doc/plan/PERF-TCC-GAP.md b/doc/plan/PERF-TCC-GAP.md
@@ -0,0 +1,247 @@
+# Closing the tcc gap — a structural map
+
+Companion to `PERF.md`. That doc tracks the running standings and the
+constant-factor sprints; this one is the **structural diagnosis**: where the
+2.22 B vs 0.66 B (3.35×) instruction gap to tcc actually lives, *why* (grounded
+in code paths), and the redesign tracks that can close it. Written after a
+measured phase decomposition + a four-strand code-path audit (kit token
+pipeline, kit codegen, tcc baseline, kit memory density).
+
+## The headline finding: it is instructions, not cache
+
+Measured on the sqlite amalgamation (`sqlite3.c`, arm64 macOS, best-of-7,
+`/usr/bin/time -l`), low load:
+
+| compiler | instructions | cycles | **IPC** | peak RSS |
+|---|--:|--:|--:|--:|
+| kit `-c` | 2.216 B | 0.598 B | **3.70** | 70.6 MB |
+| tcc `-c` | 0.663 B | 0.190 B | **3.48** | 13.7 MB |
+
+**kit's IPC (3.70) is *higher* than tcc's (3.48).** Despite 5× the RSS and
+pointer-chasing data structures, kit is **not** cache/stall-bound relative to
+tcc — both are compute-bound on an 8-wide core. The gap is **purely instruction
+count**: kit executes 3.35× more instructions and retires them slightly *more*
+efficiently. The "denser, cache-friendlier design" intuition is the right
+*direction*, but the payoff mechanism is **fewer instructions** (fewer copies,
+fewer indirect calls, fewer redundant recomputations) — not recovering memory
+stalls. There is no large hidden cache-miss penalty to claw back; do not chase
+that ghost. Smaller/denser structures help because they cost fewer
+load/store/move *instructions*, and they keep IPC high.
+
+## The phase decomposition (instruction-grounded)
+
+The wall-clock `sample` profile in PERF.md is **single-peaked on `lex_next`
+(62 %)** — but that is a *wall-clock* artifact of one huge inlined leaf function
+on a single-peaked workload. The **instruction** truth (load-independent, the
+metric to trust) is very different and is derived by subtraction:
+
+- `emit+objwrite = (-c) − (-fsyntax-only)` = 2.216 − 1.846 = **0.372 B** (exact).
+- Compile the *already-preprocessed* source as a `.c` (re-preprocesses only
+ trivial `# line` markers, so PP work ≈ 0; kit produces the **same 3.7 MB
+ object**, `rc=0`): `-c`(exp) 1.589 B, `-fsyntax`(exp) 1.217 B, `-E`(exp)
+ 0.343 B. So `parse+sema+types+CG-drive = -fsyntax(exp) − -E(exp)` ≈ **0.874 B**
+ and `emit+objwrite(exp) = 1.589 − 1.217 = 0.372 B` (matches — same program).
+- `lex+pp` = remainder = 2.216 − 0.372 − 0.874 = **~0.97 B** (≈ kit `-E` raw
+ 0.974 B — independently consistent).
+
+| phase | kit `-c` instr | share | tcc (est. within 0.663 B) | ratio |
+|---|--:|--:|--:|--:|
+| **lex + pp** (scan, include, macro expand) | ~0.97 B | ~44 % | ~0.35 B | ~2.8× |
+| **parse + sema + types + CG value-stack drive** | ~0.87 B | ~39 % | ~0.25 B | ~3.5× |
+| **native emit + obj write** | 0.37 B | ~17 % | ~0.05 B | **~7×** |
+| **total** | **2.22 B** | 100 % | **0.66 B** | **3.35×** |
+
+(tcc's phases are fused; its per-phase figures are estimates from `tcc -E`
+1.152 B and its structure. The point is the *shape*, not the third digit.)
+
+**Two facts reframe the whole effort:**
+
+1. **The gap is roughly uniform (~3×) across all three phases** — there is no
+ single hot function to crush. Closing 3.35× is a *campaign across the
+ pipeline*, not one patch.
+2. **Post-PP work alone (≥ `-c` − `-E` = 1.24 B) is already ~1.87× tcc's entire
+ compile.** Even a *free* lexer+pp leaves kit at ≥1.87× tcc. **The lexer is
+ not the sole frontier** — the prior "scanner is THE lever" framing (true for
+ wall-clock self-time, and the recent raw-cursor rewrite was a real −84 M win)
+ does **not** close the tcc gap. The post-PP pipeline must be attacked too.
+
+## Why each phase is ~3× tcc (structural, file:line-grounded)
+
+### tcc's target model — one pass, no second representation
+
+tcc fuses lex+preprocess+parse+codegen into one recursive-descent pass with **no
+IR and no token objects** (`tmp/tinycc/tccpp.c`, `tccgen.c`, `arm64-gen.c`):
+
+- The current token is a **single global `int tok` + `CValue tokc`** (16 B
+ union). `next()` returns `void` and mutates globals — no struct returned or
+ copied per token. Identifiers are interned to small ints **while being
+ scanned** (`hash_ident`, one inline hash fold), and the `TokenSym` caches
+ `sym_define/_struct/_identifier/_label` pointers directly — so macro/symbol
+ resolution is a **pointer load off the interned token**, not a per-occurrence
+ hash lookup.
+- The value stack is a fixed `SValue _vstack[513]` (48 B entries); push is
+ `vtop++` + four field writes, pop is `vtop--`. `gen_op('+')` constant-folds /
+ strength-reduces *in place* and otherwise calls the backend `gen_opi`
+ **directly** (a `ST_FUNC`, no vtable). The backend's `o()` writes one 4-byte
+ instruction straight into `cur_text_section->data` — the final image.
+- Macro bodies are pre-tokenized `int[]` streams replayed by **pointer-swap**
+ (`begin_macro`/`end_macro` push/pop `macro_ptr`), no per-expansion copy.
+
+Net: each source byte is touched ~once, each token is an `int`, each operator is
+a `vtop` adjustment plus ≤1 four-byte store. **There is no second copy of the
+program anywhere.**
+
+### kit lex+pp (~0.97 B, ~2.8×) — `lang/cpp/lex/lex.c`, `lang/cpp/pp/*`, `lang/c/parse/parse.c`
+
+- **24 B `Tok` returned by value across a 4-frame relay**: `lex_next` →
+ `pp_next` (`pp.c:182`) → `fetch_tok` (`parse.c:165`) → `advance`
+ (`parse.c:185`). The same Tok is **copied ~3 extra times** through frames that
+ never mutate it (~72 B of redundant motion/token). *Caveat:* PERF.md records
+ that collapsing these *pull wrappers* alone measured ~5 % (a near-dead-end) —
+ the copies are real but a bounded constant factor; weight this below interning
+ and Tok-size.
+- **Per-occurrence re-interning**: every content token re-runs FNV-1a + a pool
+ probe (`pool_intern_slice`, `pool.c:120`), even the millionth `int`/`;`.
+ Punctuators are cached (`punct_sym[]`); identifiers and numbers are **not**.
+ tcc hashes once during the scan, then it's an int. **This is the single
+ biggest lex+pp lever** (~14 % of total self-time).
+- **`Tok` is 24 B, half of it `SrcLoc {file,line,col}` (12 B)** copied through
+ every layer (`lex.h:67`, `core.h:64`). Packing it to a 32-bit position (lazy
+ decode on diagnostics) shrinks `Tok` to 16 B → 33 % less token-copy bandwidth.
+- **`TOK_NEWLINE` is materialized, copied up 3 layers, then dropped** in
+ `pp_next` (`pp.c:194`) — a full Tok produced+copied+discarded per source line.
+- **Object-macro expansion double-copies the body** (`tmp[i]=m->body[i]` +
+ `subst_phase2`, `pp_expand.c:374`) even with no `##`; function-macro args take
+ 3–4 copies/token (`pp_expand.c:620`).
+- **Interner table/entry split**: the open-addressed table slot holds only a
+ 4 B `Sym`; the `hash`+`len` guard lives in a *separate* `entries[]` array at a
+ hash-scattered index, so every occupied probe slot pays a random
+ `entries[sym]` line (`pool.c:140`). Dense at the table, pointer-chasing at the
+ entry. (At IPC 3.7 this is extra *loads*, not stalls.)
+
+### kit parse+sema+types+CG-drive (~0.87 B, ~3.5×) — `src/cg/*`, `lang/c/parse/cg_adapter.c`
+
+At `-O0` **no IR is recorded** — the bare `NativeDirectTarget` is installed and
+`opt_cgtarget_new` is skipped (`src/cg/session.c:147`). So this 0.87 B is the
+value-stack + type machinery itself, run to drive emission:
+
+- **56 B `ApiSValue` per operand** (`internal.h:99`) carrying delayed-arith,
+ bitfield (12 B), and source-local riders the common `a+b` never uses — vs
+ tcc's 48 B register-resident `SValue`. Every push/pop moves 56 B.
+- **A fold / delay / strength-reduce / identity ladder runs on the hot path even
+ at -O0** (`arith.c:48-99`), plus 4 type-class probes before any work in
+ `kit_cg_int_binop` (`arith.c:1105`). -O0 wants none of this value-quality work.
+- **Type re-decoded ~8–12× per statement**, and `abi_cg_type_info` (size/align)
+ is **not memoized** — a recursive `cg_type_get` + alias chase **every call**
+ (`abi.c:90`), hit from `alloc_temp_local`, `nd_type_mem`, `class_for_type`, …
+ Only the packed `api_type_class` *byte* is cached (`type.c:289`).
+- The CgTarget seam sits **above** all this (per PERF Round 7): even routed to
+ the no-op check backend, the value-stack drive pays the full cost.
+
+### kit native emit + objwrite (0.37 B, ~7× — worst ratio) — `native_direct_target.c`, `src/arch/aa64/native.c`, `src/arch/mc.c`
+
+- **Three stacked vtable layers**: `CgTarget` → `NativeTarget` → `MCEmitter`,
+ each an **indirect call per primitive**. `x = a + b;` costs ~7–9 indirect
+ calls (`nd_binop` 1542 → `aa_binop` → `m_emit_bytes` 298, ×{add, store,
+ operand materializations}) where tcc does a couple of *direct* `o()` byte
+ appends. Three indirections where tcc has zero.
+- **The NDT runs an LRU register-cache** — `reg_owner`/`cache_head`/`touch_local`
+ /`flush`/`writeback`/`pick_victim` (`native_direct_target.c:516-930`) — a
+ *mini register allocator at -O0*, where tcc keeps top-of-stack in a fixed reg
+ and spills on demand.
+- kit emits **~2× tcc's machine-code bytes** (unoptimized -O0 codegen: 4.26 MB
+ vs 2.11 MB object) → ~2× the emit + objwrite volume. Track B
+ (`o0-codesize-vs-tcc`) is already shrinking this (3.45×→2.42× text) and
+ **directly reduces this phase**.
+
+## The roadmap — tracks to close the gap
+
+No single change closes 3.35×; this is a campaign. Ranked by
+instruction-payoff × structural leverage. Every track gates on
+`scripts/perf_identity_gate.sh` byte-identical output (or, where it changes
+codegen, run-correctness + determinism) and is measured on RELEASE best-of-7
+instructions.
+
+### Track 1 — Collapse the codegen vtable stack + the -O0 value machinery (biggest lever: ~0.37 B emit at 7× + much of the 0.87 B middle)
+
+The worst ratio and the densest cluster of redundant work. Structural moves:
+
+1. **Fuse `CgTarget`+`NativeTarget` into one direct -O0 emit path** — remove 2
+ of 3 indirect calls per primitive and the `NativeLoc` re-marshalling between
+ the layers (`native_direct_target.c:1542-1648` ↔ `aa64/native.c`). The
+ CgTarget seam exists to share the frontend with the opt-IR / C-source / Wasm
+ backends; at -O0 it is pure overhead. Consider a compile-time-selected direct
+ emitter for the native -O0 path.
+2. **Memoize size/align/regclass on the type id** (extend the `api_type_class`
+ memo, `type.c:289`) → kills the uncached recursive `abi_cg_type_info`
+ (`abi.c:90`) and the per-operand `class_for_type` vtable hops.
+3. **Gate the fold/delay/strength-reduce ladder OFF at -O0** (`arith.c:48-99`,
+ `1105-1114`) → binop becomes pop,pop,emit.
+4. **Replace the NDT LRU register-cache with a tcc-style fixed TOS-register
+ discipline at -O0** (`native_direct_target.c:516-930`).
+5. **Shrink `ApiSValue` 56→~24 B** — move bitfield/delayed/source-local fully
+ off-node (`internal.h:99`).
+6. **Couples with Track B** (`o0-codesize-vs-tcc`): fewer emitted bytes → less
+ emit + objwrite + assembler work.
+
+### Track 2 — Densify the token relay (lex+pp, 0.97 B)
+
+1. **Per-occurrence intern cache / deferred intern** (highest lex+pp payoff,
+ ~14 %): stop re-hashing hot identifiers. Cache the last-interned Sym by
+ spelling start+len, or intern lazily only when the parser needs the Sym.
+ (`lex.c` intern sites, `pool.c:120`.)
+2. **Pack `SrcLoc` → 32-bit position; `Tok` 24→16 B** — 33 % less token-copy
+ bandwidth through PP/macro-expansion/parser; lazy file:line:col decode on the
+ diagnostic path only (`lex.h:67`, `core.h:64`).
+3. **Collapse the 4-frame pull into one inlined `pp_pull` writing straight into
+ `p->cur`** — eliminate ~3 Tok copies/token and fold newline filtering into the
+ scanner so newlines never become parser-facing Toks. *(Bounded: pull-wrapper
+ fusion alone measured ~5 % before — do it for the copy elimination, not as
+ the main lever.)*
+
+### Track 3 — Interner self-sufficiency (part of lex+pp; ~14 %)
+
+Put `hash`+`len` (and an inline small-string prefix, SSO for ≤14 B identifiers)
+**in the probe slot** so a probe rejects without the random `entries[sym]` line
+(`pool.c:31-45,139`). Converts a ~2–3 cache-line intern into ~1–2 lines and
+removes the scattered-entry loads — fewer instructions and a smaller LLC
+footprint (shrinks the ~2–3 MB `entries[]`+arena).
+
+### Track 4 — The end-state bet: adopt tcc's single-pass data-flow shape
+
+Tracks 1–3 are the incremental path; the destination is tcc's *shape*: a shared
+mutable token slot fed by both the scanner and the macro replayer (no
+per-stage Tok structs), identifiers resolved through symbol pointers cached on
+the interned token, and a thin `SValue[]` value stack the parser drives by
+calling the backend's emit directly (no vtable), writing bytes into the final
+section image. This is the "clean structural redesign" the project prizes; it
+subsumes Tracks 1–3 and is the larger lift. Treat Tracks 1–3 as independently
+shippable, byte-identical-gated steps *toward* it.
+
+## What this corrects / supersedes
+
+- PERF.md's "the scanner is THE lever (58–62 %)" is **wall-clock**; the
+ instruction-grounded gap is ~uniform across phases and **codegen-density is
+ the highest-leverage single track**. The raw-cursor scanner rewrite was still
+ a real −84 M win and `kit -E` now *beats* `tcc -E` — but it is not the path to
+ tcc parity.
+- The "fused lex→pp→parse pull pipeline = dead end (~5 %)" note stands for the
+ *pull wrappers*; it does **not** cover interning, Tok-size, or the codegen
+ vtable stack, which are the actual levers.
+- This is an **instruction-reduction** program (kit IPC ≥ tcc IPC). Density is
+ the means; fewer retired instructions is the metric.
+
+### Reproduce the decomposition
+
+```sh
+SDK=$(xcrun --sdk macosx --show-sdk-path); cd tmp/projects/sqlite-amalg
+K=build/release/kit
+# best-of-7 instr+cycles helper `mc` as in PERF.md, plus IPC
+$K cc -E sqlite3.c -o /tmp/e.c --sysroot "$SDK"; cp /tmp/e.c /tmp/exp.c # preprocessed -> .c
+mc $K cc -c sqlite3.c -o /tmp/k.o --sysroot "$SDK" # 2.216 B (full)
+mc $K cc -fsyntax-only sqlite3.c --sysroot "$SDK" # 1.846 B (− emit/objwrite)
+mc $K cc -c /tmp/exp.c -o /tmp/ke.o --sysroot "$SDK" # 1.589 B (no PP work)
+mc $K cc -fsyntax-only /tmp/exp.c --sysroot "$SDK" # 1.217 B
+mc $K cc -E /tmp/exp.c -o /dev/null --sysroot "$SDK" # 0.343 B (lex+trivpp+detok)
+mc tmp/tinycc/tcc -c sqlite3.c -o /tmp/t.o # 0.663 B (tcc, all phases)
+```
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -163,14 +163,24 @@ but *not* for blocking I/O — see the `fsync` row.)
| codegen (`nd_dst_reg`/`cg_type_is_aggregate`/`api_unalias_type`/…) | ~1.6 total | native emit | each <1 % |
| `_platform_memmove` | 0.3 | buffer moves | callers parse/codegen |
-The scanner (`lex_next` + `finish_ident`) is **~66 %** of self-time — still THE
-lever by a wide margin, and *more* concentrated than before the rewrite (the
-dispatch/classification is now one table load, so the cost is the irreducible
-per-byte cursor walk plus the per-token interning handoff). The next lever is
-`pool_intern_slice` (interning), then the parse/codegen `memset`. Three things
-that used to be hot remain absent: the **type system** (derived-type + ABI/record
-dedup are O(1)), the **preprocessor hideset** (O(1) content-addressed dedup), and
-**guarded-header re-lexing** (multiple-include optimization).
+The scanner (`lex_next` + `finish_ident`) is **~66 %** of *wall-clock* self-time.
+Three things that used to be hot remain absent: the **type system**
+(derived-type + ABI/record dedup are O(1)), the **preprocessor hideset** (O(1)
+content-addressed dedup), and **guarded-header re-lexing** (multiple-include
+optimization).
+
+> **⚠ Wall-clock self-time ≠ instruction attribution — read `PERF-TCC-GAP.md`
+> before deciding where to optimize for the tcc gap.** This single-peaked
+> `sample` profile makes the scanner *look* like the lone frontier, but it is a
+> wall-clock artifact of one big inlined leaf on a single-peaked workload. The
+> **instruction-grounded** decomposition (load-independent, the metric to trust)
+> tells a different story: `-E` 0.97 B, post-PP 1.24 B, with the gap to tcc
+> spread **~uniformly ~3× across lex+pp / parse+sema+CG / emit** — and kit `-E`
+> already *beats* `tcc -E`. The highest-leverage single track is **codegen
+> density** (the CgTarget→NativeTarget→MCEmitter vtable stack + the -O0
+> value/RA machinery, ~7× tcc), not the scanner. kit's IPC (3.70) is *higher*
+> than tcc's (3.48): the gap is **instructions, not cache stalls**. Full map,
+> per-phase diagnosis, and the redesign tracks: **`doc/plan/PERF-TCC-GAP.md`**.
### Resolved — already optimal, don't re-propose
@@ -198,13 +208,31 @@ dedup are O(1)), the **preprocessor hideset** (O(1) content-addressed dedup), an
residual `lex_next` self-time is the raw byte loads themselves + the interning
handoff, so the remaining lever is (2).
-### Next levers (ranked)
-
-1. **Identifier interning** (`pool_intern_slice`, ~15 %). Mostly fundamental
- (identifiers must be interned); word-at-a-time hashing was a measured dead end
- for short ids (see below). Now the top frontend lever after the scanner
- rewrite, but a low ceiling.
-2. **`memset`/`memmove` in parse + codegen** (~10 %, callers `cg_adapter` /
+### Next levers (ranked) — see `PERF-TCC-GAP.md` for the structural roadmap
+
+The instruction-grounded decomposition (above callout) puts the tcc gap
+~uniformly across phases; the tracks below are ordered by instruction-payoff ×
+structural leverage. Full per-phase diagnosis + redesign plan in
+**`doc/plan/PERF-TCC-GAP.md`**.
+
+1. **Codegen density — collapse the -O0 emit stack** (Track 1, ~7× tcc, the
+ worst ratio). Three stacked vtables (`CgTarget`→`NativeTarget`→`MCEmitter`,
+ ~7–9 indirects per statement), the NDT LRU register-cache running as a
+ mini-RA at -O0, the fold/strength-reduce ladder on the -O0 hot path, the
+ uncached recursive `abi_cg_type_info`, and the 56 B `ApiSValue`. Fuse the two
+ native vtables into one direct emit path, memoize size/align/regclass on the
+ type id, gate the fold ladder off at -O0, shrink the value node. Highest
+ single lever; couples with Track B (`o0-codesize`: fewer emitted bytes →
+ less emit/objwrite).
+2. **Identifier interning** (`pool_intern_slice`, ~14 %). Per-occurrence
+ re-hash+probe of hot identifiers; cache/defer the intern, and make the probe
+ slot self-sufficient (`hash`+`len`+SSO inline) so it rejects without the
+ random `entries[sym]` line. Word-at-a-time hashing was a measured dead end —
+ this is a *layout* change, not a hash change.
+3. **Token relay density** (lex+pp): pack `SrcLoc`→32-bit so `Tok` is 16 B (33 %
+ less copy bandwidth), collapse the 4-frame by-value relay into one inlined
+ pull. (Pull-wrapper fusion alone was ~5 % — do it for the copy elimination.)
+4. **`memset`/`memmove` in parse + codegen** (~8 %, callers `cg_adapter` /
`native` / `m_emit_bytes` / `parse_*`, **not** the lexer). Right-size the struct
zeroing and buffer copies on the per-expression / per-emit path.
