Skip to content

perf(resolver): index paramBindings and objectPropBindings to reduce Phase 8.3f from O(n³) to O(n) #1374

Description

@carlos-alm

Problem

The Phase 8.3f resolution in buildPointsToMap (src/domain/graph/resolver/points-to.ts:187-199) uses three nested for...of loops with no early indexing:

for (const restBinding of objectRestParamBindings) {
  for (const paramBinding of paramBindings) {
    for (const propBinding of objectPropBindings) {
      if (...equality guards...) { ... }
    }
  }
}

In a large generated or bundled file with many rest-param functions and object literals, the inner-loop body executes on every combination before the equality guards discard most pairs. This is O(|objectRestParamBindings| × |paramBindings| × |objectPropBindings|).

Fix

Pre-index the bindings before the loops:

  • paramBindings as Map<callee+argIndex, argName[]>
  • objectPropBindings as Map<objectName, {propName, valueName}[]>

This reduces the lookup to O(n) and avoids the quadratic scan of paramBindings for each rest binding.

Impact

Low risk for current benchmark files (small fixtures). Becomes a performance concern for large real-world codebases with many rest-destructured parameters.

Context

Identified in Greptile review of PR #1331.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions