commit b073810bd67ba34a5f4f213fa3899d6df6f03429
parent 8e8000ef0e4b077ea707cf17e46d23b2695af928
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Wed, 10 Jun 2026 21:31:58 -0700
perf(types): hash-cons structural types; drop O(n) derived-list scan
type_ptr/array/func and qualified non-tagged types were interned by a linear
scan of one flat per-pool derived list, which grows O(types) — so each
construction was O(types) and a type-population-heavy TU was O(n^2). Replace the
scan with an open-addressed structural intern table keyed on kind/qual + the
kind-specific identity fields (field-wise hash+eq, never a raw memcmp).
Tagged types (struct/union/enum) keep their existing declaration-identity list
and exact memcmp semantics — only the high-volume structural types move. Their
nodes are now arena-allocated without zeroing (the table compares fields, not
bytes), removing the per-node memset for the common case.
type-decl axis 1234ms -> 1078ms (-12.6%); object output byte-identical across the
toy/parse/derived-type corpora. Verified: test-cg-api/toy/parse/isa/opt/debug/
dwarf/smoke-x64 all green.
Diffstat:
| M | lang/c/type/type.c | | | 306 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------- |
1 file changed, 243 insertions(+), 63 deletions(-)
diff --git a/lang/c/type/type.c b/lang/c/type/type.c
@@ -37,10 +37,30 @@ struct CgRecordMemo {
KitCgTypeId id;
};
+/* Open-addressed structural intern table for derived types whose identity is
+ * STRUCTURAL — pointer / array / function, and qualified variants of any
+ * non-tagged type. Slots hold the canonical Type*; lookup hashes and compares
+ * only the kind-specific identity fields (never a raw memcmp), so structural
+ * nodes need no zeroing and their padding is irrelevant. Tagged types
+ * (struct/union/enum) are interned by declaration identity instead and live on
+ * `derived`. Replaces the former O(n) linear scan of the whole derived list —
+ * that scan was O(types * derivations), catastrophic on type-population-heavy
+ * TUs. The table backing array is arena-allocated; old arrays leak into the
+ * arena and are reclaimed wholesale at pool teardown (no fini hook). */
+typedef struct TypeInternTable {
+ const Type** slots; /* cap entries, power-of-two; NULL == empty */
+ u32 cap;
+ u32 used;
+} TypeInternTable;
+
typedef struct PoolTypeCache {
/* Direct slots for void + primitive kinds (TY_VOID..TY_LDOUBLE). */
const Type* prim[NUM_PRIM_KINDS];
- /* Linked list of every other type allocated through this pool. */
+ /* Structurally-interned ptr/array/func + qualified non-tagged types. */
+ TypeInternTable structural;
+ /* Identity-interned tagged types (struct/union/enum, qualified or not) and
+ * the throwaway record-builder results: a list, scanned only by the (rare)
+ * tag-based type_qualified / type_unqual paths and never per derivation. */
TypeListNode* derived;
/* Completed record layout ids are compiler-local. */
CgRecordMemo* cg_record_memos;
@@ -68,6 +88,115 @@ static Type* alloc_type_node(Pool* p, PoolTypeCache* c) {
return &n->ty;
}
+/* Bare structural-type node: arena-allocated, NOT linked into `derived`, NOT
+ * zeroed. Each constructor writes exactly the fields its kind reads; the
+ * structural table compares those fields (not raw bytes), so the union tail and
+ * padding may stay uninitialized. */
+static Type* alloc_struct_type(Pool* p) { return arena_new(p->arena, Type); }
+
+static u32 type_fnv_ptr(u32 h, const void* q) {
+ u64 u = (u64)(uintptr_t)q;
+ h = (h ^ (u32)u) * 16777619u;
+ h = (h ^ (u32)(u >> 32)) * 16777619u;
+ return h;
+}
+
+/* Structural hash over a (non-tagged) derived type's identity fields. */
+static u32 type_struct_hash(const Type* t) {
+ u32 h = 2166136261u;
+ h = (h ^ (u32)t->kind) * 16777619u;
+ h = (h ^ (u32)t->qual) * 16777619u;
+ switch (t->kind) {
+ case TY_PTR:
+ h = type_fnv_ptr(h, t->ptr.pointee);
+ break;
+ case TY_ARRAY:
+ h = type_fnv_ptr(h, t->arr.elem);
+ h = (h ^ t->arr.count) * 16777619u;
+ h = (h ^ (u32)t->arr.incomplete) * 16777619u;
+ break;
+ case TY_FUNC: {
+ u16 i;
+ h = type_fnv_ptr(h, t->fn.ret);
+ h = (h ^ (u32)t->fn.nparams) * 16777619u;
+ h = (h ^ (u32)t->fn.variadic) * 16777619u;
+ for (i = 0; i < t->fn.nparams; ++i) h = type_fnv_ptr(h, t->fn.params[i]);
+ break;
+ }
+ default: /* qualified primitive: kind + qual is the whole key */
+ break;
+ }
+ return h;
+}
+
+static int type_struct_eq(const Type* a, const Type* b) {
+ if (a->kind != b->kind || a->qual != b->qual) return 0;
+ switch (a->kind) {
+ case TY_PTR:
+ return a->ptr.pointee == b->ptr.pointee;
+ case TY_ARRAY:
+ return a->arr.elem == b->arr.elem && a->arr.count == b->arr.count &&
+ a->arr.incomplete == b->arr.incomplete;
+ case TY_FUNC: {
+ u16 i;
+ if (a->fn.ret != b->fn.ret || a->fn.nparams != b->fn.nparams ||
+ a->fn.variadic != b->fn.variadic)
+ return 0;
+ for (i = 0; i < a->fn.nparams; ++i)
+ if (a->fn.params[i] != b->fn.params[i]) return 0;
+ return 1;
+ }
+ default: /* qualified primitive: kind + qual already matched */
+ return 1;
+ }
+}
+
+static const Type* type_intern_find(const TypeInternTable* tab,
+ const Type* probe, u32 h) {
+ u32 mask, i;
+ const Type* s;
+ if (!tab->slots) return NULL;
+ mask = tab->cap - 1u;
+ i = h & mask;
+ while ((s = tab->slots[i]) != NULL) {
+ if (type_struct_eq(s, probe)) return s;
+ i = (i + 1u) & mask;
+ }
+ return NULL;
+}
+
+/* Insert a freshly built canonical node. Best-effort under OOM: on a failed
+ * grow the node is simply not interned (a later identical query allocates a
+ * duplicate — correct, just unshared), matching the arena/buf failure policy. */
+static void type_intern_add(Pool* p, TypeInternTable* tab, const Type* t,
+ u32 h) {
+ u32 mask, i;
+ if (!tab->slots || (tab->used + 1u) * 4u >= tab->cap * 3u) {
+ u32 ncap = tab->cap ? tab->cap * 2u : 64u;
+ const Type** ns = arena_zarray(p->arena, const Type*, ncap);
+ if (!ns) return;
+ if (tab->slots) {
+ u32 nmask = ncap - 1u, k;
+ for (k = 0; k < tab->cap; ++k) {
+ const Type* s = tab->slots[k];
+ u32 j;
+ if (!s) continue;
+ j = type_struct_hash(s) & nmask;
+ while (ns[j]) j = (j + 1u) & nmask;
+ ns[j] = s;
+ }
+ }
+ tab->slots = ns;
+ tab->cap = ncap;
+ }
+ if (!tab->slots) return;
+ mask = tab->cap - 1u;
+ i = h & mask;
+ while (tab->slots[i]) i = (i + 1u) & mask;
+ tab->slots[i] = t;
+ tab->used++;
+}
+
const Type* type_void(Pool* p) { return type_prim(p, TY_VOID); }
const Type* type_prim(Pool* p, TypeKind kind) {
@@ -85,61 +214,72 @@ const Type* type_prim(Pool* p, TypeKind kind) {
const Type* type_ptr(Pool* p, const Type* pointee) {
PoolTypeCache* c = cache_get(p);
+ Type probe;
+ u32 h;
+ const Type* found;
+ Type* t;
if (!c) return NULL;
- /* Linear search; small N in practice. */
- for (TypeListNode* n = c->derived; n; n = n->next) {
- if (n->ty.kind == TY_PTR && n->ty.qual == 0 &&
- n->ty.ptr.pointee == pointee) {
- return &n->ty;
- }
- }
- Type* t = alloc_type_node(p, c);
+ probe.kind = TY_PTR;
+ probe.qual = 0;
+ probe.ptr.pointee = pointee;
+ h = type_struct_hash(&probe);
+ found = type_intern_find(&c->structural, &probe, h);
+ if (found) return found;
+ t = alloc_struct_type(p);
if (!t) return NULL;
t->kind = TY_PTR;
t->qual = 0;
t->ptr.pointee = pointee;
+ type_intern_add(p, &c->structural, t, h);
return t;
}
const Type* type_array(Pool* p, const Type* elem, u32 count, int incomplete) {
PoolTypeCache* c = cache_get(p);
+ Type probe;
+ u32 h;
+ const Type* found;
+ Type* t;
if (!c) return NULL;
- for (TypeListNode* n = c->derived; n; n = n->next) {
- if (n->ty.kind == TY_ARRAY && n->ty.qual == 0 && n->ty.arr.elem == elem &&
- n->ty.arr.count == count &&
- n->ty.arr.incomplete == (u8)(incomplete ? 1 : 0)) {
- return &n->ty;
- }
- }
- Type* t = alloc_type_node(p, c);
+ probe.kind = TY_ARRAY;
+ probe.qual = 0;
+ probe.arr.elem = elem;
+ probe.arr.count = count;
+ probe.arr.incomplete = (u8)(incomplete ? 1 : 0);
+ h = type_struct_hash(&probe);
+ found = type_intern_find(&c->structural, &probe, h);
+ if (found) return found;
+ t = alloc_struct_type(p);
if (!t) return NULL;
t->kind = TY_ARRAY;
t->qual = 0;
t->arr.elem = elem;
t->arr.count = count;
t->arr.incomplete = (u8)(incomplete ? 1 : 0);
+ type_intern_add(p, &c->structural, t, h);
return t;
}
-static int param_arrays_eq(const Type* const* a, const Type* const* b, u16 n) {
- for (u16 i = 0; i < n; ++i)
- if (a[i] != b[i]) return 0;
- return 1;
-}
-
const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
int variadic) {
PoolTypeCache* c = cache_get(p);
+ Type probe;
+ u32 h;
+ const Type* found;
+ Type* t;
if (!c) return NULL;
- for (TypeListNode* nd = c->derived; nd; nd = nd->next) {
- if (nd->ty.kind == TY_FUNC && nd->ty.qual == 0 && nd->ty.fn.ret == ret &&
- nd->ty.fn.nparams == n &&
- nd->ty.fn.variadic == (u8)(variadic ? 1 : 0) &&
- param_arrays_eq(nd->ty.fn.params, params, n)) {
- return &nd->ty;
- }
- }
- Type* t = alloc_type_node(p, c);
+ /* Borrow the caller's params array for the lookup; type_struct_eq compares it
+ * element-wise. Only on a miss do we allocate a persistent copy. */
+ probe.kind = TY_FUNC;
+ probe.qual = 0;
+ probe.fn.ret = ret;
+ probe.fn.params = params;
+ probe.fn.nparams = n;
+ probe.fn.variadic = (u8)(variadic ? 1 : 0);
+ h = type_struct_hash(&probe);
+ found = type_intern_find(&c->structural, &probe, h);
+ if (found) return found;
+ t = alloc_struct_type(p);
if (!t) return NULL;
t->kind = TY_FUNC;
t->qual = 0;
@@ -154,6 +294,7 @@ const Type* type_func(Pool* p, const Type* ret, const Type** params, u16 n,
} else {
t->fn.params = NULL;
}
+ type_intern_add(p, &c->structural, t, h);
return t;
}
@@ -164,25 +305,44 @@ const Type* type_qualified(Pool* p, const Type* base, u16 qual) {
if (!base || qual == 0) return base;
c = cache_get(p);
if (!c) return NULL;
- /* Build the comparison template once, via assignment (not aggregate
- * initialization). Struct assignment copies the full object representation,
- * including padding bytes, so the memcmp below is byte-stable against the
- * interned nodes (which are likewise produced by `*t = tmpl`). An aggregate
- * *initializer* (`Type tmpl = *base;`) is lowered as a field-by-field copy
- * that leaves padding unspecified, which would make this memcmp miss and
- * intern a duplicate qualified type. See type_unqual for the same idiom. */
- tmpl = *base;
- tmpl.qual = qual;
- for (TypeListNode* n = c->derived; n; n = n->next) {
- if (n->ty.kind == base->kind && n->ty.qual == qual &&
- memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) {
- return &n->ty;
+ if (base->kind == TY_STRUCT || base->kind == TY_UNION ||
+ base->kind == TY_ENUM) {
+ /* Tagged types are identity-interned on `derived`. Build the comparison
+ * template via assignment (not aggregate initialization). Struct assignment
+ * copies the full object representation, including padding bytes, so the
+ * memcmp below is byte-stable against the interned nodes (which are likewise
+ * produced by `*t = tmpl`). An aggregate *initializer* (`Type tmpl =
+ * *base;`) is lowered as a field-by-field copy that leaves padding
+ * unspecified, which would make this memcmp miss and intern a duplicate. */
+ tmpl = *base;
+ tmpl.qual = qual;
+ for (TypeListNode* n = c->derived; n; n = n->next) {
+ if (n->ty.kind == base->kind && n->ty.qual == qual &&
+ memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) {
+ return &n->ty;
+ }
}
+ t = alloc_type_node(p, c);
+ if (!t) return NULL;
+ *t = tmpl;
+ return t;
+ }
+ /* Non-tagged: structurally interned (qualified prim / ptr / array / func). */
+ {
+ Type probe = *base;
+ u32 h;
+ const Type* found;
+ probe.qual = qual;
+ h = type_struct_hash(&probe);
+ found = type_intern_find(&c->structural, &probe, h);
+ if (found) return found;
+ t = alloc_struct_type(p);
+ if (!t) return NULL;
+ *t = *base;
+ t->qual = qual;
+ type_intern_add(p, &c->structural, t, h);
+ return t;
}
- t = alloc_type_node(p, c);
- if (!t) return NULL;
- *t = tmpl;
- return t;
}
/* ---- aggregates ---- */
@@ -306,24 +466,44 @@ const Type* type_unqual(Pool* p, const Type* t) {
return type_prim(p, (TypeKind)t->kind);
c = cache_get(p);
if (!c) return NULL;
- if ((t->kind == TY_STRUCT || t->kind == TY_UNION) &&
- t->rec.tag_id != TAG_NONE) {
- for (TypeListNode* n = c->derived; n; n = n->next) {
- if (n->ty.kind == t->kind && n->ty.qual == 0 &&
- n->ty.rec.tag_id == t->rec.tag_id && !n->ty.rec.incomplete) {
- return &n->ty;
+ if (t->kind == TY_STRUCT || t->kind == TY_UNION || t->kind == TY_ENUM) {
+ /* Tagged types are identity-interned on `derived`. */
+ if ((t->kind == TY_STRUCT || t->kind == TY_UNION) &&
+ t->rec.tag_id != TAG_NONE) {
+ for (TypeListNode* n = c->derived; n; n = n->next) {
+ if (n->ty.kind == t->kind && n->ty.qual == 0 &&
+ n->ty.rec.tag_id == t->rec.tag_id && !n->ty.rec.incomplete) {
+ return &n->ty;
+ }
}
}
+ tmpl = *t;
+ tmpl.qual = 0;
+ for (TypeListNode* n = c->derived; n; n = n->next) {
+ if (memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) return &n->ty;
+ }
+ nt = alloc_type_node(p, c);
+ if (!nt) return NULL;
+ *nt = tmpl;
+ return nt;
}
- tmpl = *t;
- tmpl.qual = 0;
- for (TypeListNode* n = c->derived; n; n = n->next) {
- if (memcmp(&n->ty, &tmpl, sizeof(Type)) == 0) return &n->ty;
+ /* Non-tagged: structurally interned (qualified prim is handled above as a
+ * prim; here that leaves ptr / array / func). */
+ {
+ Type probe = *t;
+ u32 h;
+ const Type* found;
+ probe.qual = 0;
+ h = type_struct_hash(&probe);
+ found = type_intern_find(&c->structural, &probe, h);
+ if (found) return found;
+ nt = alloc_struct_type(p);
+ if (!nt) return NULL;
+ *nt = *t;
+ nt->qual = 0;
+ type_intern_add(p, &c->structural, nt, h);
+ return nt;
}
- nt = alloc_type_node(p, c);
- if (!nt) return NULL;
- *nt = tmpl;
- return nt;
}
const Type* type_promoted(Pool* p, const Type* t) {
