Repository navigation
Improve performance of v_complement #161127
Description
Feature or enhancement
v_complement() computes the two's complement of a digit vector as ~a + 1, passing a carry from one loop iteration to the next, which prevents vectorization. We can rewrite the implementation so it vectorizes: the +1 carries through the trailing zero digits, the first nonzero digit is negated, and every digit above it is
just inverted.
long_bitwise() calls v_complement for every &, | or ^ with a negative multi-digit operand.
| Benchmark | main | PR | not vectorized: PR vs main |
|---|---|---|---|
| a & -b (2 digits) | 40.6 ns | 38.7 ns: 1.05x faster | not significant |
| a & -b (5 digits) | 41.6 ns | 38.7 ns: 1.08x faster | not significant |
| a & -b (10 digits) | 43.7 ns | not significant | 1.05x slower |
| a & -b (100 digits) | 99.6 ns | 52.3 ns: 1.90x faster | 1.08x faster |
| a & -b (1000 digits) | 692 ns | 228 ns: 3.03x faster | 1.29x faster |
| -a & -b (3 digits) | 53.6 ns | 52.1 ns: 1.03x faster | not significant |
| -a & -b (1000 digits) | 1.80 us | 402 ns: 4.47x faster | 1.70x faster |
| -a ^ b (1000 digits) | 1.22 us | 305 ns: 4.01x faster | 1.77x faster |
| -a | -b (1000 digits) | 1.78 us | 402 ns: 4.42x faster | 1.81x faster |
| a & b (1000 digits, no negatives) | 132 ns | not significant | not significant |
The last column compares main and the PR with longobject.c compiled with -fno-tree-vectorize in both, to show what a compiler that does not vectorize the loop would get: the new scalar loop is also faster, because it does less work per digit.
Idioms that reach this path with wide operands are mostly ints used as bitsets. A real-world example is bit-parallel string matching. The pure-Python fallback of rapidfuzz implements Myers' algorithm with one bit per character of the first string, and computes HP = VN | ~(D0 | VP) and VP = HN | ~(D0 | HP) for every character of the second. HP and VP are negative, so most bitwise operations in the loop take this path: long_bitwise() is 39% of the instructions of a 2000-character comparison on main.
RAPIDFUZZ_IMPLEMENTATION=python |
main | PR |
|---|---|---|
Levenshtein.distance, 100 chars |
151 us | not significant |
Levenshtein.distance, 500 chars |
1.10 ms | 1.05 ms: 1.05x faster |
Levenshtein.distance, 2000 chars |
8.14 ms | 6.37 ms: 1.28x faster |
OSA.distance, 2000 chars |
9.84 ms | 7.83 ms: 1.26x faster |
Benchmark script
import pyperf
runner = pyperf.Runner()
def ints(n):
return (f"import random; r = random.Random(7); "
f"a = r.getrandbits({n*30-1}) | (1 << {n*30-2}); "
f"b = r.getrandbits({n*30-1}) | (1 << {n*30-2}); na = -a; nb = -b")
for n in (2, 3, 5, 10, 100, 1000):
runner.timeit(f"a & -b ({n} digits)", "a & nb", setup=ints(n))
for n in (3, 1000):
runner.timeit(f"-a & -b ({n} digits)", "na & nb", setup=ints(n))
runner.timeit(f"-a ^ b ({n} digits)", "na ^ b", setup=ints(n))
runner.timeit(f"-a | -b ({n} digits)", "na | nb", setup=ints(n))
runner.timeit("a & b (1000 digits, no negatives)", "a & b", setup=ints(1000))🤖 Generated with Claude Code
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Activity
gh-161127: Let compilers vectorize `v_complement()` (#161128)