Skip to content

Commit 10b3b79

Browse files
committed
perf(rust-lsp): O(1) type map in the registry build + macro-expansion dedup
The four kernel rust files' wall time was a CONSTANT ~63.5 s that no resolution-side fix moved -- because it was not resolution. The shared all_defs registry build had two lookups INSIDE its registration loop (receiver auto-registration probe via cbm_registry_lookup_type, and the trait-linkage scan), and before finalize the registry has no buckets: both probes were full linear scans over the types registered so far. On the 1.4M-def shared build that is ~10^10 strcmps ~= 63 s, paid once by the building file while the sibling null-filter files waited on the once-guard for exactly the same wall time. This is the checklist's own lookup-in-registration-loop pattern -- invisible on small per-file builds. Fix: a CBMIdxMemo (new in lsp_neg_memo.h: exact-match, strcmp-verified string-key -> index map, arena-backed, first-put-wins to mirror the linear scans' first-match semantics) maintained alongside every add_type in rust_populate_cross_registry; both probes become O(1). Also rides along: a per-root-invocation macro-expansion memo. Kernel macro_rules are self-recursive (define_sizes! re-invokes itself) and the expansion fallback ("no pattern matched -- still expand the first rule") made recursion non-convergent: unbounded BREADTH under the depth-8 guard turned 2-44 source invocations into ~200k expansions (each a fresh tree-sitter parse of the substituted body). Identical (macro, substituted text) now expands once per chain; the memo resets at each top-level source site so per-site attribution is untouched, and the arg re-parse dedup only applies at recursion depth > 0. Side effect: the eval-step cap no longer exhausts, so a few previously-truncated real calls now resolve (kernel: +25 edges). Verified: kernel rust subtree byte-identical before/after (sorted node and edge sets, exact); rust_lsp suite 506 passed. Signed-off-by: Martin Vogel <[email protected]>
1 parent 2f11a4d commit 10b3b79

3 files changed

Lines changed: 156 additions & 8 deletions

File tree

‎internal/cbm/lsp/lsp_neg_memo.h‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -139,4 +139,92 @@ static inline void cbm_negmemo_insert(CBMNegMemo *m, CBMArena *arena, uint64_t k
139139
}
140140
}
141141

142+
/* ── CBMIdxMemo: exact-match string-key → int index map ─────────────────────
143+
* Companion for build-time registration loops that need "have I registered
144+
* this QN, and at which index?" in O(1) — the registry's own buckets don't
145+
* exist before finalize, and probing it linearly from inside the registration
146+
* loop is the classic quadratic (kernel shared rust registry: ~63 s).
147+
* Exact match: each slot stores the borrowed key pointer and verifies with
148+
* strcmp, so hash collisions can't map to a wrong index. First-put wins. */
149+
typedef struct {
150+
struct cbm_idxmemo_slot {
151+
uint64_t h; /* 0 = empty */
152+
const char *key;
153+
int32_t val;
154+
} *slots;
155+
int cap; /* power of two */
156+
int count;
157+
} CBMIdxMemo;
158+
159+
static inline int32_t cbm_idxmemo_get(const CBMIdxMemo *m, const char *key) {
160+
if (!m->slots || !key || m->count == 0) {
161+
return -1;
162+
}
163+
uint64_t h = cbm_negmemo_key(0, key, NULL);
164+
uint64_t mask = (uint64_t)(m->cap - 1);
165+
for (uint64_t i = h & mask;; i = (i + 1) & mask) {
166+
if (m->slots[i].h == 0) {
167+
return -1;
168+
}
169+
if (m->slots[i].h == h && m->slots[i].key && strcmp(m->slots[i].key, key) == 0) {
170+
return m->slots[i].val;
171+
}
172+
}
173+
}
174+
175+
static inline void cbm_idxmemo_put_raw(struct cbm_idxmemo_slot *slots, int cap, uint64_t h,
176+
const char *key, int32_t val) {
177+
uint64_t mask = (uint64_t)(cap - 1);
178+
for (uint64_t i = h & mask;; i = (i + 1) & mask) {
179+
if (slots[i].h == 0) {
180+
slots[i].h = h;
181+
slots[i].key = key;
182+
slots[i].val = val;
183+
return;
184+
}
185+
if (slots[i].h == h && slots[i].key && strcmp(slots[i].key, key) == 0) {
186+
return; /* first-put wins */
187+
}
188+
}
189+
}
190+
191+
static inline void cbm_idxmemo_put_if_absent(CBMIdxMemo *m, CBMArena *arena, const char *key,
192+
int32_t val) {
193+
if (!arena || !key) {
194+
return;
195+
}
196+
if (!m->slots) {
197+
m->slots = cbm_arena_alloc(arena,
198+
sizeof(struct cbm_idxmemo_slot) * CBM_NEGMEMO_INIT_CAP);
199+
if (!m->slots) {
200+
return;
201+
}
202+
memset(m->slots, 0, sizeof(struct cbm_idxmemo_slot) * CBM_NEGMEMO_INIT_CAP);
203+
m->cap = CBM_NEGMEMO_INIT_CAP;
204+
m->count = 0;
205+
}
206+
if ((int64_t)(m->count + 1) * CBM_NEGMEMO_LOAD_DEN >=
207+
(int64_t)m->cap * CBM_NEGMEMO_LOAD_NUM) {
208+
int new_cap = m->cap * CBM_NEGMEMO_GROW;
209+
struct cbm_idxmemo_slot *ns =
210+
cbm_arena_alloc(arena, sizeof(struct cbm_idxmemo_slot) * (size_t)new_cap);
211+
if (!ns) {
212+
return;
213+
}
214+
memset(ns, 0, sizeof(struct cbm_idxmemo_slot) * (size_t)new_cap);
215+
for (int i = 0; i < m->cap; i++) {
216+
if (m->slots[i].h) {
217+
cbm_idxmemo_put_raw(ns, new_cap, m->slots[i].h, m->slots[i].key, m->slots[i].val);
218+
}
219+
}
220+
m->slots = ns;
221+
m->cap = new_cap;
222+
}
223+
uint64_t h = cbm_negmemo_key(0, key, NULL);
224+
if (cbm_idxmemo_get(m, key) < 0) {
225+
cbm_idxmemo_put_raw(m->slots, m->cap, h, key, val);
226+
m->count++;
227+
}
228+
}
229+
142230
#endif /* CBM_LSP_NEG_MEMO_H */

