classification
Title: Victor Stinner's GMP patch for longs
Type: enhancement Stage:
Components: Interpreter Core Versions: Python 3.0
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: christian.heimes, gvanrossum, haypo, mark.dickinson, tim_one
Priority: low Keywords: patch

Created on 2008-01-12 17:12 by christian.heimes, last changed 2008-12-05 21:04 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
py3k-long_gmp-v4.patch haypo, 2008-11-04 03:21
py3k-long_gmp-v11.patch haypo, 2008-11-04 17:27
longobject.c haypo, 2008-11-04 17:28
Messages (12)
msg59828 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-12 17:12
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.
msg59833 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2008-01-12 17:43
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.
msg59858 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2008-01-13 17:27
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)
msg59860 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2008-01-13 17:36
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.
msg75486 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 01:00
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(-)
msg75487 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 01:21
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)
msg75489 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 03:21
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).
msg75496 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 17:27
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 :-)
msg75497 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-04 17:28
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...
msg75838 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-11-13 21:26
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)
msg77018 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2008-12-05 14:32
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.
msg77069 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2008-12-05 21:04
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.
History
Date User Action Args
2008-12-05 21:04:47mark.dickinsonsetmessages: + msg77069
2008-12-05 14:53:57hayposetstatus: open -> closed
resolution: rejected
2008-12-05 14:32:27hayposetmessages: + msg77018
2008-11-13 21:26:16hayposetmessages: + msg75838
2008-11-04 17:28:59hayposetfiles: + longobject.c
messages: + msg75497
2008-11-04 17:27:57hayposetfiles: + py3k-long_gmp-v11.patch
messages: + msg75496
2008-11-04 03:22:27hayposetfiles: - py3k-long_gmp-v3.patch
2008-11-04 03:22:25hayposetfiles: - py3k-long_gmp-v2.patch
2008-11-04 03:22:11hayposetfiles: + py3k-long_gmp-v4.patch
messages: + msg75489
2008-11-04 01:21:24hayposetmessages: + msg75487
2008-11-04 01:01:18hayposetfiles: + py3k-long_gmp-v3.patch
nosy: + haypo
messages: + msg75486
2008-01-13 17:36:54gvanrossumsetmessages: + msg59860
2008-01-13 17:27:31christian.heimessetmessages: + msg59858
2008-01-12 17:43:26gvanrossumsetpriority: normal -> low
nosy: + gvanrossum
messages: + msg59833
keywords: + patch
2008-01-12 17:12:12christian.heimescreate