What psyco is goot at [Was: Rookie Speaks]

[Samuel Walters]

|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
        #adjust the argument based on your system.
        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
        #adjust the argument based on your system.
        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()