Finding — Asymptotic time complexity: O(E²)
Subsystem: Manager (src/manager.ts:143–170), Persist (src/persist.ts:50–86)
Input variables
E = number of events in persist.dat (grows with total enqueue+dequeue operations since last restart — unbounded)D = maximum queue depth reached during replay (D = E/2 in the worst-case bulk-dequeue pattern)
Current complexity
- Time: O(E + D²) → O(E²) worst case (bulk-dequeue pattern)
- Space: O(E) — entire event log read into memory, parsed, and held
Cause
load() replays the append-only event log event-by-event. Each dequeue event calls queue.shift() (src/manager.ts:160), which reindexes the entire backing array — O(current depth) per call. In the bulk-dequeue pattern (enqueue D items, then dequeue D — a realistic "queue builds up, then drains" workload), accumulated shift cost = D + (D-1) + ... + 1 = O(D²/2) = O(E²/4).
Evidence (MemoryStore replay, isolating from file I/O)
| Events |
Time (median) |
Ratio |
| 2,000 |
0.53 ms |
— |
| 8,000 |
3.23 ms |
6.05× (4× events) |
| 32,000 |
26.62 ms |
8.24× (4× events) |
Super-linear scaling (8.24× for 4× input) confirms the quadratic term becoming dominant. The alternating pattern (depth ≤ 1, each shift is O(1)) scales linearly: 2,000→32,000 (16×) = 15.8× — isolating shift() as the sole quadratic factor.
Runtime: Deno 2.7.6, V8 14.6.202.9-rusty, darwin (Apple Silicon)
Remediation direction
Replace the Array-backed queue with a doubly-linked list or ring buffer (O(1) dequeue). This fixes both this issue and the per-request dequeue cost. Alternatively, snapshot current state instead of replaying the full event log.
Confidence
High — source analysis + benchmark. Uncertainty: real-world event-log size depends on uptime and traffic; a short-lived process never reaches large E.
Related
Shares the same root cause (Array.shift() for FIFO dequeue) as the per-request dequeue performance issue. One data-structure fix resolves both.
Finding — Asymptotic time complexity: O(E²)
Subsystem: Manager (
src/manager.ts:143–170), Persist (src/persist.ts:50–86)Input variables
E= number of events inpersist.dat(grows with total enqueue+dequeue operations since last restart — unbounded)D= maximum queue depth reached during replay (D = E/2in the worst-case bulk-dequeue pattern)Current complexity
Cause
load()replays the append-only event log event-by-event. Each dequeue event callsqueue.shift()(src/manager.ts:160), which reindexes the entire backing array — O(current depth) per call. In the bulk-dequeue pattern (enqueue D items, then dequeue D — a realistic "queue builds up, then drains" workload), accumulated shift cost = D + (D-1) + ... + 1 = O(D²/2) = O(E²/4).Evidence (MemoryStore replay, isolating from file I/O)
Super-linear scaling (8.24× for 4× input) confirms the quadratic term becoming dominant. The alternating pattern (depth ≤ 1, each shift is O(1)) scales linearly: 2,000→32,000 (16×) = 15.8× — isolating shift() as the sole quadratic factor.
Runtime: Deno 2.7.6, V8 14.6.202.9-rusty, darwin (Apple Silicon)
Remediation direction
Replace the Array-backed queue with a doubly-linked list or ring buffer (O(1) dequeue). This fixes both this issue and the per-request dequeue cost. Alternatively, snapshot current state instead of replaying the full event log.
Confidence
High — source analysis + benchmark. Uncertainty: real-world event-log size depends on uptime and traffic; a short-lived process never reaches large E.
Related
Shares the same root cause (Array.shift() for FIFO dequeue) as the per-request dequeue performance issue. One data-structure fix resolves both.