Some Ruby Performance Tests

**Warning - This post is for CS and/or Math nerds only.  All other readers will find it very boring**

For a while now I've been hooked on Project Euler.  It's a great way to exercise the brain muscles, and has really helped me get some practice reps in with Ruby, my newly adopted programming language of choice.

A lot of the projects require that you be able to generate prime numbers very quickly.  After several iterations of my algorithm, I had something that was pretty respectable, but my friend who was working through the same problem in Python was getting much better performance than I was, so I started digging deeper.

The first discovery I made was that a lot of the things that make Ruby pretty hurt the performance.  My first version of the algorithm generates all the primes less than 10^6 in about 14 seconds. (Keep in mind all these timings are done on a basic Macbook laptop, so the relative timings are what is most interesting)

def generate_primes(max_prime)
  @prime_hash = Hash.new { |h,k| h[k] = true }
  @primes = [ 2 ]
   3.step(max_prime, 2) do |next_prime|
    if(@prime_hash[next_prime])
      @primes << next_prime
      if(next_prime < Math.sqrt(max_prime))
        next_prime.step(max_prime/next_prime, 2) { |i|
                  @prime_hash[i * next_prime] = false }
      end
    end
  end
end

 
$ time ruby gen.rb
Generating all primes less than 1000000
78498 primes found

real 0m14.505s
user 0m10.912s
sys 0m3.205s

Interestingly, I was able to get a nearly 4x speedup factor by pulling apart all my pretty syntax and going back to some good old fasioned while loops.  As far as I can tell, this didn't really change the algorithm at all, just the way it's coded up.  Some other simple tests seem to indicated that all the Ruby iterators are noticeably slower than hand-built while loops.

def generate_primes(max_prime)

  @prime_hash = Hash.new { |h,k| h[k] = true }

  @primes = [ 2 ]

  

  next_prime = 3

  while (next_prime < Math.sqrt(max_prime))

    i = next_prime

    while (i <= (max_prime / next_prime))

      @prime_hash[i * next_prime] = false

      i += 2

    end

   @primes << next_prime

    next_prime += 2

    while (!@prime_hash[next_prime])

      next_prime += 2

    end

  end

  while (next_prime <= max_prime)

    if @prime_hash[next_prime]

      @primes << next_prime

    end

    next_prime += 2

  end

end

$ time ruby gen2.rb
Generating all primes less than 1000000
78498 primes found

real 0m3.470s
user 0m3.095s
sys 0m0.294s

My next experiment was to try an alternative Ruby VM that I had read about, Rubinius.  The docs I saw indicated that they had made some performance improvements, so I thought I'd try it out.  This did not meet with success.  Rubinius, for this particular app, was much slower.

$ time rbx gen2.rb
Generating all primes less than 1000000
78498 primes found

real    0m12.608s
user    0m11.863s
sys    0m0.310s

At this point, I believe I griped about Rubinius on Twitter, and actually got some great feedback from Evan Phoenix, the key maintainer of Rubinius.  I wrote a really simple function to test recursion and looping, and sure enough, Rubinius blew away MRI.  I'm guessing that the slowdown in my prime generator might be related to Array and Hash operations, but I need to isolate that further.

def recurse(num)
  return 0 if (num == 0)
  1.upto(10) { |i| recurse(num - 1)}
end

recurse(6)

$time ruby recurse.rb

real    0m14.937s
user    0m9.847s
sys    0m4.805s

$ time rbx recurse.rb

real    0m1.745s
user    0m1.632s
sys    0m0.061s

So there it is.  I don't claim to be a performance expert, but enough people expressed interest in what I had found that I thought I would make my life easier and post it up here.  I have some theories that the MRI vs Rubinius differences might be related to the ability to store large hashes in memory, but that's not tested yet.  I would love feedback on what I could be doing better, what might explain some of these results, etc.  I'd also be happy to run more tests if people have unanswered questions.

All of these code samples are available on GitHub.

Comments

[Ruby on Rails]

Ruby is fastest way to develop app. It is depend on our experience to face problem algorithm

[coach factory outlet]

We like to think of ourselves as one big happy family.*

[air max 90]

I love you post!

[Taobao buy]

*Forget about stupidity, discover your ability.

[ClubPenguin]

I have some theories that the MRI vs Rubinius differences might be related to the ability to store large hashes in memory, but that's not tested yet.

[oakley sunglasses]

^*^189We have to cut through yards, over fences, on roofs, through gravel roads, scramble in woods and cross creeks for emancipation and settlement, just like a fugitive traffics along an escape route to find safety and freedom.

[Christian louboutin]

Red shoes of recognition is high, it is another advantage of the female stars free advertising. See red soles is Christian Louboutin. Today is my birthday, and one birthday present is Christian louboutin shoes. Actually I prefer tenis nike. Usually I like running, often wearing nike shox

[Coach Factory Online]

Today the quality of our natural environment has become an important issue. The world population is rising so quickly that the world has become too crowded.

[oakley sunglass]

Can not need arrogant, keeps an connotation; The point does not need to reveal, keeps a depth to collect; Active does not need to invite, keeps to modestly decline

[iPhone Application Development]

Now,Ruby is fastest way to develop application. It is depend on our skill and experience to face problem algorithm

[Christian Louboutin Outlet]

I used your instructions for making a reversible jumper and they were great.I agree with your opinions on men and how they more clean cut.
People usually talk about gender when they discuss the metero male, but I like how you link it with a historical context to class and divisions between men.

[Evering2010]

Thak you for sharing them with us , I think it's worth reading

[did]

test