You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
BuildDDG kill computation is quadratic on large switch-heavy functions #18
Describe the bug BuildDDG (internal/dataflow/reachdefs.go) computes each node's kill set against every definition in the function, which is O(nodes × defs). On very large, switch-heavy generated functions this dominates L3 time: a goyacc-style function with 3,000 case clauses takes 3.9 s, and one with 6,000 takes 15 s, for that single function.
To Reproduce
Generate a function with a 6,000-case switch, each case assigning the same few variables.
cango -i <dir> -a 3 -o /tmp/out and time it, or profile BuildDDG.
Expected behavior
Kill computation scales with the number of definitions of the same base, not with all definitions in the function.
Logs
Measured by the final review of PR #16 (synthetic probe): 3.9 s at 3,000 cases, 15 s at 6,000.
Additional context
Fix: index definitions by Path.Base and test kills only within that bucket.
No real-app run in the evaluation (7 apps incl. Kubernetes) hit this; it is a scaling risk on generated parsers.
Activity
sinha108 commentedon Oct 25, 2026
Consolidated into #27, which carries this issue's full detail.