performance problem in python 2.2

[Fernando Perez]

Jeff Davis wrote:

> I wrote a small python program to help me solve a math problem. When I
> tried to run it with large values, it ate all my RAM and I eventually had
> to kill it. I tried writing the same thing in C and it used almost no RAM
> (and had an upper limit) and finished much faster.
> 
> Then I was talking to someone who suggested that I try perl. I have the
> exact same algorithm in perl, and it doesn't eat my RAM, and executes much
> more quickly (same order of magnitude as the c program). It seems almost
> as if there's a memory leak in one of python's simple math operations,
> because it is so much worse than the other ones I tried.
> 
> I have listed the two programs below. Does someone think I found a
> bug/memory leak? Does someone know about something else that might be
> going on?

Well a few people have already given you some pointers, and the caveats to 
the problem of representing p as a float which Tim Peters indicated. But 
ignoring those for a moment, and doing things with xrange, it remains true 
that Python's flexibility does have a price. All names are bound to objects 
whose behavior needs to be looked at every time.

On the other hand, I'd be INCREDIBLY surprised to see that perl can come 
anywhere close to C speed on this little problem. Here are some quick 
benchmarks:


# Python version:

higgs[python]> time ./numbers.py 1000000
2.71050724088e-08
4.360u 0.000s 0:04.42 98.6%     0+0k 0+0io 457pf+0w


# Perl version:

higgs[python]> time ./numbers.pl 1000000
2.71050724087729e-08
1.920u 0.000s 0:01.93 99.4%     0+0k 0+0io 293pf+0w

# C version:

higgs[python]> time ./numbers.cx 1000000
2.7105081417191923e-08
0.030u 0.000s 0:00.04 75.0%     0+0k 0+0io 115pf+0w

As you see, perl/python are in the same league, even though perl is a factor 
of 2 faster. I am one of those people who would like to see that factor of 2 
gone, but in reality when speed matters I'm happy inlining C code in python 
via weave. But the C code is in a different league altogether, as it should.

I'm aware though that the factor of 2 for perl's faster performance isn't 
always there, it just tends to show up under certain circumstances. 99% of 
the time I don't care, and I'd much rather see the dev team's time and 
efforts spent on more important problems (as they do).

For reference, the codes are below:

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char *argv[])
{
    long i,c;
    double n = 1.0;
    double p = 1.8446744073709551616e+19;

    c = atol(argv[1]);
    for (i=1;i<=c;++i)
        n = (n * (p-i)) / p;
    printf("%.16e\n",1-n);
    return 0;
}

#!/usr/bin/perl

$p = 2**64;
$c = $ARGV[0];


$n = 1;
foreach $i (1..$c) {
        $n = ($n * ($p-$i)) / $p
}
print 1-$n, "\n";


#!/usr/bin/env python

import sys

n = 1.0
p = 2.0**64 # making p a float for fariness of comparison, not correctness
c = int(sys.argv[1])

for i in xrange(1,c+1):
    n = (n * (p-i)) / p
print 1-n


So in summary, Python does offer you the easiest way to get the problem 
_right_, by allowing you to use long integers for everything. In the tight 
loops it does remain a bit slower. Most of us are willing to pay that price 
though (even though we'd like it to disappear, of course, if it was so easy 
:).

But again, there's NO WAY you are going to write perl code to do this at C 
speed (short of a trick like inlining C in perl).

Cheers,

f.