Fiber message queue dequeues with Array.splice(0,1) — O(N²) to drain N queued messages
Repo: effect-ts/effect
Location: packages/effect/src/internal/fiberRuntime.ts:676 (drainQueueOnCurrentThread) and :729 (drainQueueWhileRunning); producers at fiberScope.ts:43 Local.add and FiberRuntime.tell/unsafeInterruptAsFork
Severity: medium · Confidence: 0.88
Type: complexity-at-a-distance
Description
FiberRuntime._queue is a plain array dequeued with this._queue.splice(0, 1)[0] in both drainQueueOnCurrentThread (packages/effect/src/internal/fiberRuntime.ts:676) and drainQueueWhileRunning (fiberRuntime.ts:729) — each dequeue shifts every remaining element, so draining N queued messages is O(N²). Producers live in other modules: fiberScope.ts Local.add sends a Stateful message to the parent via parent.tell on EVERY fork, and fiber.unsafeInterruptAsFork/ask enqueue InterruptSignal/Stateful messages; when the target fiber is mid-op (tell() only pushes while _running), bursts accumulate and the next runLoop iteration drains them quadratically. Validated on effect 3.21.4 by enqueuing N no-op Stateful messages from within a running fiber: 0.38ms at N=2,000 vs 483ms at N=60,000 — a 1283x increase for 30x N, matching the O(N²) prediction of 900x (GC pushes it slightly past). The fix is a head-index or ring-buffer FIFO; severity is medium because large single-fiber bursts require interrupt storms or fork bursts rather than steady-state traffic.
Benchmark
Enqueuing N no-op Stateful messages onto a running fiber and letting the run loop drain them should scale as O(N²) due to splice(0,1) shifting the remaining queue on every dequeue, while the message handlers themselves are O(1). Measured: 1283x at 30x N (O(N) predicts 30x, O(N²) predicts 900x).
Observed complexity: O(N²)
| Input | median_ms | ratio | note |
|-------|-----------|-------|------|
| N=2000 | 0.455 | 1.00 | — |
| N=10000 | 5.561 | 12.23 | — |
| N=20000 | 35.202 | 77.40 | — |
| N=60000 | 292.011 | 642.02 | — |
benchmark confirmed
Fiber message queue dequeues with Array.splice(0,1) — O(N²) to drain N queued messages
Repo:
effect-ts/effectLocation: packages/effect/src/internal/fiberRuntime.ts:676 (drainQueueOnCurrentThread) and :729 (drainQueueWhileRunning); producers at fiberScope.ts:43 Local.add and FiberRuntime.tell/unsafeInterruptAsFork
Severity: medium · Confidence: 0.88
Type: complexity-at-a-distance
Description
FiberRuntime._queue is a plain array dequeued with
this._queue.splice(0, 1)[0]in both drainQueueOnCurrentThread (packages/effect/src/internal/fiberRuntime.ts:676) and drainQueueWhileRunning (fiberRuntime.ts:729) — each dequeue shifts every remaining element, so draining N queued messages is O(N²). Producers live in other modules: fiberScope.ts Local.add sends a Stateful message to the parent via parent.tell on EVERY fork, and fiber.unsafeInterruptAsFork/ask enqueue InterruptSignal/Stateful messages; when the target fiber is mid-op (tell() only pushes while _running), bursts accumulate and the next runLoop iteration drains them quadratically. Validated on effect 3.21.4 by enqueuing N no-op Stateful messages from within a running fiber: 0.38ms at N=2,000 vs 483ms at N=60,000 — a 1283x increase for 30x N, matching the O(N²) prediction of 900x (GC pushes it slightly past). The fix is a head-index or ring-buffer FIFO; severity is medium because large single-fiber bursts require interrupt storms or fork bursts rather than steady-state traffic.Benchmark
Enqueuing N no-op Stateful messages onto a running fiber and letting the run loop drain them should scale as O(N²) due to splice(0,1) shifting the remaining queue on every dequeue, while the message handlers themselves are O(1). Measured: 1283x at 30x N (O(N) predicts 30x, O(N²) predicts 900x).
Observed complexity: O(N²)
benchmark confirmed