Skip to content

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

Closed

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
  2. TMHSDigital commented on Nov 18, 2026

    @TMHSDigital
    OwnerAuthor

    Fixed in b9bc33c. countUnbuilt's label/index tables and countUnbuiltRepeats' walk list depend only on the entries, the multi-label set and the scope, so they are now built on the first stopAdmitting and kept on the dispatcher. A parent found after the cap costs O(walk) or O(patterns under it) instead of a pass over the wordlist.

    Verified: new BenchmarkCapLateParent (one late parent per op, both counters) measures about 0.3-0.6 us per call at both 100k and 1M entries. The #393/#394 counting tests pass unchanged; full suite, vet and golangci-lint pass; CI green.

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