[compiler] Avoid quadratic Array.shift() in three worklist traversals #37582

Open
sleitor opened 4:39am on September 11, 2026 wants to merge 1 commit into facebook/react main from
fix-37414

Summary

Three breadth-first/worklist traversals dequeue with Array.shift(): queued program functions, HIR reachability shrinking, and control post-dominators. Each dequeue moves every remaining array entry, making the queue portion quadratic on large inputs.

Expected behavior

Queue traversal should advance a cursor over the append-only worklist so every queued item is visited once without repeatedly moving the remainder.

Actual behavior

All three loops repeatedly call shift() until empty. Output order is FIFO, but queue maintenance scales as O(nΒ²).

Version

React Compiler main 2dc7da790d63.

Diff Delta:
0
About 0 Diff Delta/hour
Classified as:  General

sleitor's Description of Work #37414 React Compiler uses quadratic array queues in three traversals

Summary

Fixes #37414.

Three BFS/worklist traversals in the React Compiler dequeue with Array.prototype.shift():



  • compileProgram's worklist of functions to compile (Entrypoint/Program.ts)

  • HIR reachability shrinking, _shrink (HIR/HIRBuilder.ts)

  • control-flow post-dominator computation, postDominatorsOf (Inference/ControlDominators.ts)

Array.prototype.shift() is O(n) because it re-indexes every remaining element, so looping shift() until the queue is empty makes each of these traversals O(nΒ²) instead of O(n) on large inputs.

All three queues are append-only worklists (items are only ever pushed, and visited/seen-set checks prevent re-processing), so the front element never needs to be physically removed. This PR replaces each shift()-based loop with an index cursor (let queueIndex = 0; while (queueIndex < queue.length) { const item = queue[queueIndex++]; ... }) that advances over the same backing array. Traversal order (FIFO) and dequeue/visit behavior are unchanged β€” only the O(n) removal cost per dequeue is eliminated.

How did you test this change?



  • yarn workspace babel-plugin-react-compiler lint β€” passes


  • tsc --noEmit for babel-plugin-react-compiler β€” passes


  • yarn workspace babel-plugin-react-compiler test (fixture/snapshot suite) β€” passes, no fixture output changes (traversal order is identical since these are FIFO append-only worklists)

3 total changed files
Loading changes...
Loading changes...
Loading changes...
You’ve reached the end
Please mind the merge button