Skip to content

perf(ext/fetch): remove quadratic line buffering in EventSource#35881

Merged
bartlomieju merged 3 commits into
denoland:mainfrom
tomas-zijdemans:perf/text-line-stream-quadratic
Jul 15, 2026
Merged

perf(ext/fetch): remove quadratic line buffering in EventSource#35881
bartlomieju merged 3 commits into
denoland:mainfrom
tomas-zijdemans:perf/text-line-stream-quadratic

Conversation

@tomas-zijdemans

@tomas-zijdemans tomas-zijdemans commented Jul 8, 2026

Copy link
Copy Markdown
Contributor

An SSE event carrying a large single-line data: payload stalls the built-in
EventSource with quadratic CPU on the event loop — 2.6 seconds of
blocking work for one 8 MiB line. This PR makes line splitting linear,
bringing wall time to Node parity:

single data line baseline this PR Node 26.3
2 MiB 184 ms 20 ms (9x) 28 ms
4 MiB 651 ms 26 ms (25x) 25 ms
8 MiB 2,675 ms 46 ms (58x) 42 ms

Single data: line delivered in 1460-byte fragments to the real built-in
EventSource; medians of 5, macOS aarch64. Both Deno binaries were built
from the same tree with the same profile — the baseline is this branch's
base commit, so the only difference is this diff. The Node column is the
same workload against Node's EventSource (undici,
--experimental-eventsource). Every run integrity-verified: received event
length exact and every byte checked against the sent pattern.

The baseline's ~3.7x growth per size doubling is the signature of the bug.
With this PR, growth is linear: ~5 ms of marginal cost per 2 MiB on top of
~15 ms of fixed connection overhead. Payloads this size are not exotic —
one SSE event carrying a large single-line JSON payload (LLM tool results,
base64 images) is enough, and a server that never sends a newline can pin
the client's event loop with quadratic work indefinitely.

Cause

The private TextLineStream copy in ext/fetch/27_eventsource.js
re-concatenates its entire pending buffer into every incoming fragment
(chunk = this.#buf + chunk) and re-slices the remaining tail once per
extracted line. When a line spans many network reads, each fragment costs
O(buffered bytes), so the total is O(n^2) in the line length. There is a
second quadratic behind the first: with allowCR: true (always on for
EventSource), indexOf("\r") rescans from position 0 for every line
extracted from a multi-line chunk.

This is the same bug as [denoland/std#7211], which fixes the @std/streams
TextLineStream this code was originally copied from. The built-in carries
its own copy, so it needs its own fix; the two land independently.

Fix

Same approach as the std PR. Fragments that cannot complete a line are
pushed to an array (O(1)) and joined only when a fragment arrives that
contains a line terminator. Complete lines are then extracted with
position-based indexOf(x, start) instead of re-slicing the remainder,
and the position of the next CR is cached across loop iterations, which
removes the second quadratic. Emitted lines are byte-identical to the
previous implementation (see Verification).

No regression on the common case

Small events were already fine and stay that way: 50,000 events of ~120 B
(one JSON token-delta frame per event, 1460 B fragments, real
EventSource end to end) run in 48 → 44 ms (~0.9 µs/event), medians
of 5, all 50,000 events received and length-checked on every run.

Verification

  • Differential fuzz — the old #handle/flush implementation
    verbatim vs the new one: ~300,000 cases across 5 PRNG seeds, random
    fragmentation (including empty chunks and splits inside \r\n) over 8
    adversarial alphabets (pure \r, pure \n, CR-heavy, terminator-free,
    mixed), both allowCR modes, plus directed edge cases (trailing \r
    at chunk end, CR resolved by the next chunk, CR at EOF). Emitted line
    sequences byte-identical in every case.
  • End-to-end differential — 13 SSE payloads (CR/LF/CRLF mixes, BOM,
    comments, multi-line data, field parsing, id/retry, trailing CR at EOF)
    served at 5 fragment sizes (1/2/3/7/4096 bytes) to baseline and patched
    binaries. The observed MessageEvent sequences (data, type, lastEventId)
    are identical.
  • cargo test unit::event_source_test passes on the patched tree.
  • tools/format.js and tools/lint.js --js pass.
Benchmark source
// Single long SSE data line delivered in TCP-sized fragments to the
// built-in EventSource. Usage: deno run -A bench.ts
const enc = new TextEncoder();
const sizes = [2 * 1024 * 1024, 4 * 1024 * 1024, 8 * 1024 * 1024];
let currentSize = 0;
const ac = new AbortController();
const portReady = Promise.withResolvers<number>();
Deno.serve({
  port: 0,
  signal: ac.signal,
  onListen: ({ port }) => portReady.resolve(port),
}, () => {
  const FRAG = 1460; // typical TCP segment payload
  const full = `data: ${"x".repeat(currentSize)}\n\n`;
  let off = 0;
  return new Response(
    new ReadableStream({
      pull(c) {
        if (off < full.length) {
          c.enqueue(enc.encode(full.slice(off, off + FRAG)));
          off += FRAG;
        } else {
          c.close();
        }
      },
    }),
    { headers: { "content-type": "text/event-stream" } },
  );
});
const PORT = await portReady.promise;
for (const size of sizes) {
  currentSize = size;
  const t0 = performance.now();
  const es = new EventSource(`http://127.0.0.1:${PORT}/`);
  const data = await new Promise<string>((resolve, reject) => {
    es.onmessage = (ev) => {
      if (ev.data.length !== size) reject(new Error("bad size"));
      es.close();
      resolve(ev.data);
    };
    es.onerror = () => {};
  });
  const dt = performance.now() - t0;
  // Integrity: verify every received byte (outside the timed region).
  for (let i = 0; i < data.length; i++) {
    if (data[i] !== "x") throw new Error(`bad byte at ${i}`);
  }
  console.log(`${size / 1024} KiB: ${dt.toFixed(0)} ms (integrity OK)`);
}
ac.abort();

The Node reference script, the small-events regression guard, and both differential test harnesses are separate scripts; happy to paste them on request.

I used Cursor (Claude) to help investigate and write this change.

@bartlomieju
bartlomieju enabled auto-merge (squash) July 15, 2026 09:54
@bartlomieju
bartlomieju disabled auto-merge July 15, 2026 10:27
@bartlomieju
bartlomieju enabled auto-merge (squash) July 15, 2026 10:27
@bartlomieju
bartlomieju merged commit 17f28bc into denoland:main Jul 15, 2026
136 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants