Skip to content

BuildDDG kill computation is quadratic on large switch-heavy functions #18

Closed as not planned

Description

@sinha108

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

  1. Generate a function with a 6,000-case switch, each case assigning the same few variables.
  2. 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

  1. sinha108 commented on Oct 25, 2026

    @sinha108
    ContributorAuthor

    Consolidated into #27, which carries this issue's full detail.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions