classification
Title: Performance regression in long division in 2.6
Type: Stage:
Components: Interpreter Core Versions: Python 2.6
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: fredrikj, loewis, pitrou, vstinner
Priority: normal Keywords:

Created on 2008-10-15 10:03 by fredrikj, last changed 2008-10-17 18:00 by loewis. This issue is now closed.

Files
File name Uploaded Description Edit
division_speed.txt fredrikj, 2008-10-15 10:03
Messages (7)
msg74798 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-15 10:03
On my laptop (Windows XP, 32-bit), long division is about 15% slower in
2.6 compared to 2.5. See the attached .txt for timings.

I noticed this when comparing the unit tests for mpmath
(http://code.google.com/p/mpmath/) under 2.5 and 2.6. It appears that
most tests run 10-20% faster under 2.6 (good work all Python
developers!), but the tests performing very high precision arithmetic
run noticeably slower.

From some quick benchmarking, addition and multiplication are not the
culprits (they both actually seem to be quite a bit faster in 2.6). 

There could be other factors involved, but from what I've found out so
far, it is only division that has become slower in 2.6.

Division in Python 2.4 is also the same speed as 2.5.
msg74799 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2008-10-15 10:44
The source code is unchanged except the format functions (binary and 
octal bases with the new prefixes: 0b, 0o). The speed difference comes 
from different compiler options.
 - (Ubuntu Gutsy) python2.5: 1010 ms
 - python trunk: 1010 ms
 - python trunk with -O0: 1800 ms

I'm using -O0 to help gdb debug, but the default gcc optimization 
level for Python is -03.

Did you recompiled your own Python or did you use the binary at 
python.org? Look at the compilater option for python 2.5 and python 
2.6.
msg74800 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-15 10:51
> The speed difference comes from different compiler options.

I figured as much. I'm using the binaries from python.org (see the .txt
file; it includes version headers).

The question is why the compilation changes for 2.6 slowed down division
but not e.g. multiplication, and if there is a workaround.
msg74906 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-10-17 13:14
It may be that one of the builds was done with profile-guided
optimization and the other was not.
If you are interested in long division performance, you may also take a
look at #3451.
msg74909 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2008-10-17 14:09
The 2.5 build was done by VS 2003, with no PGO, and the 2.6 build was
done with VS 2008, and it used profile-guided optimization.

To understand why it behaves the way it behaves, you probably need to
look at the respective machine code.

I propose to close this as "won't fix"; I'm not interested in 150ms
speed differences when dividing 100000 digit numbers.
msg74915 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2008-10-17 14:49
> I propose to close this as "won't fix"

I agree.

> I'm not interested in 150ms speed differences when dividing 100000 
digit numbers.

I'm ok to close the ticket, but I'm also interrested to optimize 
Python. But the compiler option is not the best choice to optimize a 
program. I prefer changes like using a O(n) algorithm instead of 
O(n^2) algorithm.
msg74927 - (view) Author: Fredrik Johansson (fredrikj) Date: 2008-10-17 17:55
> I propose to close this as "won't fix"; I'm not interested in 150ms
> speed differences when dividing 100000 digit numbers.

Sure.

(I care about differences like this, because they have a tendency to add
up. But it's a minor issue, and a faster algorithm in Python 2.7 will
indeed solve the problem.)
History
Date User Action Args
2008-10-17 18:00:48loewissetstatus: open -> closed
resolution: wont fix
2008-10-17 17:55:17fredrikjsetmessages: + msg74927
2008-10-17 14:49:44vstinnersetmessages: + msg74915
2008-10-17 14:09:06loewissetmessages: + msg74909
2008-10-17 13:14:20pitrousetnosy: + loewis, pitrou
messages: + msg74906
2008-10-15 10:51:22fredrikjsetmessages: + msg74800
2008-10-15 10:44:08vstinnersetnosy: + vstinner
messages: + msg74799
2008-10-15 10:03:16fredrikjcreate