microsoft / microsoft/TypeScript
tsc -b: builders idle on upstream projects because projects are scheduled in depth-first reference order
- Dominant language
- Go
- Stars
- 111k
- Forks
- 14.3k
- PR merge metrics
- PR metrics pending
Description
### 🔎 Search Terms
tsc -b, build mode, --builders, project references, parallel build, idle builders, build order, depth-first, tsgo
### 🕗 Version & Regression Information
- TypeScript 7.0.2 (`@typescript/native-preview`) and `main` (7.1.0-dev). Not a regression: the scheduling has always worked this way in the Go build orchestrator.
### ⏯ Playground Link
Not applicable (build-mode scheduling).
### 💻 Code
Any wide project-reference graph with `tsc -b --builders N`. The root's `references` are handed to builders in the depth-first (topological) order, e.g. for
```
root -> A -> B -> C -> D (a chain)
root -> E, F, G, H, ... (many independent leaves)
```
the order is `D, C, B, A, E, F, G, H, …`. Builder 1 takes `D`, builder 2 takes `C` and blocks on `D`, builder 3 takes `B` and blocks on `C`, builder 4 takes `A` and blocks on `B`. Only after the chain is done do the leaves get built, even though they were buildable from the start.
### 🙁 Actual behavior
Builders spend most of their time blocked in `waitOnUpstream`. On a monorepo of 19,430 composite projects (dependency graph 124 levels deep) a cold `tsc -b` on a 64-core machine kept ~13 of 32 builders busy on average. Sorting the root `references` by dependency depth by hand cut the cold build from 5.4 to 4.1 min, and the reference order of a config file should not have that effect.
### 🙂 Expected behavior
The builders should be kept busy regardless of how `references` are ordered: schedule projects so that every project at a lower dependency depth has been picked up before a builder takes a deeper one (a stable sort of the topological order by depth), while keeping the reported output order unchanged.
### Additional information about the issue
Measured with a patched build of `main` (`--builders 8`, cold, 4 runs each): alphabetical root 530 s → 262 s median (2.0× faster), depth-sorted root 442 s → 261 s. CPU time unchanged (~3,150 s user), so the gain is idle time removed; peak RSS +15% because more builders actually compile at once. I have a PR for this.
Contributor guide
Assessment
This issue has not been assessed yet.