aws / aws/aws-cdk-cli

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

Open
#1,860 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.