‎internal/cbm/lsp/rust_lsp.c‎

Lines changed: 56 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@
2929
#include "rust_cargo.h"
3030
#include "../helpers.h"
3131
#include <ctype.h>
32+
#include <stdint.h>
3233
#include <stdio.h>
3334
#include <stdlib.h>
3435
#include <string.h>
@@ -3159,6 +3160,20 @@ static void rust_expand_user_macro(RustLSPContext *ctx, const char *mname, TSNod
31593160
if (!substituted)
31603161
return;
31613162

3163+
/* Expansion memo (see RustLSPContext.macro_memo): reset per top-level
3164+
* invocation, dedup identical (macro, substituted body) within the
3165+
* recursion chain — kills the exponential breadth of self-recursive
3166+
* macro_rules without losing any distinctly-attributed source site. */
3167+
if (ctx->macro_expand_depth == 0 && ctx->macro_memo.slots) {
3168+
memset(ctx->macro_memo.slots, 0, sizeof(uint64_t) * (size_t)ctx->macro_memo.cap);
3169+
ctx->macro_memo.count = 0;
3170+
}
3171+
uint64_t mm_key = cbm_negmemo_key(3, mname, substituted);
3172+
if (cbm_negmemo_contains(&ctx->macro_memo, mm_key)) {
3173+
return;
3174+
}
3175+
cbm_negmemo_insert(&ctx->macro_memo, ctx->arena, mm_key);
3176+
31623177
/* Wrap and parse. */
31633178
char *wrapped = cbm_arena_sprintf(ctx->arena, "fn __cbm_macro_expand() { %s; }\n", substituted);
31643179
if (!wrapped)
@@ -3239,6 +3254,20 @@ static void rust_resolve_macro_arg_exprs(RustLSPContext *ctx, TSNode invocation)
32393254
if (!arg_text)
32403255
return;
32413256

3257+
/* Same expansion memo as rust_expand_user_macro (site tag 4), but ONLY
3258+
* inside a recursion chain (depth > 0): there the identical argument text
3259+
* is re-parsed on every re-expansion of a self-recursive macro and has no
3260+
* distinct source site. Top-level invocations (depth 0) always parse —
3261+
* identical args in different enclosing functions attribute differently
3262+
* and must all be walked. */
3263+
if (ctx->macro_expand_depth > 0) {
3264+
uint64_t am_key = cbm_negmemo_key(4, arg_text, NULL);
3265+
if (cbm_negmemo_contains(&ctx->macro_memo, am_key)) {
3266+
return;
3267+
}
3268+
cbm_negmemo_insert(&ctx->macro_memo, ctx->arena, am_key);
3269+
}
3270+
32423271
/* Wrap the comma-separated arguments in a tuple expression so the whole
32433272
* thing parses as one valid expression (a trailing format-spec arg like
32443273
* `width = w` would otherwise break statement parsing). Calls inside any
@@ -5342,6 +5371,24 @@ static void rust_populate_cross_registry(CBMTypeRegistry *reg, CBMArena *arena,
53425371
cbm_registry_init(reg, arena);
53435372
cbm_rust_stdlib_register(reg, arena);
53445373

5374+
/* qn → (type index + 1), FIRST occurrence wins (mirrors the linear scans
5375+
* this map replaces). Both in-loop registry probes below — the receiver
5376+
* auto-registration check and the trait-linkage lookup — used to scan the
5377+
* UNFINALIZED registry linearly (no buckets exist before finalize): the
5378+
* checklist's lookup-in-registration-loop pattern. Invisible on small
5379+
* per-file builds; on the shared all_defs build (~1.4M entries) those
5380+
* scans were a constant ~63 s of the kernel run — and the sibling
5381+
* null-filter files waited on the build once-guard for exactly that long,
5382+
* which is why no resolution-side fix ever moved their wall time. Index,
5383+
* not pointer, because reg->types reallocs as it grows. */
5384+
CBMIdxMemo type_idx = {0};
5385+
for (int ti = 0; ti < reg->type_count; ti++) {
5386+
const char *qn = reg->types[ti].qualified_name;
5387+
if (qn) {
5388+
cbm_idxmemo_put_if_absent(&type_idx, arena, qn, ti);
5389+
}
5390+
}
5391+
53455392
for (int i = 0; i < def_count; i++) {
53465393
CBMRustLSPDef *d = &defs[i];
53475394
if (!d->qualified_name || !d->short_name || !d->label)
@@ -5358,6 +5405,7 @@ static void rust_populate_cross_registry(CBMTypeRegistry *reg, CBMArena *arena,
53585405
rt.is_interface = d->is_interface || strcmp(d->label, "Trait") == 0 ||
53595406
strcmp(d->label, "Interface") == 0;
53605407
cbm_registry_add_type(reg, rt);
5408+
cbm_idxmemo_put_if_absent(&type_idx, arena, rt.qualified_name, reg->type_count - 1);
53615409
}
53625410

53635411
if (strcmp(d->label, "Function") == 0 || strcmp(d->label, "Method") == 0) {
@@ -5398,13 +5446,15 @@ static void rust_populate_cross_registry(CBMTypeRegistry *reg, CBMArena *arena,
53985446

53995447
if (strcmp(d->label, "Method") == 0 && d->receiver_type && d->receiver_type[0]) {
54005448
rf.receiver_type = cbm_arena_strdup(arena, d->receiver_type);
5401-
if (!cbm_registry_lookup_type(reg, rf.receiver_type)) {
5449+
if (cbm_idxmemo_get(&type_idx, rf.receiver_type) < 0) {
54025450
CBMRegisteredType auto_t;
54035451
memset(&auto_t, 0, sizeof(auto_t));
54045452
auto_t.qualified_name = rf.receiver_type;
54055453
const char *dot = strrchr(d->receiver_type, '.');
54065454
auto_t.short_name = dot ? cbm_arena_strdup(arena, dot + 1) : rf.receiver_type;
54075455
cbm_registry_add_type(reg, auto_t);
5456+
cbm_idxmemo_put_if_absent(&type_idx, arena, auto_t.qualified_name,
5457+
reg->type_count - 1);
54085458
}
54095459
}
54105460

@@ -5413,12 +5463,9 @@ static void rust_populate_cross_registry(CBMTypeRegistry *reg, CBMArena *arena,
54135463
/* If trait_qn set: encode embedded_type linkage on receiver. */
54145464
if (rf.receiver_type && d->trait_qn && d->trait_qn[0]) {
54155465
CBMRegisteredType *rt = NULL;
5416-
for (int ti = 0; ti < reg->type_count; ti++) {
5417-
if (reg->types[ti].qualified_name &&
5418-
strcmp(reg->types[ti].qualified_name, rf.receiver_type) == 0) {
5419-
rt = &reg->types[ti];
5420-
break;
5421-
}
5466+
int32_t tix = cbm_idxmemo_get(&type_idx, rf.receiver_type);
5467+
if (tix >= 0) {
5468+
rt = &reg->types[tix];
54225469
}
54235470
if (rt) {
54245471
int existing = 0;
@@ -5437,7 +5484,8 @@ static void rust_populate_cross_registry(CBMTypeRegistry *reg, CBMArena *arena,
54375484
}
54385485
}
54395486

5440-
/* Finalise the cross-file registry now that all defs are added. */
5487+
/* Finalise the cross-file registry now that all defs are added.
5488+
* (type_idx is arena-owned — freed with the registry's arena.) */
54415489
cbm_registry_finalize(reg);
54425490
}
54435491

‎internal/cbm/lsp/rust_lsp.h‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -174,6 +174,18 @@ typedef struct {
174174

175175
/* CBM_LSP_DEBUG=1 in env enables verbose stderr trace. */
176176
bool debug;
177+
178+
/* Per-ROOT-invocation macro-expansion memo. Kernel macro_rules are often
179+
* self-recursive (define_sizes! re-invokes itself with @internal/@impls
180+
* args) and the expansion fallback ("no pattern matched — still expand the
181+
* first rule") makes that recursion non-convergent: with an unbounded
182+
* BREADTH under the depth-8 guard, 2-44 source invocations exploded into
183+
* ~200k expansions (each a full tree-sitter parse) ≈ 63 s per file.
184+
* Within one expansion chain an identical (macro, substituted body) is
185+
* walked once — identical text implies an identical walk, and recursive
186+
* re-invocations have no distinct source site to attribute. Reset at each
187+
* top-level invocation so distinct source sites keep their attribution. */
188+
CBMNegMemo macro_memo;
177189
} RustLSPContext;
178190

179191
/* Initialise an empty context for processing one file. */

0 commit comments

Comments
 (0)