perf(toolkit-lib): cdk gc's active-asset lookup is O(assets x stacks x template size)
- Dominant language
- TypeScript
- Stars
- 105
- Forks
- 122
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 71
Description
### 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`](https://github.com/aws/aws-cdk-cli/blob/main/packages/%40aws-cdk/toolkit-lib/lib/api/garbage-collection/stack-refresh.ts):
```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).
Contributor guide
Research direction
Read packages/@aws-cdk/toolkit-lib/lib/api/garbage-collection/stack-refresh.ts, then trace the ActiveAssetCache.contains() calls from garbage-collector.ts. Reproduce the synthetic benchmark described in the issue and verify that the replacement preserves the current lookup results; done means lookup scales with total template size plus checked assets rather than rescanning every template for each asset.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- aws, typescript
- Domain
- cli, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100