Is there something wrong with this python code, why does it run so slow compared to ruby?

Question

I was interested in comparing ruby speed vs python so I took the simplest recursive calculation, namely print the fibonacci sequance.

This is the python code

#!/usr/bin/python2.7                       
def fib(n):
    if n == 0: 
        return 0
    elif n == 1:
        return 1 
    else:
        return fib(n-1)+fib(n-2)

i = 0
while i < 35:
    print fib(i)
    i = i + 1

and here is the ruby code

#!/usr/bin/ruby

def fib(n)
    if n == 0
        return 0
    elsif n == 1
        return 1
    else
        fib(n-1)+fib(n-2)
    end
end 

i = 0 
while (i < 35)
    puts fib(i)
    i = i + 1 
end

over several runs, time reports this average real 0m4.782s user 0m4.763s sys 0m0.010s thats for ruby, now python2.7 gives

real 0m11.605s user 0m11.563s sys 0m0.013s

Whats the deal?

Answer 1

So for this code, Python is a bit more than two times slower than Ruby. Probably for other codes, Python will be faster than Ruby.

Your implementation of fib() has exponential run time. This can easily be avoided by using a loop. Python example:

a, b = 1, 1
for i in range(35):
    a, b = b, a+b
print b

Answer 2

Your method of calculating the first 35 numbers in the fibonacci sequence is immensely inefficient. You run a function fib() 35 times, and each time fib() has exponential run time. The generator in Python is the perfect solution to this problem and is far more efficient than what you wrote in Ruby.

def fibo_generator(n):
    # gets Fibonacci numbers up to nth number using a generator
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

You can then print all fibonacci numbers up to 35 using this code:

for f in fibo_generator(35):
    print f

This is by far the most efficient way to implement the fibonacci sequence in Python as well as the most versatile.

Answer 3

I was interested in comparing ruby speed vs python

Microbenchmarks are a really bad way to compare languages, especially before you mastered both. If you want a benchmark that has any real world meaning then you need to put a lot of effort into it - or you google for "language shootout"

Here is a better comparison of Python and Ruby

Answer 4

The recursion efficiency of python is the cause of this overhead. See this article for much more detail. The above solutions that solve this iteratively are better for python since they do not incur the function call overhead recursion does. My assumption about ruby would be that it is clearly optimizing the code while python is not. Again, that article goes into a lot detail about this using a nearly identical fib function.

Answer 5

Here's some more numbers to compare:

Python2.7
9.67 user 0.09 system 0:09.78 elapsed 99%CPU (0avgtext+0avgdata 16560maxresident)k
0inputs+0outputs (0major+1169minor)pagefaults 0swaps

ruby 1.8.7 (2010-06-23 patchlevel 299) [x86_64-linux]
28.37 user 0.35 system 0:28.78 elapsed 99% CPU (0avgtext+0avgdata 9200maxresident)k
1896inputs+0outputs (9major+656minor)pagefaults 0swaps

ruby 1.9.2p0 (2010-08-18 revision 29036) [x86_64-linux]
6.21 user 0.08 system 0:06.36 elapsed 98% CPU (0avgtext+0avgdata 14160maxresident)k
4416inputs+0outputs (16major+953minor)pagefaults 0swaps

Python is three times faster than ruby1.8 and 30% slower than ruby1.9.1 for the code provided.

Other Python versions for comparison:

2.4.6 took 10.30 seconds

2.5.5 took 9.93 seconds

2.6.6 took 9.22 seconds

2.7   took 9.35 seconds

3.0.1 took 11.67 seconds

3.1.2 took 11.35 seconds

3.2a3+ (py3k:85895, Oct 29 2010, 01:41:57) 
[GCC 4.4.5] took 13.09 seconds

2.5.2 (77963, Oct 15 2010, 02:00:43)
[PyPy 1.3.0] took 21.26 seconds

2.5.1 (Release_2_5_1:6813, Sep 26 2009, 13:47:54) 
[OpenJDK 64-Bit Server VM (Sun Microsystems Inc.)] took 8.81 seconds