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, h.venev, haypo, mark.dickinson, tim.peters
Priority: low Keywords: patch

Created on 2008-01-12 17:12 by christian.heimes, last changed 2014-04-07 10:59 by haypo. 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 (14)
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.
msg215690 - (view) Author: Hristo Venev (h.venev) * Date: 2014-04-07 10:45
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.
msg215691 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2014-04-07 10:59
> 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.
History
Date User Action Args
2014-04-07 10:59:13hayposetmessages: + msg215691
2014-04-07 10:45:27h.venevsetnosy: + h.venev
messages: + msg215690
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