Skip to content

Commit a4c0ffb

Browse files
committed
perf(cs): eliminate the C# corpus-proportional scans — 1211s -> 450s, +37% edges
Four measured changes on the dotnet/runtime corpus (58,656 files; every step's numbers below are from full-corpus runs on the same host, baselines captured this session; v0.9.0 = 444.3 s): 1. Two-phase cs registry build (types -> finalize -> funcs), the same pre-finalize linear-lookup disease fixed for Java: prepare 280 -> 140 s. 2. C# import-context carve-out: cs_import_types lists namespace_declaration (for namespace-name mapping) and using_statement (C#'s RAII block — a grammar-name collision), so EVERY namespaced C# file's whole body ran with inside_import=true. That both suppressed ordinary usage extraction under namespaces and sent every identifier through the ancestor-walking import-binding check (tree-sitter's ts_node_parent re-descends from the root, so wide files went quadratic: one 147 KB JIT torture file cost 490 s; 6.8 s after). Only using_directive / namespace_use_declaration open an import scope now. Restores the suppressed usages: edges 4,291,387 -> 5,869,093 (+37%), nodes identical. 3. The usages walker maintains call/import ancestry as enter/exit counters on its explicit stack instead of per-node ancestor re-walks (extract_usages.c had grown from 6 to 100 ts_node_parent calls since v0.9.0; the two per-node gates are now O(1) with semantics preserved — strict ancestors only, emit before self-count). 4. Registry short-name indexes replace the two remaining full scans: cs_lookup_extension walked all 963k funcs per unresolved invocation (now the existing free-func short-name iterator, first-match order preserved via min-index selection), and cs_resolve_type_name's step-9 fallback scanned every type per unresolved name IN BOTH the builder and per-file resolution (new type_short index in finalize, same reverse-insertion ascending-order pattern, best-score ties keep the first-in-registration-order winner). Builder 140,095 -> 500 ms; resolve cross-LSP CPU 5.5M -> 317k ms (us_per_file_per_kdef 191 -> 11). End state: 449.9 s wall (1.01x of v0.9.0) with +48.6% edges vs v0.9.0 — per-edge cost 32% BETTER than v0.9.0. Extract's remaining 359 s is the 24 MB hugeexpr1.cs parse floor both versions pay. Guarded by the complexity suite; cs_lsp/extraction/edge/lang-contract suites green including the 53-language calls-breadth contract. Refs #1669. Signed-off-by: Martin Vogel <[email protected]>
1 parent e700b62 commit a4c0ffb

6 files changed

Lines changed: 1095 additions & 556 deletions

File tree

