Optimize long_bitwise: eliminate temporary allocations for negative ints and fast-path non-negative ops #161075
Description
Feature or enhancement
While benchmarking bitwise operations (&, |, ^) on int, I noticed several suboptimal paths in long_bitwise() (Objects/longobject.c):
- Temporary heap allocations and
O(size_a)work on negative integers:
Whenaorbis negative,long_bitwise()allocates temporaryPyLongObjectbuffers (new_a,new_b) and runsv_complement()across allsize_a/size_bdigits before determiningsize_z.
In cases likehuge_neg & small_pos_maskorhuge_neg | small_neg,size_zissize_b, so allocating and complementing allsize_adigits doesO(size_a)time and memory work instead ofO(size_b). Even for equal-sized negative integers, this requires up to 3 heap allocations (new_a,new_b,z), 2 deallocations, and 4 passes over the digits. - Over-allocation and redundant normalization on non-negative integers:
For non-negative&and equal-length^, leading zero digits are only stripped afterlong_alloc(size_z)vialong_normalize(z). When high digits cancel out to0or a 1-digit small integer,long_bitwise()allocates a multi-digitPyLongObjectonly formaybe_small_long()to immediately deallocate it. For|,long_normalize(z)is called even though the most significant digit of a non-zero positive operand cannot become zero. - Cold negative path mixed with the hot non-negative path:
long_bitwise()is only called fromlong_and,long_xor, andlong_orwith a constantop('&','^','|'). Keeping the negative path inside the same function prevents constant-foldingopand increases register pressure on the common non-negative path.
Changes
I implemented the following optimizations in my fork branch:
https://github.com/ashm-dev/cpython/tree/perf/long-bitwise
- Extracted the negative path into a
Py_NO_INLINEhelper (long_bitwise_negative) and markedlong_bitwiseasstatic inline Py_ALWAYS_INLINEso the compiler specializeslong_and,long_xor, andlong_orfor constantop. - Replaced
v_complement()and temporarynew_a/new_ballocations with a single-pass on-the-fly two's complement step (twos_comp_step), bounding work strictly tosize_z. - Pre-trimmed cancelling high digits on the non-negative path before
long_alloc(), returning cached small ints or 1-digit medium ints directly and eliminatinglong_normalize()on the non-negative path. - Added unit tests in
Lib/test/test_long.py(test_bitwise_cancellationandtest_bitwise_digit_boundaries).
Benchmark Results
Output of pyperf compare_to main.json patch.json --table:
+------------------------+---------+------------------------+
| Benchmark | main | patch |
+========================+=========+========================+
| 1_xorshift_32b | 230 ms | 220 ms: 1.05x faster |
+------------------------+---------+------------------------+
| 1_xorshift_64b | 224 ms | 219 ms: 1.02x faster |
+------------------------+---------+------------------------+
| 1_xorshift_128b | 227 ms | 225 ms: 1.01x faster |
+------------------------+---------+------------------------+
| 1_xorshift_256b | 239 ms | 235 ms: 1.02x faster |
+------------------------+---------+------------------------+
| 2_pos_ops_128b | 43.5 ms | 39.3 ms: 1.11x faster |
+------------------------+---------+------------------------+
| 2_pos_ops_1024b | 56.3 ms | 50.3 ms: 1.12x faster |
+------------------------+---------+------------------------+
| 3_neg_both_128b | 88.7 ms | 52.8 ms: 1.68x faster |
+------------------------+---------+------------------------+
| 3_neg_both_1024b | 197 ms | 123 ms: 1.60x faster |
+------------------------+---------+------------------------+
| 4_mixed_signs_256b_64b | 81.2 ms | 59.9 ms: 1.36x faster |
+------------------------+---------+------------------------+
| 5_huge_neg_mask_64kb | 164 ms | 5.53 ms: 29.68x faster |
+------------------------+---------+------------------------+
| Geometric mean | (ref) | 1.65x faster |
+------------------------+---------+------------------------+
Benchmark script (bench.py)
from collections.abc import Iterator
from functools import reduce
from itertools import islice
from operator import add
import pyperf
class Random(Iterator[int]):
__slots__ = ("__mask", "__seed")
def __init__(self, seed: int, bits: int = 64) -> None:
self.__mask: int = (1 << bits) - 1
self.__seed: int = seed & self.__mask
def __next__(self) -> int:
s = self.__seed
s ^= (s << 13) & self.__mask
s ^= (s >> 17)
s ^= (s << 5) & self.__mask
self.__seed = s
return s
def bench_xorshift(bits: int, iterations: int) -> int:
return reduce(add, islice(Random(1, bits=bits), iterations))
def bench_pos_ops(a: int, b_same: int, b_small: int, loops: int) -> int:
res = 0
for _ in range(loops):
res = (a | b_same) ^ (a | b_small)
res = (a ^ b_small) | (a & b_same)
res = (a | b_same) ^ (a & b_small)
res = (a ^ b_same) | (a ^ b_small)
return res
def bench_neg_both(na: int, nb: int, loops: int) -> int:
res = 0
for _ in range(loops):
res = (na ^ nb) & (na | nb)
res = (na & nb) ^ (na | nb)
res = (na | nb) & (na ^ nb)
res = (na ^ nb) | (na & nb)
return res
def bench_mixed_signs(pos_big: int, neg_small: int, neg_big: int, pos_small: int, loops: int) -> int:
res = 0
for _ in range(loops):
res = (pos_big & neg_small) ^ (pos_big ^ neg_small)
res = (neg_big ^ pos_small) | (neg_big & pos_small)
res = (pos_big | neg_small) ^ (neg_big | pos_small)
res = (pos_big & neg_small) | (neg_big ^ pos_small)
return res
def bench_huge_neg_asym(huge_neg: int, small_pos: int, small_neg: int, loops: int) -> int:
res = 0
for _ in range(loops):
res = (huge_neg & small_pos) ^ (huge_neg | small_neg)
res = (huge_neg & small_pos) | (huge_neg | small_neg)
res = (huge_neg & small_pos) ^ (huge_neg | small_neg)
res = (huge_neg & small_pos) | (huge_neg | small_neg)
return res
def main() -> None:
runner = pyperf.Runner()
for bits in (32, 64, 128, 256):
runner.bench_func(
f"1_xorshift_{bits}b",
bench_xorshift,
bits,
500_000,
)
for bits in (128, 1024):
a = (1 << bits) - 123456789
b_same = (1 << bits) - 987654321
b_small = (1 << (bits // 2)) - 1337
runner.bench_func(
f"2_pos_ops_{bits}b",
bench_pos_ops,
a,
b_same,
b_small,
100_000,
)
for bits in (128, 1024):
na = -((1 << bits) - 123456789)
nb = -((1 << bits) - 987654321)
runner.bench_func(
f"3_neg_both_{bits}b",
bench_neg_both,
na,
nb,
100_000,
)
pos_big = (1 << 256) - 0xDEADBEEF
neg_small = -((1 << 64) - 0xCAFEBABE)
neg_big = -((1 << 256) - 0x12345678)
pos_small = (1 << 64) - 0x87654321
runner.bench_func(
"4_mixed_signs_256b_64b",
bench_mixed_signs,
pos_big,
neg_small,
neg_big,
pos_small,
100_000,
)
huge_neg = -((1 << 65536) - 0xABCDEF)
small_pos = 0xFFFFFFFF_FFFFFFFF
small_neg = -0xFFFFFFFF_FFFFFFFF
runner.bench_func(
"5_huge_neg_mask_64kb",
bench_huge_neg_asym,
huge_neg,
small_pos,
small_neg,
10_000,
)
if __name__ == "__main__":
main()All unit tests (test_long) pass and there are no regressions in the test suite or pyperformance. If this looks reasonable, I'm happy to open a PR from the branch above.
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Activity
picnixz commentedon Nov 1, 2026
cc @eendebakpt
eendebakpt commentedon Nov 1, 2026
@ashm-dev Are there any applications that really benefit from these optimizations? If so, a PR might be worthwhile. If only microbenchmarks improve, then I suggest to only make individual PRs if the the change is small, easy to review and does not complicate the code (or better: simplifies the code).
ashm-dev commentedon Nov 1, 2026
@eendebakpt
pyperformancedoesn't have dedicated benchmarks for bitwise operations, so the overall impact on the existing suite is roughly neutral.However, the main goal here isn't just raw loop speed, but eliminating unnecessary heap allocations:
long_alloc(new_a/new_b) for negative operands by computing two's complement on the fly.long_alloccompletely when the result shrinks to a single digit / small int (e.g., bit cancellation in&or^).To keep the changes small and easy to review as you suggested, I can split this into two separate PRs (one for the streaming two's complement on negative ints, and another for the non-negative fast path). Would that work for you?
picnixz commentedon Nov 1, 2026
How frequent are those unnecessary heap allocations? In which situations are we slower? the benchmarks are not easy to read and they seem too specific.
OTOH,EDIT: I forgot about Myers' algorithm so this applies.huge_neg | small_negis not really something you do in general. Bitwise operations are usually performed on positive quantities.OTOH:
This could be relevant.
This looks like something an LLM would say. What numbers in your benchmarks actually support this hypothesis? (again, it's just hard to parse as there is lots of information dumped at once).
That being said, while it could make the work faster for some cases, could it make the work slower in other cases because of more branches in the code?