commit c7e600b5d08b758d2493e2ac839dcb62da456a4a
parent a753147bfd561abf78e6b010eeaaad3d3950b114
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 14:39:45 -0700
doc(perf): refresh PERF.md to current state (drop changelog, re-sample)
Strip the per-round 'what landed' narrative and refresh every measurement to the
current binary: standings (kit -c 2.43B vs tcc 0.66B = ~3.7x; obj 4.26MB), phase
split (-E 1.06B / -fsyntax 1.98B / -c 2.43B), and the 'where the time goes' table
from an 80-run / 1809-sample PROFILE merge (lex_next 58%, pool_intern 15%, memset
7%, the pp pump + memmove ~10%, codegen ~6%). The scanner is still THE lever.
Also: bump the hotspot recipe to ~80 runs (a -c is ~0.2s now, so 24 runs
undersamples), and warn to verify the build completes a full -c before trusting a
sample (a build that errors partway inflates the frontend's share).
Diffstat:
| M | doc/plan/PERF.md | | | 161 | ++++++++++++++++++++++++++++++++----------------------------------------------- |
1 file changed, 66 insertions(+), 95 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -34,19 +34,18 @@ recent low-load reading.
| compiler | instructions | cycles † | wall † | object |
|---|--:|--:|--:|--:|
-| **tcc 0.9.28** | 0.67 B | 0.22 B | 0.06 s | 2.11 MB |
-| **kit (current)** | 2.84 B | — | — | 5.12 MB |
-| kit (pre-sym-centric) | 3.37 B | 0.89 B | 0.28 s | 5.12 MB |
+| **tcc 0.9.28** | 0.66 B | 0.22 B | 0.06 s | 2.11 MB |
+| **kit (current)** | 2.43 B | — | — | 4.26 MB |
| clang 22 | 8.73 B | 2.57 B | 0.81 s | 1.50 MB |
-† low-load reading; re-confirm on a quiet machine. cycles/wall for the current
-row are pending a quiet-machine re-read (the −16% is an instruction A/B).
+† low-load reading; re-confirm on a quiet machine (`instructions` is
+load-independent and the figure to trust; cycles/wall are pending a quiet-machine
+re-read).
kit beats clang on compile speed and is the fastest *general* backend here, but
-**tcc is the bar**: now ~4.2× instructions ahead (down from ~5.0×). The last
-−16 % came from the sym-centric / hideset work below; closing the rest is the
-whole game. (kit's object is larger because `-O0` codegen is deliberately
-unoptimized — irrelevant to this goal.)
+**tcc is the bar**: ~3.7× 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
@@ -99,28 +98,32 @@ 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. Current binary: `-E` 1.42 B, `-fsyntax-only` 2.35 B, `-c`
-2.83 B → that delta is ~0.48 B / ~17 % — i.e. **codegen+emit is a small slice;
-the frontend is the rest.** Within that frontend, `-E` alone (1.42 B) is now the
-majority, and the scanner (`lex_next`) is the bulk of it — see *Where the time
+object write** only. Current binary: `-E` 1.06 B, `-fsyntax-only` 1.98 B, `-c`
+2.43 B → that delta is ~0.44 B / ~18 % — i.e. **codegen+emit is a small slice;
+the frontend is the rest.** Within that frontend, `-E` alone (1.06 B) is just
+under half, and the scanner (`lex_next`) is the bulk of it — see *Where the time
goes*.
-**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:
+**4. Hotspot profile** (self-time per function). One run is far too fast for
+`sample` (a `-c` is ~0.2 s now), so merge the `Sort by top of stack` sections
+across many runs — use **~80** to get a stable distribution (~1800 samples; 24
+runs yields only a few hundred and the percentages wobble):
```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
+for i in $(seq 1 80); 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
+ | awk '{c[$1]+=$2;t+=$2} END{for(k in c) printf "%.1f%% %s\n",100*c[k]/t,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.
+the shipped release and arm64 stacks are reliable. **Verify the build actually
+completes a full `-c`** (`rc=0`, non-empty object) before trusting a sample — a
+build that errors partway through inflates the frontend's apparent share.
**5. End-to-end correctness** (sqlite as a correctness test):
@@ -130,100 +133,68 @@ build/release/kit cc sqlite3.c shell.c -o /tmp/sq --sysroot "$SDK" -lc
select sum(a)+sum(b), count(*) from t;" # -> 84|2
```
-## Current state (2026-06-12)
-
-### Landed 2026-06-12: sym-centric bindings + hideset O(1) dedup (−16 % `-c`)
-
-Three byte-identical structural changes (gated 60/60 across objects/`-E`/`-S`/
-`-g`/diagnostics/exe/splice, sqlite `-E` bit-identical, test-pp 110/110):
-
-1. **Sym-centric bindings** (`KIT_SYMTAB_DEFINE`, `include/kit/support/symtab.h`).
- kit's `Sym` ids are dense + monotonic, so the "binding hung off the interned
- token" that tcc gets from `TokenSym` fields is just a flat `Sym`-indexed
- array — one bounds-check + one load, no hashing. The preprocessor macro table
- (was a `Sym→Macro*` hashmap, `mt_get` per identifier) and the parser keyword
- map (was a `Sym→u8` hashmap, probed per identifier) are now `SymTab`s. Each
- layer keeps its own table, so the cpp↔c boundary stays intact. **−4.3 % `-c`.**
-2. **Hideset dedup O(n²) → O(1)** (`hs_register`, `pp_expand.c`). The per-macro-
- invocation dedup linearly scanned *every* hideset ever created in the TU — the
- real cost behind the 17.5 % `hs_add` (kit doesn't even do the Prosser
- intersection, so this scan was the whole expense). Now a content-addressed
- open-addressed index (`Pp.hs_index`, keyed on the hideset's stored hash). Ids
- are still assigned in first-appearance order, so output is bit-identical.
- **The big win: −11.5 % `-c` over (1); −24.6 % on `-E`.**
-3. **Per-token hideset → per-buffer scalar** (`TokSrc.hs_uniform`,
- `push_buf_uniform`). Macro-body buffers share one hideset, so they no longer
- materialize a parallel `HidesetId` array; only the (genuinely non-uniform)
- argument-prescan path keeps the array. Byte-identical, **perf-neutral** (the
- array fill was cheap xarena bump traffic; the win was all in (2)) — kept as a
- memory/structure simplification.
-
-Net: sqlite `-c` 3.37 B → **2.84 B**, `-E` 1.89 B → **1.42 B**; **~5.0× → ~4.2× tcc**.
-
-**The headline finding still holds: real-world compilation is frontend-bound, not
-codegen-bound.** The phase split (instructions: `-E` 1.42 B, `-c` 2.84 B) puts
-native codegen + emit + object-write at well under ~20 %; the frontend —
-preprocessor, lexer, interner, parser, semantic analysis, and the CG
-value-stack/type-lowering it drives — is the rest. (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.
+## Current state
+
+**Real-world compilation is frontend-bound, not codegen-bound.** The phase split
+(instructions: `-E` 1.06 B, `-c` 2.43 B) puts native codegen + emit + object-write
+at ~18 %; the frontend — preprocessor, lexer, interner, parser, semantic analysis,
+and the CG value-stack/type-lowering it drives — is the rest. (The synthetic
+`bench-cc` axes below over-weight codegen by construction; trust the sqlite profile
+for where to spend effort.)
### Where the time goes (self-time, real sqlite `-c`)
-**Fresh 24-run merged `sample`** on the current binary (punct-cache `11fddf5b` +
-CG-type memo `d881c8d9` + hideset-O(1)/sym-centric, this pass). The earlier table
-is obsolete: the three biggest old rows are gone, and the scanner now dominates.
+80-run merged `sample` on a `PROFILE=1` build (1809 samples). The profile is
+**single-peaked**: the scanner dominates and everything downstream of it is flat.
| function | self % | stage | note |
|---|--:|---|---|
-| `lex_next` | **56.2** | lexer (the scanner) | **the frontier** — was 19.8 % |
-| `pool_intern_slice` | 11.2 | identifier interning | mostly identifiers (puncts now cached) |
-| `_platform_memset` | 7.6 | zeroing | callers are **parse + codegen**, not the lexer |
-| `pp_next_raw_into` | 6.4 | preprocessor token pump | |
-| `_platform_memmove` | 5.1 | buffer moves | callers parse/codegen (`m_emit_bytes`, cg) |
-| `src_next_raw_into` | 4.2 | preprocessor source stack | |
-| `scope_lookup` | 2.1 | symbol lookup | cheap (lazy index) |
-| `type_cg_lower` / `kit_cg_type_record_field` | ~3 | type lowering | **was ~16 %** — memoized (`d881c8d9`) |
-| `hs_add` | **0** | preprocessor hideset | **RESOLVED** — O(1) dedup, this pass |
-
-The profile has gone from flat to **single-peaked**: `lex_next` is 56 % and
-everything downstream of it has been flattened. At ~2.6 M tokens for sqlite that
-is ~600 instructions/token in the scanner alone — the gap to tcc is now almost
-entirely *the scanner loop itself*.
-
-### Resolved (don't re-propose)
-
-- **Punctuator interning** — `11fddf5b` caches the spelling `Sym` per lexer
- (`Lexer.punct_sym[]`, `punct_spelling()`); digraphs intern verbatim. Near-
- optimal; the only residual is a negligible per-`#include` cache re-warm.
-- **CG-type lowering** — `d881c8d9` memoizes the lowered `KitCgTypeId` + the
- complete-record `type_unqual` on the pool. The ~16 % type bucket is now ~3 %.
-- **Preprocessor hideset** — O(n²) dedup → O(1) content index; per-token hideset
- array → per-buffer scalar (this pass).
-- **Sym-centric macro + keyword tables** — `SymTab` array loads (this pass).
+| `lex_next` | **58.0** | lexer (the scanner) | **the frontier** |
+| `pool_intern_slice` | 14.8 | identifier interning | identifiers (puncts cached) |
+| `_platform_memset` | 7.0 | zeroing | callers are **parse + codegen**, not the lexer |
+| `src_next_raw_into` | 4.0 | preprocessor source stack | |
+| `pp_next_raw_into` | 3.5 | preprocessor token pump | |
+| `_platform_memmove` | 2.7 | buffer moves | callers parse/codegen (`m_emit_bytes`, cg) |
+| `scan_pp_number` | 1.4 | lexer (number scan) | inlined into the scanner lever |
+| codegen (`nd_dst_reg`/`cg_type_get`/`aa_emit_mem`/…) | ~6 total | native emit | each <1.5 % |
+
+`lex_next` plus its inlined helpers (`scan_pp_number`, `bump`, …) is ~60 % of
+self-time; the gap to tcc is now almost entirely *the scanner loop itself*. Three
+things that used to be hot are absent from the profile: 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).
+
+### Resolved — already optimal, don't re-propose
+
+- **Multiple-include optimization** — a controlling-`#ifndef` guard + `#pragma
+ once` memo skips re-lexing a guarded header while its macro is defined. (Was
+ ~37 % of scanned bytes: `sys/cdefs.h`-style headers re-lexed dozens of times.)
+- **Punctuator interning** — the spelling `Sym` is cached per lexer
+ (`Lexer.punct_sym[]`, `punct_spelling()`); digraphs intern verbatim.
+- **CG-type lowering** — the lowered `KitCgTypeId` + the complete-record
+ `type_unqual` are memoized on the pool.
+- **Preprocessor hideset** — O(1) content-addressed dedup; per-buffer scalar id
+ (no per-token `HidesetId` array on the uniform macro-body path).
+- **Sym-centric macro + keyword tables** — flat `Sym`-indexed array loads, no hash.
### Next levers (ranked)
-1. **The scanner loop** (`lex_next`, 56 % — now THE lever by a wide margin). The
+1. **The scanner loop** (`lex_next`, 58 % — THE lever by a wide margin). The
per-token cost is `skip_ws_and_comments` + the first-char `switch` dispatch +
`scan_ident_run`; `lex_here`/`scan_ident_run` are already tight splice-free
loops, so the win is in the *dispatch and classification*. Replace the branchy
`is_space`/`is_alnum`/punct cascade with a single 256-entry **char-class table**
(one load → ident-start / ident-cont / digit / space / punct), tcc-style; fuse
the whitespace skip into the same table walk so a token with no leading space
- pays nothing. Gate byte-identical (`-E` + objects + the splice battery).
-2. **`memset`/`memmove` in parse + codegen** (~13 %, 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.
-3. **Identifier interning** (`pool_intern_slice`, 11 %). Mostly fundamental
+ pays nothing; defer the per-byte column to a `line_start` pointer. Gate
+ byte-identical (`-E` + objects + the splice battery).
+2. **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). Low ceiling — attack only after (1).
+3. **`memset`/`memmove` in parse + codegen** (~10 %, 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.
## The synthetic scaling benchmark (`make bench-cc`)
