You are viewing dga

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.

Comments

(Anonymous)

I think you missed the point.

Of course trial division is much slower than any reasonable algorithm. The fact that they were computing primes wasn't the point; the point was to do some simple looping numeric code. I imagine the primes thing was chosen because it is obvious and an example that yields a result that people understand.. Perhaps they should use a different example, but it'd be hard to find a simple algorithm that couldn't be done more efficiently with more complex code. If you have an example of a simple-and-obvious calculation that has clear meaning and shouldn't be done a different way, I'd be in favour of using that instead.

(I feel like noting that the primes thing has the same problem as most examples.. any example small enough to be quite clear tends to be oversimplified in such a way that it could be done differently. It is the rare feature/language/library that can have its usefulness made apparent in a bite-sized chunk of code.)

Re: I think you missed the point.

I didn't miss the point at all: I understand that he was looking for a simple example, and stated so, but this one is particularly egregious. The speedup is enormous and the code to do it is still simple. I'd be much more a fan of

  • Time to insert and find 10,000 elements in a hash
  • Time to increment a variable 100,000,000 times
  • Time to traverse a linked list many times
  • Compute the ip checksum over a chunk of data (many times)

The problem with using examples like finding primes the wrong way is that there's an implicit message that rewriting your code in C is actually the right way to do it instead of going the simpler route. At least the real microbenchmarks represent situations that you might actually need to implement or represent speedups that you might take away and put in another context.

(Anonymous)

Nice

Nice example.

Am I being pedantic by pointing out that 1 isn't a prime number?

Re: Nice

Thanks. Updated. :)

August 2012

S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 

Links

Powered by LiveJournal.com