perf(toolkit-lib): cdk gc's active-asset lookup is O(assets x stacks x template size)

[Adityaj0]

Describe the bug

cdk gc (garbage collection of orphaned S3/ECR bootstrap assets) determines whether an asset is still referenced by any stack via ActiveAssetCache.contains() in packages/@aws-cdk/toolkit-lib/lib/api/garbage-collection/stack-refresh.ts:

public contains(asset: string): boolean {
  for (const stack of this.stacks) {
    if (stack.includes(asset)) {
      return true;
    }
  }
  return false;
}

This is called once per asset from garbageCollectEcr/garbageCollectS3 in garbage-collector.ts, each call doing a full linear scan over every remembered stack template (raw template JSON text), searching for the asset's hash as a substring.

For an account with S stacks (each up to hundreds of KB) and A orphaned assets accumulated over time (easily tens of thousands in a long-lived account), this makes the asset-lookup phase of cdk gc cost roughly O(A x S x avg template size) — every asset re-scans every stack template from scratch.

Expected Behavior

cdk gc's active-asset lookup should scale roughly with total template size plus the number of assets being checked, not their product — it shouldn't get quadratically slower as an account accumulates more stacks and more garbage over time.

Observed Behavior

In a synthetic benchmark modeling a large, long-lived account (500 stacks x ~20KB templates, 50,000 orphaned assets processed in batches of 1000, matching cdk gc's real batch size), the asset-lookup phase alone took ~13.3s.

What's the environment?

• aws-cdk-cli main branch
• N/A (algorithmic, reproducible via unit benchmark, not environment-specific)

Other

I'll follow up with a PR that replaces the per-asset linear scan with a single multi-pattern search (Aho-Corasick) built once per batch, cutting the above benchmark to ~5.3s (~2.5x) with results verified identical to the current implementation (no false negatives/positives — this matters a lot here since a false negative would delete an asset that's still in use).