‎internal/cbm/extract_unified.c‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1646,6 +1646,18 @@ static bool is_actual_import_boundary(CBMExtractCtx *ctx, TSNode node, const CBM
16461646
char *name = ts_node_is_null(head) ? NULL : cbm_node_text(ctx->arena, head, ctx->source);
16471647

16481648
switch (ctx->language) {
1649+
case CBM_LANG_CSHARP:
1650+
/* cs_import_types also lists namespace_declaration (so the import pass
1651+
* can map namespace names) and using_statement (C#'s RAII block, a
1652+
* grammar-name collision with using_directive). Neither is an import
1653+
* CONTEXT: treating them as one put every namespaced C# file's whole
1654+
* body behind inside_import, which both suppressed ordinary usage
1655+
* extraction there and sent every identifier through the ancestor-
1656+
* walking import-binding check — 92% of extract time on wide files
1657+
* (dotnet/runtime JIT torture tests, 490 s for one 147 KB file). Only
1658+
* the using DIRECTIVE opens an import scope. */
1659+
return strcmp(kind, "using_directive") == 0 ||
1660+
strcmp(kind, "namespace_use_declaration") == 0;
16491661
case CBM_LANG_ELIXIR:
16501662
return strcmp(kind, "call") != 0 ||
16511663
(name && (strcmp(name, "import") == 0 || strcmp(name, "alias") == 0 ||

‎internal/cbm/extract_usages.c‎

Lines changed: 75 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -49,36 +49,6 @@ static void walk_usages(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec
4949
static bool is_direct_argument_value(TSNode node);
5050
static TSNode python_direct_callable_attribute_site(TSNode node);
5151

52-
// Check if a node is inside a call expression (to avoid double-counting as usage)
53-
static bool is_inside_call(TSNode node, const CBMLangSpec *spec) {
54-
TSNode cur = ts_node_parent(node);
55-
while (!ts_node_is_null(cur)) {
56-
if (cbm_kind_in_set(cur, spec->call_node_types)) {
57-
return true;
58-
}
59-
cur = ts_node_parent(cur);
60-
}
61-
return false;
62-
}
63-
64-
// Check if a node is inside an import statement
65-
static bool is_inside_import(TSNode node, const CBMLangSpec *spec) {
66-
bool has_imports = spec->import_node_types && spec->import_node_types[0];
67-
bool has_from_imports = spec->import_from_types && spec->import_from_types[0];
68-
if (!has_imports && !has_from_imports) {
69-
return false;
70-
}
71-
TSNode cur = ts_node_parent(node);
72-
while (!ts_node_is_null(cur)) {
73-
if ((has_imports && cbm_kind_in_set(cur, spec->import_node_types)) ||
74-
(has_from_imports && cbm_kind_in_set(cur, spec->import_from_types))) {
75-
return true;
76-
}
77-
cur = ts_node_parent(cur);
78-
}
79-
return false;
80-
}
81-
8252
// Is this an identifier-like node that represents a reference?
8353
static bool is_reference_node(TSNode node, CBMLanguage lang) {
8454
const char *kind = ts_node_type(node);
@@ -2426,7 +2396,8 @@ static bool emit_direct_perl_coderef_usage(CBMExtractCtx *ctx, TSNode node,
24262396
}
24272397

24282398
// Try to emit a usage for a reference node. Returns early if the node should be skipped.
2429-
static void try_emit_usage(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *spec) {
2399+
static void try_emit_usage(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *spec,
2400+
bool inside_call, bool inside_import) {
24302401
if (emit_direct_perl_coderef_usage(ctx, node, cbm_enclosing_func_qn_cached(ctx, node), 0)) {
24312402
return;
24322403
}
@@ -2439,7 +2410,7 @@ static void try_emit_usage(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *s
24392410
if (is_call_argument_label(node)) {
24402411
return;
24412412
}
2442-
if (is_inside_call(node, spec) || is_inside_import(node, spec)) {
2413+
if (inside_call || inside_import) {
24432414
return;
24442415
}
24452416
if (is_binding_occurrence(ctx, node, spec, NULL) ||
@@ -2456,18 +2427,79 @@ static void try_emit_usage(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *s
24562427
}
24572428
}
24582429

2459-
// Iterative usage walker — explicit stack
2430+
// Iterative usage walker — explicit stack.
2431+
//
2432+
// The call/import ancestry that gates usage emission is maintained as ENTER/
2433+
// EXIT counters on the walk instead of per-node ancestor re-walks: the old
2434+
// is_inside_call/is_inside_import helpers climbed every ancestor via
2435+
// ts_node_parent, and tree-sitter's ts_node_parent RE-DESCENDS from the root
2436+
// scanning siblings — O(depth x sibling-position) per node, which went
2437+
// quadratic on wide nodes (a 1,536-argument call in dotnet/runtime's JIT
2438+
// torture tests put 92% of extract time into these walks; 490 s for one
2439+
// 147 KB file). Counter semantics match the helpers exactly: strict ancestors
2440+
// only — a node is emitted BEFORE its own kind increments the counters, so a
2441+
// call node itself does not count as "inside a call".
24602442
static void walk_usages(CBMExtractCtx *ctx, TSNode root, const CBMLangSpec *spec) {
2461-
TSNodeStack stack;
2462-
ts_nstack_init(&stack, ctx->arena, 4096);
2463-
ts_nstack_push(&stack, ctx->arena, root);
2464-
2465-
while (stack.count > 0) {
2466-
TSNode node = ts_nstack_pop(&stack);
2467-
try_emit_usage(ctx, node, spec);
2468-
uint32_t count = ts_node_child_count(node);
2469-
for (int i = (int)count - LAST_IDX; i >= 0; i--) {
2470-
ts_nstack_push(&stack, ctx->arena, ts_node_child(node, (uint32_t)i));
2443+
typedef struct {
2444+
TSNode node;
2445+
uint32_t next_child;
2446+
bool counts_call;
2447+
bool counts_import;
2448+
} UsageFrame;
2449+
int cap = 256;
2450+
UsageFrame *frames = (UsageFrame *)cbm_arena_alloc(ctx->arena, (size_t)cap * sizeof(*frames));
2451+
if (!frames) {
2452+
return;
2453+
}
2454+
bool has_imports = spec->import_node_types && spec->import_node_types[0];
2455+
bool has_from_imports = spec->import_from_types && spec->import_from_types[0];
2456+
int call_depth = 0;
2457+
int import_depth = 0;
2458+
int top = 0;
2459+
frames[top++] = (UsageFrame){root, 0, false, false};
2460+
bool entering = true;
2461+
2462+
while (top > 0) {
2463+
UsageFrame *f = &frames[top - 1];
2464+
if (entering) {
2465+
try_emit_usage(ctx, f->node, spec, call_depth > 0, import_depth > 0);
2466+
f->counts_call = cbm_kind_in_set(f->node, spec->call_node_types);
2467+
f->counts_import =
2468+
(has_imports && cbm_kind_in_set(f->node, spec->import_node_types)) ||
2469+
(has_from_imports && cbm_kind_in_set(f->node, spec->import_from_types));
2470+
if (f->counts_call) {
2471+
call_depth++;
2472+
}
2473+
if (f->counts_import) {
2474+
import_depth++;
2475+
}
2476+
}
2477+
uint32_t count = ts_node_child_count(f->node);
2478+
if (f->next_child < count) {
2479+
TSNode child = ts_node_child(f->node, f->next_child);
2480+
f->next_child++;
2481+
if (top == cap) {
2482+
int new_cap = cap * 2;
2483+
UsageFrame *grown =
2484+
(UsageFrame *)cbm_arena_alloc(ctx->arena, (size_t)new_cap * sizeof(*grown));
2485+
if (!grown) {
2486+
return;
2487+
}
2488+
memcpy(grown, frames, (size_t)cap * sizeof(*frames));
2489+
frames = grown;
2490+
cap = new_cap;
2491+
}
2492+
frames[top++] = (UsageFrame){child, 0, false, false};
2493+
entering = true;
2494+
} else {
2495+
if (f->counts_call) {
2496+
call_depth--;
2497+
}
2498+
if (f->counts_import) {
2499+
import_depth--;
2500+
}
2501+
top--;
2502+
entering = false;
24712503
}
24722504
}
24732505
}

0 commit comments

Comments
 (0)