Prime Directive

Let's see how D and C++ stack up when it comes time to maintain and expand our code.

I created a bash script to run the programs a lot (so we can check performance).

#!/usr/bin/bash
for i in {1..100}
do
./d_prime.exe > /dev/null
done

This isn't the greatest (generating more primes would be good too), but it should suffice...

On my Pentium 4, 2.4 GHz, D gives:
real 0m12.865s
user 0m3.888s
sys 0m10.450s

While C++ gives:
real 0m13.325s
user 0m4.128s
sys 0m10.667s

I won't be comparing the speeds directly, as much of that is a compiler issue (and I would need to evaluate turning on optimizations, which is a big headache). I am most interested in algorithmic improvements, and how hard they are to code.

The obvious thing is that the code is O(n^2), or at least O(n*p) where p is the current number of primes. We don't need to check primes that are larger than sqrt(n). So, how can we encode this?

The D code is an easy change:
We add:

uint ct = 0;
uint sqr = 4;
if( i >= sqr )
{
ct++;
sqr = primes[ct] * primes[ct];
}

And change:

if( isPrime(i, primes[0..ct+1]) )

This makes use of D's "slice syntax". That is, we can create a subarray just by specifying the elements we desire. The slice is a reference, so there is no copying.

real 0m12.915s
user 0m3.923s
sys 0m10.507s

The new time isn't any better, probably because the time is dwarfed by system (/dev/null doesn't seem any faster under Cygwin). But we have introduced a new algorithm that is potentially twice as fast with little effort.

When I come to the C++ version, I realize I've made a terrible error... the isPrime function takes a reference to a vector. But I only want to pass in part of my current vector. Now I have to come up with a slice class which is derived from vector, or change my function to use iterators (Note: I did not plan this to make C++ look bad!).

Iterators are ugly, but not as ugly as trying to implement my own slice class!

The new prototype is:

bool isPrime(unsigned n, const std::vector<unsigned>::const_iterator b,
const std::vector<unsigned>::const_iterator e)

and the for loop becomes:

for(std::vector<unsigned>::const_iterator i = b; i != e; ++i)

while the call point is:

if( isPrime(i, primes.begin(), primes.begin()+ct+1) )

Again the time isn't any better:
real 0m13.561s
user 0m4.097s
sys 0m10.855s

Of course, iterator addition is pretty unusual. It might give someone pause. And make them think about how it is just as ugly as normal iterator usage!

Now imagine I've had to edit header files and caused a dependency chain reaction which forces everything to rebuild. Or worse, altered a public API, which drives a version change. Maybe implementing that slice class wouldn't be so bad...