renderData (s3-deployment Source.data) is quadratic in the number of tokens
- 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
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