Home's Markdown parser stores normalized reference definitions in an ArrayList but resolves and deduplicates them with linear scans.\n\nConfirmed stale paths:\n- packages/runtime/src/md/ref_defs.zig lookupRefDef scans every RefDef\n- packages/runtime/src/md/ref_defs.zig buildRefDefHashtable scans every prior definition\n- packages/runtime/src/md/blocks.zig consumeRefDefsFromCurrentBlock repeats the same scan\n\nFor D definitions and R references, missing/reference-tail lookups become O(D x R). The copied Bun regression test at packages/runtime/test/test/js/bun/md/md-edge-cases.test.ts builds 100,000 definitions and 120,000 misses specifically to catch this.\n\nBun's live Rust parser carries ref_def_labels: StringSet, inserts normalized labels in lockstep with ref_defs, and obtains the vector index from the ordered hash set for O(1)-average lookup.\n\nAcceptance:\n- port an owned normalized-label index with exact first-definition-wins behavior\n- use the same index in both definition ingestion paths and lookup\n- preserve reference rendering semantics and resource ownership\n- propagate/handle allocation failures consistently; no input cap or shortcut\n- verify ordinary first/last/missing/duplicate definitions\n- run a fair size-doubling stress benchmark under the fixed 3,840 MB guard\n- update #66 with the commit and exact evidence
perf(markdown): index reference definitions
#749Implemented and pushed in c065a00.\n\nPorted Bun's normalized-label index across all three stale Home paths:\n- lookupRefDef now hashes normalized labels to stable ref_defs indices\n- consumeRefDefsFromCurrentBlock uses the index for first-definition-wins deduplication\n- buildRefDefHashtable uses the same index\n- vector/hash capacity is reserved before either structure mutates, so OOM cannot desynchronize indices\n- normalized lookup temporaries are released\n- stored label/destination/title buffers are released during Parser teardown\n\nVerification:\n- focused real Markdown leaf suite: 17/17 passed\n- allocator leak check: clean (the initial run exposed and then drove the ownership fix)\n- guarded peak tree footprint: 185 MB under the fixed 3,840 MB ceiling\n- Home direct ReleaseFast parser size-doubling benchmark (Mach ticks, best of 3):\n - N=10,000 definitions + misses: 1,199,735\n - N=20,000: 2,352,117 (1.96x)\n - N=40,000: 4,798,583 (2.04x)\n- pinned Bun control:\n - N=10,000: 2.997 ms\n - N=20,000: 6.015 ms (2.01x)\n - N=40,000: 11.782 ms (1.96x)\n- ordinary first/last/missing and duplicate-first-wins rendering passed\n- zig ast-check, zig fmt --check, and git diff --check passed\n\nAbsolute timings are not compared because Home uses a direct Zig leaf harness and Bun uses its optimized JS API. The fair result is matching linear size-doubling behavior instead of O(definitions x references).
Sign in to comment on this issue.