aws / aws/aws-cdk

renderData (s3-deployment Source.data) is quadratic in the number of tokens

Open Beginner friendly
#38,768 0 comments 0 reactions 0 assignees View on GitHub
@aws-cdk/aws-s3-deployment bug p2
Dominant language
TypeScript
Stars
12.9k
Forks
4.6k
Avg merge
2d 3h
Merged PRs (30d)
83

Description

### Describe the bug

`renderData` (used by `s3deploy.Source.data()` / `Source.jsonData()`) is **O(n²)** in the number of tokens in the source string.

`TokenToMarkerMapper.mapToken` derives each marker id from the size of the marker map it is in the middle of filling:

```ts
// packages/aws-cdk-lib/aws-s3-deployment/lib/render-data.ts
mapToken(token: IResolvable) {
const newMarker = `<>`;
this.markers[newMarker] = token.toString();
return newMarker;
}
```

`mapToken` is called once per token fragment by `Tokenization.reverseString(data).mapTokens(...)`. `Object.keys(this.markers).length` materializes the full key array on **every** call just to read its length, which is `O(k)` per token and therefore `O(k²)` over `k` tokens.

This is the same shape as the `tree.json` quadratic fixed in #38761 / #38762.

### Expected Behavior

`renderData` scales linearly with the number of tokens.

### Current Behavior

Quadratic. Benchmark of the real `renderData` on a string of `n` interleaved literal + `Lazy` token fragments (Node 24, `aws-cdk-lib` local build):

| n tokens | current (ms) | with counter (ms) | speedup |
|---:|---:|---:|---:|
| 1,000 | 18.0 | 1.3 | 14× |
| 2,000 | 71.6 | 2.7 | 27× |
| 4,000 | 324.9 | 7.2 | 45× |
| 8,000 | 1,510.3 | 23.0 | 66× |
| 16,000 | 7,204.2 | ~413 | 17× |
| 32,000 | 35,301.6 | ~417 | 85× |

Time roughly quadruples per doubling of `n` today; with the fix it is flat/linear (the residual at 16k–32k is token resolution + GC, not the marker loop).

### Reproduction Steps

Call `s3deploy.Source.data()` (or `jsonData`) with a large string containing many tokens (e.g. a big JSON config interpolating thousands of resource attributes) and observe synth time.

### Possible Solution

Track a running counter on the mapper instead of re-measuring the map:

```ts
const newMarker = `<>`;
```

Ids are generated in the same order with the same values, so the emitted markers and marker map are **byte-for-byte unchanged** (existing `content.test.ts` already pins ids to `0,1,2,…`).

### Other information

Found while sweeping the codebase for the pattern fixed in #38761.

### CDK CLI Version

N/A (framework)

### Framework Version

main / aws-cdk-lib latest

### Language

TypeScript

Contributor guide

Open the contributing guide

Research direction

Start in packages/aws-cdk-lib/aws-s3-deployment/lib/render-data.ts, focusing on TokenToMarkerMapper.mapToken and how renderData processes Tokenization.reverseString(data). Review the existing content.test.ts coverage for marker IDs, then run the relevant aws-s3-deployment tests. Done means renderData scales linearly for many token fragments while preserving the existing marker output and IDs.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
performance
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
88/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.