Repository navigation
Improve performance of pidigits and int arithmetic #157742
Description
Feature or enhancement
Proposal:
For obvious reasons pidigits is the most important benchmark we have for Python. We should to everything we can to improve performance, including rust (rust-for-python) or a jit (accept PEP 836).
Tagging release managers @hu g ovk@ s avann ahostrows ki to mark this a release blocker.
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Activity
sergey-miryanov commentedon Sep 18, 2026
@hugovk @savannahostrowski
hugovk commentedon Sep 18, 2026
Erm, not sure if this is a joke, but making a benchmark 1.02x faster isn't a release blocker.
And performance improvements usually aren't backported, so this is for 3.16/
mainonly.gvanrossum commentedon Sep 18, 2026
Joke.
terryjreedy commentedon Sep 18, 2026
The 3rd PR says 1.24x improvement in pydigits. The 2nd did not test pydigits; perhaps not relevant? A more prosaic issue title would be "speed-up int arithmetic".
[-]Improve performance of pidigits[/-][+]Improve performance of pidigits and int arithmetic[/+]gvanrossum commentedon Sep 18, 2026
I can get behind making very long int arithmetic faster, although this matters only for a vanishingly small number of users. IIRC @tim-one has mentioned in the past that people who need the fastest huge integer math are (or should not be) using Python ints but GMP.
The lead-in about pidigits being the most important benchmark still feels like a joke, and the OP looks like a cat ran over the keyboard at the end. :-)
skirpichev commentedon Sep 19, 2026
Not sure, assuming that integer arithmetics reinvented several times in the Python ecosystem (Sagemath, gmpy2, python-flint, python-gmp...). IMO, Sage, SymPy or mpmath (major consumers of this) are popular enough.
And suffer from severe speed loss for small integers, where builtin integers hard to beat for external extensions. IMO, things go worse with years: bytecode specialization and jit come into play...
The problem is that practical integer-heavy applications (like e.g. Sagemath) usually use operands of different sizes. In this d.p.o thread that was demonstrated on example of the mpmath test suite.
eendebakpt commentedon Sep 19, 2026
The importance of pidigits was a joke, but I do think making int arithmetic faster if possible is a good thing. The cat has knowledge of Ludolph's constant though ;-)
For reviewers: just treat the PR's as serious attempts to make int arithmetic faster (pidigits being faster is just a consequence).
skirpichev commentedon Sep 20, 2026
Optimization for small integers, perhaps. Not sure that optimization for big ints is ok: we never can beat here professional libraries, like GMP. At least, not at cost of lowering code readability: that's why your 2nd pr looks acceptable for me. (Another example is Karatsuba cutoff, probably it's value could be lowered nowadays.)
I think it's better just use external library for doing big ints arithmetic.
gvanrossum commentedon Sep 20, 2026
That was my point exactly, but I got the feeling I was overruled.
skirpichev commentedon Sep 20, 2026
There is a difference. I meant: use external library in the CPython for this.
gvanrossum commentedon Sep 20, 2026
Oh, sorry. I believe @tim-one once posted an explanation of why that's not an attractive option.
skirpichev commentedon Sep 20, 2026
His objections were rather about license stuff. (I can't judge on this, but it's not a problem for Wolfram, distributing libgmp.so with the Wolfram Engine or Mathematica.)
That can be workarounded e.g. by a stable API layer for big integers, as suggested by Mark Shannon. Then people could choose external big ints library by some ./configure switch.
We already have similar layer of functions (x_add, x_mul and so on), but they are tightly coupled to the CPython. E.g. in using exceptions instead of return codes to handle errors, or in memory management. But the rest is same as for other big int libraries, using similar data structures (modulo less sophisticated algorithms).
mdickinson commentedon Sep 20, 2026
I think this is only one half of the story. The other concern is that improvements to bigint arithmetic should not come at the expense of decreased performance on small integers. Small int performance is overwhelmingly more important than bigint performance.
Relevant d.p.o. message from Tim: https://discuss.python.org/t/pylongobject-just-use-gmp/106086/42 (not the only relevant one; read forwards and backwards from that point).
eendebakpt commentedon Sep 20, 2026
The PRs here either (slightly) improve performance for small integers, or are neutral (e.g. in the noise). The gain is mostly in the area that is not small (e.g. not compact or 64-int), but not yet in the "bigint" sizes (e.g. sizes where algorithms are used with lower complexity).
For reference: here a plot of the computation times of some int operations, together with the thresholds used for the bigint algorithms in cpython.
skirpichev commentedon Sep 21, 2026
Sure, but this concern shared by most (all?) core devs in the thread.
I don't think it's relevant. We already have special code paths for small integers (something that wasn't here in previous attempts to use GMP), and I'm not suggesting to change that. I don't see how decreased performance for small integers could appear on this road. But of course, only a complete implementation could prove or disprove that.