7 ms·
Concurrent Sieve of Eratosthenes in Go
- ahh 14y agoThis 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 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.
- EricBurnett 14y agoI'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-seive-of-eratosthenes.html http://www.thelowlyprogrammer.com/2010/03/writing-efficient-... [2] http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segmented-sieve.html http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segm...
- tantalor 14y agoAn excellent long-form article about this type of algorithm in Go: http://scienceblogs.com/goodmath/2009/11/13/the-go-i-forgot-concurrency-an/ http://scienceblogs.com/goodmath/2009/11/13/the-go-i-forgot-...
- sentiental 14y agoVery 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 14y agoDid 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 http://golang.org/src/pkg/runtime/proc.c
- feniv 14y agoDoes 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/ http://create.stephan-brumme.com/eratosthenes/)
- Scaevolus 14y agoPretty 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-nuts/zRvkdfpeOY8 https://groups.google.com/forum/m/?fromgroups#!topic/golang-...
- StavrosK 14y agoDoes 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.
- icebraining 14y agoWell, there's lies, damn lies and benchmarks, but the Shootout has Go: http://shootout.alioth.debian.org/u64q/compare.php?lang=go http://shootout.alioth.debian.org/u64q/compare.php?lang=go (only the standard compiler, though. No gccgo)
- StavrosK 14y agoThat's very useful, thank you. I wish it had PyPy, though...
- igouy 14y ago"If you're interested in something not shown then please take the program source code and the measurement scripts and publish your own measurements." http://shootout.alioth.debian.org/more.php#languagex http://shootout.alioth.debian.org/more.php#languagex
- tmhedberg 14y agoJust for fun, I translated it to Haskell: https://gist.github.com/4105055 https://gist.github.com/4105055
- EricBurnett 14y agoAs 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-segmented-sieve.html http://www.thelowlyprogrammer.com/2012/08/primes-part-2-segm...