Repeated sorting and truncation of matched files on every search result chunk
perfloop/zoekt · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_3tyhw53hc7
Verdict
VERIFIED · settled 2026-08-03 · merged as sourcegraph/zoekt#1110
What happened: The paired measurements met the required improvement.
Hypothesis
In search.collectSender.Send, every time a new search result chunk is received (which happens once per repository per shard via sendByRepository), the new files are appended to c.aggregate.Files, and the entire slice is immediately sorted and truncated via index.SortAndTruncateFiles. Across M chunks and N matched files, this repeated sorting leads to an O(M * N log N) complexity instead of O(N log N). On large queries matching many repositories or shards, this redundant sorting dominates CPU time on the query orchestrator.
Change to test: Modify collectSender to accumulate matched files in a raw slice during Send calls instead of sorting and truncating every time. Defer sorting and truncation (index.SortAndTruncateFiles) until collectSender.Done is called, or lazily perform it only when the slice size exceeds a safe multiple (e.g., twice) of the desired limit to bound memory.
Where it lives
perfloop/zoekt · search/shards.go
Evidence
end-to-end sharded search: 128 repositories × 64 interleaved file matches, no display limit · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
223830837 |
8627536 |
−96.1% (−215135473) |
−223253064 to −208254612 |
< 0 |
PASSED |
file-slots/op |
9760 |
9760 |
0 |
0 to 0 |
≤ 0 |
PASSED |
B/op |
10186104 |
10174993 |
−0.1% (−11090) |
−11850 to −10298 |
≤ 0 |
PASSED |
allocs/op |
562 |
366 |
−34.7% (−195) |
−198 to −194 |
< 0 |
PASSED |
Checks: 2 of 2 passed. Verification: no defect found.