Skip to content

perf: avoid O(n^2) queue ops in DataFlowAnalyzer BFS #163

@omsherikar

Description

@omsherikar

Summary

DataFlowAnalyzer._collect_nodes uses a Python list queue with pop(0), which is O(n) per pop. On large CFGs this turns node collection into avoidable O(n^2) behavior.

Suggested direction

  • Replace list queue with collections.deque and popleft().
  • Keep traversal behavior identical (reachable nodes only, deterministic ordering after final sort).

Acceptance

  • Same node set and order semantics as before.
  • Reduced collection time in synthetic large-CFG benchmark.

Code

  • refactron/analysis/data_flow.py_collect_nodes

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions