Skip to content

Commit a33878c

Browse files
authored
Merge pull request #2420 from Fieldnote-Echo/perf/py-cross-registry-index
perf(py-lsp): O(1) type membership in the shared Python cross-registry build
2 parents edb4a6e + 5985131 commit a33878c

2 files changed

Lines changed: 189 additions & 6 deletions

File tree

‎internal/cbm/lsp/py_lsp.c‎

Lines changed: 49 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -6179,10 +6179,36 @@ static void py_split_field_defs(CBMArena *arena, const char *field_defs, const c
61796179
*types_out = types;
61806180
}
61816181

6182+
/* Qualified names of reg->types[0..noted), for a caller that registers into a
6183+
* registry it does not finalize until the end (cbm_py_build_cross_registry):
6184+
* that registry's own lookup scans every type. qns == NULL probes the
6185+
* registry instead. */
6186+
typedef struct {
6187+
CBMHashTable *qns;
6188+
int noted;
6189+
} PyKnownTypes;
6190+
6191+
/* Note the types added since the last call. Run after every add_type, so an
6192+
* add that failed silently cannot desync set and registry. If the set cannot
6193+
* grow it is dropped and probes fall back to the registry. */
6194+
static void py_note_known_types(PyKnownTypes *known, const CBMTypeRegistry *reg) {
6195+
for (; known && known->qns && known->noted < reg->type_count; known->noted++) {
6196+
const char *qn = reg->types[known->noted].qualified_name;
6197+
if (!qn || cbm_ht_has(known->qns, qn))
6198+
continue;
6199+
cbm_ht_set(known->qns, qn, (void *)(uintptr_t)(known->noted + 1));
6200+
if (!cbm_ht_has(known->qns, qn)) {
6201+
cbm_ht_free(known->qns);
6202+
known->qns = NULL;
6203+
}
6204+
}
6205+
}
6206+
61826207
/* Build a registry from CBMLSPDef[] supplied by the caller — covers both
6183-
* the source file's own defs and cross-file referenced defs. */
6208+
* the source file's own defs and cross-file referenced defs. known is NULL
6209+
* except for the shared Tier-2 build. */
61846210
static bool py_register_lsp_defs(CBMArena *arena, CBMArena *idx_arena, CBMTypeRegistry *reg,
6185-
CBMLSPDef *defs, int def_count) {
6211+
CBMLSPDef *defs, int def_count, PyKnownTypes *known) {
61866212
/* Pass 1: types only — the method pass probes the registry per Method def
61876213
* (receiver auto-registration), which is a LINEAR scan pre-finalize:
61886214
* O(methods x types) per file (same quadratic as php_register_lsp_defs;
@@ -6206,6 +6232,7 @@ static bool py_register_lsp_defs(CBMArena *arena, CBMArena *idx_arena, CBMTypeRe
62066232
}
62076233
py_split_field_defs(arena, d->field_defs, &rt.field_names, &rt.field_types);
62086234
cbm_registry_add_type(reg, rt);
6235+
py_note_known_types(known, reg);
62096236
}
62106237
}
62116238
/* idx_arena == NULL skips the mid-build finalize: the tier-2 builder
@@ -6259,13 +6286,17 @@ static bool py_register_lsp_defs(CBMArena *arena, CBMArena *idx_arena, CBMTypeRe
62596286

62606287
if (strcmp(d->label, "Method") == 0 && d->receiver_type && d->receiver_type[0]) {
62616288
rf.receiver_type = d->receiver_type; /* borrowed */
6262-
if (!cbm_registry_lookup_type(reg, rf.receiver_type)) {
6289+
bool recv_known = known && known->qns
6290+
? cbm_ht_has(known->qns, rf.receiver_type)
6291+
: cbm_registry_lookup_type(reg, rf.receiver_type) != NULL;
6292+
if (!recv_known) {
62636293
CBMRegisteredType auto_t;
62646294
memset(&auto_t, 0, sizeof(auto_t));
62656295
auto_t.qualified_name = rf.receiver_type;
62666296
const char *dot = strrchr(d->receiver_type, '.');
62676297
auto_t.short_name = dot ? dot + 1 : rf.receiver_type; /* borrowed substring */
62686298
cbm_registry_add_type(reg, auto_t);
6299+
py_note_known_types(known, reg);
62696300
}
62706301
}
62716302
cbm_registry_add_func(reg, rf);
@@ -6277,7 +6308,7 @@ static bool py_register_lsp_defs(CBMArena *arena, CBMArena *idx_arena, CBMTypeRe
62776308
#ifdef CBM_ENABLE_TEST_SEAMS
62786309
bool cbm_py_lsp_test_register_defs(CBMArena *arena, CBMTypeRegistry *reg, CBMLSPDef *defs,
62796310
int def_count) {
6280-
return py_register_lsp_defs(arena, NULL, reg, defs, def_count);
6311+
return py_register_lsp_defs(arena, NULL, reg, defs, def_count, NULL);
62816312
}
62826313
#endif
62836314

@@ -6774,7 +6805,7 @@ CBMLSPStatus cbm_run_py_lsp_cross_status(CBMArena *arena, const char *source, in
67746805
py_lsp_init_for_stage(&ctx, arena, source, source_len, &reg, module_qn, out, "cross");
67756806
if (ctx.eval_failure)
67766807
goto cross_cleanup;
6777-
if (!py_register_lsp_defs(arena, &idx_arena, &reg, defs, def_count)) {
6808+
if (!py_register_lsp_defs(arena, &idx_arena, &reg, defs, def_count, NULL)) {
67786809
ctx.eval_failure = CBM_LSP_SCOPE_FAILED;
67796810
goto cross_cleanup;
67806811
}
@@ -6813,15 +6844,27 @@ CBMTypeRegistry *cbm_py_build_cross_registry(CBMArena *arena, CBMLSPDef *defs, i
68136844
cbm_registry_init(reg, arena);
68146845
cbm_python_stdlib_register(reg, arena);
68156846

6847+
/* The registry is not finalized until the end, so probing it for each
6848+
* Method's receiver scanned every type: O(methods x types), single-threaded
6849+
* (~54 s of lsp_cross_prepare on a large Python tree). Probe a set of
6850+
* the registered type QNs instead; registration order is unchanged. Sized
6851+
* for the stdlib seed, not def_count (the mixed all-language count). NULL
6852+
* on allocation failure: the registry probe runs as before. */
6853+
PyKnownTypes known = {cbm_ht_create((uint32_t)reg->type_count), 0};
6854+
py_note_known_types(&known, reg);
6855+
68166856
/* Filter to Python defs only — defs[] is mixed-language all_defs. */
68176857
for (int i = 0; i < def_count; i++) {
68186858
CBMLSPDef *d = &defs[i];
68196859
if (d->lang != CBM_LANG_PYTHON)
68206860
continue;
68216861
/* Reuse the existing register fn on a single-def slice (n=1 inline). */
6822-
if (!py_register_lsp_defs(arena, NULL, reg, d, 1))
6862+
if (!py_register_lsp_defs(arena, NULL, reg, d, 1, &known)) {
6863+
cbm_ht_free(known.qns);
68236864
return NULL; /* caller owns the shared arena and other registries */
6865+
}
68246866
}
6867+
cbm_ht_free(known.qns);
68256868

68266869
py_mark_ambiguous_callable_bindings(reg, arena);
68276870
cbm_registry_build_type_qn_order(reg, arena);

‎tests/test_py_lsp.c‎

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -751,6 +751,91 @@ TEST(pylsp_fused_self_attr_chain_via_overlay) {
751751
PASS();
752752
}
753753

754+
/* Characterization of the shared Tier-2 build order. Defs register one at a
755+
* time in defs[] order, so a Method seen before its Class auto-registers a
756+
* placeholder receiver type that stays ahead of the Class entry, and a Method
757+
* whose receiver is already known adds no type. Any change to how the build
758+
* probes for known receivers must keep this exact sequence. */
759+
TEST(pylsp_cross_registry_interleaved_order) {
760+
CBMArena arena;
761+
cbm_arena_init(&arena);
762+
CBMTypeRegistry *base = cbm_py_build_cross_registry(&arena, NULL, 0);
763+
ASSERT_NOT_NULL(base);
764+
int tb = base->type_count, fb = base->func_count;
765+
766+
CBMLSPDef defs[] = {
767+
{.qualified_name = "t.m.A.m",
768+
.short_name = "m",
769+
.label = "Method",
770+
.receiver_type = "t.m.A",
771+
.def_module_qn = "t.m",
772+
.lang = CBM_LANG_PYTHON},
773+
{.qualified_name = "t.m.A",
774+
.short_name = "A",
775+
.label = "Class",
776+
.def_module_qn = "t.m",
777+
.lang = CBM_LANG_PYTHON},
778+
{.qualified_name = "t.m.B",
779+
.short_name = "B",
780+
.label = "Class",
781+
.def_module_qn = "t.m",
782+
.lang = CBM_LANG_PYTHON},
783+
{.qualified_name = "t.m.B.f",
784+
.short_name = "f",
785+
.label = "Method",
786+
.receiver_type = "t.m.B",
787+
.def_module_qn = "t.m",
788+
.lang = CBM_LANG_PYTHON},
789+
{.qualified_name = "t.m.C.g",
790+
.short_name = "g",
791+
.label = "Method",
792+
.receiver_type = "t.m.C",
793+
.def_module_qn = "t.m",
794+
.lang = CBM_LANG_PYTHON},
795+
/* Receiver auto-registered by C.g just above: no second placeholder. */
796+
{.qualified_name = "t.m.C.h",
797+
.short_name = "h",
798+
.label = "Method",
799+
.receiver_type = "t.m.C",
800+
.def_module_qn = "t.m",
801+
.lang = CBM_LANG_PYTHON},
802+
/* Non-Python defs are skipped by the builder. */
803+
{.qualified_name = "t.m.D",
804+
.short_name = "D",
805+
.label = "Class",
806+
.def_module_qn = "t.m",
807+
.lang = CBM_LANG_GO},
808+
};
809+
CBMTypeRegistry *reg =
810+
cbm_py_build_cross_registry(&arena, defs, (int)(sizeof(defs) / sizeof(defs[0])));
811+
ASSERT_NOT_NULL(reg);
812+
813+
/* Types: placeholder A (from A.m), Class A, Class B, placeholder C. */
814+
ASSERT_EQ(reg->type_count, tb + 4);
815+
ASSERT_TRUE(reg->types[tb].qualified_name == defs[0].receiver_type);
816+
ASSERT_STR_EQ(reg->types[tb].short_name, "A");
817+
ASSERT_TRUE(reg->types[tb + 1].qualified_name == defs[1].qualified_name);
818+
ASSERT_TRUE(reg->types[tb + 2].qualified_name == defs[2].qualified_name);
819+
ASSERT_TRUE(reg->types[tb + 3].qualified_name == defs[4].receiver_type);
820+
ASSERT_STR_EQ(reg->types[tb + 3].short_name, "C");
821+
822+
/* Funcs keep defs[] order. */
823+
ASSERT_EQ(reg->func_count, fb + 4);
824+
ASSERT_STR_EQ(reg->funcs[fb].qualified_name, "t.m.A.m");
825+
ASSERT_STR_EQ(reg->funcs[fb + 1].qualified_name, "t.m.B.f");
826+
ASSERT_STR_EQ(reg->funcs[fb + 2].qualified_name, "t.m.C.g");
827+
ASSERT_STR_EQ(reg->funcs[fb + 2].receiver_type, "t.m.C");
828+
ASSERT_STR_EQ(reg->funcs[fb + 3].qualified_name, "t.m.C.h");
829+
830+
const CBMRegisteredType *a = cbm_registry_lookup_type(reg, "t.m.A");
831+
ASSERT_NOT_NULL(a);
832+
ASSERT_STR_EQ(a->qualified_name, "t.m.A");
833+
ASSERT_NULL(cbm_registry_lookup_type(reg, "t.m.D"));
834+
835+
cbm_arena_destroy(&arena);
836+
PASS();
837+
}
838+
754839
/* Issue #228: a class/static method invoked directly on a CROSS-FILE imported
755840
* class name — ActionRecordX.build_from_text(...) — produced no CALLS edge, so
756841
* the method showed in/out degree 0 and was flagged as dead code. Distinct from
@@ -2448,6 +2533,59 @@ TEST(pylsp_scale_work_is_linear) {
24482533
PASS();
24492534
}
24502535

2536+
/* #2413 (O9: no clock): the shared Tier-2 build registers one def at a time
2537+
* into a registry it finalizes only at the end, so a receiver probe that scans
2538+
* the types registered so far makes it O(methods x types). The registry
2539+
* primitives count every candidate they examine (CBM_LSP_WORK): 4x the classes
2540+
* must cost at most ~4x the work; the scanning probe lands at ~16x. */
2541+
static uint64_t cross_registry_work_for(int n_classes, int *out_types) {
2542+
CBMArena arena;
2543+
cbm_arena_init(&arena);
2544+
int n_defs = n_classes * 3;
2545+
CBMLSPDef *defs = (CBMLSPDef *)cbm_arena_calloc(&arena, (size_t)n_defs * sizeof(*defs));
2546+
if (!defs) {
2547+
cbm_arena_destroy(&arena);
2548+
*out_types = -1;
2549+
return 0;
2550+
}
2551+
/* Extraction order: each class followed by its two methods. */
2552+
for (int i = 0; i < n_classes; i++) {
2553+
CBMLSPDef *cls = &defs[i * 3];
2554+
cls->qualified_name = cbm_arena_sprintf(&arena, "scale.mod.Cls%d", i);
2555+
cls->short_name = cls->qualified_name + strlen("scale.mod.");
2556+
cls->label = "Class";
2557+
cls->def_module_qn = "scale.mod";
2558+
cls->lang = CBM_LANG_PYTHON;
2559+
for (int j = 1; j <= 2; j++) {
2560+
CBMLSPDef *m = &defs[i * 3 + j];
2561+
m->qualified_name = cbm_arena_sprintf(&arena, "%s.m%d", cls->qualified_name, j);
2562+
m->short_name = j == 1 ? "m1" : "m2";
2563+
m->label = "Method";
2564+
m->receiver_type = cls->qualified_name;
2565+
m->def_module_qn = "scale.mod";
2566+
m->lang = CBM_LANG_PYTHON;
2567+
}
2568+
}
2569+
(void)cbm_lsp_work_take();
2570+
CBMTypeRegistry *reg = cbm_py_build_cross_registry(&arena, defs, n_defs);
2571+
uint64_t work = cbm_lsp_work_take();
2572+
*out_types = reg ? reg->type_count : -1;
2573+
cbm_arena_destroy(&arena);
2574+
return work;
2575+
}
2576+
2577+
TEST(pylsp_cross_registry_build_work_is_linear) {
2578+
int t1 = 0, t4 = 0;
2579+
uint64_t w1 = cross_registry_work_for(1000, &t1);
2580+
uint64_t w4 = cross_registry_work_for(4000, &t4);
2581+
printf(" cross registry work: 1000=%llu (types=%d) 4000=%llu (types=%d)\n",
2582+
(unsigned long long)w1, t1, (unsigned long long)w4, t4);
2583+
/* Every class registered exactly once (no duplicate placeholder). */
2584+
ASSERT_EQ(t4 - t1, 3000);
2585+
ASSERT(w4 <= 5 * w1 + 1000);
2586+
PASS();
2587+
}
2588+
24512589
extern const TSLanguage *tree_sitter_python(void);
24522590

24532591
TEST(pylsp_issue1527_memo_allocation_failure_is_reported) {
@@ -4850,6 +4988,7 @@ SUITE(py_lsp) {
48504988
RUN_TEST(pylsp_issue1527_long_binary_chain_is_not_nesting);
48514989
RUN_TEST(pylsp_issue1527_long_receiver_chain_is_not_nesting);
48524990
RUN_TEST(pylsp_scale_work_is_linear);
4991+
RUN_TEST(pylsp_cross_registry_build_work_is_linear);
48534992
/* Phase 2 — smoke */
48544993
RUN_TEST(pylsp_smoke_empty);
48554994
RUN_TEST(pylsp_smoke_one_function);
@@ -4886,6 +5025,7 @@ SUITE(py_lsp) {
48865025
RUN_TEST(pylsp_crossfile_receiver_through_typed_field);
48875026
RUN_TEST(pylsp_crossfile_typed_field_shared_registry);
48885027
RUN_TEST(pylsp_fused_self_attr_chain_via_overlay);
5028+
RUN_TEST(pylsp_cross_registry_interleaved_order);
48895029
RUN_TEST(pylsp_crossfile_classmethod_on_class_issue228);
48905030
RUN_TEST(pylsp_crossfile_inheritance);
48915031
RUN_TEST(pylsp_batch_two_files);

0 commit comments

Comments
 (0)