1

I was solving a problem that asked me to find the sum of all EVEN fibonacci numbers under 4,000,000 and I noticed that the below CoffeeScript executed faster than the below Ruby.

CoffeeScript

sum = 0

f = (n) ->
  if n == 0 then return 0
  else if n == 1 then return 1
  else return f(n-1) + f(n-2)

console.log "Starting..."

for i in [1..4000000]
  ff = f(i)
  break if ff >= 4000000
  sum += ff if ff % 2 == 0
  console.log ".." + ff

console.log "Sum:" + sum

Ruby

sum = 0

def F(n)
  if n.eql? 0
    return 0
  elsif n.eql? 1
    return 1
  else
    return F(n-1) + F(n-2)
  end
end

puts "Starting..."

4000000.times do |num|
  the_num = F(num)
  break if the_num >= 4000000
  sum += the_num if the_num % 2 == 0
  puts ".." + the_num.to_s
end

puts "Sum:" + sum.to_s

It took nearly 6-8 seconds for the Ruby script to find all even fibonacci numbers under 4,000,000 while it took roughly 0.2 seconds to complete for the NodeJS execution of the transpilation of coffeescript. Why is this??

$ ruby --version
  ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-darwin12.0]
$ node --version
  v0.10.25
ddavison
  • 28,221
  • 15
  • 85
  • 110
  • 3
    you `ruby` script start from `0` to `4000000`, in coffee from `1` to `4000000` )) – Roman Kiselenko Feb 20 '14 at 12:45
  • since `0+x=x` it really doesn't matter - i noticed that too though `:)` – ddavison Feb 20 '14 at 12:46
  • this is unfair play... `:)` – Roman Kiselenko Feb 20 '14 at 12:49
  • I suspect it is because it is not very idiomatic Ruby. This question was asked before here: http://stackoverflow.com/questions/6418524/fibonacci-one-liner; I suspect most of those answers will be far more efficient. – Mark Thomas Feb 20 '14 at 13:03
  • http://stackoverflow.com/questions/5168718/what-blocks-ruby-python-to-get-javascript-v8-speed – vkurchatkin Feb 20 '14 at 13:12
  • thanks guys for posting your comments. @MarkThomas per your comment, i have implemented that same ruby one liner and heeds the same results. vkurchatkin, thanks for that read! though it doesn't particularly answer my question, it was very interesting – ddavison Feb 20 '14 at 13:17
  • What do you mean with "why"? Do you want to spot the slower lines? Do you want a faster implementation? – mdesantis Feb 20 '14 at 13:20
  • also @MarkThomas, this question is not a duplicate of that question as that is specific to trying to _optimize_ the code. I am not trying to optimize. I am genuinely curious why the execution of the coffeescript is faster than the ruby script. As far as idiomatic Ruby, that's a very subjective statement as this is idiomatic to me. – ddavison Feb 20 '14 at 13:20
  • @mdesantis Once the ruby script gets into the millions, it starts to slow down. Once it reaches 3 million, it takes about 10 seconds just to calculate the next number. No, I don't want a faster implementation (which is why this is not aduplicate of Mark Thomas' question.) I just want to know why it takes longer than the nodejs implementation – ddavison Feb 20 '14 at 13:21
  • (I've updated the times.. I severely overexaggerated. i did this problem last night and wrote the question today [for visibility] and didn't actually time it before) – ddavison Feb 20 '14 at 13:33
  • 2
    Also, changing `.eql?` to `==` speeds up the thing from 6s to 2s – mdesantis Feb 20 '14 at 13:46
  • The answer is probably due to [JIT](http://en.wikipedia.org/wiki/Just-in-time_compilation) which is done by the Javascript V8 engine used by Node, but which is not done by the default C-Ruby. This are probably different when using [JRuby](http://jruby.org/) or [Rubinius](http://rubini.us/), both of which use JIT compilers to speed things up. And your fib code is a prime example of a very well jit-able function (even more so when the compiler support tail-recursion, but I don't know if any of them support it). – Holger Just Feb 20 '14 at 13:50
  • @HolgerJust thanks for this.. so this is definitely a per-language limitation. I'll keep this in mind for sure! – ddavison Feb 20 '14 at 14:19
  • More than per-language is a per-language-implementation limit – mdesantis Feb 20 '14 at 14:38
  • 1
    Less than a per-language than only a per-VM (aka. implementation) issue. Javascript VMs don't always have a JIT in the same way as Ruby or Python VMs sometimes have them, depending on the implementation. – Holger Just Feb 20 '14 at 16:12

1 Answers1

4

Let's profile it using ruby-prof:

# so_21908065.rb

sum = 0

def F(n)
  # using == instead of eql? speeds up from ~ 7s to ~ 2s
  if n == 0
    return 0
  elsif n == 1
    return 1
  else
    return F(n-1) + F(n-2)
  end
end

puts "Starting..."

1.upto(4000000) do |num|
  the_num = F(num)
  break if the_num >= 4000000
  sum += the_num if the_num % 2 == 0
  puts ".." + the_num.to_s
end

puts "Sum:" + sum.to_s

$ ruby-prof so_21908065.rb
 %self      total      self      wait     child     calls  name
 16.61     27.102    27.102     0.000     0.000 87403761   Fixnum#== 
  9.57     15.615    15.615     0.000     0.000 48315562   Fixnum#- 
  4.92      8.031     8.031     0.000     0.000 24157792   Fixnum#+ 
  0.00      0.000     0.000     0.000     0.000       70   IO#write 
  0.00    163.123     0.000     0.000   163.123        1   Integer#upto 
  0.00    163.122     0.000     0.000   163.122 48315596  *Object#F 
  0.00      0.000     0.000     0.000     0.000       35   IO#puts 
  0.00      0.000     0.000     0.000     0.000       34   Fixnum#to_s 
  0.00      0.001     0.000     0.000     0.000       35   Kernel#puts 
  0.00      0.000     0.000     0.000     0.000       34   String#+ 
  0.00    163.123     0.000     0.000   163.123        2   Global#[No method] 
  0.00      0.000     0.000     0.000     0.000       34   Fixnum#>= 
  0.00      0.000     0.000     0.000     0.000        2   IO#set_encoding 
  0.00      0.000     0.000     0.000     0.000       33   Fixnum#% 
  0.00      0.000     0.000     0.000     0.000        1   Module#method_added 

* indicates recursively called methods

So the main culprits are Fixnum#==, Fixnum#- and Fixnum#+.

As @HolgerJust noted, probably a "warmed" JRuby execution is much faster, due to JIT optimization.

Community
  • 1
  • 1
mdesantis
  • 8,257
  • 4
  • 31
  • 63
  • so this is definitely not just me.. excellent. Thanks for your help mdesantis – ddavison Feb 20 '14 at 14:17
  • 1
    I marked this is as the accepted answer because it answers my question "why this node program is faster than the ruby script." It is faster because of the 3 culprits mentioned above, `==, -, +`. As well as @HolgerJust's comment regarding the Just-in-time compilation. This compilation is faster for operations like this. – ddavison Feb 20 '14 at 14:23