We added _pylong.py. The idea was to make some operations on long ints faster, with minimal maintenance cost. Now, I’m not entirely sure it was a good idea. If you are doing serious work with long ints, just install gmpy2. As for what’s in the current _pylong.py module, I think it was a good cost/benefit tradeoff: it’s only 291 lines of code (332 comment lines) and generally we shouldn’t have to mess with it. However, there is always the temptation to grow it: make it faster or to support more int operations. If we can resist that and avoid it becoming a maintenance monster, I guess it’s fine.
Incorporating GMP doesn’t sound like great idea to me, even if we could avoid a slowdown for small ints. We don’t have enough CPython developers who know how to maintain that. Let it be a 3rd party package. If there is some reason why using it as a 3rd party package is not nice or convenient, let’s try to fix those issues. Not everything needs to be built-in or batteries included.
I’m much keener to make small int arithmetic faster. PyPy is proof that they can be made much faster (like at least an order of magnitude) without damaging Python’s semantics. Although PyPy doesn’t have a “C API”, which gives them much greater freedom to use funky internal representations. PyPy is the only “consumer” of its representation decisions.
An external library for small ints is also a non-starter for me. That could only slow things down even more for them.
CPython already uses different algorithms for “big enough” ints. Like Karatsuba multiplication for ints starting at the high end of “crypto size”, and even Python implementations (_pylong.py) for very large ints. Replacing those with calls to an external library would be straightforward “in theory”. Then we could delete the parts of CPython performing the same functions but more slowly, quite possibly reducing core maintenance burdens overall.
GNU licensing issues are always headaches. libtommath is different, with the most permissive “unlicense” on the planet - its author even explicitly disclaims their own copyright. It’s not as fast as GMP, but would still be a major asymptotic improvement for “galactic size” ints
BTW, these external libraries don’t only supply faster basic arithmetic for “big enough” ints, but also piles of other “number theoretic” functions. CPython has grown its own implementations of some of those too, sometimes making heroic efforts to make them faster for “big ints”. For example, math.gcd(). We could also fall back to much simpler code to do those for small ints, and delegate the big int cases to the librariy - which would usually work faster than our own custom code.
I hope someone who knows chimes in. According to the docs, tagged pointers are not used by default, and I never ask for that.
What appears to happen instead is that PyPy invisibly specializes to internal subtypes of list when it detects a list contains only “small enough” ints - or floats! Memory use then is the same as if using array.array with the appropriate type codes, and arithmetic goes fast.
It’s tempting to guess that unboxed raw machine bits are stored, but that’s not quite so:
>>>> xs = list(range(125_000_000))
At this point, memory uses increases to about a GB - 8 bytes/element. Same for a list of floats, BTW.
>>>> xs[-1] = 1 << 62
Nothing visible changes as a result of that.
But the next line takes a very noticeable time to complete, and memory use explodes to nearly 5x as much:
>>>> xs[-1] = 1 << 63
So, same as their tagged pointer implementation of ints, the range is limited to 63-bit signed ints. It’s certainly possible that, for uniformity, they use a tagged pointer representation of ints in these specialized list types despite that tagged pointers aren’t generally used by defautl. But I don’t know.
At one point, Armin (Rigo) did explicitly say that specialization to type-specific list types did happen.
So “JIT driving unboxing” is certainly a part of it.
Ack - I always forget this: PyPy doesn’t use refcounting, and garbage generally isn’t collected “at once”. If I force gc after that line, memory use falls back to about 4GB. So about 32 bytes/element, almost certainly reflecting that the “too big” int forced the list to change its internal type to a list of boxed ints (instead of the original list of unboxed ints).
Yes, maybe license is an issue. One possible workaround is using different external libraries with a same API.
I don’t think so. Major non-trivial part for me was the GMP’s memory management. The rest is using public mpn_* API. I believe it’s a lot simpler than implementing non-trivial algorithms. See my pr, that removes _pylong module completely.
The plan is to keep current layout here, i.e. _PyLongValue. The digit type will be different, of course. Small integers will be handled as now, so I don’t think we should expect speed regressions on this way.
Remember, that these benchmarks here to demonstrate disease, not it’s cure. This is something, that happens with integer arithmetic in the external module, where some optimizations aren’t possible.
1.6x-2x is a bit optimistic. Here is with PyPy:
$ pypy3 -m timeit -s 'from functools import reduce' -s 'from operator import add' -s 'mpz = int' -s "xs=list(map(mpz, range(1000)))" "reduce(add, xs)"
100000 loops, average of 7: 3.3 +- 0.00269 usec per loop (using standard deviation)
$ python3.14 -m timeit -s 'from functools import reduce' -s 'from operator import add' -s 'mpz = int' -s "xs=list(map(mpz, range(1000)))" "reduce(add, xs)"
5000 loops, best of 5: 89.2 usec per loop
$ python3.14 -m timeit -s 'from functools import reduce' -s 'from operator import add' -s 'from gmpy2 import mpz' -s "xs=list(map(mpz, range(1000)))" "reduce(add, xs)"
1000 loops, best of 5: 204 usec per loop
$ pypy3 -m timeit -u usec -s 'from functools import reduce' -s 'from operator import add' -s 'from gmpy2 import mpz' -s "xs=list(map(mpz, range(1000)))" "reduce(add, xs)"
100 loops, average of 7: 3.11e+03 +- 123 usec per loop (using standard deviation)
@tim-one, 600x is sometimes possible Though, 60x is a lot too.
The gmpy2 module on the PyPy3 lacks one optimization (object caching, see referenced above gmpy2 issue), but that offer only ~20% on CPython.
The CPython recently introduced major compatibility break in point releases just for that use case
That looks for me as another point in favor of bindings to the GMP. Why do you think that maintenance of bindings to the external bigint library is harder than reinventing yet another bigint library?
I would expect, this rather lower barriers for CPython developers, assuming that the external library is well documented.
Note, that current version of the libzz wraps not everything available in the GMP, but all functions, present now in the math.integer module — are available.
PyPy can be tricky to reason about. I used functools.reduce and operator.add for CPython, because they’re coded in C and so are “invisible” to CPython’s eval loop and its idea of JIT.
But that’s not so in PyPy. add is implemented in RPython, and reduce in pure Python. So the guts of both are visible to PyPy’s idea of JIT, and that can be very effective.
But there’s nothing CPython or PyPy can do to speed the guts of code in an external module. PyPy can get much the same speedups for reduce ... add “by magic” as CPython’s sum() gets from special-casing the snot out of small int addends.
Not with 1000x speedup case wrt gmpy2, of course. Major problems here are from the cpyext layer. Matti Picus suggested me to try HPy or CFFI. But this in turn make things noticeable slower on CPython as e.g. HPy uses heap types.
But the point is that both PyPy and CPython come with some optimizations for builtin types, that are impossible for extension types. And more is coming, I think.
Here few benchmarks, that use explicit loops. With CPython v3.15.0a7 and PGO or PGO+LTO+JIT.
Harmonic numbers:
Benchmark
ref-jit
ref
gmp
H(100)
403 us
476 us: 1.18x slower
757 us: 1.88x slower
H(1000)
5.66 ms
6.54 ms: 1.16x slower
10.2 ms: 1.80x slower
Geometric mean
(ref)
1.17x slower
1.84x slower
Sum (note, that jit-ted interpreter is slower here):
Benchmark
ref
ref-jit
gmp
sum(100)
5.94 us
6.78 us: 1.14x slower
16.3 us: 2.74x slower
sum(1000)
63.8 us
75.6 us: 1.19x slower
159 us: 2.50x slower
Geometric mean
(ref)
1.16x slower
2.62x slower
Collatz benchmark (bench/collatz.py in the python-gmp):
Benchmark
ref-jit
ref
gmp
collatz0(97)
22.2 us
24.8 us: 1.12x slower
85.9 us: 3.86x slower
collatz0(871)
34.8 us
38.7 us: 1.11x slower
130 us: 3.74x slower
collatz0((1<<128)+31)
339 us
351 us: 1.03x slower
667 us: 1.97x slower
collatz1(97)
22.0 us
23.1 us: 1.05x slower
101 us: 4.59x slower
collatz1(871)
33.8 us
35.4 us: 1.05x slower
151 us: 4.48x slower
collatz1((1<<128)+31)
337 us
325 us: 1.03x faster
786 us: 2.33x slower
collatz2(97)
22.0 us
24.5 us: 1.11x slower
85.9 us: 3.90x slower
collatz2(871)
34.0 us
36.9 us: 1.08x slower
129 us: 3.79x slower
collatz2((1<<128)+31)
339 us
not significant
666 us: 1.96x slower
Geometric mean
(ref)
1.06x slower
3.24x slower
# a.py
from fractions import Fraction
import pyperf
#mpz = int
from gmp import mpz
runner = pyperf.Runner()
def mysum(xs):
total = Fraction(mpz(0))
for t in xs:
total += t
return t
for n in [100, 1000]:
xs = [Fraction(mpz(1), mpz(i)) for i in range(1, n + 1)]
runner.bench_func(f"H({n})", mysum, xs)
# b.py
import pyperf
#mpz = int
from gmp import mpz
runner = pyperf.Runner()
def mysum(xs):
total = mpz(0)
for t in xs:
total += t
return t
for n in [100, 1000]:
xs = [mpz(i) for i in range(1, n + 1)]
runner.bench_func(f"sum({n})", mysum, xs)
Which is another reason to leave CPython’s small ints out of this. CPython can eventually evolve to approach PyPy’s speed for those too, by knowing the full context in which they’re used and exploiting that (as sum() already partially does). That possibility is lost if they’re fed one or two at a time to an external library.
For bigger ints, doing the arithmetic can be much costlier than representation conversion costs, and call overheads, so that’s where speed gains can be won with scant downside. “As fast as current CPython on small ints” isn’t really a goal worth shooting for - among current languages, current CPython is extraordinarily slow at doing small-int arithmetic. Enduring the overheads of an external call to fire off a 1-cycle integer add will never really be a win (worse, modern superscalar CPUs can generally do at least 3 integer adds simultaneously - but only if the code is tight enough for the CPU to see the iadd instructions back to back - an intervening external call kills that).
When it comes time to “sell” this to the Steering Council, please emphasize how much code we can remove from CPython. That’s an important story too. Mark Dickenson wrote a whole bunch of it, and it’s excellent code, but he’s no longer with us and that code has no real maintainer anymore. _pylong.py is just the tail end of it.
Not neeccessary, if the library clearly documents this special case. Like FLINT, for instance. Knowing that you have a “small int” — you can do arithmetic with the fmpz value directly, ignoring API functions (which, of course, also have a special path for “small ints”).
But we reserve more flexibility for future, leaving this handled entirely by the CPython. After all, it’s not “math-heavy” case.
I don’t think that we will have much problem with already written code (especially by Mark), though linked code will be faster, especially on asymptotics. But bindings to the external bigint library reduce barriers for possible future expansions of the math.integer module.
What library? I’m talking about CPython’s own implementation. If you feed “one or two at a time to an external library”, then of course you lose all possibility for optimizations that require knowing the full context.
How? Unless you “break the wall” between Python and an external library, picking apart the library’s representation yourself? Then CPYthon’s own internals get deeply tied to the specific version of the library it was written against. Stick to their advertised APIs, please.
For the same reasons you were keen to eliminate _pylong.py. The quality of the code is irrelevant. All code is partly an ongoing liability. Why, e.g., keep around fancy code for bigint gcd when (a) a library will do even fancier things by itself; and, (b) much simpler code is perfectly fine for machine-size ints. And, e.g., simple C code for binary gcd may in fact go faster than division-based code for small ints.
You want to build the strongest case you can, and undervaluing this aspect would be a strategic mistake.
Anything we are going to use for doing integer arithmetic. FLINT was chosen as an example, as it’s data type has a different layout for small ints.
Not necessary. The FLINT has an API to check if the fmpz is a small or big (i.e. it’s a pointer to the __mpz_struct-style struct). And you can utilize this e.g. in cases like the current sum() fast-path.
No. As this detail of the FLINT library is a part of it’s public API.
I’ll probably not follow to this road right now (and leave handling of small ints to the CPython). But honestly I don’t think that we lose some optimization opportunities in this way (i.e. if we utilize FLINT-like capabilities of the external library for all integer arithmetic).
Except FLINT is the only consumer of its internal types. They’re using a kind of tagged pointer to represent ints, which FLINT itself picks apart to determine whether it’s a machine int (of slightly reduced range), or a pointer to an external library’s (GMP’s) idea of an int. PyPy does something similar for its own representation of ints (slightly reduced-range machine ints, or pointer to a full-blown Python bigint). But, again, only PyPy needs to understand its representation choices.
Python’s legacy C API complicates life.
I’m not going into details now, though.
BTW, I like FLINT’s approach to tagging! It effectively reserves the top two bits “01” to mean "it’s a pointer. The representation of “small enough” signed machine ints is unchanged, so no bit-level tricks are needed to do arithmetic on them directly.
Many other schemes use the least-signifcant bit(s) instead, with “it’s an int” signaled by the last bit being set. Which then has to be shifted off, with sign extension, to get at the actual int. FLINT’s scheme optimizes the case where speed is paramount (it is a small int).
Of course, FLINT is a big monolitic C library, but this is a part of it’s API and external projects use it. Including the python-flint extension, which is roughly in the same position as the CPython as a API consumer.
I’m not entirely sure if this is backed by the C standard. Rather, not. Though, this doesn’t affect Tier 1-3 platforms from the PEP 11.
Details again. CPython’s idea of an int is in turn exposed to countless extension modules using CPyhon’s C API. No part of which yet supports a notion of “tagged pointers”. CPython can adapt to its own use of Flint’s representations, but it doesn’t end with that.
For example, nothing in C mandates a 2’s-complement representation of machine ints, and nothing guarantees that the pointers malloc returns always have two trailing zero bits. It does mandate alignment requirements, but because it doesn’t define the bit size of “a byte”, nothing can be inferred about the bits in a unintptr_t,. For example, Cray Research machines only supported addressing 64-bit words, and “a byte” in Cray’s C spanned 64 bits. Fine by C! The hardware didn’t do sign-extension on right shifts of signed ints either. Also fine by C. Nobody’s “tagged pointer” representations worked in portable C.
But everyone’s representations work fine on all current major architectures, and Cray’s machines are now ancient history.
Since C23 is a mandatory requirement (section 6.2.6.2):
NOTE 2 The sign representation defined in this document is called two’s complement. Previous revisions of this document additionally allowed other sign representations.
The FLINT implementation makes assumptions that are not standard C but are standard on “normal computers with normal OS and compiler” and that works fine because there isn’t much interest in using FLINT on systems where those assumptions don’t hold. If it were worthwhile then I’m sure that FLINT would bury this all in #ifdef for different compilers and platforms with a fallback that works in standard C but there just isn’t much interest in that.
Does the same not hold for CPython? Can it not just have a standard C fallback? Does it even need to run on systems where these assumptions don’t hold?
I don’t believe three’s any practical problem here, just nerding out by logic-chopping what standards say. I doubt there’s any major project that sticks strictly to what standard C guarantees. Possibly to what standard FORTRAN guarantees, because it guarantees almost nothing (as a former member of the FORTRAN compiler-writer club, I fondly recall long debates over whether the standard required a conforming implementation to support the integer 1 ).
Python did run on Cray 1 boxes, but because I used to work for Cray, knew where the skeletons were, and out of fondness for my former employer added things to CPython like a macro to do sign-extending right shifts. Which I usually had to apply myself, because nobody else gave a rip
And architecture variation visible at the C level has gone waaaaaaaaaay down since those days. For example, I believe all machines Python runs on now are byte-addressed and agree a byte holds 8 bits.
(Note that we run UB sanitizers that catch undefined behaviour like -1<<1 or left-shifting 1 into the sign bit, but not implementation-defined behaviour like -1>>1.)
OTOH, per PEP 11’s Unsupported platforms section, if someone wanted to maintain CPython for Cray, we could merge the patches – as we did recently for PA-RISC :)
It’s rather hard nowadays to test on platforms without 8-bit bytes, 2’s complement, tag-friendly alignment – or even pointers other than 32/64 bits. For stuff that’s easy to test, non-portable magic generally does get wrapped in #ifdefs with a standard C fallback.
(I left a draft open overnight, and posted before I saw your latest reply)
FWIW, s390x – and with it, big-endian architectures in general – is in a a similar situation now: IBM provides the buildbot hardware and can reach a core dev if things go wrong (historically through contracts & escalations; now more directly after an acquisition).
Though, 60x is a lot too.