# Concurrent Quicksort in Go

I’ve been playing around with Go to get some experience in a systems programming language before applying for applying jobs. I’ve never done concurrent/parallel programming so I thought I’d try to learn about some of Go’s concurrency tools by implementing quicksort concurrently.

I started by writing a simple in-place quicksort implementation. The majority of the algorithm happens in a partition function which picks a random pivot and then does in-place swapping to partition around the pivot. With this in place the sequential algorithm falls into place easily.

Since the divide and conquer nature of quicksort means the recursive calls to Qsort don’t touch the same memory, this should be a decent candidate for concurrency.

This works but is incredibly slow. Goroutines are cheap but not free. For large s this program spends most of its time in garbage collection as too many goroutines are created.

We need to limit the number of goroutines.

Setting MAXGOROUTINES limits the number of goroutines that ever get created by switching to a synchronous model once the workers channel is exhausted.

This performs much better than before. Benchmarking puts it at about the same speed as the built-in sort.Ints, but still slower than our basic Qsort implementation for a shuffled slice of 1 million elements created by math/rand.Perm. Playing around with MAXGOROUTINES I seemed to get slight variations when using numbers anywhere from 2 to 10000 (make sure you have the GOMAXPROCS environment variable set to the number of cores you want to use so that goroutines are executed in parallel). Above 10000 and performance starts to degrade.

This use of Go’s concurrency features purely for the purpose of parallelizing code goes against Rob Pike’s “Concurrency is not Parallelism” talk, so I’m not surprised that I don’t see a significant speedup when trying to parallelize this concurrent code against the sequential version. I am surprised that I don’t get similar speeds to the sequential version when setting MAXGOROUTINES to 1 as the code is essentially executing sequentially in this case. Perhaps the few extra statements and branches are enough to slow things down considerably. In any case it was a good experiment in writing concurrent Go that also forced me to dive into profiling with pprof and using Go’s support for writing benchmarks in test code.

Code is all up on github at (https://github.com/azundo/cqsort).