Quadratic repository matching scan in selectRepoSet for branch-targeted queries

perfloop/zoekt · INEFFICIENT ALGORITHM

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

Verdict

VERIFIED · settled 2026-08-13 · merged as sourcegraph/zoekt#1127

What happened: The paired measurements met the required improvement.

Hypothesis

When executing a search query that targets multiple branches and repositories via query.BranchesRepos, selectRepoSet checks if each repository in every shard matches any of the requested branch-repository entries by linearly scanning setQuery.List and querying each roaring.Bitmap. For multi-repository searches under high shard counts, this linear scan runs on almost all shards (which are filtered out), leading to massive CPU overhead. Pre-aggregating the bitmaps into a single union bitmap before the loop converts the nested loop scan into a single lookup per repository.

Change to test: In the shard filtering step (selectRepoSet) called during search, pre-aggregate the roaring.Bitmap of all repository IDs from query.BranchesRepos into a single union roaring.Bitmap before iterating over the shards and repositories, replacing the inner linear scan with a single Contains lookup.

Where it lives

perfloop/zoekt · search/shards.go

Evidence

branch repository filtering across 10,000 four-repository shards with 128 branch bitmaps and 90% excluded shards · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 44867662 1838278 −96% (−43087436) −45309763 to −40382174 < 0 PASSED
B/op 32888 32888 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

branch repository filtering where 10,000 four-repository shards match only the final of 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 21821016 542041 −97.5% (−21284808) −23134260 to −20940076 < 0 PASSED
B/op 82040 82040 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

four final-branch matches followed by 9,996 excluded shards across 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 22485618 904355 −95.6% (−21499041) −22529643 to −20649168 < 0 PASSED
B/op 248 248 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

one four-repository shard matching only the final non-empty branch bitmap · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2724 707.2 −74.1% (−2018) −2138 to −1909 < 0 PASSED
B/op 128 128 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

32 single-repository shards whose IDs occur in every one of 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1547 1492 −3.6% (−55.5) −86 to +2 ≤ 750 PASSED
B/op 376 376 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

32 repeated copies of one repository present in every one of 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1312 1277 −3% (−40) −58 to −18 ≤ 750 PASSED
B/op 376 376 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

10 four-repository miss shards against 128 branch bitmaps with 100 IDs each · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 24443 24195 −3.9% (−957.5) −2163 to +331 ≤ 5000 PASSED
B/op 160 160 0 0 to 0 ≤ 0 PASSED
allocs/op 5 5 0 0 to 0 ≤ 0 PASSED

128 four-repository miss shards against 128 branch bitmaps with 100 IDs each · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 277796 284457 +1.9% (+5167) −3025 to +11398 ≤ 50000 PASSED
B/op 1232 1232 0 0 to 0 ≤ 0 PASSED
allocs/op 5 5 0 0 to 0 ≤ 0 PASSED

128 four-repository miss shards against 128 sparse branch bitmaps spanning 2,048 containers · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2192690 2369321 +8.1% (+177215) +59275 to +260148 ≤ 500000 PASSED
B/op 1232 1232 0 0 to 0 ≤ 0 PASSED
allocs/op 5 5 0 0 to 0 ≤ 0 PASSED

32 known miss shards followed by unlisted shards across 128 100-ID branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 134939 127669 −3.9% (−5242) −11388 to −2388 ≤ 25000 PASSED
B/op 82000 82000 0 0 to 0 ≤ 0 PASSED
allocs/op 5 5 0 0 to 0 ≤ 0 PASSED

10,000 first-branch hits with a second sparse distributed branch bitmap · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 565103 604420 +7.3% (+40974) −138168 to +112379 ≤ 250000 PASSED
B/op 82040 82040 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

2,000 final-branch shards followed by 8,000 first-branch shards across 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6094796 668735 −87.5% (−5333086) −5581712 to −5006155 < 0 PASSED
B/op 82040 82040 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

1,400 miss shards followed by 8,600 fifth-branch shards across 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5009322 508639 −89.5% (−4482314) −4530207 to −4060520 < 0 PASSED
B/op 82040 82040 0 0 to 0 ≤ 0 PASSED
allocs/op 7 7 0 0 to 0 ≤ 0 PASSED

1,003 selected shards with sparse first-repository-only interior matches across 128 branch bitmaps · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 23635358 954396 −96.2% (−22727899) −25173529 to −22108128 < 0 PASSED
B/op 32848 32848 0 −2 to 0 ≤ 0 PASSED
allocs/op 5 5 0 0 to 0 ≤ 0 PASSED

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

Timeline