Skip to content

Commit ce2ba50

Browse files
committed
perf: root-cause fixes for fork-origin DeusData#3 (purge) + DeusData#8 (dep N+1)
DeusData#3 — incremental purge was O(C·(N+E)): cbm_gbuf_delete_by_file was called once per changed/deleted file, each a full nodes+edges scan. Add cbm_gbuf_delete_by_paths (one pass over nodes matching a path membership set + one edge cascade = O(N+E) regardless of path count); refactor cbm_gbuf_delete_by_file to delegate to it (DRY — single implementation). pipeline_incremental.c now purges all changed+deleted paths in one call (OOM fallback keeps the old per-file path). graph_buffer 49 + incremental purge tests pass; only the known B1 full-reindex failures remain. DeusData#8 — cbm_dep_link_cross_edges was N+1: one cbm_store_search per import (<=500) to find a matching dep Module. Now ONE bulk fetch of all dep Module nodes + an in-memory name->id hash (first-wins, preserving limit=1 semantics) -> O(1) per import. depindex 32 pass. DeusData#5 verified NOT a bug (avoided a false fix): node_degree IS populated by cbm_pagerank_compute (pagerank.c:422 INSERT OR REPLACE INTO node_degree); the correlated-subquery fallback only fires pre-PageRank.
1 parent 2ac5f21 commit ce2ba50

4 files changed

Lines changed: 107 additions & 40 deletions

File tree

‎src/depindex/depindex.c‎

Lines changed: 47 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
#include "store/store.h"
1010
#include "foundation/log.h"
1111
#include "foundation/compat_fs.h"
12+
#include "foundation/hash_table.h"
1213

1314
#include <limits.h>
1415
#include <stdio.h>
@@ -501,6 +502,11 @@ int cbm_dep_auto_index(const char *project_name, const char *project_root,
501502
* the project's import node to the dep's module node.
502503
*
503504
* This enables trace_call_path to follow imports across the project/dep boundary. */
505+
/* Upper bound for the one-shot bulk fetch of dep Module nodes when linking
506+
* cross-boundary IMPORTS edges. Named (not magic) — per the no-magic-values
507+
* convention. Dep linking is index-time, so a generous fetch is fine. */
508+
#define CBM_DEP_LINK_MODULE_FETCH 100000
509+
504510
int cbm_dep_link_cross_edges(cbm_store_t *store, const char *project_name) {
505511
if (!store || !project_name || !project_name[0]) return 0;
506512

@@ -518,41 +524,54 @@ int cbm_dep_link_cross_edges(cbm_store_t *store, const char *project_name) {
518524
return 0;
519525
}
520526

521-
int linked = 0;
527+
/* Perf #8: was N+1 — one cbm_store_search PER import (up to 500) to find a
528+
* matching dep Module. Now ONE bulk fetch of all dep Module nodes + an
529+
* in-memory name→id hash, then O(1) per import. Behavior preserved: first
530+
* Module matching the name wins (hash set only if absent), matching the old
531+
* limit=1 first-result semantics. */
532+
char dep_pattern[CBM_NAME_MAX];
533+
snprintf(dep_pattern, sizeof(dep_pattern), "%s" CBM_DEP_SEPARATOR "%%",
534+
project_name);
535+
536+
cbm_search_params_t mod_params = {0};
537+
mod_params.project_pattern = dep_pattern;
538+
mod_params.label = "Module";
539+
mod_params.limit = CBM_DEP_LINK_MODULE_FETCH;
540+
cbm_search_output_t mod_out = {0};
541+
CBMHashTable *mod_by_name = NULL;
542+
/* node ids are >= 1, so (void*)(intptr_t)id is non-NULL for present modules
543+
* and cbm_ht_get returns NULL for absent names — a clean presence test. */
544+
if (cbm_store_search(store, &mod_params, &mod_out) == 0) {
545+
mod_by_name = cbm_ht_create((uint32_t)mod_out.count + 8);
546+
for (int i = 0; i < mod_out.count; i++) {
547+
const char *mname = mod_out.results[i].node.name;
548+
if (!mname || !mname[0]) continue;
549+
if (cbm_ht_get(mod_by_name, mname)) continue; /* first-wins */
550+
int64_t mid = mod_out.results[i].node.id;
551+
cbm_ht_set(mod_by_name, mname, (void *)(intptr_t)mid);
552+
}
553+
}
522554

523-
/* For each import, look for a matching Module in dep projects */
555+
int linked = 0;
524556
for (int i = 0; i < out.count; i++) {
525557
const char *import_name = out.results[i].node.name;
526558
if (!import_name || !import_name[0]) continue;
527559

528-
/* Build dep project pattern: project_name.dep.% */
529-
char dep_pattern[CBM_NAME_MAX];
530-
snprintf(dep_pattern, sizeof(dep_pattern), "%s" CBM_DEP_SEPARATOR "%%",
531-
project_name);
532-
533-
/* Search for Module with matching name in dep projects */
534-
cbm_search_params_t dep_params = {0};
535-
dep_params.name_pattern = import_name;
536-
dep_params.project_pattern = dep_pattern;
537-
dep_params.label = "Module";
538-
dep_params.limit = 1;
539-
540-
cbm_search_output_t dep_out = {0};
541-
int drc = cbm_store_search(store, &dep_params, &dep_out);
542-
if (drc == 0 && dep_out.count > 0) {
543-
/* Create cross-boundary IMPORTS edge */
544-
cbm_edge_t edge = {
545-
.source_id = out.results[i].node.id,
546-
.target_id = dep_out.results[0].node.id,
547-
.type = "IMPORTS",
548-
.project = project_name,
549-
};
550-
cbm_store_insert_edge(store, &edge);
551-
linked++;
552-
}
553-
cbm_store_search_free(&dep_out);
560+
void *hit = cbm_ht_get(mod_by_name, import_name);
561+
if (!hit) continue;
562+
563+
cbm_edge_t edge = {
564+
.source_id = out.results[i].node.id,
565+
.target_id = (int64_t)(intptr_t)hit,
566+
.type = "IMPORTS",
567+
.project = project_name,
568+
};
569+
cbm_store_insert_edge(store, &edge);
570+
linked++;
554571
}
555572

573+
if (mod_by_name) cbm_ht_free(mod_by_name); /* keys borrowed from mod_out, not freed */
574+
cbm_store_search_free(&mod_out);
556575
cbm_store_search_free(&out);
557576

558577
if (linked > 0) {

‎src/graph_buffer/graph_buffer.c‎

Lines changed: 34 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -749,19 +749,46 @@ int cbm_gbuf_delete_by_label(cbm_gbuf_t *gb, const char *label) {
749749
}
750750

751751
int cbm_gbuf_delete_by_file(cbm_gbuf_t *gb, const char *file_path) {
752+
/* Single-file purge delegates to the batch path (paths=[file_path], count=1)
753+
* so there is ONE implementation of the node-scan + edge cascade — no
754+
* duplicated loop (DRY; the batch version does the same work in O(N+E)
755+
* regardless of path count). */
752756
if (!gb || !file_path) {
753757
return CBM_NOT_FOUND;
754758
}
759+
return cbm_gbuf_delete_by_paths(gb, &file_path, 1);
760+
}
761+
762+
/* Batch purge: delete every node whose file_path is in `paths`, in a SINGLE
763+
* pass over gb->nodes + a single edge cascade — O(N+E) total regardless of how
764+
* many paths are given. Replaces the old loop of cbm_gbuf_delete_by_file calls
765+
* (one full nodes+edges scan PER file = O(C·(N+E))) in the incremental engine
766+
* (perf fork-origin #3). Behaviorally identical to calling delete_by_file once
767+
* per path; just without the repeated full scans. NULL entries in paths are
768+
* skipped. Keys (paths) are borrowed — not freed by the internal path set. */
769+
int cbm_gbuf_delete_by_paths(cbm_gbuf_t *gb, const char *const *paths, int count) {
770+
if (!gb) {
771+
return CBM_NOT_FOUND;
772+
}
773+
if (count <= 0 || !paths) {
774+
return 0;
775+
}
776+
777+
CBMHashTable *path_set = cbm_ht_create((size_t)count * 32);
778+
for (int i = 0; i < count; i++) {
779+
if (paths[i]) {
780+
cbm_ht_set(path_set, paths[i], intptr_to_ptr(SKIP_ONE));
781+
}
782+
}
755783

756-
/* Collect IDs of nodes in this file */
757784
CBMHashTable *deleted_set = cbm_ht_create(CBM_SZ_64);
758785
int deleted_count = 0;
759786
int scanned = 0;
760787

761788
for (int i = 0; i < gb->nodes.count; i++) {
762789
cbm_gbuf_node_t *n = gb->nodes.items[i];
763790
scanned++;
764-
if (!n->file_path || strcmp(n->file_path, file_path) != 0) {
791+
if (!n->file_path || !cbm_ht_get(path_set, n->file_path)) {
765792
continue;
766793
}
767794
if (!n->qualified_name || !cbm_ht_get(gb->node_by_qn, n->qualified_name)) {
@@ -772,39 +799,38 @@ int cbm_gbuf_delete_by_file(cbm_gbuf_t *gb, const char *file_path) {
772799
make_id_key(id_buf, sizeof(id_buf), n->id);
773800
cbm_ht_set(deleted_set, strdup(id_buf), intptr_to_ptr(SKIP_ONE));
774801

775-
/* Remove from secondary indexes */
776802
remove_node_from_ptr_array(cbm_ht_get(gb->nodes_by_label, n->label), n->id);
777803
remove_node_from_ptr_array(cbm_ht_get(gb->nodes_by_name, n->name), n->id);
778804

779-
/* Remove from primary indexes */
780805
cbm_ht_delete(gb->node_by_qn, n->qualified_name);
781806
const char *stored_key = cbm_ht_get_key(gb->node_by_id, id_buf);
782807
cbm_ht_delete(gb->node_by_id, id_buf);
783808
free((void *)stored_key);
784809

785-
/* NULL out QN so dump's liveness check (cbm_ht_get by QN) fails
786-
* even if a new node with the same QN is inserted later via merge. */
787810
free(n->qualified_name);
788811
n->qualified_name = NULL;
789812
deleted_count++;
790813
}
791814

815+
cbm_ht_free(path_set); /* keys borrowed from caller — not freed here */
816+
792817
if (deleted_count == 0) {
793818
cbm_ht_free(deleted_set);
794819
return 0;
795820
}
796821

797-
/* Cascade-delete edges referencing deleted nodes */
798822
cascade_delete_edges(gb, deleted_set);
799823

800824
cbm_ht_foreach(deleted_set, free_key_only, NULL);
801825
cbm_ht_free(deleted_set);
802826
{
803827
char s_buf[CBM_SZ_16];
804828
char d_buf[CBM_SZ_16];
829+
char p_buf[CBM_SZ_16];
805830
snprintf(s_buf, sizeof(s_buf), "%d", scanned);
806831
snprintf(d_buf, sizeof(d_buf), "%d", deleted_count);
807-
cbm_log_info("gbuf.delete_by_file", "file", file_path, "scanned", s_buf, "deleted", d_buf);
832+
snprintf(p_buf, sizeof(p_buf), "%d", count);
833+
cbm_log_info("gbuf.delete_by_paths", "paths", p_buf, "scanned", s_buf, "deleted", d_buf);
808834
}
809835
return deleted_count;
810836
}

‎src/graph_buffer/graph_buffer.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -106,6 +106,11 @@ int cbm_gbuf_delete_by_label(cbm_gbuf_t *gb, const char *label);
106106
* Used by incremental indexing to remove stale nodes before re-extraction. */
107107
int cbm_gbuf_delete_by_file(cbm_gbuf_t *gb, const char *file_path);
108108

109+
/* Batch purge: delete every node whose file_path is in `paths` in a SINGLE pass
110+
* (O(N+E) total) instead of one scan per file (O(C·(N+E))). NULL paths skipped.
111+
* Keys borrowed (not freed). Returns total nodes deleted. */
112+
int cbm_gbuf_delete_by_paths(cbm_gbuf_t *gb, const char *const *paths, int count);
113+
109114
/* Bulk-load all nodes and edges for a project from an existing SQLite DB
110115
* into this graph buffer. Returns 0 on success. */
111116
int cbm_gbuf_load_from_db(cbm_gbuf_t *gb, const char *db_path, const char *project);

‎src/pipeline/pipeline_incremental.c‎

Lines changed: 21 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -797,13 +797,30 @@ int cbm_pipeline_run_incremental(cbm_pipeline_t *p, const char *db_path, cbm_fil
797797
cbm_log_info("incremental.edge_snapshot", "captured", itoa_buf_incr(edge_cap.count), "elapsed_ms",
798798
itoa_buf_incr((int)elapsed_ms_incr(t)));
799799

800-
/* Step 2: Purge stale nodes */
800+
/* Step 2: Purge stale nodes — single pass over all changed+deleted paths
801+
* (O(N+E) total). Was O(C·(N+E)): one cbm_gbuf_delete_by_file call per file,
802+
* each a full nodes+edges scan (perf fork-origin #3). */
801803
cbm_clock_gettime(CLOCK_MONOTONIC, &t);
802-
for (int i = 0; i < ci; i++) {
803-
cbm_gbuf_delete_by_file(existing, changed_files[i].rel_path);
804+
{
805+
int purge_count = ci + deleted_count;
806+
if (purge_count > 0) {
807+
const char **purge_paths = malloc((size_t)purge_count * sizeof(const char *));
808+
if (purge_paths) {
809+
int p = 0;
810+
for (int i = 0; i < ci; i++) purge_paths[p++] = changed_files[i].rel_path;
811+
for (int i = 0; i < deleted_count; i++) purge_paths[p++] = deleted[i];
812+
cbm_gbuf_delete_by_paths(existing, purge_paths, purge_count);
813+
free(purge_paths);
814+
} else {
815+
/* OOM fallback: per-file scan (correct, just slower) */
816+
for (int i = 0; i < ci; i++)
817+
cbm_gbuf_delete_by_file(existing, changed_files[i].rel_path);
818+
for (int i = 0; i < deleted_count; i++)
819+
cbm_gbuf_delete_by_file(existing, deleted[i]);
820+
}
821+
}
804822
}
805823
for (int i = 0; i < deleted_count; i++) {
806-
cbm_gbuf_delete_by_file(existing, deleted[i]);
807824
free(deleted[i]);
808825
}
809826
free(deleted);

0 commit comments

Comments
 (0)