setFiberRef runs structural Equal.equals on the ref's value — O(value size) per set; makes interrupt-signal handling and FiberRef<collection> updates O(N²)

[tsushanth]

setFiberRef runs structural Equal.equals on the ref's value — O(value size) per set; makes interrupt-signal handling and FiberRef updates O(N²)

Repo: effect-ts/effect
Location: packages/effect/src/internal/fiberRefs.ts:224-240 (unsafeUpdateAs Equal.equals), triggered from fiberRuntime.ts:753-756 addInterruptedCause and any FiberRef.set/update of structural values
Severity: high · Confidence: 0.92
Type: complexity-at-a-distance

Description

fiberRefs.unsafeUpdateAs (packages/effect/src/internal/fiberRefs.ts:224-240, called by updateAs on every setFiberRef) executes Equal.equals(currentValue, value) to skip no-op updates. For values implementing structural equality (Cause, Chunk, HashMap, List...), Equal.equals hashes the NEW value, which is O(size): Cause's [Hash.symbol] (internal/cause.js proto) calls flattenCause(this) over the whole cause tree before caching. Cross-module chain: an InterruptSignal fiber message → FiberRuntime.processNewInterruptSignal → addInterruptedCause (fiberRuntime.ts:753-756) → setFiberRef(currentInterruptedCause, Cause.sequential(old, new)) → unsafeUpdateAs → Equal.equals → flattenCause of the i-th accumulated cause = O(i), so N interrupt signals to one fiber cost O(N²) with very heavy constants — a sweep to N=30,000 interrupts burned 20+ CPU-minutes without completing. The same mechanism hits the public API: N FiberRef.update calls appending to a Chunk held in the ref measured 4.89ms at N=500 vs 390ms at N=6000 (79.9x, vs O(N)=12x), and a control confirmed the appends alone are linear (1.6ms at N=6000) while append+Equal.equals reproduces the quadratic (213ms).

Benchmark

N FiberRef.update calls appending to a Chunk stored in the ref should scale as O(N²) because every setFiberRef deep-hashes the new Chunk (O(i) at step i) inside Equal.equals, while the raw Chunk appends alone are O(N). Measured: 79.9x at 12x N (O(N) predicts 12x, O(N²) predicts 144x); control shows append-only is flat-linear.

Observed complexity: O(N²)

| Input | median_ms | ratio | note |
|-------|-----------|-------|------|
| N=500 | 3.03 | 1.00 | — |
| N=1000 | 6.88 | 2.27 | — |
| N=2000 | 25.94 | 8.56 | — |
| N=6000 | 259.04 | 85.52 | flat linear |

append_plus_equals N=500→6000: 7.94→400.99ms (50.5x for 12x N, squarely O(N²)).

benchmark confirmed