5

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?

comepradz
  • 21
  • 8
rapadura
  • 5,242
  • 7
  • 39
  • 57
  • 2
    I just want to point out that calculating this iteratively will be much faster in a language independent sense. Using recursion here causes the same values to be calculated over and over. – Gavin H Oct 28 '10 at 19:32
  • 10
    I won't list an answer, because I don't *know* the exact cause, but its likely that the ruby compiler has some optimizations that the Python one does not. Naive fib functions using recursion create huge call stacks that some languages don't handle well. In particular, the language usually must implement tail-call recursion optimizations to handle such situations performantly and without stack overflows under greater amounts of recursion. – CodexArcanum Oct 28 '10 at 19:34
  • 1
    I agree with CodexArcanum. This might be germane: http://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization – duffymo Oct 28 '10 at 19:36
  • 1
    @ghills: Just for the record, it's perfectly possible to calculate fib in linear time using recursion (though it won't be any more readable than the iterative version and probably good deal slower without TCO, so...). – sepp2k Oct 28 '10 at 19:37
  • 9
    @Codex: There is nothing to tail-call optimize here. That definition is not tail recursive. – sepp2k Oct 28 '10 at 19:38
  • 1
    I think you'd need to go to the people who built the compilers to get a definitive answer for this. As CodexArcanum said some optimisation is done in Ruby but not in Python. – Matti Lyra Oct 28 '10 at 19:38
  • 1
    @sepp2k I wasn't sure since I don't actually know how to identify a tail-recursive call on sight. Thus why I wrote a comment and not an answer ;) Thank you for clarifying though. I also meant to use TCO as merely an example, since I think some compilers do other forms of recursion elimination also. – CodexArcanum Oct 28 '10 at 19:40
  • 1
    @sepp2k - agreed, but in it's most simple definition, as was posted in the question, it is exponential in time and does a lot of unnecessary recalculation, where a simple loop is pretty clear and efficient. – Gavin H Oct 28 '10 at 19:40
  • ah, if I could accept your discussion as an answer I would. – rapadura Oct 28 '10 at 20:10
  • 2
    Why loop at all? `fibo = lambda n: int((((1 + math.sqrt(5)) / 2)**n + (1/((1 + math.sqrt(5)) / 2))**n) / math.sqrt(5) + 0.5)` – Nick T Oct 28 '10 at 20:24
  • I would further say that less than an order of magnitude (10X speed difference) is not a bad gap at all for naive programs running on different interpreters, assuming similar levels of abstraction for the two languages being compared. – kindall Oct 28 '10 at 21:42
  • This unidiomatic function is pretty much useless for "comparing ruby speed vs python" for any program except this one. – Chuck Oct 28 '10 at 23:08
  • Chuck, what I learned from this poor speed test is that python does not perform well on recursive function calls as ruby and one should take care in designing the algorithms to avoid this, for example to use generators instead. I know I cant judge, and I wont judge python based on this test, but it was worth the learning. – rapadura Oct 29 '10 at 09:09
  • @AntonioP >> what I learned from this poor speed test... << From your "poor speed test" how do you know that any performance difference is specifically due to recursive function calls - rather than all function calls? How do you know the difference isn't due to the if statement? How do you know the difference isn't due to integer arithmetic? – igouy Oct 29 '10 at 16:54
  • @AntonioP >> what I learned from this poor speed test... << How do you know that the Python program isn't faster than the Ruby program for fib(17) and fib(28) and fib(36)? [You haven't reported which Ruby implementation was used or which OS was used.] – igouy Oct 29 '10 at 17:06
  • @igouy, I did it for fib(12), fib(16), fib(20), fib(30), fib(40), fib(50), the 50 i had to abort because it took too much time. The higher fib I choose, the effect is more visible in speed. I used ruby 1.9.2p0 (2010-08-18 revision 29036) [x86_64-linux] on archLinux and Python 2.7 (r27:82500, Oct 6 2010, 12:29:13) [GCC 4.5.1] on linux2 If you have any other explanation, I turn into an ear. – rapadura Oct 31 '10 at 18:52
  • @AntonioP Do you understand that your "explanation" is a guess? When you say "higher fib I choose, the effect is more visible in speed" you are saying is more function calls, more if statements, more arithmetic - what makes you guess the cause is /recursive/ function calls? Have you compared both language implementations on non-recursive function calls? – igouy Oct 31 '10 at 21:33
  • @igouy, I know it is a guess. I made another one with just a while loop and one if else check and assignement. Ruby wins still. Python: i = 0 a = 0 while i < 6553500: i += 1 if i != 6553500: a = i else: print "o" print a # for ruby, just add two end statements and remove :, ruby time is 0.74s and python time is 4.1s. – rapadura Nov 01 '10 at 10:19
  • @AntonioP So now write recursive versions that make the same number of function calls, and the same if statement, and the same arithmetic - and compare that to the iterative versions. (And compare at more than one data point.) – igouy Nov 01 '10 at 19:20
  • @NickT: you loose precision with floats e.g., [compare iterfib() that uses integers and binetfib() that uses fixed precision](https://github.com/zed/txfib) – jfs Oct 18 '12 at 17:54

5 Answers5

8

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.

dcolish
  • 22,727
  • 1
  • 24
  • 25
  • I like the comments on that article you linked too. This does shed some light on using recursive function calls in python. – rapadura Oct 29 '10 at 08:54
2

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
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • 1
    The question is not how to write efficient fib() implementation. The question is why creating huge call stacks is more costly in Python (if it is) than in Ruby. – jfs Oct 28 '10 at 23:04
  • My main point actually should have been that the observed difference is small -- it is only a factor of two, which is not surprising at all. Reading my post again, I think other people's comments are better, but I will just leave it there :) – Sven Marnach Oct 29 '10 at 13:43
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.

Rafe Kettler
  • 75,757
  • 21
  • 156
  • 151
  • 4
    I dont want the most effiecient for programming language x, I want to know why the almost exact python and ruby program runs in very different time frames. Is the ruby version optimizing the code behind my back? While we are at it I think memoization would speed it up immensly. – rapadura Oct 28 '10 at 20:05
  • See THC4k's answer for why this test doesn't mean anything. This doesn't mean that Python is slower than Ruby because your application doesn't make much sense. Why would you do something that's inefficient in any language? Python is fastest when you play to its strengths, as is Ruby. – Rafe Kettler Oct 28 '10 at 20:07
2

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

Jochen Ritzel
  • 104,512
  • 31
  • 200
  • 194
  • 1
    Why is this a bad way to compare languages? What is the reason for the speed of ruby compared to the almost the same code in python? I am aware one could use generators, memoization and such to give the sequence in better time... but what Im interested in - why this big difference for the same code? – rapadura Oct 28 '10 at 20:07
  • @AntonioP: Because only beginners write code like that. Your benchmark tells you only that "this bad Python programs is slower than that bad Ruby program". It only makes sense to compare the fastest implementations, not one with the same code. – Jochen Ritzel Oct 28 '10 at 20:22
  • 5
    I have to both agree and disgree at the same time. It is true that comparing bad programs isn't helpful. However, I disagree that you should compare the fastest implementations. I think you should compare the most well-designed implementations. It is the compiler writer's job to make sure that the most well-designed implementation is also the fastest, but if it *isn't*, then you shouldn't optimize the code, you should fix the compiler. – Jörg W Mittag Oct 28 '10 at 22:27
  • @Jörg W Mittag: Yeah I completely agree with you. – Jochen Ritzel Oct 29 '10 at 00:41
  • @Jörg W Mittag: Different people are likely to have different opinions about which are the "most well-designed implementations". – igouy Oct 29 '10 at 16:58
2

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
jfs
  • 399,953
  • 195
  • 994
  • 1,670