Avoid per-input containers for all-string native BITOP OR

perfloop-oss/redis · Inefficient Algorithm

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

Verdict

VERIFIED · settled 2026-11-04 · pull request opened as redis/redis#16141

What happened: The paired measurements met the required improvement.

Hypothesis

Native BITOP OR imports distinct string sources into compressed Roaring form before combining them. When every source is already a flat string, this builds input representations that need not exist. It may add conversion, allocation and merge CPU to ordinary primary calls with bitmap-default-roaring enabled; command-level savings, input sizes and production frequency are unmeasured.

At revision 41888396080aab24ad5218f2e45e66158e24884b, bitroarUseMixedRawOp requires both a string and a Roaring source, so it excludes all-string calls. For a completed native OR over k distinct, present, nonempty string objects, bitroarApplyOp imports the first through bitroarCopyOpSource, imports each later object through bitroarGetOpSource, and performs k-1 in-place unions. Later string conversions are already limited to one live temporary; this is repeated work, not a claim that k full temporaries coexist.

Unconditionally flattening every native operand would be the wrong broader change because compressed sources can have huge sparse logical lengths. The all-string class instead already supplies raw bytes. Its result can be constructed chunk by chunk without introducing that allocation amplification. A singleton still needs one native import and is an important control.

The native contract landed in https://github.com/redis/redis/pull/15331. Although its provider patch was unavailable, direct inspection of merge f3b9b68ec67e5ebd6a7c07b3d629c477d30648c6 confirmed the same selector and OR loop. The refreshed diff of https://github.com/redis/redis/pull/15965 at 3a0fa046 adds portable interchange, not this raw-string pipeline. https://github.com/redis/redis/pull/15920 and https://github.com/redis/redis/pull/15830 change string-result tails and initialization instead. The unmerged zero-length behavior proposal https://github.com/redis/redis/pull/8918 is separate; this change leaves that command-level branch alone. No new public command or format is needed.

The four stored Tcl checks prop_vz6bhryxj3, prop_x25g1gzhx5, prop_y8ddcba4n1 and prop_cgtjsn0h7h passed at the accepted revision. They are bounded correctness controls for bytes, aliases, input preservation, early rejection and replay, not performance evidence. The first Case check should profile ordinary native BITOP OR with distinct raw sources, then compare a bounded-chunk prototype on identical inputs including result compaction. Fewer imports plus a repeatable reduction in total command CPU would confirm the benefit; raw merging or final import costs that offset the saving would reject it. This is architecture-independent work with no ISA requirement.

Change to test: Compute all-string native OR from the raw operands and construct Roaring containers only for the combined result. Use bounded chunks rather than a full-length raw result buffer, while retaining native result propagation and the existing mixed and Roaring-only routes.

Where it lives

perfloop-oss/redis · src/bitops.c

Evidence

Native BITOP OR over eight strings · 13 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_us/op 2890 205 −93.6% (−2705) −2850 to −2260 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
command_us/op 3422 509.8 −85.2% (−2917) −2968 to −2899 loss ≤ 0.05 × |baseline median| PASSED

Native BITOP OR singleton control · 78 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_us/op 2738 2748 −25 −95 to +125 loss ≤ 0.05 × |baseline median| PASSED
command_us/op 3390 3403 +13.48 −5.311 to +34.33 loss ≤ 0.05 × |baseline median| PASSED

Native BITOP OR repeated-source control · 14 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_us/op 432.5 70 −86.1% (−372.5) −420 to −285 loss ≤ 0.05 × |baseline median| PASSED
command_us/op 646 321.5 −50.2% (−324.3) −346.6 to −312.7 loss ≤ 0.05 × |baseline median| PASSED

Native BITOP OR missing-source control · 15 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_us/op 4135 4110 −50 −230 to +160 loss ≤ 0.05 × |baseline median| PASSED
command_us/op 3752 3785 +32 −211.3 to +123.6 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline