commit b66e4c71e9981f1f2b7dcefb06bacbc836c35c3d
parent 171985939029a12c44c272cc02d063a96fb3e599
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Thu, 11 Jun 2026 06:58:38 -0700
docs(perf): focus PERF.md on current state + forward-looking
Drop the round-by-round history (Rounds 1-5 + the 'fixes applied' / 'resolved
out-of-band' narratives) — that's recoverable from git. Keep the benchmark how-to
(reference) and replace the findings log with: current kit/clang ratios + the
self-time-by-stage breakdown (codegen/parser now dominate), the invariants to
hold (no superlinear axis; byte-identical gate; memset-is-explicit), and the
ranked remaining levers + measured dead ends.
Diffstat:
| M | doc/plan/PERF.md | | | 378 | ++++++++++++++++--------------------------------------------------------------- |
1 file changed, 76 insertions(+), 302 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -75,56 +75,35 @@ sudo) · `KIT_CC_BENCH_OUT`.
Quick wire-check: `KIT_CC_BENCH_SIZES='8 16 32' KIT_CC_BENCH_SAMPLE=0 make bench-cc`.
-## Findings
-
-### Round 5 — per-segment structural pass (lexer / pp / parser-types / cg / emit / link)
-
-> 2026-06-10, M1, clang-built `PROFILE=1` kit. A measurement-driven sweep across
-> every segment, grounded in fresh hotspots (multi-second runs via
-> `scripts/cc_bench_hot.sh`, which drives one axis at a tuned large size so
-> macOS `sample` captures a real call graph — the normal sweep is now too fast
-> to sample). A decisive experiment first: rebuilding with
-> `-ftrivial-auto-var-init=zero` **off** left `memset` self-time unchanged, so
-> the pervasive #1 cost is *explicit* zero-init, attacked at the call sites (the
-> hardening flag stays). Every change is object/`-E`/`-g`/diagnostic
-> byte-identical to HEAD (the gate, since ASan can't see a premature-reuse or
-> uninit read) except the two genuine latent O(n²) fixes, which only change
-> *timing*. Headline (original HEAD → after, same machine + sizes):
-
-| segment | change | result |
-|---|---|---|
-| **types** | hash-cons structural types (ptr/array/func) — kills an O(types) per-derivation scan of one flat list; memoize ABI facts + record layouts | type-decl 1229→976 ms (−21%); record-heavy TU 904→41 ms (**22×**, was O(records²)); pointer-population stress 29.5 s→0.27 s (**108×**) |
-| **codegen** | build `NativeLoc`/`NativeAddr`/`MemAccess` via designated compound literals, not `memset`+stores (the ~64 B descriptor zeroing was the top self-time on cg-heavy axes) | body-size −8%, locals −8%, ref-density −4% |
-| **emit** | tail-chunk fast path in the chunked buffer; batch the aa64 prologue patch + 32-NOP reserve into one op each (x64 already did); skip per-instruction `obj_pos` without `-g` | fn-count 1056→752 ms (−29%) |
-| **link** | per-section delta table + a `link_sec_id→MSec*` index replace two per-section rescans of the whole reloc+sym vectors in the Mach-O finalizer | obj-count restored to LINEAR; 16384 objs 1045→379 ms (2.76×, gap widens with N) |
-| **pp** | drop the degenerate per-token hideset vector; batch `-E` output into a local buffer; pre-size the substitution token vectors | pp-macro `-E` 1316→985 ms (−25%) |
-| **lexer** | **redesign**: fold translation-phase-2 line splices out once up front so the scanner walks a clean buffer with plain direct indexing — no per-byte splice re-test in `peek`/`bump`; splice-free input is zero-copy, spliced input keeps exact line/col via a fold-offset array | body-size −7%, type-decl −9%, pp-macro −6%, fn-count −4.5% on top of the above |
-| **core** | hoist the table/entries bases out of the per-identifier intern probe | small, free, byte-identical |
-
-Net kit/clang `-O0` (lower = faster, all axes LINEAR): fn-count 0.12→0.08×,
-body-size 0.33→0.27×, **type-decl 0.68→0.55×** (was the weakest compile axis),
-pp-macro 0.48→0.37×, global-decl 0.42→0.34×, ref-density 0.08→0.07×, obj-count
-0.26→0.23×. pp-include (file-I/O bound) and symbol-count (image-byte bound)
-unchanged.
-
-**Consistency cleanup (per review):** added `KIT_HASHSET_DEFINE` (open-addressed
-set with custom hash+eq) to `kit/support/hashmap.h` for the structural type
-intern, routed the ABI/record memos through the existing `KIT_HASHMAP_DEFINE`,
-and gave `Pool` one shared arena-heap facade (`Pool.arena_heap`) so all per-pool
-maps — including the parser's scope/tag/extern indexes, migrated off their
-duplicate local facade — get arena lifetime with no teardown.
-
-**Deliberately deferred.** image-id FNV→HW-SHA (a real symbol-count win but
-changes every executable's LC_UUID/build-id bytes); `nd_grow_*` non-zeroing
-(uninit-read risk without MSan); word-at-a-time intern hash / lower load factor /
-inline-prefix cache (all measured *slower* or negligible for real short
-identifiers). The residual top frame on the largest links is the image-id FNV.
-
-**Where the time goes now (post-Round-5 self-time, `scripts/cc_bench_stages.py`).**
-The bottleneck has *moved*: the token pump and the explicit-`memset` overhead that
-dominated before are cut, exposing **codegen** as the floor on the per-statement
-axes and the **parser** as the floor on `type-decl`. Self-time % by stage (each
-axis isolates one dimension):
+## 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.55× |
+| ref-density | 0.07× | pp-macro `-E` | 0.37× |
+| fn-count | 0.08× | global-decl | 0.34× |
+| obj-count (link) | 0.23× | pp-include `-E` | 0.80× |
+| body-size | 0.27× | symbol-count (link) | 0.87× |
+
+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`)
+
+The bottleneck is now **codegen** on the per-statement axes and the **parser** on
+`type-decl`; the token pump, `memset`, and IO that used to lead are cut. Self-time
+% by stage (each axis isolates one input dimension):
| stage | body-size | locals | ref-density | fn-count | type-decl | pp-macro `-E` |
|---|--:|--:|--:|--:|--:|--:|
@@ -138,20 +117,39 @@ axis isolates one dimension):
| **libc memset/memmove** | 10 | 13 | 13 | **16** | 8 | 13 |
| **libc io/vm** (`write`) | 3 | 1 | 4 | 4 | – | – |
-(`pp-macro` was a thin 69-sample run — noisier; its 62 % pp is the irreducible
-token-pump + substitution that *is* `-E`'s work.)
-
-**Possible gains — the concrete next levers, ranked.** All four are the
-higher-risk codegen/representation findings deliberately left this round:
-
-1. **Per-operand type-query gauntlet** (codegen, biggest compile-axis lever).
- `kit_cg_int_binop` runs `api_i128_stack_top`×2 + `api_wide64_stack_top`×2 —
- each a `cg_type_get` + `api_unalias_type` round-trip — on *every* int binop,
- only to detect a rare wide case. These (`api_unalias_type`/`cg_type_get`) are
- the top frames inside the 27–42 % codegen bucket. Fix: compute a small
- `wide_kind` flag once when a value is pushed and store it on the value node;
- the predicates become a load+compare. Touches the rv64/i128 split paths →
- verify on `test-smoke-rv64`.
+(`pp-macro -E` is preprocess-only, so its 62 % pp is the irreducible token-pump +
+substitution that *is* `-E`'s work.)
+
+### 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.
+- **`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
+ allocations) — the hardening flag stays.
+
+## Forward-looking — the remaining levers
+
+Ranked by (impact × confidence) / risk. All are the higher-risk
+codegen/representation changes; codegen and the per-function `memset` are where
+the compile-axis time now concentrates.
+
+1. **Per-operand type-query gauntlet** (codegen — biggest compile-axis lever).
+ `kit_cg_int_binop` runs `api_i128_stack_top`×2 + `api_wide64_stack_top`×2,
+ each a `cg_type_get` + `api_unalias_type` round-trip, on *every* int binop
+ only to detect a rare wide case. Those two are the top frames inside the
+ 27–42 % codegen bucket. Fix: compute a small `wide_kind` flag once when a
+ value is pushed and store it on the value node; the predicates become a
+ load+compare. Touches the rv64/i128 split paths → verify on `test-smoke-rv64`.
2. **`-O0` register-cache scan** (`nd_pick_cache_victim`, `nd_dst_reg`). A
per-pressured-op linear scan over the 16 allocable regs that re-derefs
`nd_local(owner)->last_use` with a bounds-check each iteration. Fix: a flat
@@ -160,241 +158,17 @@ higher-risk codegen/representation findings deliberately left this round:
3. **Residual per-function `memset`** (still 8–16 %). The remaining explicit
zero-init is `aa_plan_ret`'s `arena_zarray(NativeCallPlanRet, 4)` (512 B/fn,
≤1 used) and per-function arena scratch — right-size / lazily-zero them.
-4. **Token-pump sret tax** (deepest, pp-macro lever). `lex_next` / `src_next_raw`
- return a 24-byte `Tok` by value, so each token round-trips through an x8
- indirect-result stack slot. Converting the hottest readers to an out-pointer
- (or shrinking `Tok` ≤ 16 B by packing `SrcLoc`) returns it in registers — but
- `SrcLoc` is load-bearing frontend-wide, so bench-gate it in isolation.
-
-### Round 4 — CPU work: linker output hashing + the codegen type-query path
-
-> 2026-06-10, M1, clang-built `PROFILE=1` kit. With memory + IO handled
-> (Rounds 2–3), the remaining cost is **CPU in the actual passes**. Profiling
-> the largest input of each axis (multi-second runs so `sample` captures a real
-> call graph) surfaced two concentrated hotspots.
-
-**Linker — `symbol-count` was the only axis kit lost to the system linker
-(2.00× ld64).** For a large output the link was ~85 % two full-image content
-hashes: `compute_codesig` (the mandatory macOS ad-hoc code signature — SHA-256
-over every 4 KB page) at ~58 %, and `link_image_id_compute` (the LC_UUID /
-build-id — **two** byte-at-a-time FNV-1a passes over the whole image) at ~27 %.
-kit hashed with a portable scalar SHA-256 while ld64 uses the ARMv8 crypto
-extension. Three fixes, all output-bit-identical:
-
-1. **Hardware SHA-256** (`src/core/sha256.c`). Added an ARMv8 crypto-extension
- block (`sha256h`/`h2`/`su0`/`su1` inline asm, no `arm_neon.h` so it survives
- the freestanding `-nostdinc` build) gated on `defined(__aarch64__) &&
- defined(__ARM_FEATURE_SHA2)` — always set on Apple Silicon, so the macOS
- linking host (the codesig consumer) is covered with zero runtime detection.
- ~5–8× the scalar throughput; same digest. Linux/FreeBSD aarch64 could gain it
- behind a HWCAP probe (deferred — keeps core free of platform detection).
-2. **memcpy-free `sha256_update`.** The old update staged every byte through a
- 64-byte buffer; now full blocks are absorbed straight from the caller — a
- whole pass over the data removed (helps every SHA user: codesig, CAS, pkg).
-3. **Fused FNV in `link_image_id_compute`.** One pass updating both 64-bit
- streams (each byte read once, the two multiply chains issue in parallel)
- instead of two passes — bit-identical, ~2× on that 27 %.
-
-Result: 256k-symbol link **1.12 s → 0.46 s**; benchmark `symbol-count`
-**2.00× → 0.89× clang** (per-symbol 3897 ns → 1472 ns), i.e. kit's linker is now
-faster than ld64 across the whole axis. The residual large-link top frame is the
-image-id FNV (now ~31 %, but only on pathologically large outputs); switching it
-to the hardware SHA would help further at the cost of changing UUID/build-id
-bytes — deferred.
-
-**Codegen — the type-query path.** On `body-size` (pure per-statement codegen),
-`cg_type_get` was 9.6 % self-time and `_platform_memset` 10 %. Two causes, both
-plumbing waste in the hot per-operand path:
-
-- `type_cg_builtin` (frontend type lowering) fetched **two structs by value per
- call** — `kit_cg_builtin_types` builds + copies the whole ~15-entry id table,
- `kit_compiler_target_spec` memset+copies the spec — to read one field. Added a
- public `kit_cg_builtin_type_id(c, which)` single-id accessor and made the
- target-spec fetch lazy (only the `long`/`long double` cases need it). Killed
- the by-value-copy memsets (19 → 0 sampled, memset 10.2 % → 6.3 %).
-- `cg_type_get` called `cg_api_init_builtins` redundantly per lookup (cg_api_get
- already guarantees init) and went through an un-inlined `cg_api_get` call;
- inlined the already-initialized fast path (load + index, no call).
-
-Result: `body-size` **~2.36 s → ~2.06 s (~13 %)**; `cg_type_get`/`cg_api_get`
-fall out of the top-10. The hot frame is now the **lexer/pp token pump**
-(`lex_next`, `peek`, `pp_next_raw`) — in every compile's path and the clear next
-target (left untouched here: intricate, correctness-sensitive, diffuse gains).
-
-Verified: hash (24 checks + a 17-size `kit hash` vs `shasum` differential across
-every block boundary), link 124, macho 80, elf 41, dwarf, dist 182, tools 45,
-smoke-x64/rv64, cg-api, toy 1392, parse, opt, isa, debug — all green;
-compile+link+run end-to-end correct. (Pre-existing, unrelated:
-`test-driver-cc/cc-print-search-dirs-hosted` greps `<sysroot>/include` but the
-driver emits `<sysroot>/usr/include` for a Linux sysroot — untouched by this
-work.)
-
-### Round 3 — bounded preprocessor memory (O(expansions) → O(depth))
-
-> 2026-06-10. Round 2's note proposed a heap block free-list to kill the
-> residual `arena_fini` teardown. **Measurement vetoed it**: large-block reuse
-> on a single compile is 1.00× (pp-macro: 73,148 allocs, 73,148 peak-live) —
-> blocks accumulate and free once, so a cache only defers the same frees. The
-> real bug it exposed: **`-E` (and `-c` of macro-heavy code) used O(expansions)
-> memory.** Every `subst_phase2` expansion buffer lived in `pp->arena`, which
-> "lives until pp_free" — so peak RSS was **578 MB for 4.8 MB of output**
-> (120×), 1.18 GB at the largest size.
->
-> Fix: a second arena `pp->xarena` holds only the transient expansion scratch
-> (the `tv_grow`/`hsv_grow` token/hideset buffers behind every `SRC_BUF`, arg
-> slices, paste/stringize buffers); `pp_next_raw` **resets it to its high-water
-> mark whenever the source stack drains back to a lexer** (a `SRC_BUF` always
-> sits above every `SRC_LEX`, so a lexer on top ⇒ no expansion buffer live ⇒
-> nothing in xarena is referenced; returned tokens are value copies with
-> pool-interned spellings). Permanent data (macro bodies/params, hidesets,
-> `#include` text) stays in `pp->arena`. The `#if` condition path is the one
-> place transient buffers are read inline rather than via the stack — it runs
-> under `pp->in_if_expansion`, which the reset skips.
-
-| pp-macro `-E` | before → after |
-|---|---|
-| peak RSS @128k | 578 MB → **5 MB** (115×) |
-| peak RSS @512k | 1178 MB → **16 MB** (74×) |
-| live ≥16 KB blocks @512k | 73,148 → **6** |
-| total mallocs @512k | ~75 k → **683** |
-| vs clang `-E` | 0.76× → **0.47× (2.1× faster)** |
-
-Memory is now ~constant in expansion count. Verified byte-identical: test-pp,
-test-parse, test-smoke-x64, 101-file `-E` corpus, pp-macro at 4k/32k/128k. (ASan
-can't catch a premature reset — `arena_reset` reuses memory without freeing —
-so output-diff is the gate.)
-
-### Round 2 — constant factor: zero-churn allocation + buffered IO
-
-> 2026-06-10, M1 (8-core), clang-built `PROFILE=1` release kit, best-of-3.
-> Round 1 made every axis linear; the remaining slowness was a **constant
-> factor** dominated by two things the sampler kept surfacing as kernel time:
-> `mach_vm_reclaim_*` (libmalloc churn) at 50–57 % of compile, and `write` at
-> up to 96 % of `-E`. Both are now gone. **Every compile axis is now faster than
-> clang -O0.**
-
-| axis | kit @maxN before → after | kit/clang before → after |
-|------|:------------------------:|:------------------------:|
-| body-size | 1321 ms → **305 ms** | 1.30× slower → **0.36× (2.8× faster)** |
-| global-decl | 930 ms → **77 ms** | 5.31× slower → **0.48× (2.1× faster)** |
-| fn-count | 403 ms → **129 ms** | 0.33× → **0.13× (7.7× faster)** |
-| ref-density | 565 ms → **240 ms** | 0.16× → **0.08×** |
-| locals-per-fn | 264 ms → **72 ms** | 0.04× → **0.01×** |
-| pp-macro `-E` | 132 µs/exp → **3.7 µs/exp** | 22.1× slower → **0.76× (1.3× faster)** |
-| pp-include | 436 ms → **141 ms** | 1.76× slower → **0.73× (1.4× faster)** |
-| type-decl | 77 ms → **72 ms** | 0.62× → 0.67× |
-| symbol-count | (link) 287 → 302 ms | 1.45× (unchanged — pure linker) |
-
-Allocation is now ~0 per input unit (mallocs scale with arena *blocks*, not
-items); IO is at the buffered ideal (output_bytes / 64 KB writes):
-
-| axis | mallocs/unit before → after | | write() syscalls before → after |
-|------|:---:|---|:---:|
-| body-size (128k stmt) | ~26 (3.3 M total) → **0.007** | obj 9.2 MB | ~thousands → **4** |
-| pp-macro `-E` (128k) | — → **0.15** | out 9.6 MB | **millions → 148** |
-| fn / global / ref | 1–2 → **< 0.07** | | |
-
-**Fixes (all landed, output byte-identical, ASan/UBSan-clean):**
-
-1. **Throwaway type-lowering pool** (`lang/c`). `c_abi_type_info/sizeof/alignof`
- called `type_cg_id`, which spun up and tore down a whole `Pool` (64 KB
- arena) **per query** — every integer literal / `sizeof` / arithmetic
- conversion. That single site was the 50 %+ `mach_vm_reclaim` hotspot (1 M
- 64 KB alloc+free pairs for one 128 k-stmt function). Routed the queries
- through the parser's persistent `p->pool` (matching `cg_adapter`), so
- builtins allocate nothing and records memoize. Removed `type_cg_id`.
-2. **Buffered output writer** (`driver/env/posix.c`). `fdw_write` did one
- `write()` syscall per `KitWriter::write` — and `pp_emit_text` writes once
- per token. Added a 64 KB buffer with flush-on-seek (object emit seeks to
- patch headers) and large-write passthrough. pp-macro `-E` went from millions
- of syscalls to 148.
-3. **Per-token lexer scratch** (`lang/cpp/lex/lex.c`). The pp-number path
- malloc'd a temp buffer per numeric token (splice removal); identifiers
- already had a no-splice fast path. Added the same fast path for numbers and
- a grow-once, high-water `Lexer.scratch` so even the (rare) spliced-token slow
- path never allocates per token. 256 k tiny mallocs → ~0.
-4. **Linkage-name concat** (`src/api/core.c`). `kit_cg_c_linkage_name` malloc'd
- a temp buffer per declared symbol on Mach-O (to prepend `_`); now a 256-byte
- stack buffer, heap only for pathologically long names.
-5. **Shared CFI directive vector** (`src/arch/mc.c`). Each `CfiFde` owned a
- separately heap-allocated `directives` array (a per-function 128-byte
- malloc). Replaced with one growable vector on `MCImpl`; each FDE keeps a
- `(dir_start, ndir)` range — single-pass emission keeps them contiguous.
-
-**Next candidate.** With churn + IO gone, pp-macro `-E` is now CPU-bound on the
-token machinery (`pp_next_raw`/`subst_phase2`/`lex_next`); the #2 self-time
-frame is `arena_fini` — the one-time teardown freeing the accumulated working
-set (hundreds of 64 KB blocks back to libc → `mach_vm_reclaim`). A heap-level
-block free-list (recycle arena-sized blocks instead of returning them to
-libmalloc) would erase that teardown cost and any residual block churn
-systemically.
-
-### Round 1 — linearity (all superlinear axes fixed)
-
-> 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).
+4. **Token-pump sret tax** (deepest; the pp-macro lever). `lex_next` /
+ `src_next_raw` return a 24-byte `Tok` by value, so each token round-trips
+ through an x8 indirect-result stack slot. An out-pointer on the hottest
+ readers (or shrinking `Tok` ≤ 16 B by packing `SrcLoc`) returns it in
+ registers — but `SrcLoc` is load-bearing frontend-wide, so bench-gate it in
+ isolation.
+
+**Deliberately not pursued** (measured dead ends, keep them dead):
+image-id FNV→HW-SHA is a real symbol-count win but changes every executable's
+LC_UUID/build-id bytes (needs a golden regen — separately gated); `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. The residual top frame on pathologically large links is the image-id FNV.
