Concurrent prime factorization in Go

For a little while now I've been looking for a problem that would allow me to sink my teeth into Google's Go language and see if it's as tasty as it appears to be. After coming across Alex Tkachman's request for concurrency benchmarks it was clear that I had what I needed. Alex is the driving force behind Groovy++ and his proposal was to implement a common benchmark (a concurrent version of prime factorization using the Sieve of Eratosthenes) in multiple JVM languages in order to compare and contrast what works and what doesn't. An implementation in Go wouldn't help much in benchmarking JVM languages but the highly concurrent nature of the problem does map naturally onto Go's feature set. The language distribution also includes an elegant implementation of the Sieve of Eratosthenes in it's tests so we already have a solid foundation to build from.

Let's begin with sieve.go. The implementation consists of chained goroutines. Each time a candidate makes it through the sieve and is returned as a new prime number a new goroutine is created to check future candidates and reject them if they divide evenly by the new prime. The implementation cleanly demonstrates the concept but isn't useful as a standalone application since it includes no termination condition. Let's begin by adding that in:

[varese factorization_benchmark]$ cd go
[varese go]$ ls
factor.go  sieve.go
[varese go]$ gobuild sieve.go
Parsing go file(s)...
Compiling main (sieve)...
Linking sieve...
[varese go]$ ./sieve -max 20
2
3
5
7
11
13
17
19

That seemed to work nicely. Adding in the factorization code should give us everything we need:

import "fmt"
import "flag"
import vector "container/vector"
...
var target *int = flag.Int("target",1,"Number we wish to factor")
flag.Parse()

t := *target
var rv vector.IntVector

// Retrieve a prime value and see if we can divide the target
// evenly by that prime.  If so perform the multiplication 
// and update the current value.
ch := make(chan int) // Create a new channel.
go Generate(t,ch)      // Start Generate() as a subprocess.
for prime := <-ch; (prime != -1) && (t > 1); prime = <-ch {

 for ;t % prime == 0; {
  t = t / prime
  rv.Push(prime)
 }

 // Create a goroutine for each prime number whether we use it or
 // not.  This performs the daisy chaining setup that was being
 // done by the Sieve() function in sieve.go.
 ch1 := make(chan int)
 go Filter(ch, ch1, prime)
 ch = ch1
}

fmt.Printf("Results: %s\n",fmt.Sprint(rv))

Simple enough. This leaves us with something that looks fairly robust:

[varese go]$ gobuild factor.go 
Parsing go file(s)...
Compiling main (factor)...
Linking factor...
[varese go]$ ./factor -target 60
Results: [2 2 3 5]

Examples here employ gobuild. This tool has proven to be very useful when building and testing Go applications. Complete code for both examples can be found on github. There is some interest in comparing a solution based on goroutines and channels to one based on actors and messages so in the future some Scala code might join the existing Go code.