Dave (dga) wrote,

Kill the stupid prime computation benchmark

A recent rubyinside post pointed out how cool ruby inline was because it could give a 10x speedup. The sad thing is that this example is a terrible one, and illustrates a different point far better.

The question: How fast can one print information about the first 10,000 primes in various programming languages. In fairness, the author of the RubyInline version noted that he was forbidden to change the algorithm, but dear god, why use the stupidest thing possbile as your example? Think of the children!

Original algorithm: for every number, see if it's divisible by every number smaller than it.
Original runtime: 2.9 seconds (his machine; 3.45 mine).
So he rewrote it in C as an inline function in Ruby. The code is 3x longer and relies on a complicated external library and gcc, etc., in order to compile.
Inline C runtime: 0.3 seconds.

But: GUGH. Compute the primes in pure ruby using the Sieve of Erastothenes (you know, the one we teach students their first day?):

def prime_sieve 
    p = Array.new(N + 1) { 1 } 
    (2..N).each { |n| 
        if (p[n] == 1) 
            nx = n + n 
            while (nx <= N) 
                p[nx] = n if p[nx] == 1 
                nx += n 
            end 
        end 
    } 
    (2..N).each { |n| 
        if p[n] == 1 
            puts "#{n} is a prime number" 
        else 
            puts "#{n} equals #{p[n]} * #{n/p[n]}" 
        end 
    }
end

Pure ruby, sieve runtime: 0.1 seconds.
So, it's 3x faster than a stupid C version, shorter, has no external dependencies... please, oh script hackers of the world, please abandon the "stupid prime computation" benchmark. Okay, end rant.

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 4 comments