Skip to content

Commit 793716d

Browse files
committed
perf(lsp): index C++ short-name type lookups
Avoid repeated full type-registry scans in the namespaced-type fallback. Build the optional index only for C/C++ cross registries while preserving candidate order, post-finalize tails, and allocation fallback. Refs #1677 Signed-off-by: astandrik <[email protected]>
1 parent 49d928b commit 793716d

4 files changed

Lines changed: 223 additions & 11 deletions

File tree

‎internal/cbm/lsp/c_lsp.c‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2818,7 +2818,10 @@ static const CBMRegisteredFunc *c_lookup_member_depth(CLSPContext *ctx, const ch
28182818
const char *shortn = dot ? dot + 1 : type_qn;
28192819
size_t slen = strlen(shortn);
28202820
const char *best_qn = NULL;
2821-
for (int i = 0; i < ctx->registry->type_count; i++) {
2821+
CBMTypeNameIter it;
2822+
cbm_registry_types_by_short_name(ctx->registry, shortn, &it);
2823+
int i;
2824+
while ((i = cbm_type_name_iter_next(&it)) >= 0) {
28222825
const char *q = ctx->registry->types[i].qualified_name;
28232826
if (!q) {
28242827
continue;
@@ -5972,6 +5975,7 @@ CBMTypeRegistry *cbm_c_build_cross_registry(CBMArena *arena, CBMLSPDef *defs, in
59725975
c_register_lsp_defs(arena, reg, "", d, 1);
59735976
}
59745977
cbm_registry_finalize(reg);
5978+
cbm_registry_build_type_short_index(reg);
59755979
reg->read_only = true; /* seal: shared Tier-2 registry is read-only during resolve */
59765980
return reg;
59775981
}
@@ -6055,6 +6059,7 @@ void cbm_run_c_lsp_cross(CBMArena *arena, const char *source, int source_len, co
60556059
// Finalize registry — O(1) lookups. See go_lsp.c "3c. Finalize"
60566060
// comment for the rationale (linear-scan fallback otherwise).
60576061
cbm_registry_finalize(&reg);
6062+
cbm_registry_build_type_short_index(&reg);
60586063

60596064
// Initialize context and run
60606065
CLSPContext ctx;

‎internal/cbm/lsp/type_registry.c‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -167,6 +167,51 @@ static void build_type_embed_index(CBMTypeRegistry *reg, CBMArena *idx_arena) {
167167
reg->type_embed_entry_count = idx;
168168
}
169169

170+
/* Optional index: final qualified-name segment -> chain of TYPE indices.
171+
* Descending iteration plus prepend preserves ascending registry scan order.
172+
* Consumers opt in after the QN index captures the finalized tail boundary. */
173+
void cbm_registry_build_type_short_index(CBMTypeRegistry *reg) {
174+
if (!reg || !reg->arena || !reg->type_qn_buckets || reg->type_qn_bucket_count <= 0)
175+
return;
176+
CBMArena *idx_arena = reg->arena;
177+
int count = 0;
178+
for (int i = 0; i < reg->type_count; i++) {
179+
if (reg->types[i].qualified_name)
180+
count++;
181+
}
182+
if (count == 0)
183+
return;
184+
int bucket_count = next_pow2(count * 2);
185+
if (bucket_count < 16)
186+
bucket_count = 16;
187+
int *buckets = (int *)cbm_arena_alloc(idx_arena, (size_t)bucket_count * sizeof(int));
188+
CBMRegistryHashEntry *entries = (CBMRegistryHashEntry *)cbm_arena_alloc(
189+
idx_arena, (size_t)count * sizeof(CBMRegistryHashEntry));
190+
if (!buckets || !entries)
191+
return;
192+
for (int i = 0; i < bucket_count; i++)
193+
buckets[i] = -1;
194+
int idx = 0;
195+
for (int i = reg->type_count - 1; i >= 0; i--) {
196+
const char *qn = reg->types[i].qualified_name;
197+
if (!qn)
198+
continue;
199+
const char *dot = strrchr(qn, '.');
200+
const char *short_name = dot ? dot + 1 : qn;
201+
uint64_t h = fnv1a(short_name);
202+
int slot = (int)(h & (uint64_t)(bucket_count - 1));
203+
entries[idx].hash = h;
204+
entries[idx].payload_index = i;
205+
entries[idx].next_index = buckets[slot];
206+
entries[idx].slot = slot;
207+
buckets[slot] = idx;
208+
idx++;
209+
}
210+
reg->type_short_buckets = buckets;
211+
reg->type_short_entries = entries;
212+
reg->type_short_bucket_count = bucket_count;
213+
}
214+
170215
/* Index: short_name -> chain of FREE-function (receiver_type==NULL) indices.
171216
* Descending-iterate + prepend for ascending chain order (as above). */
172217
static void build_ffunc_short_index(CBMTypeRegistry *reg, CBMArena *idx_arena) {
@@ -208,6 +253,43 @@ static void build_ffunc_short_index(CBMTypeRegistry *reg, CBMArena *idx_arena) {
208253
reg->ffunc_short_entry_count = idx;
209254
}
210255

256+
void cbm_registry_types_by_short_name(const CBMTypeRegistry *reg, const char *short_name,
257+
CBMTypeNameIter *out) {
258+
out->reg = reg;
259+
out->hash = fnv1a(short_name);
260+
if (reg->type_qn_buckets && reg->type_qn_bucket_count > 0) {
261+
if (reg->type_short_buckets && reg->type_short_bucket_count > 0) {
262+
int slot = (int)(out->hash & (uint64_t)(reg->type_short_bucket_count - 1));
263+
out->chain_idx = reg->type_short_buckets[slot];
264+
out->tail_i = reg->type_qn_entry_count;
265+
} else {
266+
out->chain_idx = -1;
267+
out->tail_i = 0; /* auxiliary-index allocation failed: preserve full-scan semantics */
268+
}
269+
out->tail_end = reg->type_count;
270+
} else {
271+
out->chain_idx = -1;
272+
out->tail_i = 0;
273+
out->tail_end = reg->type_count;
274+
}
275+
}
276+
277+
int cbm_type_name_iter_next(CBMTypeNameIter *it) {
278+
const CBMTypeRegistry *reg = it->reg;
279+
while (it->chain_idx >= 0) {
280+
const CBMRegistryHashEntry *e = &reg->type_short_entries[it->chain_idx];
281+
int p = e->payload_index;
282+
uint64_t h = e->hash;
283+
it->chain_idx = e->next_index;
284+
if (h != it->hash)
285+
continue;
286+
return p;
287+
}
288+
if (it->tail_i < it->tail_end)
289+
return it->tail_i++;
290+
return -1;
291+
}
292+
211293
void cbm_registry_types_by_embedded_bare(const CBMTypeRegistry *reg, const char *bare,
212294
CBMTypeEmbedIter *out) {
213295
out->reg = reg;

‎internal/cbm/lsp/type_registry.h‎

Lines changed: 30 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -111,9 +111,14 @@ typedef struct CBMTypeRegistry {
111111
int method_bucket_count;
112112
int method_entry_count;
113113

114-
// Auxiliary short-name / embedded-type indexes (built by finalize alongside the
115-
// QN buckets). Turn the Rust trait- and free-function fallback scans from
116-
// O(type_count)/O(func_count) into O(chain). Read-only after finalize.
114+
// Auxiliary short-name / embedded-type indexes. The type short-name index is
115+
// opt-in after finalize; the others are built by finalize. Current C/C++ cross
116+
// registries opt in, while other languages incur no construction cost.
117+
// Type short-name index: fnv1a(last-'.'-segment of qualified_name) -> chain
118+
// of TYPE indices. payload_index = type index.
119+
int *type_short_buckets;
120+
CBMRegistryHashEntry *type_short_entries;
121+
int type_short_bucket_count;
117122
// Embedded-type index: fnv1a(bare last-'.'-segment of each embedded_type) -> chain
118123
// of TYPE indices declaring it. payload_index = type index (a type may appear once
119124
// per embedded entry; consumers dedup adjacent same-type via the iterator).
@@ -156,6 +161,11 @@ void cbm_registry_finalize(CBMTypeRegistry *reg);
156161
// there add GBs across a large repo (FastAPI incremental test: +1.1 GB RSS).
157162
void cbm_registry_finalize_into(CBMTypeRegistry *reg, CBMArena *idx_arena);
158163

164+
// Build the optional final-QN-segment type index. Call immediately after
165+
// finalization. Consumers that do not opt in avoid its type_count-sized allocation
166+
// and scan. Allocation failure preserves the iterator's linear fallback.
167+
void cbm_registry_build_type_short_index(CBMTypeRegistry *reg);
168+
159169
// Register a function/method.
160170
void cbm_registry_add_func(CBMTypeRegistry *reg, CBMRegisteredFunc func);
161171

@@ -215,8 +225,24 @@ const CBMRegisteredFunc *cbm_registry_lookup_symbol_by_types(const CBMTypeRegist
215225
const CBMType **arg_types,
216226
int arg_count);
217227

218-
// --- Auxiliary index iterators (Rust trait / free-function fallback fast paths) ---
228+
// --- Auxiliary index iterators (language fallback fast paths) ---
219229
//
230+
// Iterate registry TYPE indices whose qualified-name final segment may equal
231+
// `short_name`. When the optional index is present this walks its hash chain plus
232+
// any post-finalize tail; otherwise it degrades to the original full scan. Results
233+
// preserve ascending registry order. The index is a hash prefilter; callers must
234+
// re-check their exact predicate, including tail entries.
235+
typedef struct {
236+
const CBMTypeRegistry *reg;
237+
uint64_t hash;
238+
int chain_idx;
239+
int tail_i;
240+
int tail_end;
241+
} CBMTypeNameIter;
242+
void cbm_registry_types_by_short_name(const CBMTypeRegistry *reg, const char *short_name,
243+
CBMTypeNameIter *out);
244+
int cbm_type_name_iter_next(CBMTypeNameIter *it);
245+
220246
// Iterate registry TYPE indices whose embedded_types contain an entry whose BARE
221247
// name (last '.'-segment) equals `bare`. On a finalized registry this walks the
222248
// embedded-type index plus any post-finalize tail; on an unfinalized registry it

‎tests/test_c_lsp.c‎

Lines changed: 105 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -15250,12 +15250,9 @@ TEST(clsp_tier2_shared_registry_readonly_c) {
1525015250
PASS();
1525115251
}
1525215252

15253-
/* Direct guard for the finalize-time short-name / embedded-type indexes and their
15254-
* iterators (type_registry.c), which the Rust trait/free-func fast paths rely on.
15255-
* Verifies: embed index yields exactly the types whose embedded_types carry a
15256-
* matching BARE name, in ascending registry order, deduped when a type lists the
15257-
* same bare twice; free-func index yields only free funcs (receiver_type==NULL) with
15258-
* the given short_name, not methods. */
15253+
/* Direct guard for the type-name / embedded-type / free-function registry
15254+
* indexes and their iterators (type_registry.c). Verifies that every iterator
15255+
* preserves ascending registry order, which is part of resolver tie-breaking. */
1525915256
TEST(registry_short_name_indexes) {
1526015257
CBMArena arena;
1526115258
cbm_arena_init(&arena);
@@ -15288,6 +15285,25 @@ TEST(registry_short_name_indexes) {
1528815285
t.short_name = "C";
1528915286
t.embedded_types = c_emb;
1529015287
cbm_registry_add_type(&reg, t);
15288+
memset(&t, 0, sizeof(t));
15289+
t.qualified_name = "other.Trait";
15290+
t.short_name = "Trait";
15291+
cbm_registry_add_type(&reg, t);
15292+
memset(&t, 0, sizeof(t));
15293+
t.qualified_name = "Trait";
15294+
t.short_name = "Trait";
15295+
cbm_registry_add_type(&reg, t);
15296+
15297+
/* Populate enough distinct names to force many hash-bucket collisions, with
15298+
* repeated short names spread across the registry. The differential check
15299+
* below compares the index against the exact former linear-scan order. */
15300+
for (int i = 0; i < 512; i++) {
15301+
memset(&t, 0, sizeof(t));
15302+
t.qualified_name = cbm_arena_sprintf(&arena, "bulk.mod%d.Name%d", i, i % 23);
15303+
ASSERT_NOT_NULL(t.qualified_name);
15304+
t.short_name = strrchr(t.qualified_name, '.') + 1;
15305+
cbm_registry_add_type(&reg, t);
15306+
}
1529115307

1529215308
/* free func "helper" (x2 — different QNs), method "M.helper", free func "other". */
1529315309
CBMRegisteredFunc f;
@@ -15310,6 +15326,54 @@ TEST(registry_short_name_indexes) {
1531015326
cbm_registry_add_func(&reg, f);
1531115327

1531215328
cbm_registry_finalize(&reg);
15329+
cbm_registry_build_type_short_index(&reg);
15330+
15331+
/* Qualified-name bare segment "Trait": types 0, 4, then the bare-QN type
15332+
* 5. C-LSP applies its stricter dotted-QN predicate on top of this index. */
15333+
CBMTypeNameIter nit;
15334+
cbm_registry_types_by_short_name(&reg, "Trait", &nit);
15335+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 0);
15336+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 4);
15337+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 5);
15338+
ASSERT_EQ(cbm_type_name_iter_next(&nit), -1);
15339+
cbm_registry_types_by_short_name(&reg, "Missing", &nit);
15340+
ASSERT_EQ(cbm_type_name_iter_next(&nit), -1);
15341+
15342+
for (int name_i = 0; name_i < 23; name_i++) {
15343+
char short_name[32];
15344+
snprintf(short_name, sizeof(short_name), "Name%d", name_i);
15345+
cbm_registry_types_by_short_name(&reg, short_name, &nit);
15346+
int linear_i = 0;
15347+
for (;;) {
15348+
int expected = -1;
15349+
while (linear_i < reg.type_count) {
15350+
int candidate = linear_i++;
15351+
const char *qn = reg.types[candidate].qualified_name;
15352+
const char *last_dot = qn ? strrchr(qn, '.') : NULL;
15353+
const char *candidate_short = last_dot ? last_dot + 1 : qn;
15354+
if (candidate_short && strcmp(candidate_short, short_name) == 0) {
15355+
expected = candidate;
15356+
break;
15357+
}
15358+
}
15359+
15360+
int actual;
15361+
for (;;) {
15362+
actual = cbm_type_name_iter_next(&nit);
15363+
if (actual < 0)
15364+
break;
15365+
const char *qn = reg.types[actual].qualified_name;
15366+
const char *last_dot = qn ? strrchr(qn, '.') : NULL;
15367+
const char *candidate_short = last_dot ? last_dot + 1 : qn;
15368+
if (candidate_short && strcmp(candidate_short, short_name) == 0)
15369+
break;
15370+
}
15371+
15372+
ASSERT_EQ(actual, expected);
15373+
if (expected < 0)
15374+
break;
15375+
}
15376+
}
1531315377

1531415378
/* Embed index for bare "Trait": types 1 (A) then 2 (B), ascending, B once. */
1531515379
CBMTypeEmbedIter it;
@@ -15339,6 +15403,41 @@ TEST(registry_short_name_indexes) {
1533915403
ASSERT_EQ(cbm_free_func_iter_next(&fit), 3);
1534015404
ASSERT_EQ(cbm_free_func_iter_next(&fit), -1);
1534115405

15406+
/* A type appended after finalize is covered by the iterator tail. If the
15407+
* auxiliary allocation is unavailable, the iterator falls back to the same
15408+
* complete linear scan rather than silently dropping candidates. Keep this
15409+
* after the other iterator assertions because their tails intentionally
15410+
* expose post-finalize candidates for caller-side exact filtering too. */
15411+
int tail_type_i = reg.type_count;
15412+
memset(&t, 0, sizeof(t));
15413+
t.qualified_name = "tail.Trait";
15414+
t.short_name = "Trait";
15415+
cbm_registry_add_type(&reg, t);
15416+
cbm_registry_types_by_short_name(&reg, "Trait", &nit);
15417+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 0);
15418+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 4);
15419+
ASSERT_EQ(cbm_type_name_iter_next(&nit), 5);
15420+
ASSERT_EQ(cbm_type_name_iter_next(&nit), tail_type_i);
15421+
ASSERT_EQ(cbm_type_name_iter_next(&nit), -1);
15422+
15423+
int *saved_type_short_buckets = reg.type_short_buckets;
15424+
reg.type_short_buckets = NULL;
15425+
cbm_registry_types_by_short_name(&reg, "Trait", &nit);
15426+
int fallback_expected[] = {0, 4, 5, tail_type_i};
15427+
int fallback_count = 0;
15428+
int candidate;
15429+
while ((candidate = cbm_type_name_iter_next(&nit)) >= 0) {
15430+
const char *qn = reg.types[candidate].qualified_name;
15431+
const char *last_dot = qn ? strrchr(qn, '.') : NULL;
15432+
const char *candidate_short = last_dot ? last_dot + 1 : qn;
15433+
if (!candidate_short || strcmp(candidate_short, "Trait") != 0)
15434+
continue;
15435+
ASSERT_TRUE(fallback_count < 4);
15436+
ASSERT_EQ(candidate, fallback_expected[fallback_count++]);
15437+
}
15438+
ASSERT_EQ(fallback_count, 4);
15439+
reg.type_short_buckets = saved_type_short_buckets;
15440+
1534215441
cbm_arena_destroy(&arena);
1534315442
PASS();
1534415443
}

0 commit comments

Comments
 (0)