Skip to content

L3 scaling: quadratic kill sets, streamed output, released AST memory #27

Closed

Description

@sinha108

Is your feature request related to a problem? Please describe.
Three costs on very large inputs:

  1. Quadratic kill computation (was BuildDDG kill computation is quadratic on large switch-heavy functions #18).
    • BuildDDG (internal/dataflow/reachdefs.go) computes each node's kill set against every definition in the function: O(nodes × defs).
    • On a goyacc-style function, 3,000 case clauses take 3.9 s and 6,000 take 15 s, for that one function (synthetic probe).
    • No real app in the evaluation hit this, including Kubernetes.
  2. Whole output held in memory (was Stream analysis.json output and release L3 AST references after emission #19).
    • cango builds the full analysis.json in memory and marshals it into one []byte.
    • At -a 3 the file reaches 318 MB on the Kubernetes root module and 1.1 GB on cockroach.
    • Peak memory on cockroach is 13.5 GB.
  3. ASTs kept alive (was Stream analysis.json output and release L3 AST references after emission #19). L3 nodes keep their AST pointers (Node.Stmt) alive through emission.

Describe the solution you'd like

  1. Index definitions by Path.Base and test kills only within that bucket.
  2. Stream the JSON to the output file, module by module.
  3. Drop each L3 node's AST references once emission has used them.

Describe alternatives you've considered
Capping or sampling the graph. Rejected: the spec forbids caps that drop edges (§4.13), because a dropped edge turns into a false "no flow" in taint queries.

Additional context

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

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions