DIS-047: weave/graf 3-way merge is very slow on large files

Now:: DONE

GRAFMergeWtFile / WEAVEMerge is very slow merging a large file (beagle/BE.cli.c, ~5k lines) during be get. Surfaced updating the JS-027 worktree. Method: Issues.

Input

Context

be get onto trunk 371ad14b weave-merged beagle/BE.cli.c (both sides edited it: SUBS-027b be-head + the JS-025 hook) — "merge of BE.cli.c was veeerey slow" (user, direct observation).
BE.cli.c is ~5000 lines; the single-file merge took noticeably long.
Path: GRAFMergeWtFileTunable (graf/GET.c:301) → WEAVEMerge / GRAFMerge3Bytes / WEAVENext (dog/WEAVE). Suspect superlinear token scan or repeated whole-blob rewrites per WEAVENext (the blob is rewritten whole — see dog/WEAVE.h "rewrite the whole blob").

Goals

Profile the merge on a large file; bring it to ~linear. Add a bench that makes a regression brutally obvious (CLAUDE.md §3).

Constraints

dog/WEAVE (WEAVEMerge/WEAVEEmitMerged) + graf/GET.c. Measure before optimizing.

WIP

Design decisions

(open) find where the time goes (token identity scan? per-step whole-blob rewrite?) before touching the hot loop.

TODOs

Bench: WEAVEMerge on a 5k-line file; capture baseline time + apparent complexity.
Optimize the hot path; assert the bench improvement.

Blockers

None.

Outcome

LANDED 5b062e24 (2026-06-21): O(n²)→linear WEAVEMerge Pass-2 remover-union (dog/WEAVE.c) — prefix-sum slots + one scatter pass + compaction via the existing umap, order-preserving so merge output is BYTE-IDENTICAL. 212× faster (N=5k: 9777ms→46ms; doubling 4.04×→2.27×). Bench dog/test/WEAVE04.c (DWEAVE04test, fails if ratio ≥ 3.0). FUZZ-VALIDATED: DWEAVEfuzz 235k runs × 16 jobs / 10 min, 0 crashes / 0 oracle failures / 0 sanitizer findings (corpus `/src/Corpus/dweave`).