Improve performance of pidigits and int arithmetic

[eendebakpt]

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

Linked PRs

• gh-157742: Speed up int multiplication by not zeroing the whole result in x_mul() #157743
• gh-157742: Check for signals every 64th iteration in the int arithmetic loops #157744
• gh-157742: Let compilers vectorize the int shift loops #157751

[sergey-miryanov]

@hugovk @savannahostrowski

[hugovk]

Tagging release managers @hu g ovk@ s avann ahostrows ki to mark this a release blocker.

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/main only.

[gvanrossum]

Joke.

[terryjreedy]

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".

[gvanrossum]

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]

although this matters only for a vanishingly small number of users.

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.

people who need the fastest huge integer math are (or should not be) using Python ints but GMP.

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]

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. :-)

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]

making int arithmetic faster if possible is a good thing.

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]

I think it's better just use external library for doing big ints arithmetic.

That was my point exactly, but I got the feeling I was overruled.

[skirpichev]

I think it's better just use external library for doing big ints arithmetic.

That was my point exactly

There is a difference. I meant: use external library in the CPython for this.

[gvanrossum]

There is a difference. I meant: use external library in the CPython for this.

Oh, sorry. I believe @tim-one once posted an explanation of why that's not an attractive option.