Repository navigation
perf(parser): unclosed [ and emphasis-opener runs parse in quadratic time #4
Description
Runs of unclosed openers make parse() and parseInline() super-linear. A file of a few hundred KB freezes whatever thread parses it, and every inline-markdown reader in osionos parses on the main thread.
Measured (2026-11-07)
Unclosed [ (node, parse(); osionos ADR 0009, F2):
| input | time |
|---|---|
25k [ |
406 ms |
50k [ |
1600 ms |
100k [ |
6080 ms |
50k [ across 500 lines |
2381 ms |
| 1 MiB | ~10 min, estimated (extrapolated, not run) |
Unclosed emphasis openers, "*a ".repeat(N) + "x" (node 26; ADR 0009, G3). Commit 674dd65 caches the escape/backtick indexOf in matchStackedEmphasis (markdown/parserInlineMatchers.ts), which turns cubic into quadratic. It does not remove the problem:
| N | before 674dd65 | after 674dd65 |
|---|---|---|
| 5000 | 1061 ms | 133 ms |
| 10000 (30 KB) | 7528 ms | 540 ms |
| 20000 (60 KB) | — | 2201 ms ("_a ": 2473 ms) |
| 80000 (240 KB) | — | 32,932 ms |
On node 22.23.4 the same N=10000 takes 754 ms (*) / 728 ms (_) after 674dd65. Before it, the time was 45,831 ms. The regression guard is bench/emphasis-runs.test.cjs (3000 ms budget at N=10000).
What would fix it
The opener searches re-scan forward from every unmatched opener. A delimiter stack (CommonMark's "process emphasis" with per-length openers-bottom bounds) makes both runs linear. Until then, callers bound the input: osionos's editor-page preview parses in a worker with a 3 s budget (ADR 0009, D2).
Refs Univers42/osionos ADR 0009 (EP7, EP19).
Activity
updated
perf(inline): unclosed [ and emphasis openers parse in linear time
perf(inline): memoize failed emphasis scans with no canClose candidate
fix: restore parserInlineMatchers.ts with linear emphasis memo (refs #4)