Inefficient algorithm
Quadratic repository matching scan in selectRepoSet for branch-targeted queries
- perfloop/zoekt · branch repository filtering across 10,000 four-repository…
- 44.9 ms→1.84 ms24× lower
- Problem found
Found Jun 26
- Proven change
Passed every check
- Pull request
Opened Aug 8
- Merged · Aug 14
What was wrong
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.
The full reasoning · 46 words
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.
Every measurement
Measured by Perfloop, in paired runs
branch repository filtering across 10,000 four-repository…
branch repository filtering across 10,000 four-repository shards with 128 branch bitmaps and 90% excluded shards
- Wall time
- 44.9 ms → 1.84 ms
- 24× lower
- Allocated bytes
- 32.9 kB → 32.9 kB
- No change
- Allocations
- 7 → 7
- No change
branch repository filtering where 10,000 four-repository…
branch repository filtering where 10,000 four-repository shards match only the final of 128 branch bitmaps
- Wall time
- 21.8 ms → 542 µs
- 40× lower
- Allocated bytes
- 82 kB → 82 kB
- No change
- Allocations
- 7 → 7
- No change
four final-branch matches followed by 9,996 excluded shards…
four final-branch matches followed by 9,996 excluded shards across 128 branch bitmaps
- Wall time
- 22.5 ms → 904 µs
- 25× lower
- Allocated bytes
- 248 B → 248 B
- No change
- Allocations
- 7 → 7
- No change
one four-repository shard matching only the final non-empty…
one four-repository shard matching only the final non-empty branch bitmap
- Wall time
- 2.72 µs → 707 ns
- 3.9× lower
- Allocated bytes
- 128 B → 128 B
- No change
- Allocations
- 7 → 7
- No change
32 single-repository shards whose IDs occur in every one of…
32 single-repository shards whose IDs occur in every one of 128 branch bitmaps
- Wall time
- 1.55 µs → 1.49 µs
- No change
- Allocated bytes
- 376 B → 376 B
- No change
- Allocations
- 7 → 7
- No change
32 repeated copies of one repository present in every one of…
32 repeated copies of one repository present in every one of 128 branch bitmaps
- Wall time
- 1.31 µs → 1.28 µs
- 3% lower
- Allocated bytes
- 376 B → 376 B
- No change
- Allocations
- 7 → 7
- No change
10 four-repository miss shards against 128 branch bitmaps…
10 four-repository miss shards against 128 branch bitmaps with 100 IDs each
- Wall time
- 24.4 µs → 24.2 µs
- No change
- Allocated bytes
- 160 B → 160 B
- No change
- Allocations
- 5 → 5
- No change
128 four-repository miss shards against 128 branch bitmaps…
128 four-repository miss shards against 128 branch bitmaps with 100 IDs each
- Wall time
- 278 µs → 284 µs
- No change
- Allocated bytes
- 1.23 kB → 1.23 kB
- No change
- Allocations
- 5 → 5
- No change
128 four-repository miss shards against 128 sparse branch…
128 four-repository miss shards against 128 sparse branch bitmaps spanning 2,048 containers
- Wall time
- 2.19 ms → 2.37 ms
- 8.1% higher
- Allocated bytes
- 1.23 kB → 1.23 kB
- No change
- Allocations
- 5 → 5
- No change
32 known miss shards followed by unlisted shards across 128…
32 known miss shards followed by unlisted shards across 128 100-ID branch bitmaps
- Wall time
- 135 µs → 128 µs
- 3.9% lower
- Allocated bytes
- 82 kB → 82 kB
- No change
- Allocations
- 5 → 5
- No change
10,000 first-branch hits with a second sparse distributed…
10,000 first-branch hits with a second sparse distributed branch bitmap
- Wall time
- 565 µs → 604 µs
- No change
- Allocated bytes
- 82 kB → 82 kB
- No change
- Allocations
- 7 → 7
- No change
2,000 final-branch shards followed by 8,000 first-branch…
2,000 final-branch shards followed by 8,000 first-branch shards across 128 branch bitmaps
- Wall time
- 6.09 ms → 669 µs
- 9.1× lower
- Allocated bytes
- 82 kB → 82 kB
- No change
- Allocations
- 7 → 7
- No change
1,400 miss shards followed by 8,600 fifth-branch shards…
1,400 miss shards followed by 8,600 fifth-branch shards across 128 branch bitmaps
- Wall time
- 5.01 ms → 509 µs
- 9.8× lower
- Allocated bytes
- 82 kB → 82 kB
- No change
- Allocations
- 7 → 7
- No change
1,003 selected shards with sparse first-repository-only…
1,003 selected shards with sparse first-repository-only interior matches across 128 branch bitmaps
- Wall time
- 23.6 ms → 954 µs
- 25× lower
- Allocated bytes
- 32.8 kB → 32.8 kB
- No change
- Allocations
- 5 → 5
- No change