facebook / facebook/astryx

Markdown streaming: every chunk re-scans the whole document, so a long response is still superlinear to stream

Open
#5,406 0 comments 0 reactions 1 assignee Claimed by @cixzhang View on GitHub
Dominant language
TypeScript
Stars
13.1k
Forks
1.1k
Avg merge
1d 14h
Merged PRs (30d)
669

Description

`parseMarkdownIncremental` now keeps its settled blocks at every document
length — after [#5378](https://github.com/facebook/astryx/issues/5378) the worst
chunk of a streamed document rebuilds 3 blocks whether the document is 50
paragraphs or 500. Streaming is still superlinear anyway, because four things in
the function touch the **whole input** on every chunk, cache hit or not:

| `parser.ts` | per chunk |
| --- | --- |
| `extractLinkDefinitions(input)` `:1958` | scans the whole document for `[ref]:` lines |
| `input.split('\n')` `:1970` | allocates an array of every line |
| `findSettledBoundary(lines)` `:1971` | walks every line, tracking fences from the top |
| `mergeSettledBlocks(...)` `:2033` | copies the whole block array |

Measured with the perf suite's `generateAIResponse` fixture, 50-char chunks,
best of 5, on `main` at `1b0fab89661`:

| paragraphs | chars | whole stream | cost of the last chunk |
| --- | --- | --- | --- |
| 50 | 6.6k | 3.3ms | 0.033ms |
| 200 | 26k | 40.3ms | 0.130ms |
| 500 | 66k | 240.0ms | 0.388ms |
| 1000 | 132k | 1190.0ms | 1.236ms |

Doubling the document from 500 to 1000 paragraphs multiplies the cost of
streaming it by 5.

**What a person experiences.** No single token is slow — 1.2ms at two pages is
invisible next to a frame — so this is not the stutter #5378 was. It is main-
thread work that grows with the response: 1.2s of parsing spread across a
two-page answer today, four times that at four pages, on a device that may also
be rendering it.

**Shape of a fix.** The settled prefix is immutable by construction, so all four
of these can work on the tail: keep the line count and fence state for the
settled prefix in `IncrementalState` and scan only from the boundary; keep the
link-definition signature per settled prefix and extract only from the tail; and
hand back the previously-returned array when the settled blocks are reused
unchanged. That is a change to what `IncrementalState` carries, not a repair —
worth its own PR and its own before/after on the table above.

The invariant to assert is the one [#5379](https://github.com/facebook/astryx/pull/5379)
established for the cache: an integer that stays flat across a 10x document, not
a millisecond budget. Here it would be the cost of one chunk relative to the
document length.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.