From 5c30856700a3f38dbc34e17a7d7cc8bd07f1a5b8 Mon Sep 17 00:00:00 2001 From: Zygo Blaxell Date: Thu, 2 Jul 2026 17:53:11 -0400 Subject: [PATCH] scan-next: abandon candidate search on high-V start extents MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The Plan A coverage search is O(V^2) in the boundary count and holds the start extent's Exclusion for its whole duration, so a start extent that accumulates a large, dense match pool can pin a worker and starve every task queued behind that extent. scan_next_plan_shortest_path already falls back to the linear greedy cover above rewrite.plan-max-vertices, but candidates kept flowing into the plan: the Planner loop dispatched every candidate to every plan and only stopped globally once no plan continued, so as long as Plan B still wanted candidates Plan A's pool — and its V — kept growing. Raise the abandon decision to the two places that act on it. update_continues() now clears continues() once the accumulated boundary count exceeds the vertex budget, and the Planner loop skips any plan whose continues() is already false instead of feeding it more candidates. Together these stop Plan A's pool from growing past the point where the greedy fallback has taken over, while its best-so-far still enters selection via finalize(), competing against Plan B and the do-nothing floor. The loop skip also stops feeding a fully-covered Plan A (its existing coverage-based continues()=false) and the always-false do-nothing plan (whose process_candidate is a no-op), neither of which could benefit from further candidates. Assisted-by: Claude-Code:claude-opus-4-8 --- src/bees-scan-next.cc | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/src/bees-scan-next.cc b/src/bees-scan-next.cc index e64d77df..33b2f498 100644 --- a/src/bees-scan-next.cc +++ b/src/bees-scan-next.cc @@ -2229,6 +2229,17 @@ BeesStartAsDstPlan::update_continues() return; } + // High-V abandon: once the accumulated match pool exceeds the planner's + // vertex budget, the shortest-path search would fall back to the greedy + // cover anyway (bees-plan.cc), and every further candidate only enlarges V + // (and the Exclusion hold time). Signal the planner to stop feeding this + // plan candidates; finalize()/ensure_selection() still produces the greedy + // best-so-far, which competes in selection against Plan B and do-nothing. + if (boundary_count() > m_policy.m_plan_max_vertices) { + m_continues = false; + return; + } + // Merge all accepted match dst-spans (each lies within a data region by // construction), then require every data region to fall inside one // merged interval. Merged intervals are maximal and gap-separated, so @@ -3520,6 +3531,15 @@ Planner::run(const BtrfsTreeItem &bti, bool any_continues = false; for (auto &plan : plans) { + // A plan whose continues() is already false has signalled + // it wants no more candidates (fully covered, or its + // coverage search hit the vertex budget and abandoned). + // Honor that per-plan: stop feeding it, so its match pool — + // and its search's boundary count V — stop growing. Its + // best-so-far still enters selection via finalize() below. + if (!plan->continues()) { + continue; + } // Plan-agnostic dispatch: each plan owns its own // per-role filter check inside process_candidate // and returns without state change on rejection. -- 2.53.0