Skip to content

perf(ui): layout endpoint O(n*e) edge mapping causes timeouts on large projects #169

@Selene29

Description

@Selene29

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:

  1. After querying nodes, build a sorted (node_id, index) map and qsort it — O(n log n)
  2. For each edge fetched from the DB, binary search both endpoints — O(log n) each
  3. 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    stability/performanceServer crashes, OOM, hangs, high CPU/memory

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions