`expandedRefIdsForVar` is very slow for variables that use multiple deep dimensions

[chrispcampbell]

I received access to the model referenced in discussion #790. There are a few issues affecting that model that need to be fixed in SDEverywhere. The following describes one of those defects.

Current Behavior

Overview

The expandedRefIdsForVar() function in packages/compile/src/model/read-equations.js determines which RHS variable instances are referenced by a LHS variable. It uses a cartesian product algorithm that is extremely slow for models with large subscript dimensions.

The algorithm (lines 1024-1045):

1. Computes the cartesian product of all LHS subscript dimensions → array of combo strings
2. For each RHS variable instance, computes the cartesian product of its subscript dimensions → another array of combo strings
3. Does brute-force Array.includes() string matching between the two sets

The model in discussion #790 has variables that use multiple dimensions, for example 36 countries × 56 materials × 22 kinds = 44,352 combinations per variable, this is O(product of dimension sizes) per call. With 112,753 calls during model analysis, this results in ~7 minutes of build time for what could be a ~35 second build.

Profiling Data

BEFORE optimization:
  expandedRefIdsForVar: 421,749ms across 112,753 calls
  Total build:          ~449,000ms (~7.5 min)

AFTER optimization:
  expandedRefIdsForVar:   3,443ms across 112,753 calls
  Total build:           ~35,000ms (~35 sec)

Expected Behavior

The function should produce the same results but use an O(sum of dimension sizes) algorithm instead of O(product of dimension sizes).

AI Disclosure

I guided Claude Code (Opus 4.6) to investigate the performance issue and to propose a fix. I refactored and refined the fix and tests myself. I also used Claude to help prepare a summary of the problem to help populate the issue description above.

/cc @LSarribouette @m2gi-mohamami

[chrispcampbell]

A few more notes prepared by Claude, for the record.

Key Insight

Checking whether any combination in a cartesian product of sets A₁×A₂×...×Aₙ matches any combination in B₁×B₂×...×Bₙ is equivalent to checking that each position has at least one element in common: A₁∩B₁≠∅ AND A₂∩B₂≠∅ AND ... AND Aₙ∩Bₙ≠∅.

This is because positions in a cartesian product are independent. If position 1 has a match and position 2 has a match, then there exists a full combination that matches at all positions.

Algorithm

Instead of:

const lhsCombos = cartesianProductOf(lhsSubIdsPerPosition).map(c => c.join(','))
const rhsCombos = cartesianProductOf(rhsSubIdsPerPosition).map(c => c.join(','))
for (const lhsCombo of lhsCombos) {
  if (rhsCombos.includes(lhsCombo)) { ... }  // O(product × product)
}

Use:

const lhsIndexSets = lhsSubIdsPerPosition.map(ids => new Set(ids))
for (const rhsVarInstance of rhsVarInstances) {
  let matches = true
  for (let i = 0; i < positions; i++) {
    const rhsIndices = indexNamesForSubscript(rhsVarInstance.subscripts[i])
    if (!rhsIndices.some(id => lhsIndexSets[i].has(id))) {
      matches = false
      break
    }
  }
  if (matches) rhsRefIds.push(rhsVarInstance.refId)
}