-
Notifications
You must be signed in to change notification settings - Fork 122
Description
Problem
The /api/layout endpoint maps edges to nodes using a nested linear scan: for each edge, it iterates over all selected nodes to find the source and target indices. This is O(n × e) where n = selected nodes and e = total edges.
For a project with 100K nodes and 400K edges, this produces ~40 billion comparisons, causing multi-second hangs or request timeouts.
The relevant code in src/ui/layout3d.c (cbm_layout_compute, step 3 "Map edges + degree"):
for (int e = 0; e < total_edges; e++) {
int si = -1, di = -1;
for (int i = 0; i < n; i++) {
if (search_out.results[i].node.id == all_edges[e].source_id)
si = i;
if (search_out.results[i].node.id == all_edges[e].target_id)
di = i;
if (si >= 0 && di >= 0)
break;
}
...
}Additionally, the current two-pass approach (fetch all edges, then map) keeps all edges in memory even if most don't connect selected nodes.
Proposed fix
Replace the two-pass fetch-then-map with a single-pass filter-during-fetch using binary search:
- After querying nodes, build a sorted
(node_id, index)map andqsortit — O(n log n) - For each edge fetched from the DB, binary search both endpoints — O(log n) each
- Keep only edges where both endpoints are in the selected node set; free rejected edges immediately
Complexity: O(n log n + e log n) instead of O(n × e)
Additional benefit: lower peak memory since unmatched edges are freed during fetch rather than accumulated.
This is a pure performance improvement — no API or behavior change.