Repository navigation
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