Replace Bitmap.Or’s repeated high-key slice inserts with one planned backward merge
perfloop/roaring · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_jyvmgdg1pq
Verdict
VERIFIED · settled 2026-07-16 · merged as RoaringBitmap/roaring#535
What happened: Validated. The cleanup-only tip preserved the equal-boundary fresh-receiver proof and passed all seven correctness checks. Its primary dense 4,096-container interleaved Bitmap.Or measurement improved from 6,864,674 ns/op to 999,185.5 ns/op (85.44453094203746% lower, Mann–Whitney U p=0.00001082508822446903, n=10 per arm). All eight sealed workload guard selectors held; in particular, the tail-adjacent sparse guard was statistically unchanged in latency (392,028 ns/op to 392,595.5 ns/op, p=0.9705124596765466) while reducing bytes allocated from 290,768 to 262,224. The final diff only clarifies that guard's nested benchmark name; production behavior is unchanged from the already measured merge implementation.
Hypothesis
In roaring.Bitmap.Or, every s1 > s2 branch calls insertNewKeyValueAt, and roaringArray.insertNewKeyValueAt grows then copies the suffix of all three aligned metadata slices—keys, containers, and needCopyOnWrite—before the next comparison. Consequently, interleaved disjoint high-key sets pay a growing suffix move for each source-only key even though the inputs are already sorted; the non-mutating Or implementation in the same source instead demonstrates the appropriate ordered append-merge shape. A planned backward merge gives the mutable receiver one linear metadata planning/placement path after any needed growth, while preserving its copy-on-write contract: receiver-only containers carry their markers forward, source-only containers retain the current ownership policy, and equal keys still pass through roaring.roaringArray.getUnionedWritableContainer to the existing representation-specific container.ior leaf. This removes repeated structural slice shifting rather than attempting to tune a container implementation in isolation. The case should be falsified with an end-to-end Bitmap.Or benchmark using fresh mutable receivers and increasingly large alternating high-key inputs, alongside append-only, fully overlapping, and copy-on-write controls, reporting latency, allocations, and a CPU profile of metadata movement; it should only proceed if the interleaved case repays the planning pass without unacceptable regressions or COW/alias correctness failures on those controls.
Change to test: Introduce a bulk roaringArray union-merge for Bitmap.Or: first plan/count source-only high keys, grow the receiver’s aligned keys, containers, and needCopyOnWrite slices once, then merge the two sorted streams backward into their final slots. Keep no-insert and append-only fast paths; preserve receiver COW markers, retain the existing source-container clone/COW ownership rules, and route equal keys through getUnionedWritableContainer so container.ior remains the representation-specific payload union.
Where it lives
perfloop/roaring · roaring.go