Skip to content

Call graph topological sort scales superlinearly #2830

@huitseeker

Description

@huitseeker

In crates/assembly-syntax/src/sema/passes/toposort.rs, the toposort implementation uses nested loops that result in O(n²) or worse complexity for large call graphs. Specifically:

  • The visitor pattern traverses each node
  • For each node, it may scan the entire graph to find dependencies
  • The cycle detection adds another layer of scanning

For projects with many procedures and complex call graphs, this can significantly slow down compilation.

Fix: replace with a standard Kahn's algorithm or DFS-based toposort that maintains O(V + E) complexity. Consider using a more efficient data structure (e.g., IndexSet or FxHashMap) for tracking visited nodes.

Metadata

Metadata

Assignees

No one assigned

    Labels

    assemblyRelated to Miden assembly

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions