Avoid repeated line lookups while constructing chunk search results

perfloop-oss/zoekt · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_8p1m3v22dh

Verdict

VERIFIED · settled 2026-10-25 · pull request opened as sourcegraph/zoekt#1202

What happened: The paired measurements met the required improvement.

Hypothesis

Chunk-mode Search repeatedly resolves the same matches to line numbers while grouping candidates, emitting ranges, and scoring chunks. Sharing that resolution may reduce CPU work for files with many matches. The cost attributable specifically to these lookups, and the achievable Search saving, remain unmeasured.

For M content candidates on a successfully completed call, chunkCandidates resolves both endpoint lines once per candidate (index/contentprovider.go:467-496). fillContentChunkMatches repeats that resolution at line 415. offsetRangeToLineRange invokes atOffset twice, and each atOffset starts a binary search over the file's L newline offsets (lines 545-577). scoreChunk performs another start-line lookup per candidate (index/score.go:42-86). This gives five binary-search calls per candidate across these three phases, with O(M log(L+1)) lookup work. This count does not apply to Search exits that never construct content chunks. The ordinary route already supplies sorted, non-overlapping candidates through gatherMatches (index/eval.go:431-456), so the repeated phases discard useful ordering and resolved-location information. Newline loading is cached separately; columnHelper already amortizes UTF-8 counting and is not the proposed optimization target.

A static inventory of 234 tracked checkout Go files at or below 2 MiB found 3,914 exact, non-overlapping `func` byte occurrences in 228 files, with up to 300 occurrences per file. Matching files contained up to 4,280 newline offsets. This is source-corpus shape evidence, includes generated and test files, and does not establish indexing eligibility or production frequency. The supplied discovery observation attributes 31.2% cumulative sampled CPU to this owner in paired line/chunk literal searches over checkout Go files. That share includes its callees and is not the removable lookup cost or an expected saving. ChunkMatches is an explicit experimental Search option; this contribution requires no new public API or shard format.

A mandatory walk over all L newlines could lose on sparse results. Boundary semantics also constrain reuse: the existing end line uses max(startOffset, max(endOffset, 1)-1), not the raw exclusive end offset. Scoring groups candidates by their start line, including multiline matches. Its strict score comparisons, debug output, and symbol associations must remain unchanged.

The cheapest first Case check is to add lookup counters to the existing BenchmarkScoreChunkMatches and run `go test ./index -run '^$' -bench '^BenchmarkScoreChunkMatches$' -benchmem`. This constructed benchmark can confirm the mechanism, not consumer savings. Then compare baseline and prototype chunk-mode Search CPU and ns/op over checkout-file literal searches, varying match density, file line count, and context width, including sparse matches and any lookup-strategy crossover. Reduced lookup counts without lower Search cost would reject material benefit for the measured sample. Differential checks must preserve chunk membership and ordering, content bounds and starts, range byte offsets and UTF-8 columns, scores, BestLineMatch, debug scores, and symbol metadata. Include newline and EOF endpoints, zero-length and multiline matches, both scoring modes, sorting fallback, and deserialized-shard fixtures.

Change to test: Share one endpoint-resolution pass across candidate grouping, range construction, and line-score grouping while preserving the chunk-result contract. Reuse the emitted ranges and contiguous candidate spans, with current-line reuse and binary-search jumps for sparse gaps rather than an unconditional scan of every newline.

Where it lives

perfloop-oss/zoekt · index/eval.go

Evidence

dense source-file chunk Search · 9 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 33049 25895 −20.2% (−6689) −8581 to −6111 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

sparse end-of-file chunk Search · 11 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5826 5689 −1.8% (−107) −360 to +137 loss ≤ 0.05 × |baseline median| PASSED

wide-context chunk Search · 12 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 30089 23556 −22.1% (−6644) −9160 to −5828 loss ≤ 0.05 × |baseline median| PASSED

existing synthetic chunk Search benchmark · 13 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6185029 5279857 −14.3% (−882548) −995217 to −797403 loss ≤ 0.05 × |baseline median| PASSED

Checks: 5 of 5 passed. Verification: no defect found.

Timeline