Concurrent Sieve of Eratosthenes in Go

http://play.golang.org/p/9U22NfrXeq

by paulrosenzweig • 14 years ago

68 16 14 years ago

play.golang.org

ahh• 14 years ago

This isn't actually the Sieve of Eratosthenes. My undergrad advisor published a short piece about a family of functional prime generators of this form, that don't have nearly the efficiency of the true Sieve: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

The gist of the problem is this: in the true sieve, each number is touched once for each of its prime factors. In this sieve, each number is touched once by each prime smaller than it (until a factor is found.)

There are a lot more primes that aren't factors of a given number than primes that are.

EricBurnett2• 14 years ago

I've used that paper as the impetuous for writing a few sieve algorithms (see [1] and [2]). While reasonably elegant in Haskell, my personal experience is that list-of-generator style programs cannot compare to array-based sieves for performance, due to the overhead of switching between generators all the time. Not to denigrate the main point, of course - asymptotic runtimes are far more important than implementation overheads for calculating primes.

[1] http://www.thelowlyprogrammer.com/2010/03/writing-efficient-... [2] http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segm...

tantalor• 14 years ago

An excellent long-form article about this type of algorithm in Go: http://scienceblogs.com/goodmath/2009/11/13/the-go-i-forgot-...

sentiental• 14 years ago

Very cool. I ran this, adding a print statement into the Filter function so I could inspect `i` as the channels received inputs. I expected the prints to come relatively in random order but on repeated tries they didn't - and then realized I know nothing about programming with coroutines and explicit communication between threads. Thanks for the thought exercise!

davvid• 14 years ago

Did you set the GOMAXPROCS environment variable?

  // By default, Go keeps only one kernel thread (m) running user code
  // at a single time; other threads may be blocked in the operating system.
  // Setting the environment variable $GOMAXPROCS or calling
  // runtime.GOMAXPROCS() will change the number of user threads
  // allowed to execute simultaneously.  $GOMAXPROCS is thus an
  // approximation of the maximum number of cores to use.

From http://golang.org/src/pkg/runtime/proc.c

feniv• 14 years ago

Does anyone have any benchmarks on how fast this will run?

For comparison C++ based implementations range from 13.5 seconds to 0.65 seconds when iterating over 1,000,000,000 elements on an Intel Core i7 860, quad-core, hyperthreading, 2.8Ghz cpu. (http://create.stephan-brumme.com/eratosthenes/)

Scaevolus• 14 years ago

Pretty slow. This is intended to demonstrate how Go concurrency works, so there's a lot of communication overhead.

Someone ported djb's primegen (uses the Sieve of Atkin) to Go, and got comparable performance-- .7s for primes up to a trillion. https://groups.google.com/forum/m/?fromgroups#!topic/golang-...

StavrosK2• 14 years ago

Does anyone know which ballpark Go is in, performance-wise? In my mind, it's a bit faster than Python, whereas I would expect it to be closer to C. However, I have no clue how I formed this opinion, so actual benchmarks would help.

I wonder how it compares to pypy.

tmhedberg2• 14 years ago

Just for fun, I translated it to Haskell: https://gist.github.com/4105055

tinco• 14 years ago

Hi, I added documentation to your code so people new to Haskell might understand what is going on:

https://gist.github.com/4105864

Even with extensive documentation it is only 3 lines longer than the Go version ;)

tmhedberg2• 14 years ago

Looks good, thanks. :)

EricBurnett2• 14 years ago

As ahh points out in their comment, this isn't a true sieve - it's essentially trial division, although sharded between goroutines.

For comparison, I've used Go to implement a segmented version of the true Sieve of Eratosthenes. It's a standard array-based sieve, chunked up. It takes advantage of goroutines for parallelism, and implements an efficient algorithm at the same time. The code is a lot longer than this one because it tries to do a lot more (memory efficiency, large number support, etc), but it should give you an idea what a full implementation might look like. http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segm...

Concurrent Sieve of Eratosthenes in Go

Related Stories