## Very symple code with bad performance

This is the place for queries that don't fit in any of the other categories.

### Very symple code with bad performance

Hi..

I'm new with Python and i want to know if is there any way to improve the time execution of this simple code:
Code: Select all
`import mathdef IsPrime(x):        if x == 1:        return False    elif x == 2 or x == 3 or x == 5:        return True    elif x % 2 == 0 or x % 3 == 0 or x % 5 == 0:        return False            top = int(math.ceil(math.sqrt(x)))    for i in range(7, top+1, 30):                if x%i == 0 or x%(i+2) == 0 or x%(i+4) == 0 or x%(i+6) == 0 or x%(i+10) == 0 or x%(i+12) == 0 or x%(i+16) == 0 or x%(i+22) == 0 or x%(i+24) == 0:            return False    return Trueprint IsPrime(9007199254740881)`

when i run it, it takes at least 6 seconds to return me the result, i've coded the same task in other languages like Javascript and it takes less than 1 second
Code: Select all
`<script>    function IsPrime(x){  if (x == 1)      return false;  else if( x == 2 || x == 3 || x == 5)      return true;  else if( x % 2 == 0 || x % 3 == 0 || x % 5 == 0)      return false;    top = Math.ceil(Math.sqrt(x));    for(i=7; i < top+1; i+=30)  {      if( x%i == 0 || x%(i+2) == 0 || x%(i+4) == 0 || x%(i+6) == 0 || x%(i+10) == 0 || x%(i+12) == 0 || x%(i+16) == 0 || x%(i+22) == 0 || x%(i+24) == 0)          return false;  }    return true;}  window.alert( IsPrime(9007199254740881) );</script>`

As i'm new i don't know if i'm loosing something.

Last edited by ja0335 on Tue Jun 17, 2014 10:53 pm, edited 1 time in total.
ja0335

Posts: 2
Joined: Sun Jun 15, 2014 11:32 pm

### Re: Very symple code with bad performance

I can't tell for sure, but I'm thinking the Javascript engine you're using might have some JIT aspect. This takes 0.6 seconds for me with Pypy, although it takes like 2.6s with regular Python 2. Just 2.4s swapping out range() for xrange().
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Very symple code with bad performance

Your exact code takes around 2 seconds for me as is.
Code: Select all
`metulburr@ubuntu ~ \$ time python test.pyTruereal   0m1.825suser   0m1.790ssys   0m0.034smetulburr@ubuntu ~ \$ time python3 test.pyTruereal   0m2.870suser   0m2.861ssys   0m0.006s`

Your exact code wrapped in a c library executed by python runs at about .02 seconds

test.c
Code: Select all
`#include <math.h>#include <stdbool.h>bool IsPrime(unsigned long int x){  if (x == 1)      return false;  else if( x == 2 || x == 3 || x == 5)      return true;  else if( x % 2 == 0 || x % 3 == 0 || x % 5 == 0)      return false;    unsigned long int top = ceil(sqrt(x));    for(unsigned int i=7; i < top+1; i+=30)  {      if( x%i == 0 || x%(i+2) == 0 || x%(i+4) == 0 || x%(i+6) == 0 || x%(i+10) == 0 || x%(i+12) == 0 || x%(i+16) == 0 || x%(i+22) == 0 || x%(i+24) == 0)          return false;  }    return true;}`

wrapper.py
Code: Select all
`import ctypesimport ospath = os.path.dirname(os.path.abspath(__file__))fullpath = os.path.join(path, 'lib.so')ctypes.cdll.LoadLibrary(fullpath)lib = ctypes.CDLL(fullpath)lib.IsPrime(9007199254740881)`

Code: Select all
`metulburr@ubuntu ~  \$ gcc -std=c99 -shared -o lib.so -fPIC test.cmetulburr@ubuntu ~  \$ time python wrapper.pyreal   0m0.020suser   0m0.015ssys   0m0.006smetulburr@ubuntu ~ \$ time python3 wrapper.pyreal   0m0.049suser   0m0.022ssys   0m0.006s`
we will be moving to python-forum.io on October 1 2016
more details here

metulburr

Posts: 2244
Joined: Thu Feb 07, 2013 4:47 pm
Location: Elmira, NY

### Re: Very symple code with bad performance

Here is a slightly faster version of your program. The running time dropped from 2.3s to 1.6s on my computer.

Code: Select all
`import mathdef IsPrime(x):    if x == 1:        return False    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29):        if x == p:            return True        if not x % p:            return False            top = int(math.ceil(math.sqrt(x)))    for d in (1, 7, 11, 13, 17, 19, 23, 29):        for i in xrange(30 + d, top+1, 30):            if not x % i:                return False    return Trueprint IsPrime(9007199254740881)`

If your goal is to run the algorithm in both languages, I can think of any obvious improvements. If you just want to check if a number is prime, there are faster ways.

casevh
casevh

Posts: 114
Joined: Sat Feb 09, 2013 7:35 am

### Re: Very symple code with bad performance

2 seconds?

I'm running the code in a AMD A8 Processor, 6GB of Memory with Windows 8, and it takes 12 seconds... May be Windows 8 the problem?
ja0335

Posts: 2
Joined: Sun Jun 15, 2014 11:32 pm

### Re: Very symple code with bad performance

I rebooted into Windows 8.1 and timed the code I posted previously. The execution time varied significantly depending on the version of Python and whether or not a 32-bit or 64-bit version of Python was used. The slowest time was reported by 32-bit Python 2.6 at ~10 seconds. The best time was reported by 64-bit Python 3.3 at ~4.5 seconds. The running time on Linux for 64-bit Python 2.7 was 1.6 seconds. The best time I could achieve using Python 3.x on Linux was ~2.8 seconds.

Why the differences?

The program spends much of its time calculating with small integers. Python 2.x has two integer types: "int" is optimized for small integers and "long' supports arbitrary precision integers. Since Python 2.x transparently converts between the two integer types, the differences rarely appear (usually just an "L" at the end of a long). Python 3.x only support arbitrary precision integers and operations are slower on the arbitrary precision integers. The threshold where "int" is promoted to "long" depends on the operating system and the version of Python used.

This particular benchmark accidentally highlights one of the differences between various versions (both operating system and Python releases) of the Python interpreter.

Historical note

In early versions of Python, "int" did not automatically overflow to "long". The OverflowError exception was all too common. IIRC, the automatic conversion to long was introduced in Python 2.2.

casevh
casevh

Posts: 114
Joined: Sat Feb 09, 2013 7:35 am