]> git.hungrycats.org Git - bees/commit
bees-plan: always collapse the op-split; drop the exact 2-D search
authorZygo Blaxell <bees@furryterror.org>
Thu, 2 Jul 2026 22:18:23 +0000 (18:18 -0400)
committerZygo Blaxell <bees@furryterror.org>
Sat, 5 Sep 2026 04:04:13 +0000 (00:04 -0400)
commitb1fe4287d94d597ffb458a438627be915c00a43e
treec358bfb2fff2c83099da96def6886adc6fe08d11
parent5c30856700a3f38dbc34e17a7d7cc8bd07f1a5b8
bees-plan: always collapse the op-split; drop the exact 2-D search

The coverage search kept two regimes: a collapsed one that merges the
(dedupe, copy) op dimensions into their sum (state set O(total_max) per
vertex) and an exact 2-D one used when total-max exceeds a per-type cap.
The exact regime was ~O(V^4) in the boundary count — a single dense
extent took 76 s at V=2048 and did not finish at V=4096 — and it bought
correctness only for the "total-max above a per-type cap" configuration,
which the V-budget greedy fallback and the acceptance gate now cover.

Always collapse.  The walk enforces only the total op limit (the
collapsed dimension); the per-type dedupe/copy caps are already
scan_next_rewrite_acceptable's authority on the final covering, so a
config that sets total-max above a per-type cap now gets a total-optimal
covering that acceptance rejects if it exceeds a per-type cap (do-nothing
wins) instead of paying the exact search's cost.  For every config where
each per-type cap is >= total-max — all defaults, and the recommended
"raise all limits together" tuning — this is bit-identical to before.

Removed: the collapse_ops predicate, the dominates() helper and the
non-collapse branches of add_state()/dominated(), and the dead
per-state copy fan-out (the swept copy-source front already serves every
copy landing).  within_limits() and the greedy fallback are now
total-only.

The former O(V^4) config now runs in tens of milliseconds where it took
tens of seconds (per test/bench-bees-plan.cc).  The brute-force oracle
test now enforces total-only (matching what the search optimizes) and so
exercises total-max-above-per-type configs too; its by-construction
assertion drops the per-type checks.  bench-bees-plan drops its now-
meaningless collapse-on/off label.

Assisted-by: Claude-Code:claude-opus-4-8
src/bees-plan.cc
test/bench-bees-plan.cc
test/test-bees-plan.cc