ReviewOS

home-lang/home

perf(markdown): resolve emphasis floods in linear time

#748
Closed glennmichael123 opened this 9 days ago ·
9 days ago

Parent

Confirmed parity gap

Home still uses the stale delimiter resolver: every closer scans backward across every already-consumed or inactive delimiter. Inputs shaped as ("a " x N) + ("a " x N) therefore take Theta(N^2), matching the copied Bun corpus regression in js/bun/md/md-edge-cases.test.ts.

Bun live Rust maintains 18 opener-bottom frontiers keyed by delimiter kind, run length modulo three, and can-open state, plus a path-compressed previous-candidate chain. Dead delimiter prefixes are skipped once and matched interiors are removed from later searches.

Scope

  • Port the opener-bottom and previous-candidate algorithm exactly into Home.
  • Preserve CommonMark rule-of-three, strikethrough exact-count, active delimiter, and repeated-closer semantics.
  • Propagate scratch allocation failure through the existing parser error set rather than silently degrading to quadratic behavior.
  • Verify ordinary nested emphasis output and adversarial scaling with a fair size-doubling benchmark.

No input cap, truncation, timeout change, or benchmark exception.

9 days ago

Implemented and pushed in 6bf5037.\n\nPorted Bun's 18-class opener-bottom frontier and path-compressed predecessor chain into Home's CommonMark emphasis resolver. This removes repeated prefix scans without imposing a depth/size cap, preserves ordinary emphasis/strong/strikethrough semantics, and propagates scratch-allocation failure.\n\nVerification:\n- focused real Markdown leaf suite: 17/17 passed\n- peak guarded tree footprint: 210 MB under the fixed 3,840 MB ceiling\n- Home direct ReleaseFast parser benchmark (best of 3):\n - N=20,000: 24.042 ms\n - N=40,000: 47.568 ms (1.98x)\n - N=80,000: 87.553 ms (1.84x)\n- pinned Bun control, same generated input:\n - N=20,000: 1.511 ms\n - N=40,000: 2.804 ms (1.86x)\n - N=80,000: 6.413 ms (2.29x)\n- zig ast-check, zig fmt --check, and git diff --check passed\n\nThe absolute Home/Bun timings are intentionally not treated as comparable because the Home measurement is a direct Zig leaf harness with testing allocator while Bun uses its optimized JS API. The fair conclusion is the size-doubling behavior: Home now scales linearly like Bun instead of quadratically.

Sign in to comment on this issue.