performance problem in python 2.2

[Jeff Davis]

Tim Peters wrote:

> [Jeff Davis]
>> I wrote a small python program to help me solve a math problem. When I
>> tried to run it with large values,
> 
> What does "large values" mean?  Please be specific.
> 

If I run it with about 10 million for 'c', it works ok, but if it's about 
100 million, it doesn't seem to work very well (although much better now 
that someone pointed out to use xrange() instead of range()). I think now 
that I am using xrange(), it is pretty much linear wrt the c value that I 
supply, like the C and perl versions. After using the other suggestions, 
my concern now has more to do with python just being about 5 times slower 
than perl (see time listings and code listings below). 

>> 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.
> 
> When you wrote it in C, how did you declare p?  In your Perl code $p is a
> double-precision float, and in your Python code p is an unbounded integer
> (a
> data type Perl doesn't have natively).  It's impossible to know what you
> intended (although easy to guess <wink>).
> 

'p' was an unsigned long long int. I slightly modified the algorithm in C 
because it doesn't have (native) support for > 64-bit ints. Since the 
number of possibilities is 2**64 that value will be slightly bigger than a 
64 bit int could hold. So, I just basically multiplied twice by 2^32 and 
divided twice by 2^32. In other words, I basically treated 'p' as 
sqrt(p)*sqrt(p) and commuted the multiplication so that I would arrive at 
the same result (and the testing seemed to show the same results as my 
other algorithm). I have attached my c code below in case you'd like to 
know exactly what's going on. 

>> 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?
> 
> I don't, no.
> 

Yeah, neither do I. I was mostly questioning python's RAM eating approach 
to my iterative algorithm that really shouldn't use very much memory. 
Someone else pointed out that I should use xrange() instead of range() (my 
fault, not python's), and that alleviated the boundless RAM usage, and 
comforted me quite a bit about python's computation ability. However, I 
later used the unix "time" command to test execution time, and the perl 
version was still about 5 times faster.

>> Does someone know about something else that might be going on?
> 
> You do, yes -- but you haven't told us what yet <wink>.
> 
>> ...

I hope this information is more specific/useful. Thanks very much for your 
reply (and others who also replied), it's helped me a lot. 

Regards,
        Jeff


code listings:
=============c========================
#include <stdio.h>

int main(int argc, char * argv[])
{
  unsigned long long int p,c,i;
  long double r = 1.0;
  p = 4294967296;
  c = 100000000;
  for(i = 1; i < c+1; i++) {
    r = (r*p)*p - (r*i);
    r /= p;
    r /= p;
  }

  printf("%.75Lf\n",1-r);
}
==================perl=================
#!/usr/bin/perl

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

$n = 1;
foreach $i (1..$c) {
        $n = ($n * ($p-$i)) / $p
}
print 1-$n, "\n";
=================python================
#!/usr/bin/python2.2

import sys

n = 1.0
p = 2L**64
c = long(sys.argv[1],10)

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

================time listings===============
===========c==============
jdavis at jeff:~/code/c$ time ./crunch
0.000271013814962212042265765621351647496339865028858184814453125000000000000

real    0m32.915s
user    0m32.310s
sys     0m0.030s
=========perl==============
jdavis at jeff:~$ time code/pl/crunch.pl 100000000
0.000271014079116894

real    2m12.835s
user    2m8.400s
sys     0m0.110s
===========python==========
jdavis at jeff:~$ time code/py/crunch.py 100000000
0.000271014073697

real    13m19.242s
user    12m53.200s
sys     0m2.420s