python/cpython
eendebakpt's Description of Work
x_mul() (schoolbook multiplication in Objects/longobject.c) starts by memset-ing all digits of the result to zero, then accumulates row by row with carry += *pz + *pb++ * f.
The zeroing is not needed for the non-squaring path. Row 0 can store its size_b + 1 digits outright, and row i only reads digits that row i - 1 already wrote; each carry slot z[i + size_b] is written exactly once before it is ever read. So no digit needs to start out zero, and the per-row if (carry) *pz += carry becomes a plain store.
This matters most for the common big Γ small case (size_a == 1). Karatsuba and lopsided multiplication call x_mul() for their base cases, so they gain a little too.
Benchmarks
| Benchmark | main | branch |
|---|---|---|
| mul 1x2 | 38.0 ns | 27.9 ns: 1.36x faster |
| mul 1x10 | 40.0 ns | 31.3 ns: 1.28x faster |
| mul 2x10 | 51.6 ns | 43.3 ns: 1.19x faster |
| mul 10x10 | 158 ns | 148 ns: 1.07x faster |
| mul 60x60 | 2.58 us | not significant |
| mul 1x2000 | 1.28 us | 1.20 us: 1.07x faster |
| mul 2x2000 (lopsided) | 2.45 us | 2.37 us: 1.03x faster |
| mul 500x500 (karatsuba) | 95.0 us | 91.4 us: 1.04x faster |
| mul 2000x2000 (karatsuba) | 876 us | 846 us: 1.04x faster |
| Geometric mean | (ref) | 1.11x faster |
| pyperformance pidigits | 157 ms | 154 ms: 1.02x faster |
Benchmark script
```python
import pyperf
runner = pyperf.Runner()
CASES = [("mul 1x2", 1, 2), ("mul 1x10", 1, 10), ("mul 2x10", 2, 10),
("mul 10x10", 10, 10), ("mul 60x60", 60, 60), ("mul 1x2000", 1, 2000),
("mul 2x2000 (lopsided)", 2, 2000), ("mul 500x500 (karatsuba)", 500, 500),
("mul 2000x2000 (karatsuba)", 2000, 2000)]
for name, na, nb in CASES:
setup = (f"import random; r = random.Random(1234); "
f"a = r.getrandbits({na*30-1}) | (1 << {na*30-2}); "
f"b = r.getrandbits({nb*30-1}) | (1 << {nb*30-2})")
runner.timeit(name, stmt="a*b", setup=setup)
```
- Issue: gh-157742
<!-- /gh-issue-number -->