An efficient sieve of Eratosthenes using CSP

[Anh Hai Trinh]

Hello,

I've written a much more efficient prime sieve that uses CSP than the
one from the tutorial. It implements a faithful sieve of Eratosthenes
and is algorithmically similar to the one described here:
<http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf>.

The code is available here: <http://github.com/aht/gosieve>.

Some timing results:

// Comparing with the program from the tutorial

$ time ./sieve1 100000 | wc -l
9592

real 1m33.599s
user 1m31.124s
sys 0m0.547s

$ time ./sieve2 100000 | wc -l
9592

real 0m0.440s
user 0m0.273s
sys 0m0.160s

The program from the tutorial tests divisibility by all primes <= n
for every n. No surprise that it is completely smoked.


// Comparing with the 2-thread version and the Haskell version from the paper

$ time ./sieve2 -n 1000000
15485863

real 0m21.655s
user 0m21.249s
sys 0m0.197s

$ time GOMAXPROCS=2 ./sieve2 -n 1000000
15485863

real 0m39.086s
user 0m25.608s
sys 0m18.492s

$ time ./ONeillPrimesTest 1000000
(1000000,15485863)

real 0m5.553s
user 0m5.526s
sys 0m0.007s

I thought the algorithm was parallelizable but perhaps there is too
much overhead context-switching. Using CSP itself seems elegant but
also carries much overhead compared to Haskell cons'ed list.

One thing that I thought makes the implementation a bit less elegant
is the lack of a non-blocking write channel. The program has to size
the channel buffer appropriately to prevent deadlock. It would be nice
to have a channel that you can always send successfully. Doesn't
GoogleFS have atomic record appends?

Comments? Thoughts?

----aht