Mailing List Archive: Python: Dev

Optimize Python long integers

Index | Next | Previous | View Threaded

victor.stinner at haypocalc

Nov 11, 2008, 5:25 AM

Post #1 of 12 (1295 views)
Permalink

Optimize Python long integers

Hi,

Patches
=======

There are some very interesting propositions (with patches!) to optimize
Python int and long types (especially the long integers).
--------------------------------
haypo: Macros for PyLong: sign, number of digits, fits in an int
http://bugs.python.org/issue4294

marketdickinson: Use 30-bit digits instead of 15-bit digits for integers
http://bugs.python.org/issue4258

pernici: faster long multiplication
http://bugs.python.org/issue3944

haypo: Victor Stinner's GMP patch for longs
http://bugs.python.org/issue1814

fredrikj: Asymptotically faster divmod and str(long)
http://bugs.python.org/issue3451
--------------------------------

See also:
--------------------------------
fredrikj: create a numbits() method for int and long types
http://bugs.python.org/issue3439
--------------------------------

Benchmark
=========

I tried to do benchmark on all these patches using pystone or pybench, but the
results are inaccurate. Pystone results change with +/- 20% with the same
code on different runs. I tried more loops (pystone 250000), but it doesn't
change anything. Pybench is better it is also inaccurate to benchmark
operations on integers.

That's I started to write a *basic* benchmark tool to compare the different
patches: see file bench_int.py of the issue #4294.

Benchmark on a 64 bits CPU @2.5 GHz :
-------------------------------
original : 896.5 ms
+ macros : 891.0 ms (+0.6%) |
++ optimize : 884.3 ms (+1.4%) |-- issue #4294
+++ shift : 880.8 ms (+1.7%) |
fast long : 746.8 ms (+16%) -- issue #3944
GMP : 700.9 ms (+22%) -- issue #1814
30 bits : 659.9 ms (+26%) -- issue #4258
-------------------------------

Benchmark on a 32 bits CPU @3.0 GHz :
---------------------------
original : 1564.3 ms
fast long : 1591.7 ms (-2%)
GMP : 1564.4 ms (=)
30 bits : 1497.3 ms (+4%)
---------------------------

Don't trust the benchmark results since my tool is young and may also be
inaccurate, but it's a good start to compare the patches.

Notes:
- my macro patch doesn't want to optimize anything, it's just
a preparation for new patches; but I also attached "optimization"
patches which are useless (only +1.7% with all patches).
- 30 bits is always faster
- GMP is faster on 64 bits or at same speed on 32 bits
- fast long is slower on a 32 bits CPU

Python integers
===============

I tried to understand why the "30 bits" patch is not as fast as I expected. I
introduced statistics in the long type: see long_stat.patch of the issue
#4258. Summary (on a 32 bits CPU):

- PyLong_FromLong(), long_add() and long_compare() are the 3 most common
operations on integers.
- Most integers are in range [-255; 255], large integers are rare. With
make and pystone programs, largest integer has 1321 bits, but there is
just one such integer. Another is 33 bits, but all other integers fits
in 32 bits (without the sign, so 33 bits with the sign). I saw that the
symbol table use memory address in a dictionary key (so 32 bits on a
32 bits CPU and 64 bits on a 32 bits CPU).
=> we have to focus on small integers
- pystone is inaccurate to benchmark integers: it only uses a big integer
(more than 1 digit in base 2^30) on 1.000.000 integers
=> don't use pystone!

I don't have a solution working on any CPU with all numbers, this email is
just a summary of the interesting integer patches.

--
Victor Stinner aka haypo
http://www.haypocalc.com/blog/
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

solipsis at pitrou

Nov 11, 2008, 5:35 AM

Post #2 of 12 (1253 views)
Permalink

Re: Optimize Python long integers [In reply to]

Victor Stinner <victor.stinner <at> haypocalc.com> writes:
>
> I tried to do benchmark on all these patches using pystone or pybench, but the
> results are inaccurate. Pystone results change with +/- 20% with the same
> code on different runs. I tried more loops (pystone 250000), but it doesn't
> change anything. Pybench is better it is also inaccurate to benchmark
> operations on integers.
>
> That's I started to write a *basic* benchmark tool to compare the different
> patches: see file bench_int.py of the issue #4294.

If you want to benchmark arithmetic on large integers, you may try out the
pidigits test from the Computer Language Shootout :
http://shootout.alioth.debian.org/u64/benchmark.php?test=pidigits&lang=python&id=1

cheers

Antoine.

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

thomas at python

Nov 11, 2008, 2:40 PM

Post #3 of 12 (1241 views)
Permalink

Re: Optimize Python long integers [In reply to]

