commit 2e236aa0196bbee9a2c39a5e4c4f9786fd963b99
parent 701328a47fd27f1af9f38ce77ee463c3e3cd47e6
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Fri, 12 Jun 2026 13:42:11 -0700
perf(cpp,parse): sym-centric bindings + O(1) hideset dedup (-16% -c on sqlite)
Frontend-bound -O0 throughput work toward the tcc bar. Three byte-identical
structural changes (perf_identity_gate 60/60, sqlite -E bit-identical over
119263 lines, test-pp 110/110, test-parse green):
- New KIT_SYMTAB primitive (include/kit/support/symtab.h): a Sym-indexed dense
value table. kit's Sym ids are dense+monotonic, so a flat array is the
kit-native form of tcc's "binding hung off the interned token" -- one load,
no hashing -- while each layer keeps its own table (cpp<->c boundary intact).
- pp macro table: MacroMap (Sym->Macro* hashmap, mt_get per identifier) ->
MacroTab SymTab (inlined array load).
- parser keyword map: KwMap (Sym->u8 hashmap) -> KwTab SymTab.
- pp hideset dedup: hs_register linearly scanned every hideset in the TU per
macro invocation (the real cost behind the profile's 17.5% hs_add) -> O(1)
content index (Pp.hs_index). Ids still assigned in first-appearance order,
so output is bit-identical.
- pp per-token hideset: uniform macro-body buffers now share one
TokSrc.hs_uniform (push_buf_uniform) instead of a parallel HidesetId array;
only the non-uniform arg-prescan path keeps the array. Perf-neutral,
memory/structure cleanup.
sqlite -c 3.37B -> 2.84B instructions (~5.0x -> ~4.2x tcc); -E 1.89B -> 1.42B
(-24.6%). PERF.md refreshed with the post-change profile (lex_next now ~56%,
the new frontier) and a Resolved-levers section.
Diffstat:
7 files changed, 322 insertions(+), 124 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -35,15 +35,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)** | 3.40 B | 0.89 B | 0.28 s | 5.12 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 |
| clang 22 | 8.73 B | 2.57 B | 0.81 s | 1.50 MB |
-† low-load reading; re-confirm on a quiet machine.
+† 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).
kit beats clang on compile speed and is the fastest *general* backend here, but
-**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.)
+**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.)
### Reproducing the detailed measurements
@@ -96,9 +99,11 @@ 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.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 %.**
+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
+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:
@@ -127,14 +132,41 @@ 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 (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
-the other **~86 %**. (The synthetic `bench-cc` axes below over-weight codegen by
-construction; trust the sqlite profile for where to spend effort.)
+### 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
@@ -144,46 +176,54 @@ 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` | 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).
+**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.
+
+| 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).
### 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
- level. `scope_lookup` is already cheap (lazy index), so this is lower-priority
- now, but it removes the residual per-identifier probes.
+1. **The scanner loop** (`lex_next`, 56 % — now 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
+ (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).
## The synthetic scaling benchmark (`make bench-cc`)
diff --git a/include/kit/support/symtab.h b/include/kit/support/symtab.h
@@ -0,0 +1,90 @@
+#ifndef KIT_SUPPORT_SYMTAB_H
+#define KIT_SUPPORT_SYMTAB_H
+
+/* Sym-indexed dense value table — the O(1) "binding hung off the interned
+ * symbol", expressed for kit's dense-Sym world.
+ *
+ * The interner hands out Sym ids that are small, dense, and monotonic. That
+ * makes a flat array indexed by Sym the kit-native form of the trick a
+ * monolithic compiler plays by storing a field on each interned token (tcc's
+ * TokenSym.sym_define / sym_identifier, etc.): one bounds check and one load,
+ * no hashing and no probe loop. Crucially, each consumer keeps its OWN table,
+ * so a layer can bind a Sym (the preprocessor: Sym -> Macro*; the parser:
+ * Sym -> keyword id) without any shared per-symbol struct — the module
+ * boundary stays intact and there is no global state.
+ *
+ * Use a SymTab for a hot per-identifier "what is bound to this Sym" lookup
+ * that a KIT_HASHMAP keyed on Sym would otherwise serve. Prefer KIT_HASHMAP
+ * when the key is not a dense Sym, when the table is sparse over a huge key
+ * space, or when iteration over entries is needed (a SymTab does not
+ * enumerate). Pair this with the heap conventions of kit/support/hashmap.h.
+ *
+ * KIT_SYMTAB_DEFINE(NAME, T)
+ * NAME — typedef name for the table instance.
+ * T — element (value) type. The zero value of T is the "unbound"
+ * sentinel returned for any Sym never set: NULL for a pointer T,
+ * 0 for an integer T. Pick T so that 0 means "no binding".
+ *
+ * Emits typedef NAME and these static functions:
+ * void NAME##_init (NAME*, KitHeap*)
+ * void NAME##_fini (NAME*)
+ * T NAME##_get (const NAME*, uint32_t sym) — zero(T) if sym unbound
+ * void NAME##_set (NAME*, uint32_t sym, T val) — grows to cover sym
+ *
+ * _get never allocates and never grows; it is the read side of the hot path.
+ * _set grows the backing array (doubling, new region zero-filled) so a later
+ * _get of any sym set so far is a plain in-range load. Storage is one
+ * contiguous heap block; growth reallocs through the KitHeap (which frees the
+ * old block), so a long-lived table set across a wide Sym range does not leak
+ * intermediate buffers the way an arena-backed grow would.
+ */
+
+#include <kit/core.h>
+#include <stdint.h>
+#include <string.h>
+
+#if defined(__GNUC__) || defined(__clang__)
+#define KIT_SYMTAB_UNUSED __attribute__((unused))
+#else
+#define KIT_SYMTAB_UNUSED
+#endif
+
+#define KIT_SYMTAB_DEFINE(NAME, T) \
+ typedef struct NAME { \
+ KitHeap* heap; \
+ T* v; /* dense, indexed by Sym; [0,cap) live + zero-defaulted */ \
+ uint32_t cap; /* number of slots allocated */ \
+ } NAME; \
+ \
+ KIT_SYMTAB_UNUSED static inline void NAME##_init(NAME* t, KitHeap* h) { \
+ t->heap = h; \
+ t->v = NULL; \
+ t->cap = 0; \
+ } \
+ \
+ KIT_SYMTAB_UNUSED static inline void NAME##_fini(NAME* t) { \
+ if (t->v) t->heap->free(t->heap, t->v, sizeof(T) * t->cap); \
+ t->v = NULL; \
+ t->cap = 0; \
+ } \
+ \
+ KIT_SYMTAB_UNUSED static inline T NAME##_get(const NAME* t, uint32_t sym) { \
+ return sym < t->cap ? t->v[sym] : (T)0; \
+ } \
+ \
+ KIT_SYMTAB_UNUSED static inline void NAME##_set(NAME* t, uint32_t sym, \
+ T val) { \
+ if (sym >= t->cap) { \
+ uint32_t nc = t->cap ? t->cap * 2u : 64u; \
+ while (nc <= sym) nc *= 2u; \
+ t->v = (T*)t->heap->realloc(t->heap, t->v, sizeof(T) * t->cap, \
+ sizeof(T) * nc, _Alignof(T)); \
+ memset(t->v + t->cap, 0, sizeof(T) * (nc - t->cap)); \
+ t->cap = nc; \
+ } \
+ t->v[sym] = val; \
+ } \
+ /* trailing struct decl swallows the macro-call's semicolon */ \
+ struct NAME
+
+#endif /* KIT_SUPPORT_SYMTAB_H */
diff --git a/lang/c/parse/parse.c b/lang/c/parse/parse.c
@@ -1637,11 +1637,11 @@ void parse_c(Compiler* c, Pool* pool, Pp* pp, DeclTable* decls, CG* cg,
/* Index storage for the scope/tag tables and the external-function table all
* comes from the arena via the pool's shared arena-heap facade. */
ExternalFuncMap_init(&p.external_funcs, &p.pool->arena_heap);
- KwMap_init(&p.kw_map, &p.pool->arena_heap);
+ KwTab_init(&p.kw_map, &p.pool->arena_heap);
for (i = (CKw)1; i < KW_COUNT; ++i) {
p.kw_sym[i] = kit_sym_intern(p.pool->c, kit_slice_cstr(kw_names[i]));
- (void)KwMap_set(&p.kw_map, p.kw_sym[i], (u8)i); /* canonical keyword */
+ (void)KwTab_set(&p.kw_map, p.kw_sym[i], (u8)i); /* canonical keyword */
}
p.sym_b_alloca = kit_sym_intern(p.pool->c, KIT_SLICE_LIT("__builtin_alloca"));
@@ -1734,14 +1734,14 @@ void parse_c(Compiler* c, Pool* pool, Pp* pp, DeclTable* decls, CG* cg,
/* GNU alias spellings -> their canonical CKw. Registered after the canonical
* keywords above so the canonical mapping always wins (matching the old
* ident_kw_inline fall-through, which scanned kw_sym[] before the aliases). */
- (void)KwMap_set(&p.kw_map, p.sym_alignof_alias, (u8)KW_ALIGNOF);
- (void)KwMap_set(&p.kw_map, p.sym_asm_alias, (u8)KW_BUILTIN_ASM);
- (void)KwMap_set(&p.kw_map, p.sym_inline_alias, (u8)KW_INLINE);
- (void)KwMap_set(&p.kw_map, p.sym_inline_alias2, (u8)KW_INLINE);
- (void)KwMap_set(&p.kw_map, p.sym_restrict_alias, (u8)KW_RESTRICT);
- (void)KwMap_set(&p.kw_map, p.sym_restrict_alias2, (u8)KW_RESTRICT);
- (void)KwMap_set(&p.kw_map, p.sym_thread_alias, (u8)KW_THREAD_LOCAL);
- (void)KwMap_set(&p.kw_map, p.sym_volatile_alias, (u8)KW_VOLATILE);
+ (void)KwTab_set(&p.kw_map, p.sym_alignof_alias, (u8)KW_ALIGNOF);
+ (void)KwTab_set(&p.kw_map, p.sym_asm_alias, (u8)KW_BUILTIN_ASM);
+ (void)KwTab_set(&p.kw_map, p.sym_inline_alias, (u8)KW_INLINE);
+ (void)KwTab_set(&p.kw_map, p.sym_inline_alias2, (u8)KW_INLINE);
+ (void)KwTab_set(&p.kw_map, p.sym_restrict_alias, (u8)KW_RESTRICT);
+ (void)KwTab_set(&p.kw_map, p.sym_restrict_alias2, (u8)KW_RESTRICT);
+ (void)KwTab_set(&p.kw_map, p.sym_thread_alias, (u8)KW_THREAD_LOCAL);
+ (void)KwTab_set(&p.kw_map, p.sym_volatile_alias, (u8)KW_VOLATILE);
p.sym_int128 = kit_sym_intern(p.pool->c, KIT_SLICE_LIT("__int128"));
p.sym_int128_t = kit_sym_intern(p.pool->c, KIT_SLICE_LIT("__int128_t"));
p.sym_uint128_t = kit_sym_intern(p.pool->c, KIT_SLICE_LIT("__uint128_t"));
diff --git a/lang/c/parse/parse_priv.h b/lang/c/parse/parse_priv.h
@@ -7,6 +7,7 @@
#pragma once
#include <kit/support/hashmap.h>
+#include <kit/support/symtab.h>
#include <stdarg.h>
#include <string.h>
@@ -166,11 +167,11 @@ KIT_HASHMAP_DEFINE(TagEntryMap, Sym, TagEntry*, kit_hash_u32);
KIT_HASHMAP_DEFINE(ExternalFuncMap, Sym, SymEntry*, kit_hash_u32);
/* Interned keyword/alias Sym -> CKw (stored as u8), built once in parse_c.
- * Replaces the per-identifier linear scan of kw_sym[] (plus the alias compares)
- * with a single O(1) probe: every non-keyword identifier (variable / typedef /
- * field name) previously scanned all ~52 keyword syms before returning KW_NONE.
+ * Sym-indexed dense table: classifying an identifier is one in-range load,
+ * no hashing. Most identifiers in a body are interned after the keyword set
+ * (higher Sym than kw_cap), so they classify as KW_NONE without even a load.
* Storage comes from the pool's shared arena-heap facade (Pool.arena_heap). */
-KIT_HASHMAP_DEFINE(KwMap, Sym, u8, kit_hash_u32);
+KIT_SYMTAB_DEFINE(KwTab, u8);
typedef struct Scope Scope;
struct Scope {
@@ -243,7 +244,7 @@ typedef struct Parser {
int has_pending;
Sym kw_sym[KW_COUNT];
- KwMap kw_map; /* keyword/alias Sym -> CKw; built once, see ident_kw_inline */
+ KwTab kw_map; /* keyword/alias Sym -> CKw; built once, see ident_kw_inline */
Sym sym_b_alloca;
Sym sym_b_ctz;
@@ -462,8 +463,7 @@ static inline int is_pp_hash(const Tok* t) { return t->kind == TOK_PP_HASH; }
* with no separate "alias-aware" path. Everything below (and the per-token
* classify_kw / is_kw adapters) routes through this. */
static inline CKw ident_kw_inline(const Parser* p, Sym name) {
- const u8* v = name ? KwMap_get(&p->kw_map, name) : NULL;
- return v ? (CKw)*v : KW_NONE;
+ return name ? (CKw)KwTab_get(&p->kw_map, name) : KW_NONE;
}
/* A token's keyword identity (KW_NONE for a non-identifier or non-keyword). The
diff --git a/lang/cpp/pp/pp.c b/lang/cpp/pp/pp.c
@@ -63,7 +63,7 @@ void src_next_raw_into(Pp* pp, Tok* out, HidesetId* hs_out, u8* src_kind_out) {
if (s->kind == SRC_BUF) {
if (s->i < s->n) {
*out = s->toks[s->i];
- if (hs_out) *hs_out = s->hs ? s->hs[s->i] : HS_EMPTY;
+ if (hs_out) *hs_out = s->hs ? s->hs[s->i] : s->hs_uniform;
if (src_kind_out) *src_kind_out = SRC_BUF;
++s->i;
return;
@@ -138,6 +138,21 @@ void push_buf(Pp* pp, Tok* toks, HidesetId* hs, u32 n) {
src_push(pp, s);
}
+/* Push a buffer whose tokens all share one hideset (the common macro-body
+ * case): no per-token array, just the scalar in hs_uniform (read when
+ * TokSrc.hs is NULL). */
+void push_buf_uniform(Pp* pp, Tok* toks, u32 n, HidesetId hs_uniform) {
+ TokSrc s;
+ memset(&s, 0, sizeof(s));
+ s.kind = SRC_BUF;
+ s.toks = toks;
+ s.hs = NULL;
+ s.hs_uniform = hs_uniform;
+ s.i = 0;
+ s.n = n;
+ src_push(pp, s);
+}
+
/* ============================================================
* Public streaming entries
* ============================================================ */
@@ -834,7 +849,12 @@ Pp* pp_new(Compiler* c) {
pp, NULL, 0, sizeof(Hideset*) * pp->hsets_cap, _Alignof(Hideset*));
pp->hsets[0] = NULL;
pp->hsets_n = 1;
- MacroMap_init_cap(&pp->mtab, h, 32u);
+ pp->hs_index_cap = 64;
+ pp->hs_index_used = 0;
+ pp->hs_index = (HidesetId*)pp_xrealloc(
+ pp, NULL, 0, sizeof(HidesetId) * pp->hs_index_cap, _Alignof(HidesetId));
+ memset(pp->hs_index, 0, sizeof(HidesetId) * pp->hs_index_cap);
+ MacroTab_init(&pp->macros, h);
pp_intern_keywords(pp);
compute_date_time(pp);
pp_register_static_predefined(pp);
@@ -849,8 +869,9 @@ void pp_free(Pp* pp) {
/* Pop / close any remaining lex sources. */
while (pp->nsources) src_pop(pp);
pp_xfree(pp, pp->sources, sizeof(TokSrc) * pp->sources_cap);
- MacroMap_fini(&pp->mtab);
+ MacroTab_fini(&pp->macros);
pp_xfree(pp, pp->hsets, sizeof(Hideset*) * pp->hsets_cap);
+ pp_xfree(pp, pp->hs_index, sizeof(HidesetId) * pp->hs_index_cap);
pp_xfree(pp, pp->ifstk, sizeof(IfFrame) * pp->ifstk_cap);
pp_xfree(pp, pp->inc_dirs, sizeof(*pp->inc_dirs) * pp->inc_dirs_cap);
c_pool_free(pp->pool);
diff --git a/lang/cpp/pp/pp_expand.c b/lang/cpp/pp/pp_expand.c
@@ -17,21 +17,56 @@ static int sym_in_array(const Sym* a, u32 n, Sym s) {
return 0;
}
+/* FNV-1a over the (sorted) Sym array — the dedup index key. */
+static u32 hs_hash(const Sym* names, u32 n) {
+ u32 h = 0x811C9DC5u, i;
+ for (i = 0; i < n; ++i) {
+ h ^= names[i];
+ h *= 0x01000193u;
+ }
+ return h;
+}
+
+/* Re-place every live hideset (ids 1..hsets_n-1) into a freshly zeroed index
+ * of capacity nc (a power of two). Called when the load factor crosses 3/4. */
+static void hs_index_rebuild(Pp* pp, u32 nc) {
+ u32 mask, k;
+ pp->hs_index = (HidesetId*)pp_xrealloc(
+ pp, pp->hs_index, sizeof(HidesetId) * pp->hs_index_cap,
+ sizeof(HidesetId) * nc, _Alignof(HidesetId));
+ for (k = 0; k < nc; ++k) pp->hs_index[k] = 0;
+ pp->hs_index_cap = nc;
+ mask = nc - 1;
+ for (k = 1; k < pp->hsets_n; ++k) {
+ u32 i = pp->hsets[k]->hash & mask;
+ while (pp->hs_index[i] != 0) i = (i + 1) & mask;
+ pp->hs_index[i] = (HidesetId)k;
+ }
+}
+
+/* Intern a hideset: return the canonical id for `names` (content-deduplicated),
+ * allocating a new one on first sight. Ids are assigned in first-appearance
+ * order (identical to the historical linear scan — the id is internal-only, but
+ * the order match keeps the dedup behavior bit-for-bit). */
static HidesetId hs_register(Pp* pp, const Sym* names, u32 n) {
Hideset* h;
- u32 i;
+ u32 hash, mask, i, j;
+ HidesetId id;
if (n == 0) return HS_EMPTY;
- /* Linear search for an existing identical hideset. Hidesets are tiny. */
- for (i = 1; i < pp->hsets_n; ++i) {
- Hideset* e = pp->hsets[i];
- if (e->n != n) continue;
- {
- u32 j;
+ hash = hs_hash(names, n);
+ mask = pp->hs_index_cap - 1;
+ i = hash & mask;
+ /* Probe for an existing identical hideset; the loop also lands `i` on the
+ * first empty slot for this hash, which is where a miss inserts. */
+ while ((id = pp->hs_index[i]) != 0) {
+ Hideset* e = pp->hsets[id];
+ if (e->hash == hash && e->n == n) {
for (j = 0; j < n; ++j)
if (e->names[j] != names[j]) break;
- if (j == n) return (HidesetId)i;
+ if (j == n) return id;
}
+ i = (i + 1) & mask;
}
if (pp->hsets_n == pp->hsets_cap) {
@@ -45,9 +80,15 @@ static HidesetId hs_register(Pp* pp, const Sym* names, u32 n) {
sizeof(Hideset) + sizeof(Sym) * (n ? n - 1 : 0),
_Alignof(Hideset));
h->n = n;
- for (i = 0; i < n; ++i) h->names[i] = names[i];
- pp->hsets[pp->hsets_n] = h;
- return (HidesetId)pp->hsets_n++;
+ h->hash = hash;
+ for (j = 0; j < n; ++j) h->names[j] = names[j];
+ id = (HidesetId)pp->hsets_n;
+ pp->hsets[pp->hsets_n++] = h;
+ /* Insert at the empty slot the probe found, then grow+rehash if loaded. */
+ pp->hs_index[i] = id;
+ if (++pp->hs_index_used * 4u >= pp->hs_index_cap * 3u)
+ hs_index_rebuild(pp, pp->hs_index_cap * 2u);
+ return id;
}
int hs_contains(Pp* pp, HidesetId id, Sym s) {
@@ -87,25 +128,10 @@ HidesetId hs_add(Pp* pp, HidesetId id, Sym s) {
}
/* ============================================================
- * Macro table
- * ============================================================ */
-
-/* Thin wrappers over the generated MacroMap_* functions; preserved
- * because the call sites are tagged "mt_*" throughout this TU. */
-Macro* mt_get(Pp* pp, Sym name) {
- Macro** v = MacroMap_get(&pp->mtab, name);
- return v ? *v : NULL;
-}
-
-void mt_put(Pp* pp, Sym name, Macro* m) {
- (void)MacroMap_set(&pp->mtab, name, m);
-}
-
-void mt_del(Pp* pp, Sym name) { MacroMap_del(&pp->mtab, name); }
-
-/* ============================================================
* #define / #undef
* ============================================================ */
+/* mt_get / mt_put / mt_del are inlined Sym-indexed loads in pp_priv.h
+ * (MacroTab, a SYMTAB mapping Sym -> Macro*). */
void do_define(Pp* pp, const Tok* line, u32 n) {
Macro* m;
@@ -338,7 +364,6 @@ static void expand_object_macro(Pp* pp, const Macro* m, const Tok* invoke,
TokVec body = {0};
Tok* tmp;
HidesetId hs;
- HidesetId* hids;
u32 i;
if (m->body_len == 0) {
@@ -359,9 +384,7 @@ static void expand_object_macro(Pp* pp, const Macro* m, const Tok* invoke,
for (i = 0; i < body.n; ++i) body.data[i].loc = invoke->loc;
hs = hs_add(pp, invoke_hs, m->name);
- hids = arena_array(pp->xarena, HidesetId, body.n);
- for (i = 0; i < body.n; ++i) hids[i] = hs;
- push_buf(pp, body.data, hids, body.n);
+ push_buf_uniform(pp, body.data, body.n, hs);
}
/* ============================================================
@@ -888,15 +911,9 @@ static int try_expand_func_macro(Pp* pp, const Macro* m, const Tok* invoke,
result_hs = hs_add(pp, invoke_hs, m->name);
substitute_body(pp, m, &args, invoke, &body);
- {
- u32 i;
- HidesetId* hids = arena_array(pp->xarena, HidesetId, body.n ? body.n : 1);
- /* result_hs is uniform across the entire substituted body, so fill it
- * directly — like the object-macro path — instead of materializing a
- * parallel hideset token vector. */
- for (i = 0; i < body.n; ++i) hids[i] = result_hs;
- push_buf(pp, body.data, hids, body.n);
- }
+ /* result_hs is uniform across the entire substituted body, so push it as a
+ * single-hideset buffer — no per-token parallel array. */
+ push_buf_uniform(pp, body.data, body.n, result_hs);
return 1;
}
@@ -943,7 +960,7 @@ void pp_next_raw_into(Pp* pp, Tok* out) {
(s = &pp->sources[pp->nsources - 1])->kind == SRC_BUF &&
s->i < s->n) {
*out = s->toks[s->i];
- hs = s->hs ? s->hs[s->i] : HS_EMPTY;
+ hs = s->hs ? s->hs[s->i] : s->hs_uniform;
src_kind = SRC_BUF;
++s->i;
} else {
diff --git a/lang/cpp/pp/pp_priv.h b/lang/cpp/pp/pp_priv.h
@@ -8,6 +8,8 @@
#include <stdlib.h>
#include <string.h>
+#include <kit/support/symtab.h>
+
#include "cpp_support.h"
#include "pp/pp.h"
@@ -35,11 +37,17 @@ typedef struct Macro {
u32 body_len;
} Macro;
+/* MacroTab = Sym -> Macro* (NULL = not a macro). Sym-indexed dense table:
+ * the macro binding is read with one in-range load on every identifier in
+ * the expander's hot loop, replacing a per-identifier hashmap probe. */
+KIT_SYMTAB_DEFINE(MacroTab, Macro*);
+
typedef u32 HidesetId;
#define HS_EMPTY 0u
typedef struct Hideset {
u32 n;
+ u32 hash; /* content hash of names[0..n) — dedup index key (see hs_register) */
Sym names[1]; /* flexible; allocated with extra trailing slots */
} Hideset;
@@ -57,7 +65,14 @@ typedef struct TokSrc {
Lexer* lex;
/* SRC_BUF */
Tok* toks;
+ /* Per-token hidesets. When `hs` is non-NULL it is a parallel array (one id
+ * per token) — used only by the argument-prescan path, where tokens can
+ * carry differing hidesets. When `hs` is NULL the whole buffer shares the
+ * single `hs_uniform` id: macro-body expansions (object- and function-like)
+ * are uniform, so they take this path and skip the per-token array entirely
+ * (no alloc, no fill, one scalar instead of n copies). */
HidesetId* hs;
+ HidesetId hs_uniform;
u32 i;
u32 n;
/* #line state (SRC_LEX only). line_delta is added to every emitted
@@ -88,11 +103,8 @@ typedef struct IfFrame {
SrcLoc loc;
} IfFrame;
-/* MacroMap = Sym -> Macro*. Generated open-addressed hashmap with
- * deletion (#undef). See core/hashmap.h. */
+/* Sym-keyed hashmaps below (include caches). See core/hashmap.h. */
#include <kit/support/hashmap.h>
-static inline u32 macro_hash_(Sym s) { return kit_hash_u32((u32)s); }
-KIT_HASHMAP_DEFINE(MacroMap, Sym, Macro*, macro_hash_);
/* IncCache = Sym(resolved-path) -> cached header bytes. The same guarded
* header included many times across a TU is read from disk once; later
@@ -137,8 +149,8 @@ struct Pp {
u32 nsources;
u32 sources_cap;
- /* Macro table (open-addressed; key = Sym, value = Macro*). */
- MacroMap mtab;
+ /* Macro table (Sym-indexed dense; value = Macro*, NULL = not a macro). */
+ MacroTab macros;
/* Header-content cache (key = interned resolved-path Sym, value =
* arena-resident bytes). Collapses N re-includes of the same header to
@@ -162,6 +174,13 @@ struct Pp {
Hideset** hsets;
u32 hsets_n;
u32 hsets_cap;
+ /* Content-addressed dedup index over hsets: open-addressed, power-of-two,
+ * slot holds a HidesetId (0 = empty). Replaces the O(n) linear scan in
+ * hs_register with an O(1) probe — the per-macro-invocation dedup was the
+ * superlinear cost on macro-heavy input. */
+ HidesetId* hs_index;
+ u32 hs_index_cap;
+ u32 hs_index_used;
/* Include directories (stage 9). */
struct {
@@ -360,6 +379,7 @@ Tok src_next_raw(Pp* pp, HidesetId* hs_out, u8* src_kind_out);
void src_push(Pp* pp, TokSrc s);
void src_pop(Pp* pp);
void push_buf(Pp* pp, Tok* toks, HidesetId* hs, u32 n);
+void push_buf_uniform(Pp* pp, Tok* toks, u32 n, HidesetId hs_uniform);
/* pp_next_raw is the mutual-recursion entry: expand_arg_to_eof calls it,
* and pp_next_raw drives directives and expansion. Declared non-static so
@@ -372,11 +392,21 @@ Tok pp_next_raw(Pp* pp);
/* --- pp_expand.c → pp.c, pp_directive.c --- */
HidesetId hs_add(Pp* pp, HidesetId id, Sym s);
int hs_contains(Pp* pp, HidesetId id, Sym s);
-Macro* mt_get(Pp* pp, Sym name);
-void mt_put(Pp* pp, Sym name, Macro* m);
-void mt_del(Pp* pp, Sym name);
void expand_arg_to_eof(Pp* pp, Tok* in, HidesetId* hs, u32 nin, TokVec* out);
+/* Macro binding lookup/define/undef. Inlined Sym-indexed loads (no hashmap
+ * probe): mt_get runs on every identifier the expander sees. NULL/absent =
+ * not a macro; #undef stores NULL. */
+static inline Macro* mt_get(Pp* pp, Sym name) {
+ return MacroTab_get(&pp->macros, name);
+}
+static inline void mt_put(Pp* pp, Sym name, Macro* m) {
+ MacroTab_set(&pp->macros, name, m);
+}
+static inline void mt_del(Pp* pp, Sym name) {
+ MacroTab_set(&pp->macros, name, NULL);
+}
+
/* --- pp_directive.c → pp_expand.c --- */
i64 eval_if_expr(Pp* pp, const Tok* line, u32 n, SrcLoc loc);
void process_directive(Pp* pp, SrcLoc hash_loc);
