Python recursion performance test
That’s really shocking, I even tried several ways to optimize performance without touching the code and still performance sucks!
Fibonacci simple recursion solution takes 3 seconds to execute with C code and about 2 minutes in python!
Here is the code I used for the python version
def fib(x):
if x == 0 or x == 1: return x
return fib(x-1) + fib(x-2)
if you called fib(40) it will take about 2 minutes! the C code is exactly the same and it’s compiled with normal optmizations (-O0)
I compiled the python to pyc and used the pyc and still around 2 minutes (slightly less)
the impressive thing is that the dynamic programming solution works perfectly in no time, try this
def fib(x):
t = [0, 1]
for i in xrange(x):
t.append(t[-1] + t[-2])
return t[-2]
call it for fib(40) and see the performance gain.
the bottomline is that you shouldn’t use recursion in python.
If you have any suggestions to make this goes faster (I thought about trying stackless python here) I’m really happy to discuss them.
dammit, 2mins !!!!!!!
can you till me the regular iterative way took how mush ?
I think it’s supposed to take as much as C, since the trade-off C is recursive but native
the real reason behind why python is really slow there is the cost of function calls, in C function calls are simple JMP but in python there is the scope namespace search and stack handling and it’s really cost. so the trick is that if you want faster execution times in situations where you want thousand of direct function calls, use loops instead.
This is also a lesson to avoid using unnecessary getters and setters for your instance members, use simple instance variable instead.
I’ll give stackless python a trial and see how it’s different, but note that the implementation of the fibonacci is not efficient at all and the iterative way in C was 2 times faster which is acceptable and expected.
hey Ahmed, how are you? I got sometime to write function in python because I didn’t try it before. But my point here is Recursion is too slow in all programming language. So you should use Tail Recursion instead
def fib(x):
if x > 0:
fib_help(x, 0, 1);
else:
print(“Please Enter value more than zero”);
def fib_help(x, result, next):
if x == 0:
print(result);
else:
fib_help(x-1, next, result + next);
This function will work fine, and the performance will be good, and like I said to you before about Erlang programming Language that in the latest release Recursion and Tail recursion has the same performance, but I didn’t try it yet, but I will when I will have time.
I’m beginner in Python, so excuse my Code :$
Yes abdul fattah, tail recursion is one way to ‘optimize’ but in fact this is not what I’m talking about, I’m not talking about how to write this particular function, I know many many ways of optimization there but that trick showed the cost of calling functions in python and illustrated it quite clearly.
I agree that in general,recursion is very slow in all programming languages due to the time it take in function call and the language that handle functions calls efficiently can perform recursions in high speed.
But in some situations recursion is similar to looping in run time plus the code of recursion is fewer and more readable.
There are some problems like binary search,tree searching and sorting ,tower of Hanoi,…etc we used to solve it recursively and i will be very complicated in traditional looping approach.
I see that dynamic programming is efficient here but in other situations generating a list of million number to catch one number doesn’t make any sense and consuming resources.
I simply want to say that we can’t neglect recursion approach as it may be the best solution.
Thanks Eng. Ahmed
Replied at http://eikke.com/re-python-recursion-performance-test/
[...] is a reply on a post by Ahmed Soliman on recursion performance in (C)Python, and CPython function call overhead in [...]
[...] solution, since as my colleague, Ahmed Soliman, rightly concluded that recursion in Python is slow. (An interesting argument can be found here as [...]
Python is slow.
There is no doubt that Python is a very powerful language but it is also a very slow language.
It is okay for PHP or ASP to be slow because PHP and ASP do not pretend to be advanced languages and both are very easy to learn and program. But Python is supposed to be a very powerful language – and so how can it be so slow? (and I am not comparing it with C or any other compiled language).
I may agree that PHP and ASP are pretty slow but Python is not slow, but it depends on your code more than compiled languages (talking java here) because the compiler there is capable of doing more advanced optimizations than interpreter.
It really worth reading so you can see how your code can make a difference http://wiki.python.org/moin/PythonSpeed/PerformanceTips
Thanks for you comment.
Iam not understanding what you are saying if i execut it iam not getting output it terminates the programm could you help me in recursions?
“the real reason behind why python is really slow there is the cost of function calls, in C function calls are simple JMP but in python there is the scope namespace search and stack handling and it’s really cost. so the trick is that if you want faster execution times in situations where you want thousand of direct function calls, use loops instead.”
thanks for the info: in my program it took C 8mins to execute, while for Python I simply had to terminate after an hour.