**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.
