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
2026-11-01· Case opened2026-11-01· PR opened