Beagle SCM

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

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.