Why tail recursive gcd is faster than looping with rubinius

Question

I have two implementations of the gcd function:

def gcd1(a,b) if a==b a elsif a>b if (a%b)==0 b else gcd1(a%b,b) end else if (b%a)==0 a else gcd1(a,b%a) end end end def gcd2(a,b) if(a==b) return a elsif b>a min,max=a,b else min,max=b,a end while (max%min)!=0 min,max=max%min,min end min end 

The gcd1 function is tail recursive, and gcd2 uses a while loop.

I checked that rubinius does TCO by comparing the factorial function, only with the factorial function the tests showed that the recursive version and the iteration version are “the same” (I used benchmark-ips).

But for the above, tests show that gcd1 is at least twice as fast as gcd2 (recursion is twice as fast as iteration, even faster).

The code I used for comparison:

 Benchmark.ips do |x| x.report "gcd1 tail recursive" do gcd1(12016,18016) end x.report "gcd2 while loop" do gcd2(12016,18016) end x.compare! end 

result:

 Warming up -------------------------------------- gcd1 tail recursive 47.720ki/100ms gcd2 while loop 23.118ki/100ms Calculating ------------------------------------- gcd1 tail recursive 874.210k (± 7.1%) i/s - 4.343M gcd2 while loop 299.676k (± 6.6%) i/s - 1.503M Comparison: gcd1 tail recursive: 874209.8 i/s gcd2 while loop: 299676.2 i/s - 2.92x slower 

I am running Arch linux x64, processor i5-5200 2.2 GHZ quad-core.

Ruby implementation - Rubinius 3.40.

So how can recursion be faster than a loop?

Update

Just to say that the fibonacci has the same situation: the tail recursive version is at least twice as fast as the loop version, the program I used for fibonacci: http://pastebin.com/C8ZFB0FR

Answer 1

In the example you are using, it only takes 3 calls / loops to answer it, so I don't think you are actually checking the right things. Try instead of two consecutive Fibonacci numbers (for example, the 2000s and 2001s), and the results should not differ much.

(Sorry, I have no reputation to make a comment yet).

EDIT: I finally managed to install [part] rubinius and managed to recreate the phenomena you are talking about. This is not about recursion, but about multiple assignment. If you change

  while n>0 a,b=b,a+b n-=1 end 

to

  while n>0 t=a a=b b=t+b n-=1 end 

the while loop version should execute (bit) faster. The same applies to the original GCD program, i.e. Replacing

  min,max=max%min,min 

from

  t=min min=max%t max=t 

- thing.

This does not apply to ruby-2.1, i.e. the while loop seemed faster, just in the form you provided.

Hope this helps!