kit

commit f8c7eacf57f036647a13db18ba687a4160515635
parent 02cecfe1ee79bd72dc1b388ec1d86095da6b2f4b
Author: Ryan Sepassi <rsepassi@gmail.com>
Date:   Sat, 13 Jun 2026 09:25:53 -0700

perf(pool): direct-mapped byte-verified intern cache — skip FNV+probe on repeats

Diffstat:
M
src/core/pool.c
 | 
60
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
M
src/core/pool.h
 | 
16
++++++++++++++++

2 files changed, 75 insertions(+), 1 deletion(-)
diff --git a/src/core/pool.c b/src/core/pool.c
@@ -18,6 +18,19 @@
 #define POOL_TABLE_LOAD_NUM 3
 #define POOL_TABLE_LOAD_DEN 4 /* grow when used*4 >= cap*3 */
 
+/* Cheap fold of (len + the first up-to-4 bytes) into a u32 cache key. This is
+ * deliberately NOT FNV: the whole point of the accelerator cache is to skip the
+ * full hash on repeats, so the key must be a couple of shifts/multiplies, not a
+ * per-byte hash. Collisions are harmless — every cache hit byte-verifies. */
+static u32 pool_icache_fold(const char* s, size_t len) {
+  u32 f = (u32)len * 0x9E3779B1u;
+  if (len > 0) f = (f ^ (u8)s[0]) * 0x01000193u;
+  if (len > 1) f = (f ^ (u8)s[1]) * 0x01000193u;
+  if (len > 2) f = (f ^ (u8)s[2]) * 0x01000193u;
+  if (len > 3) f = (f ^ (u8)s[3]) * 0x01000193u;
+  return f;
+}
+
 static u32 fnv1a(const char* s, size_t len) {
   u32 h = 0x811C9DC5u;
   size_t i;
@@ -94,6 +107,13 @@ void pool_init(Pool* p, Heap* h) {
   p->entries = NULL;
   p->nentries = 0;
   p->entries_cap = 0;
+  /* Direct-mapped intern accelerator, zero-init (sym 0 = empty slot). If the
+   * allocation fails the cache stays NULL and intern simply runs the normal
+   * hash+probe path — it is a pure accelerator. */
+  p->icache = (PoolICacheSlot*)h->alloc(
+      h, sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE, _Alignof(PoolICacheSlot));
+  if (p->icache)
+    memset(p->icache, 0, sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE);
   table_rehash(p, POOL_INITIAL_TABLE_CAP);
   /* Reserve entry 0 as the "none" sentinel. */
   if (entries_grow(p) == 0) {
@@ -108,9 +128,13 @@ void pool_fini(Pool* p) {
   if (p->table) p->heap->free(p->heap, p->table, sizeof(Sym) * p->cap);
   if (p->entries)
     p->heap->free(p->heap, p->entries, sizeof(*p->entries) * p->entries_cap);
+  if (p->icache)
+    p->heap->free(p->heap, p->icache,
+                  sizeof(PoolICacheSlot) * POOL_ICACHE_SIZE);
   arena_fini(&p->arena);
   p->table = NULL;
   p->entries = NULL;
+  p->icache = NULL;
 }
 
 Sym pool_intern_cstr(Pool* p, const char* z) {
@@ -121,9 +145,31 @@ Sym pool_intern_slice(Pool* p, Slice in) {
   const char* s = in.s;
   size_t len = in.len;
   u32 h, mask, i;
+  u32 fold = 0, cidx = 0;
   Sym sym;
 
   if (!s || len == 0) return 0;
+
+  /* Direct-mapped accelerator: try to short-circuit BEFORE FNV+probe. On a hit
+   * we byte-verify against the interned bytes (same compare sym_eq does), so
+   * this can never return a wrong Sym. Misses/mismatches fall through to the
+   * normal path and then re-prime this slot from the result. */
+  if (p->icache) {
+    fold = pool_icache_fold(s, len);
+    cidx = fold & (POOL_ICACHE_SIZE - 1);
+    {
+      const PoolICacheSlot* slot = &p->icache[cidx];
+      if (slot->keyhash == fold && slot->sym != 0) {
+        const PoolEntry* e = &p->entries[slot->sym];
+        if (e->len == (u32)len) {
+          size_t k = 0;
+          while (k < len && e->data[k] == s[k]) ++k;
+          if (k == len) return slot->sym;
+        }
+      }
+    }
+  }
+
   if (p->used >= p->grow_threshold) {
     table_rehash(p, p->cap * 2);
   }
@@ -137,7 +183,14 @@ Sym pool_intern_slice(Pool* p, Slice in) {
     const Sym* table = p->table;
     const PoolEntry* ents = p->entries;
     while ((sym = table[i]) != 0) {
-      if (sym_eq(&ents[sym], s, len, h)) return sym;
+      if (sym_eq(&ents[sym], s, len, h)) {
+        /* Prime the accelerator so the next occurrence skips FNV+probe. */
+        if (p->icache) {
+          p->icache[cidx].keyhash = fold;
+          p->icache[cidx].sym = sym;
+        }
+        return sym;
+      }
       i = (i + 1) & mask;
     }
   }
@@ -168,6 +221,11 @@ Sym pool_intern_slice(Pool* p, Slice in) {
     p->table[i] = sym;
     p->used++;
   }
+  /* Prime the accelerator with the freshly interned spelling. */
+  if (p->icache) {
+    p->icache[cidx].keyhash = fold;
+    p->icache[cidx].sym = sym;
+  }
   return sym;
 }
 
diff --git a/src/core/pool.h b/src/core/pool.h
@@ -12,6 +12,19 @@ typedef struct PoolEntry {
   u32 hash;
 } PoolEntry;
 
+/* Direct-mapped accelerator cache for pool_intern_slice. Keyed on a cheap fold
+ * of (len + the leading bytes), NOT full FNV. A hit byte-verifies via the
+ * interned bytes, so it is a pure accelerator that can never return a wrong
+ * Sym and never affects Sym numbering (a first occurrence still goes through
+ * the normal hash+probe+insert). sym == 0 marks an empty slot. We store only
+ * {keyhash, sym} — never a borrowed input pointer (those aim into transient
+ * lexer buffers). Power-of-two size; mask is POOL_ICACHE_SIZE - 1. */
+#define POOL_ICACHE_SIZE 1024u
+typedef struct PoolICacheSlot {
+  u32 keyhash;
+  Sym sym;
+} PoolICacheSlot;
+
 struct Pool {
   Heap* heap;
   Arena arena; /* string storage */
@@ -26,6 +39,9 @@ struct Pool {
   PoolEntry* entries;
   u32 nentries;
   u32 entries_cap;
+
+  /* Direct-mapped intern accelerator (zero-init = all empty). */
+  PoolICacheSlot* icache;
 };
 
 void pool_init(Pool*, Heap*);