tsc -b: builders idle on upstream projects because projects are scheduled in depth-first reference order

🔎 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 <root> --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.