homepage

A while ago Victor Stinner has spend several weeks in porting PyLongs to
GMP:
http://mail.python.org/pipermail/python-3000/2007-September/010718.html
http://mail.python.org/pipermail/python-3000/2007-October/010755.html
Although his patch didn't give the speedup he hoped for, the patch might
be interesting someday in the future. He never submitted it to our bug
tracker. I'm posting it to conserve it for the future.

Since this keeps coming up, I think it would make sense to turn this
into an optional extension module.
PS. The licensing concerns are another reason not to use this for the
core long (or int in Py3k) type.

Why was the mpz module removed from Python 2.4 in the first place? 2.3
has it.
I see three way to implement the option:
 * Let somebody implement a mpz type as a 3rd party extension.
 * Let somebody implement a mpt type and ship it with the Python core
 * Let somebody write a patch that replaces the built-in long type
implementation with a GMP based implementation (./configure
--with-gmp-integer)

I don't recall, but I suppose it had stopped working and nobody could be
found who wanted to maintain it. Possibly the Python-unfriendly license
was also a reason.

I updated my patch against Python3 trunk. I fixed my patch to pass 
most long and struct tests:
 - fix byte array import/export
 - check for overflow
 - compute exponent in conversion to a float (use PyLong_SHIFT=1)
 - fix formating to support 0b, 0o, 0x or custom base (XX#...)
You have to add "-lgmp" to LIBS variable of the Makefile.
There are still some issues about (unsigned) long long: overflow is 
not detected. mashal is broken for long.
diffstat py3k-long_gmp-v3.patch
 Include/longintrepr.h | 49
 Include/longobject.h | 3
 Modules/mathmodule.c | 6
 Objects/boolobject.c | 12
 Objects/longobject.c | 3053 
+++++---------------------------------------------
 Python/marshal.c | 9
 Python/mystrtoul.c | 26
 7 files changed, 376 insertions(+), 2782 deletions(-)

And Now for Something Completely Different. Benchmarks!
 - python3 rev67089.
 - Pentium4 @ 3.0 GHz (integer = 32 bits)
 - GCC 4.1.3 (Ubuntu Gutsy)
gcc -O0:
 builtin: 20920.5 pystones/second
 GMP: 17985.6 pystones/second
gcc -O3:
 builtin: 30120.5 pystones/second
 GMP: 25641.0 pystones/second
(I took the biggest value of 3 runs)

New version of the patch using short integer for long_add, long_sub, 
long_mul, etc. New benchmark with -0O : 20161.3 pystones/second 
(versus 20920.5 for the vanilla version). The overhead is now -3,6% 
(yes, it's slower with GMP).

Updated patch, changes:
 - fix mashal module
 - fix all conversion from/to small integer (long, unsigned long, long 
long, unsigned long long, size_t, ssize_t)
 - create numbits() method for the long type (see also issue #3439)
 - catch memory allocation failure
 - fix many other bugs to fix most tests
Failing tests:
 - decimal: long_hash() is broken (doesn't use MSB)
 - io, pickle, pickletools, sqlite, tarfile: null byte in argument for 
int()
 - random: use old files from pickle whih contains '2147483648L\n' 
(trailing L)
 - sys: sizeof is invalid
To do: 
- raise OverflowError in numbits() for integer 2**(2**k) where 2**k
doesn't fit in an integer
- fix last tests
This version is slower than previous version, but it has less bugs :-)

Since it's hard to compare patches, I will now attach the 
longobject.c. But it would be better to use a DVCS with a branch to 
test it...

Notes:
- GNU Common LISP uses CLN, which uses GMP's low-level
functions (http://cvs.savannah.gnu.org/viewvc/gcl/gcl/gmp/)
- GHC (Haskell compiler, http://haskell.org/ghc/) uses (or 
used) GMP. But Haskell is a statically typed language, where one can 
choose between fixed sized types like Int, and variable sized 
integers.
(informations from the GMP mailing list)

After many benchmarks, I realized that it's not a good idea to use GMP 
for the int (and long) integers because most integers are very small: 
less or equals than 32 bits (or 64 bits on a 64 bits CPU). GMP 
overhead is too big. See other propositions to optimize Python 
integers.

I agree that this probably isn't right for core Python. But I think this 
is valuable work, and it would be nice to see this patch available and 
maintained somewhere, if anyone has the energy.
I'm wondering whether the Sage folks would be interested in this; as I 
understand it, they currently have Python integers *and* Sage integers 
(based on GMP), along with various rules about which integers you can use 
for what. For example, according to
http://www.sagemath.org/doc/prog/node21.html
you can't use a Sage integer as a list index. Having just one type of 
integer might simplify things a little.

What about using PyVarObject of mp_limb_t and mpn instead of mpz_t? 
Addition:
 - Check signs and allocate.
 - Possibly compare absolute values.
 - Call mpn_(add|sub)_n and possibly mpn_(add|sub)_1 if the integers have different sizes.
 - Overhead for small integers: 1 Python->GMP, 1 if.
Subtraction:
 - Same as addition
Multiplication:
 - Check signs and allocate.
 - Call mpn_mul.
 - Overhead for small integers: 1 Python->GMP, 2 GMP->GMP, 3 if.
Division:
 - Check signs and allocate.
 - Call mpn_div_q.
 - Overhead for small integers: 1 Python->GMP, 1 GMP->GMP, 1 if, maybe a 3 more ifs in mpn_divrem_1.
Pow:
 - Create mpz_t values using MPZ_ROINIT_N(limbs, size) and call mpz_pow(m?). Copy from mpz_limbs_read(result).
* The overhead is after checking if both arguments are integers until going to the right function (mpn_mul -> mpn_mul_n -> mpn_mul_basecase).
Checks for adding integers < 1<<(GMP_NUMB_BITS-1), multiplying < 1<<(GMP_NUMB_BITS/2) and dividing < 1<<GMP_NUMB_BITS can be added.

> What about using PyVarObject of mp_limb_t and mpn instead of mpz_t? 
FYI this issue is closed, it's not a good practice to comment closed issue (for example, the issue is hidden in the list of recent issues).
If you want to learn more about my old patch, you should also read python-dev archives. Another major blocking point was the license: GMP is released under the GNU GPL license, which is incompatible with the Python License.