Bound BSI BatchEqual memory on scattered IN-lists
perfloop/roaring · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_djnh9mjw8v
Verdict
VERIFIED · settled 2026-07-08 · merged as RoaringBitmap/roaring#533
What happened: We have successfully validated a clean, upstream-ready, and fully optimized candidate (commit 37fa4fc3b73eee8170772a33c45df5494cb8defd) that completely resolves all review feedback items from rev_2tebx5ba6v while preserving the BSI BatchEqual parallel scan fallback optimization perfectly on the hot path.
By auditing the codebase and removing all Perfloop-internal scaffolding, we achieved the following: 1. Deleted the 'IsCandidate' harness marker from 'bsi_helper.go'. 2. Removed the 'IsCandidate' gate and folded the parallel-scan correctness tests from 'bsi_candidate_test.go' into the main 'bsi_test.go' suite to run unconditionally for complete coverage. 3. Removed the leftover debug printf statement from 'bsi_successor_test.go'. 4. Corrected the stale comment referencing the old crossover limits, explicitly stating the final crossover criteria: 'len(vals) >= 128 and estimateBranchCount >= 64'. 5. Retained 'ParallelBSIScanHelper' as a minimally exported core helper because the 'BitSliceIndexing' package is a separate Go package that needs to access private internals of roaring containers. A robust, justifying doc comment was added to make it maintainer-friendly. 6. Maintained absolute behavioral and structural identity on the hot path, including the panic safety guard for >128 bitplanes. 7. Polished comments in 'shouldUseParallelScan' explaining the rationales behind the threshold checks to make the code clean and maintainable.
Fresh co-measurements of our clean candidate 'cand_a14wqk8qqa' against the baseline on 'BenchmarkBatchEqualM128Scattered' perfectly reproduced the validated wins: - An exceptional 88.88% reduction in allocations (214,941 -> 23,891 allocs/op). - An exceptional 44.45% reduction in memory usage volume (283,462,220 -> 157,455,576 B/op). - A statistically significant 32.64% speedup in query execution time (953,792,936.5 -> 642,468,364 ns/op).
All 7 non-regression guard benchmarks (contiguous queries, clustered queries, and small scattered queries near the crossover threshold) remain perfectly held with no regressions, and correctness was strictly verified by 'TestBatchEqualExistenceAuthority'.
Hypothesis
Under the BSI Batch Query Verification workload, the vectorized BatchEqual (merged PR #532, present at the current fork HEAD) walks the bitplanes as an MSB-first trie over the sorted query values via matchTrie (BitSliceIndexing/bsi.go:791). Its speed comes from prefix sharing and whole-subtree collapse; cost is proportional to the number of branch points — nodes where the value set splits into both a 0- and a 1-subtree — and each branch materializes intermediate bitmaps via planeChild (roaring.And/AndNot of prefix and plane). A scattered IN-list shares no prefix and never collapses, so the trie degenerates into a near-complete binary tree: many large intermediate bitmaps, hence a memory and allocation blowup with no speed benefit, since the total bitwise work already approaches a full scan. On the library's own testdata/age fixture (28M columns, 8 planes) the scattered M=128 shape allocates ~270MiB vs the pre-PR scan's 147MiB (+83%) and 215k vs 24k allocs/op (+798%) at essentially flat wall time (422ms vs 425ms). A bounded-memory parallel eBM scan for detected-scattered queries reclaims that memory and those allocations with no time regression, while contiguous and clustered queries keep the trie's wins. Measure on BenchmarkBatchEqual M128Scattered; the requirement is no regression on the contiguous M128/M200 and small-M shapes.
Change to test: In BatchEqual (the merged PR #532 trie implementation at the current fork HEAD), before any bitmap work, estimate the match-trie branch count from the sorted, deduplicated query values alone — a pure integer walk mirroring matchTrie's partition and whole-subtree-collapse decisions, no bitmaps. When the estimate exceeds a crossover threshold, skip the trie and compute the result with a parallel, existence-rooted linear membership scan that iterates only the existence bitmap (eBM), partitioning it across cores like parallelExecutor. Contiguous and clustered queries stay on the trie unchanged. eBM remains authoritative, so the result is always a subset of eBM (must pass TestBatchEqualExistenceAuthority).
Where it lives
perfloop/roaring · BitSliceIndexing/bsi.go