On Tue, Nov 11, 2008 at 14:25, Victor Stinner
<victor.stinner [at] haypocalc>wrote:

> There are some very interesting propositions (with patches!) to optimize
> Python int and long types (especially the long integers).

Here's another one:
http://code.python.org/loggerhead/users/twouters/intopt-- integer
inlining through pointer tagging trickery. In Python 2.6 it costs
2-4% overall performance but increases integer arithmetic (in the range
[-0x40000000, 0x40000000) only) by 10-20% according to my rough measurements
(I haven't tried your benchmark yet.) I haven't ported it to 3.0 but it
should provide a bigger win there. It also breaks API compatibility in a few
ways: Py_TYPE(o) and Py_REFCNT(o) are no longer valid lvalues, and they and
Py_INCREF(o) and Py_DECREF(o) may all evaluate 'o' twice. And, worst of all,
it exposes the tagged pointers to third-party extensions, so anything not
doing typechecks with Py_TYPE(o) will likely cause buserrors.

In retrospect, perhaps this is too controversial to be added to the list ;-)
I don't really expect this to be something CPython would want to use as-is,
although there may be use for tagged pointers in more controlled
environments (like function locals.)

--
Thomas Wouters <thomas [at] python>

Hi! I'm a .signature virus! copy me into your .signature file to help me
spread!

martin at v

Nov 11, 2008, 3:14 PM

Post #4 of 12 (1251 views)
Permalink

Re: Optimize Python long integers [In reply to]

> There are some very interesting propositions (with patches!) to optimize
> Python int and long types (especially the long integers).

Just trying to clarify the focus: would you like to see any of these
applied to 2.6? To me, it's clear that they are out of scope now, as
they don't fix bugs.

Regards,
Martin
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

barry at python

Nov 11, 2008, 3:52 PM

Post #5 of 12 (1238 views)
Permalink

