Skip to content

perf: Optimize Call Graph Traversal Algorithm for Deep Context Generation #42

@BETAER-08

Description

@BETAER-08

Problem

The --depth context expansion logic in ContextGenerator::generate currently loads all relationship edges from the database into a Vec and performs a full-scan loop for every depth iteration. For large projects with thousands of nodes and edges, this $O(E \times \text{Depth})$ operation becomes exponentially slow.

Proposed Solution

  • Optimize the graph traversal logic in src/core/generator.rs.
  • Option A: Transform the edge list into an Adjacency List (HashMap<String, Vec<String>>) in memory so that neighbor lookups take $O(1)$ time.
  • Option B: Utilize SQLite's Recursive CTE in src/db/query.rs to delegate the deep traversal entirely to the database engine.

Definition of Done

  • Graph traversal logic is updated (Adjacency List or Recursive CTE).
  • Generation time with --depth 2 or higher is significantly reduced on large repositories.
  • The output context remains exactly the same as the unoptimized version.

Metadata

Metadata

Assignees

No one assigned

    Labels

    area: coreLogic for Indexer, Parser, Graph, or Generator.area: dbDatabase schema, VectorStore, and Query logic.enhancementNew feature or request (e.g., config file, depth control).priority: mediumNormal priority; adds value but not urgent.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions