I’m excited about the Go programming language. I read the spec and Effective Go, I’ve been playing with the FreeBSD port, I signed up for the gonuts Google group, I attended the inaugural meeting of the Seattle Go Programmers, and I’ve even written an article on it for TechRepublic. I just need a T-shirt and a mascot plush toy to make my fandom complete.
Oh, and maybe write some real code.
Go’s built-in support for concurrency attracted me from the start. The syntax is simple. If you want to execute the “foo” function concurrently with the rest of your program, you just say:
go foo()
Go provides a special data type called “channels” to allow you to pass data back and forth between goroutines (their name for concurrently executing routines). Channels are typed, and with Go’s flexible yet precise type system you can therefore regulate the kind of data you can send and receive on each channel as much or as little as you like.
As I read about this in Effective Go, I began to imagine use cases for parallelism, and one that popped into my head is the mergesort. In a mergesort, you split the items to sort in half, sort each half, then merge the results. For each of the halves, you sort them the same way, splitting and merging until you get down to where each half is only one item. In a single-threaded model, you can’t do anything with the right half until after you’re done with the left half. Why not sort both halves at the same time?
So, we can change this (taking the “merge” function as given):
func SortInts(a []int) []int {
if (len(a) < 2) {
return a
}
var mid = ((len(a) - 1) / 2)
return merge(SortInts(a[:mid]), SortInts(a[mid+1:]))
}
To this:
func SortInts_parallel(a []int) []int {
if (len(a) < 2) {
return a
}
var mid = ((len(a) - 1) / 2)
left := make(chan []int)
right := make(chan []int)
go gosort(a[:mid], left)
go gosort(a[mid+1:], right)
return merge(<- left, <-right);
}
func gosort(a []int, c chan []int) {
c <- SortInts_parallel(a)
}
The result was horrible. It ran so long, I finally had to kill it. Can you guess why?
The overhead of starting a goroutine and receiving its result over a channel outweighs the benefit of concurrency when the slice to sort is small. There's a threshold at which that is no longer the case. From my experimentation, it seems to lie somewhere between 25000 and 200000 elements. Thus, we can mix parallel and sequential sorts:
func SortInts_parallel(a []int) []int {
if (len(a) < 2) {
return a
}
var mid = ((len(a) - 1) / 2)
if (mid >= Threshold) {
left := make(chan []int)
right := make(chan []int)
go gosort(a[:mid], left)
go gosort(a[mid+1:], right)
return merge(<- left, <-right);
}
return merge(SortInts(a[:mid]), SortInts(a[mid+1:]))
}
For arrays with a million or so elements, this beats the pants off both the original naive mergesort (by almost 3:1) and the built-in "sort" package's SortInts function (by about 2:1), depending of course on the data.
I've often observed that a well-written quicksort generally out-performs a mergesort on a smaller number of elements, so when we drop out of concurrent mode, why not switch to quicksort as well? Especially since the built-in "sort" package provides one! Here's that mod:
func SortInts_combo(a []int) []int {
if (len(a) < 2) {
return a
}
var mid = ((len(a) - 1) / 2)
if (mid >= Threshold) {
left := make(chan []int)
right := make(chan []int)
go gosort(a[:mid], left)
go gosort(a[mid+1:], right)
return merge(<- left, <-right);
}
// Degrade to quicksort
var left, right []int
left = a[:mid]
sort.SortInts(left)
right = a[mid+1:]
sort.SortInts(right)
return merge(left, right);
}
Interestingly, this version seems to perform roughly the same as the mergesort-only version. But don't trust me! Go grab the sources yourself from one of the links below and time these routines on your system. You can adjust the number of elements in the array, the threshold for concurrency, and the types of sorts to perform, all via command-line options.
My conclusion: Yes, you can use Go's concurrency to reduce the elapsed time required for potentially parallel operations, if you do so judiciously. Goroutines aren't free, but they aren't terribly expensive, either. Go for it!
Oh By The Way -- you may notice that testsort.go calls runtime.GOMAXPROCS(64) -- I found from experimentation that concurrency doesn't help much if you don't set this to at least (number of actual processors) minus 1. Anything at or above that number seems to behave the same. Apparently, Go will only use additional processors if you tell it that it can, but it doesn't hurt it to tell it to use processors that you don't have. I'm on FreeBSD 8.2-STABLE amd64. YMMV.
UPDATE 2011-04-03: Rob Pike corrected my terminology re: concurrency vs. parallelism.
I’ve 
Not too many sites use RSS 1.0 any more. It’s a completely different standard than RSS 2.0 — even the abbreviation stands for something different: RDF Site Summary (instead of Really Simple Syndication). But recently, I wanted to subscribe to a hilarious web comic called 
Since I 
I’ve been meaning to learn more about 
Subscribe by Email
