Skip to content

Each parent found after a recursive scan's cap rescans the whole wordlist #398

Open

Description

@TMHSDigital

Summary

Since #394, a recursive scan's parent found after the budget stopped admission calls stopAdmitting again. stopAdmitting rebuilds its lookup tables with a pass over the whole wordlist on every call, so each late parent costs O(wordlist) on the dispatcher goroutine.

Where

  • internal/scan/dispatcher.go:467-475 (expand, case d.capped)
  • internal/scan/dispatcher.go:324-340 (countUnbuilt builds labels/index over all entries)
  • internal/scan/dispatcher.go:366-381 (countUnbuiltRepeats builds prefixes/walk over all entries)

Details

countUnbuilt (single-label entries with any exact -exclude pattern) and countUnbuiltRepeats (multi-label entries, no exclusions) each start with for i, entry := range d.cfg.Entries { … } to build tables that depend only on Entries, multi and the scope. They never depend on the frontier, so the result is the same on every call. Before #394 they ran once. Now they run once per parent found after the cap.

Impact

BenchmarkCapRecursiveDotted, which is one such pass over 100k entries, measures 2.7 ms/op. That is roughly 30-80 ms per late parent at 1-3M entries. When the budget hits, the jobs channel can hold about 40 jobs per worker (handoffPerWorker x maxChunk). At -t 1000 that is about 40k jobs in flight, which at a 0.5% find rate gives about 200 late parents: several seconds of serial dispatcher CPU. The unbuffered enqueue blocks every worker that found a name in the meantime. This matters most for -max-duration, which is meant to stop on time. Recursive scans with -ct/-sources (multi-label names) or with -exclude take this path.

The multi-label-with-exclusions branch, which still builds every remaining candidate, is tracked in #365.

Suggested fix

Compute the frontier-independent tables once per dispatcher, lazily on the first stopAdmitting, and keep them on the struct: the walk index list for countUnbuiltRepeats and the labels/index maps for countUnbuilt. A late parent then costs O(len(walk)) or O(patterns under the parent).

Acceptance criteria

Getting started


Filed by repo-audit/full-audit at dd5b156. Severity: medium. Effort: S. audit-key: performance|internal/scan/dispatcher.go|expand

Activity

  1. added
    help wantedExtra attention is needed
    area: scanScan engine / dispatcher
    severity: mediumEdge-case bugs, degraded behavior, meaningful maintenance cost
    on Nov 17, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    area: scanScan engine / dispatcherhelp wantedExtra attention is neededperformanceSpeed or memory usageseverity: mediumEdge-case bugs, degraded behavior, meaningful maintenance cost

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions