# What psyco is goot at [Was: Rookie Speaks]

Samuel Walters swalters_usenet at yahoo.com
Thu Jan 8 19:25:33 CET 2004

```|Thus Spake Jacek Generowicz On the now historical date of Thu, 08 Jan
2004 11:43:01 +0100|

> Samuel Walters <swalters_usenet at yahoo.com> writes:
>
>> If you'd like to see an example of both the psyco and profile modules
>> in action, let me know and I'll give you some more understandable code
>> that I once wrote to see what types of things psyco is good at
>> optimizing.
>
> I think this is generally interesting, and would be curious to see it,
> if you'd care to share.

Sure thing.  The functions at the top are naive prime enumeration
algorithms.  I chose them because they're each of a general "looping"
nature and I understand the complexity and methods of each of them.  Some
use lists (and hence linearly indexed) methods and some use dictionary(
and hence are has bound). One of them, sieve_list is commented out because
it has such dog performance that I decided I wasn't interested in
how well it optimized.

These tests are by no means complete, nor is this probably a good example
of profiling or the manner in which psyco is useful.  It's just from an
area where I understood the algorithmic bottlenecks to begin with.

Sam Walters.

--
Never forget the halloween documents.
http://www.opensource.org/halloween/
""" Where will Microsoft try to drag you today?
Do you really want to go there?"""

from math import sqrt
def primes_list(Limits = 1,KnownPrimes = [ 2 ]):
RetList = KnownPrimes
for y in xrange(2,Limits + 1):
w = y
p, r = 0,0
for x in RetList:
if x*x > w:
RetList.append(w)
break
p,r = divmod(y,x)
if r == 0:
w = p
return RetList

def primes_dict(Limits = 1,KnownPrimes = [ 2 ]):
RetList = KnownPrimes
RetDict = {}
for x in KnownPrimes:
RetDict[x] = 1
w = x + x
n = 2
while w <= Limits + 1:
RetDict[w] = n
w += x
n += 1
p, r = 0,0
for y in xrange(2, Limits + 1):
for x, z in RetDict.iteritems():
if x*x > y:
RetDict[y] = 1
break
p,r = divmod(y,x)
if r == 0:
RetDict[y] = p
break
return RetList

def sieve_list(Limits = 1, KnownPrimes = [ 2 ]):
RetList = KnownPrimes
CompList = [ ]
for y in xrange(2, Limits + 1):
if y not in CompList:
w = y
n = 1
while w <= Limits:
CompList.append(w)
w += y
n += 1
return RetList

def sieve_list_2(Limits = 1, KnownPrimes = [ 2 ]):
SieveList = [ 1 ]*(Limits )
RetList = [ ]
for y in xrange(2, Limits + 1):
if SieveList[y-2] == 1:
RetList.append(y)
w = y + y
n = 2
while w <= Limits + 1:
SieveList[w - 2] = n
w += y
n += 1
return RetList

def sieve_dict(Limits = 1, KnownPrimes = [ 2 ]):
SieveDict = { }
RetList = KnownPrimes
for x in KnownPrimes:
SieveDict[x] = 1
w = x + x
n = 2
while w <= Limits + 1:
SieveDict[w] = n
n += 1
w += x

for y in xrange(2, Limits + 1):
if not SieveDict.has_key(y):
RetList.append(y)
w = y
n = 1
while w <= Limits + 1:
SieveDict[w] = n
w += y
n += 1
return RetList

if __name__ == "__main__":
import sys
import profile
import pstats

import psyco

#this function wraps up all the calls that we wish to benchmark.
def multipass(number, args):
for x in xrange(1, number + 1):
primes_list(args, [ 2 ])
print ".",
sys.stdout.flush()
primes_dict(args, [ 2 ])
print ".",
sys.stdout.flush()
#Do not uncomment this line unless you have a *very* long time to wait.
#sieve_list(args)
sieve_dict(args, [ 2 ])
print ".",
sys.stdout.flush()
sieve_list_2(args, [ 2 ])
print "\r           \r%i/%i"%(x, number),
sys.stdout.flush()
print "\n"

#number of times through the test
passes = 5
#find all primes up to maximum
maximum = 1000000

#create a profiling instance
pr = profile.Profile( bias = 7.5e-06)

#run the tests
pr.run("multipass(%i, %i)"%(passes,maximum))
#save them to a file.
pr.dump_stats("primesprof")

#remove the profiling instance so that we can get a clean comparison.
del pr

#create a profiling instance
pr = profile.Profile( bias = 7.5e-06)

#"recompile" each of the functions under consideration.
psyco.bind(primes_list)
psyco.bind(primes_dict)
psyco.bind(sieve_list)
psyco.bind(sieve_list_2)
psyco.bind(sieve_dict)

#run the tests
pr.run("multipass(%i, %i)"%(passes,maximum))
#save them to a file
pr.dump_stats("psycoprimesprof")

#clean up our mess
del pr

#load and display each of the run-statistics.
pstats.Stats('primesprof').strip_dirs().sort_stats('cum').print_stats()
pstats.Stats('psycoprimesprof').strip_dirs().sort_stats('cum').print_stats()

```