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
- Proven change
Candidate checks passed
- Pull request
Opened
- Merged ·
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.
Where it lives
perfloop/zoekt @ 893a523 · reading…
Every measurement
Measured by Perfloop, in paired runs
Each change is the median of paired runs, so it can differ from the ratio of the two figures.
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
- change within −86 to +2 ns
- 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.312 µs → 1.277 µ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
- change within −2163 to +331 ns
- 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
- change within −3025 to +11398 ns
- 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
- change within −138168 to +112379 ns
- 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
- change within −2 to 0 B
- Allocations
- 5 → 5
- No change