commit f29ca291d13f441b4116feb9766984e80a6874f4
parent 1943e48b626acbd09b4728d0abd8a9d95140399d
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 11:22:46 -0700
perf(cg): tcc-style -O0 prologue on aa64; caller-saved-only NDT invariant
The single-pass (-O0) NativeDirectTarget path reserved a worst-case 32-word
prologue region per function (sized for a fat frame + callee-save area +
Windows probe), patched the real ~4-word prologue in, and branched over the
rest -- ~27 NOP words/function. Measured: 70,836 NOP words across sqlite3.o
(6.0% of text).
Root cause: the region had to cover a *variable* prologue because the frame
size and callee-save set are unknown until the body is emitted. But the -O0
path never actually allocates a callee-saved register (0/2633 functions in
sqlite, like tcc). So:
1. Make that an enforced invariant: nd_scratch_acquire never takes a
callee-saved register (the allocable-pass fallback skipped them; pressure is
absorbed by evicting a cached local instead), and nd_func_end asserts
callee_saved_used==0. The optimizer/known-frame path is untouched -- it
drives the NativeTarget directly, never through NDT, and keeps full
callee-save freedom (69% of sqlite functions use callee-saves at -O1).
2. With no callee-saves, only the frame sub-sp (+ Windows page probe) is
deferred. Restructure the aa64 prologue tcc-style: emit the frame-independent
entry live (stp x29,x30,[sp,#-(16+top_home)]! ; mov x29,sp), then reserve
only a tiny region (5 words, or 12 with a probe) for the deferred sub-sp. The
frame is byte-identical in memory -- same fp/sp, same fp-relative offsets,
same epilogue -- only the instruction sequence changes; CFI advances by the
live entry plus the reserved region.
sqlite3.o: 70,836 -> 7,793 NOP words (6.0% -> 0.7%, fewer than tcc's 13,757);
text 4.73MB -> 4.47MB. Validated: test-parse 3920/0, test-toy 1392/0,
test-dwarf + debug roundtrip + CFI unit all OK.
Diffstat:
| M | doc/plan/PERF.md | | | 175 | ++++++++++++++++++++++++++++++++----------------------------------------------- |
1 file changed, 71 insertions(+), 104 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -27,19 +27,21 @@ 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.
+Apple-silicon arm64 / macOS. **`instructions` is the metric to trust** — it is
+load-independent (from `/usr/bin/time -l`, best-of-7); wall and cycles are only
+meaningful on a quiet machine (`sysctl -n vm.loadavg`) and are shown from a
+recent low-load reading.
-| compiler | wall | instructions | cycles | object |
+| compiler | instructions | cycles † | wall † | 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 |
+| **tcc 0.9.28** | 0.67 B | 0.22 B | 0.06 s | 2.11 MB |
+| **kit (current)** | 3.40 B | 0.89 B | 0.28 s | 5.12 MB |
+| clang 22 | 8.73 B | 2.57 B | 0.81 s | 1.50 MB |
+
+† low-load reading; re-confirm on a quiet machine.
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
+**tcc is the bar**: ~5.1× instructions (~4× cycles / ~4.7× wall) ahead. Closing
that is the whole game. (kit's object is larger because `-O0` codegen is
deliberately unoptimized — irrelevant to this goal.)
@@ -94,8 +96,9 @@ m build/release/kit cc -c -o /tmp/k.o sqlite3.c --sysroot "$SDK" # + codegen
`-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 %.**
+object write** only. Current binary: `-E` 1.90 B, `-fsyntax-only` 2.91 B, `-c`
+3.40 B → that delta is ~0.49 B / ~14 % — i.e. **codegen+emit is a small slice;
+the frontend is ~86 %.**
**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:
@@ -125,64 +128,57 @@ build/release/kit cc sqlite3.c shell.c -o /tmp/sq --sysroot "$SDK" -lc
## 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,
+codegen-bound.** The phase split (current binary, instructions: `-E` 1.90 B,
+`-fsyntax-only` 2.91 B, `-c` 3.40 B) puts native codegen + emit + object-write at
+the `-c` − `-fsyntax-only` delta of **~0.49 B (~14 %)**, of which pure native
+codegen is **~6 %** 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 |
+the other **~86 %**. (The synthetic `bench-cc` axes below over-weight codegen by
+construction; trust the sqlite profile for where to spend effort.)
+
+**The type system is no longer a bottleneck.** The derived-type dedup paths
+(ptr/array/func CG types, and the ABI func/record caches) used to linearly scan a
+growing table on *every* type use — O(n²) on type-heavy input, once ~70 % of
+frontend self-time. They are now O(1) (hashmap/hashset dedup), and the type
+system has dropped out of the profile entirely.
+
+### Where the time goes (self-time, real sqlite `-c`)
+
+24-run merged `sample` (current binary; % of total samples). The profile is flat
+— no single dominant hotspot, and the type-lowering hotspots are gone.
+
+| 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
+| `lex_next` | 19.8 | lexer (the scanner) |
+| `hs_add` | 17.5 | **preprocessor hideset** (macro-recursion tracking) |
+| `pool_intern_slice` | 13.2 | identifier interning |
+| `type_unqual` | 7.6 | frontend type query |
+| `pp_next_raw_into` | 4.8 | preprocessor token pump |
+| `_platform_memset` | 3.6 | zeroing |
+| `kit_cg_type_record_field` | 2.2 | frontend type lowering |
+| `type_cg_lower` / `type_qualified` / `api_type_class` | ~4 | frontend type lowering |
+| `nd_*` / `aa_*` (codegen) | ~6 | native codegen + emit |
+| `src_next_raw_into` / `skip_until_active` | ~2 | preprocessor |
+| `scope_lookup` | 0.9 | symbol lookup (already cheap — lazy scope index) |
+| `__rename` / write | ~1 | object output (atomic temp+rename) |
+
+Rolled up: **lexer + preprocessor + interner ≈ 57 %** (lex 20 + hideset 17.5 +
+intern 13 + pp ~6), **frontend type queries/lowering ≈ 16 %**, **native
+codegen+emit ≈ 6 %**. 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).
+### Next levers (ranked)
+
+1. **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** (`type_unqual`, `TypeInternSet`). The CG-layer
+ re-lowering is gone; 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
@@ -255,44 +251,15 @@ all of them; that guarantee is the floor this benchmark defends.
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.
+## Dead ends (measured — don't retry)
+
+- **16-byte `Tok` (LocId side-table, register return).** Byte-identical but a net
+ `-c` regression: the compile path is loc-heavy, so each token pays a `LocId`
+ store (lexer) + resolve (parser) that costs more than the smaller copy saves.
+ `Tok` is shared by `-c` and `-E`, and `-c` dominates. Do not revive.
+- **Fused lex→pp→parse pull pipeline.** The pull-wrapper layers are only ~5 % of
+ frontend self-time; `pp_next_raw`'s real cost (macro/directive logic) survives
+ the rewrite. Not worth it.
- **`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.
+- **Word-at-a-time intern hash · lower hash load factor · inline-prefix entry
+ cache** — all slower or negligible for the short identifiers real code uses.