Re: Optimize Python long integers [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Nov 11, 2008, at 6:14 PM, Martin v. L�wis wrote:

>> There are some very interesting propositions (with patches!) to
>> optimize
>> Python int and long types (especially the long integers).
>
> Just trying to clarify the focus: would you like to see any of these
> applied to 2.6?

No!
- -Barry

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iQCVAwUBSRoa1nEjvBPtnXfVAQKwwgP/YvkcFbFc+RDV3VSJ6EHWuBVOdG9YFEGq
Riq2GAst7kBMrteMfMHSv0Vb3elngLPRCKxTndUIV9B/ksfVQEHNbz9l1z7HRxmZ
0jVeYCkXCj923bsZ48Gq1MmcZ1d07TERfSVCDXnKooQgj8GlNqT70ru/0+eMFk8d
wKLL6cpdak0=
=cNoh
-----END PGP SIGNATURE-----
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

victor.stinner at haypocalc

Nov 11, 2008, 3:56 PM

Post #6 of 12 (1237 views)
Permalink

Re: Optimize Python long integers [In reply to]

Le Wednesday 12 November 2008 00:14:40, vous avez �crit�:
> > There are some very interesting propositions (with patches!) to optimize
> > Python int and long types (especially the long integers).
>
> Just trying to clarify the focus: would you like to see any of these
> applied to 2.6?

All optimisations patches are long and may introduce new regressions. It's
better to wait for 2.7/3.1.

But it would be nice to get numbits() method (or property?) in Python 3.0(.1)
and/or Python 2.6.1.

--
Victor Stinner aka haypo
http://www.haypocalc.com/blog/
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

barry at python

Nov 11, 2008, 4:02 PM

Post #7 of 12 (1247 views)
Permalink

Re: Optimize Python long integers [In reply to]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Nov 11, 2008, at 6:56 PM, Victor Stinner wrote:

> Le Wednesday 12 November 2008 00:14:40, vous avez �crit :
>>> There are some very interesting propositions (with patches!) to
>>> optimize
>>> Python int and long types (especially the long integers).
>>
>> Just trying to clarify the focus: would you like to see any of these
>> applied to 2.6?
>
> All optimisations patches are long and may introduce new
> regressions. It's
> better to wait for 2.7/3.1.
>
> But it would be nice to get numbits() method (or property?) in
> Python 3.0(.1)
> and/or Python 2.6.1.

Anyone remember the bool debacle?

- -Barry

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iQCVAwUBSRodJHEjvBPtnXfVAQK0VwP/f2vyfahYxhRh/ug+ekMp63rhVvy2iMTn
VXndnaKqJtJovjuM3YAGQk9/8l6tD4w0DklAi4e175aBvwzRkWb4RwMHGMO2/jn1
mNjloHqku6qIg6+p7jS5ytwsH6sGndgAjARY7jFE8OgYoYPrxtTabgXpr9HM631K
a2j8FUmCVQ8=
=yirj
-----END PGP SIGNATURE-----
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

dickinsm at gmail

Nov 11, 2008, 4:03 PM

Post #8 of 12 (1237 views)
Permalink

Re: Optimize Python long integers [In reply to]

On Tue, Nov 11, 2008 at 11:14 PM, "Martin v. Löwis" <martin [at] v> wrote:
> Just trying to clarify the focus: would you like to see any of these
> applied to 2.6? To me, it's clear that they are out of scope now, as
> they don't fix bugs.

There are some minor bugs in longobject.c that I think should be applied
to 2.6.1 and 3.0.1 (not worth it for 3.0). I'll try to put together a
separate patch containing these. They're mostly either missing casts
or places where int should have been changed to Py_ssize_t.

numbits shouldn't go into 2.6 or 3.0.

Mark
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

steve at holdenweb

Nov 11, 2008, 6:07 PM

Post #9 of 12 (1237 views)
Permalink

Re: Optimize Python long integers [In reply to]

Victor Stinner wrote:
> Le Wednesday 12 November 2008 00:14:40, vous avez �crit :
>>> There are some very interesting propositions (with patches!) to optimize
>>> Python int and long types (especially the long integers).
>> Just trying to clarify the focus: would you like to see any of these
>> applied to 2.6?
>
> All optimisations patches are long and may introduce new regressions. It's
> better to wait for 2.7/3.1.
>
> But it would be nice to get numbits() method (or property?) in Python 3.0(.1)
> and/or Python 2.6.1.
>
>
But that would be new functionality in a micro-release, which is verboten.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

steve at holdenweb

Nov 11, 2008, 6:07 PM

Post #10 of 12 (1235 views)
Permalink

Re: Optimize Python long integers [In reply to]

tjreedy at udel

Nov 11, 2008, 7:30 PM

Post #11 of 12 (1235 views)
Permalink

Re: Optimize Python long integers [In reply to]

Victor Stinner wrote:
> Le Wednesday 12 November 2008 00:14:40, vous avez �crit :
>>> There are some very interesting propositions (with patches!) to optimize
>>> Python int and long types (especially the long integers).
>> Just trying to clarify the focus: would you like to see any of these
>> applied to 2.6?
>
> All optimisations patches are long and may introduce new regressions. It's
> better to wait for 2.7/3.1.
>
> But it would be nice to get numbits() method (or property?) in Python 3.0(.1)
> and/or Python 2.6.1.

Try something on Pypi if you want to distribute to non-svn users sooner
than 2.7/3.1.

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

ondrej at certik

Nov 13, 2008, 6:53 AM

Post #12 of 12 (1231 views)
Permalink

Re: Optimize Python long integers [In reply to]

On Tue, Nov 11, 2008 at 11:40 PM, Thomas Wouters <thomas [at] python> wrote:
>
>
> On Tue, Nov 11, 2008 at 14:25, Victor Stinner <victor.stinner [at] haypocalc>
> wrote:
>>
>> There are some very interesting propositions (with patches!) to optimize
>> Python int and long types (especially the long integers).
>
> Here's another one: http://code.python.org/loggerhead/users/twouters/intopt
> -- integer inlining through pointer tagging trickery. In Python 2.6 it costs
> 2-4% overall performance but increases integer arithmetic (in the range
> [.-0x40000000, 0x40000000) only) by 10-20% according to my rough measurements
> (I haven't tried your benchmark yet.) I haven't ported it to 3.0 but it
> should provide a bigger win there. It also breaks API compatibility in a few
> ways: Py_TYPE(o) and Py_REFCNT(o) are no longer valid lvalues, and they and
> Py_INCREF(o) and Py_DECREF(o) may all evaluate 'o' twice. And, worst of all,
> it exposes the tagged pointers to third-party extensions, so anything not
> doing typechecks with Py_TYPE(o) will likely cause buserrors.
>
> In retrospect, perhaps this is too controversial to be added to the list ;-)
> I don't really expect this to be something CPython would want to use as-is,
> although there may be use for tagged pointers in more controlled
> environments (like function locals.)

You might also try sympy (http://code.google.com/p/sympy/). Calculates
10**5 decima digits of pi:

pure Python integers:

$ MPMATH_NOGMPY=yes ipython
In [1]: from sympy import pi

In [2]: %time a=pi.evalf(10**5)
CPU times: user 8.56 s, sys: 0.00 s, total: 8.56 s
Wall time: 8.56 s

gmpy integers:

$ ipython
In [1]: from sympy import pi

In [2]: %time a=pi.evalf(10**5)
CPU times: user 0.28 s, sys: 0.00 s, total: 0.28 s
Wall time: 0.28 s

So with gmpy, it is 30x faster.

Ondrej
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads