DOG-017: WEAVEMerge global qsort is ~half the merge; bucket by anchor instead

Now: OPEN
Sev: MED

Retroactive ticket (2026-07-07 libdog WEAVE perf session). After DIS-047 removed the Pass-2 remover-union quadratic, a three-agent audit + phase profile of WEAVEMerge (libdog WEAVE.c) showed the RGA-linearise $sort(sks, rga_cmp) was still ~~49% of merge wall time (musl smoothsort + an indirect call per compare; 79.9 ms of 164 ms at N=10k lines, -O2), plus~~ 19% more in the per-pop gmap hash probe of PUSH_CHILDREN. The emit DFS never needs a global order — only each anchor's sibling group contiguous and internally (cidx DESC, ord ASC)-sorted — so the sort is replaceable by O(nu) bucketing with byte-identical output. Also the n·log n term was the main superlinear creep behind DIS-047's WEAVE04 ratio gate (the gate itself proved VM-flaky on mac CI and was disabled the same session).

Input

Context

WEAVE.c (libdog): rgakey qsort + gmap group map, old :819-842; DFS probe per pop in PUSH_CHILDREN, old :869-887. Bench test/WEAVE04.c.
Measured (-O2, N=10k, nu=154k union tokens): qsort 48.8%, DFS push/pop 18.7%, decode 8.1%, pass1 8.0%, emit 6.6%, pass2 4.7%; merge grows 5.5x for 4x work.
Sibling groups are almost always 1-2 tokens; group-vs-group order is unused by the DFS, so a global (anchor, cidx, ord) sort does O(n log n) wasted work.

Goals

Replace the global sort: hash-bucket tokens by anchor, insertion-sort within each (tiny) sibling group; resolve each group's parent ONCE so the DFS pushes children by direct index (no hash probe per pop).
Byte-identical merge output (DIS-044 tie-break preserved verbatim); all tests green; ~2x+ faster WEAVEMerge on the WEAVE04 workload.

Constraints

libdog ABC style; no wire-format change; no behaviour change under idh/anchor hash collisions (seen guard semantics kept, stack stays 2*nu+1).

WIP

Design decisions

Bucketing is count → prefix-sum → insertion-scatter into a flat gtok[]; per-token-parent cstart/ccnt arrays replace per-pop gmap probes (ROOT group kept addressable via a colliding idh, as before).
Proof of equivalence: old WEAVEMerge from git HEAD symbol-renamed via objcopy, linked beside the new one; 96 scenarios x 6 merges (both arg orders, chained re-merges, deletes, N=1..5000) memcmp'd — 0 mismatches.

TODOs

T1 bucket-by-anchor + per-group insertion sort replacing $sort/rga_cmp.
T2 per-parent cstart/ccnt child runs; probe-free PUSH_CHILDREN.
T3 differential old-vs-new byte-identity harness; 66/66 ctest green.
T4 bench: -O2 56.8→21.4 ms (N=5k), 133.2→55.7 ms (N=10k); -O0 ~1.5x.
T5 land the commit in libdog; record the hashlet below.

Blockers and bummers

Remaining superlinear creep is u64map cache misses at N>>10k, not compute; interleaved key/val slots would help — that is DOG-013 T2 (u64map→HASHx) territory. wmerge_commits O(C^2) tail scan is a separate follow-up candidate.
Test/bench builds run -O0 (TEST_CXX_FLAGS "-g", empty CMAKE_BUILD_TYPE), so CI times an unshipped build; WEAVE04's ratio gate is disabled pending that.

Outcome

Implemented + verified 2026-07-07; sits uncommitted in the libdog working tree together with the WEAVE04 gate disable. Hashlet TBD on landing.
Audit 2026-07-07: confirmed — ~/src/libdog has M WEAVE.c (uncommitted; rga_cmp/$sort(sks…) absent in the worktree copy, still present in HEAD 79612854); the WEAVE04 ratio-gate disable is ALREADY landed (commented out at test/WEAVE04.c:135). Only T5 (land) remains.