kit

commit 5ff33ea3ab65aa517e6dbb0e50f6c9734d18fe1d
parent 39c384b15f4d072000fa24e54ed52c85de2d4c38
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Sat, 13 Jun 2026 11:44:36 -0700

perf(parse): Sym-keyed binding cache — scope_lookup in one load (A1)

(cherry picked from commit 28b2fd7ed7831a9a71a9f82c5b038645bf590232)

Diffstat:
M
lang/c/parse/parse.c
 | 
22
+++++++++++++++++++++-
M
lang/c/parse/parse_priv.h
 | 
18
++++++++++++++++++

2 files changed, 39 insertions(+), 1 deletion(-)
diff --git a/lang/c/parse/parse.c b/lang/c/parse/parse.c
@@ -307,6 +307,14 @@ void scope_push(Parser* p) { p->scope = scope_new(p, p->scope); }
 
 void scope_pop(Parser* p) {
   if (p->scope) {
+    /* Unwind the binding cache: walk the popped scope's LIFO list head-first
+     * (newest define first) so multiple same-scope shadows of one Sym restore
+     * to the pre-scope value. e->shadowed is the binding that was current when
+     * e was defined, i.e. the value bind[name] must return once this scope is
+     * gone. */
+    SymEntry* e;
+    for (e = p->scope->entries; e; e = e->next)
+      if (e->name) BindingTab_set(&p->bind, e->name, e->shadowed);
     p->vla_mark = p->scope->saved_vla_mark;
     p->scope = p->scope->parent;
   }
@@ -352,10 +360,12 @@ SymEntry* scope_define(Parser* p, Sym name, SymEntryKind kind,
   e->name = name;
   e->kind = (u8)kind;
   e->type = type;
+  if (name) e->shadowed = BindingTab_get(&p->bind, name);
   e->next = s->entries;
   s->entries = e;
   s->nentries++;
   scope_entries_index_put(p, s, e);
+  if (name) BindingTab_set(&p->bind, name, e);
   return e;
 }
 
@@ -376,7 +386,10 @@ static SymEntry* scope_lookup_from(Scope* from, Sym name) {
 }
 
 SymEntry* scope_lookup(Parser* p, Sym name) {
-  return scope_lookup_from(p->scope, name);
+  /* Sym-keyed cache: the innermost-visible binding in one load. Equivalent to
+   * scope_lookup_from(p->scope, name) by construction (the cache tracks the
+   * newest define per scope and unwinds on pop); no caller passes name == 0. */
+  return name ? BindingTab_get(&p->bind, name) : NULL;
 }
 
 static void sym_set_decl(SymEntry* e, DeclId id, DeclStorage storage,
@@ -436,6 +449,11 @@ static SymEntry* scope_define_checked(Parser* p, Sym name, SymEntryKind kind,
   e->name = name;
   e->kind = (u8)kind;
   e->type = type;
+  /* The shadowed binding is the current innermost-visible one (== bind_get),
+   * not `prior`: prior is the current-scope prior (used only for the redef
+   * rule) and may be NULL while an outer binding exists, which must be the
+   * value restored on pop. */
+  if (name) e->shadowed = BindingTab_get(&p->bind, name);
   if (name && s->emap.cap) {
     /* Active index: prepend to the LIFO list, then fold the prior-read and the
      * index install into a single probe (newest define wins). */
@@ -457,6 +475,7 @@ static SymEntry* scope_define_checked(Parser* p, Sym name, SymEntryKind kind,
       scope_entries_index_build(p, s);
   }
   reject_redef_on(p, prior, kind, type);
+  if (name) BindingTab_set(&p->bind, name, e);
   return e;
 }
 
@@ -1635,6 +1654,7 @@ void parse_c(Compiler* c, Pool* pool, Pp* pp, DeclTable* decls, CG* cg,
    * comes from the arena via the pool's shared arena-heap facade. */
   ExternalFuncMap_init(&p.external_funcs, &p.pool->arena_heap);
   KwTab_init(&p.kw_map, &p.pool->arena_heap);
+  BindingTab_init(&p.bind, &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]));
diff --git a/lang/c/parse/parse_priv.h b/lang/c/parse/parse_priv.h
@@ -141,6 +141,13 @@ struct SymEntry {
    */
   Sym reg_asm_name;
   SymEntry* next;
+  /* The binding that was current for this entry's name (in the innermost
+   * visible scope) at the moment this entry was defined; 0 = none. The
+   * Sym-keyed BindingTab cache on Parser restores bind[name] = shadowed when
+   * this entry's scope is popped, so scope_lookup is one array load instead of
+   * a scope-chain walk. memset-0 by scope_define/_checked, so default is NULL.
+   */
+  SymEntry* shadowed;
 };
 
 typedef struct TagEntry TagEntry;
@@ -173,6 +180,14 @@ KIT_HASHMAP_DEFINE(ExternalFuncMap, Sym, SymEntry*, kit_hash_u32);
  * Storage comes from the pool's shared arena-heap facade (Pool.arena_heap). */
 KIT_SYMTAB_DEFINE(KwTab, u8);
 
+/* Interned identifier Sym -> the SymEntry currently visible for that name (the
+ * innermost binding a scope-chain walk would return), or NULL when unbound.
+ * scope_define/_checked maintain it (newest define wins, prior saved in
+ * SymEntry.shadowed); scope_pop unwinds it. Lets scope_lookup be a single
+ * in-range load instead of a per-nesting-level scope_entries_find walk. Storage
+ * comes from the pool's shared arena-heap facade (Pool.arena_heap). */
+KIT_SYMTAB_DEFINE(BindingTab, SymEntry*);
+
 typedef struct Scope Scope;
 struct Scope {
   SymEntry* entries; /* LIFO */
@@ -340,6 +355,9 @@ typedef struct Parser {
   Sym sym_sync_synchronize;  /* __sync_synchronize (legacy full barrier) */
 
   Scope* scope;
+  /* Sym -> innermost-visible binding cache; the O(1) read side of scope_lookup.
+   * Maintained by scope_define/_checked (write) and scope_pop (restore). */
+  BindingTab bind;
   /* name -> current file-scope function entry. Replaces what was an O(n) linear
    * list walked on every function declaration/reference. Storage comes from the
    * pool's shared arena-heap facade (Pool.arena_heap). */