Home

Go's sort performance

Saturday 23 February 2013

Go's performance is good. It's a statically typed language like C++, but doesn't yet have the benefits of intense compiler optimizations (unless you count gccgo). So in general it's not as fast as a similar program written in C or C++. Probably faster than Java though, unless JIT compilation steals the show with its runtime knowledge...
All that's a bit vague, and micro-benchmarks are a silly thing to optimize for. But unless someone comes up with a diverse set of benchmarks in multiple languages, we're going to have to live with it. The Go compiler is getting better, and Go has advantages other than speed.
Performance depends as much on the choice and implementation of an algorithm as on the language or runtime.
I looked at the performance of Go's Sort function. Instead of comparing it to other sort functions or those in other languages, I looked at how its performance depends on its input. For instance, if you try to sort something that's already sorted, is it any faster?
Go's sort is based loosely on Engineering A Sort Function (1993) [PDF], which describes the rationale and techniques behind a good sorting routine. In particular, its performance when given certain types of input was carefully considered. Quicksort (the main algorithm used) has a worst-case run time of O(n²), and care has been taken to make sure this can't be abused.
Go prevents this by limiting the depth of the recursive calls to quicksort. Once it reaches its maximum depth it switches to Heapsort, which guarantees a worst-case run time of O(n log n).

Tests

To keep the code simple and to allow the compiler to optimise as much as possible, I chose to sort various distributions of integers using sort.Ints. I kept the length of the slices constant.
const size = 1e5

Distributions

Ordered

What could be more simple than sorting a slice that's already sorted? Does having repeat elements help? Ordered returns a slice of the requested length, with increasing, repeated elements. There should be x distinct elements in the slice.
func Ordered(l, x int) []int {
        if x > l {
                x = l
        }
	s := make([]int, l)
	for i := range s {
		s[i] = i / (l / x)
	}
	return s
}

Sawtooth

Sawtooth and its reverse generate ordered sequences of length x.
func Sawtooth(l, x int) []int {
	s := make([]int, l)
	for i := range s {
		s[i] = i % x
	}
	return s
}

Organpipe

An increasing, then decreasing sequence of total length x
func Organpipe(l, x int) []int {
	s := make([]int, l)
	for i := range s {
		if i%x < x/2 {
			s[i] = i % x
		} else {
			s[i] = x - i%x - 1
		}
	}
	return s
}

Random

Random generates a slice of integers picked from a pool of size x. When x is 1, all elements are the same.
func Random(l, x int) []int {
	s := make([]int, l)
	for i := range s {
		s[i] = rand.Intn(x)
	}
	return s
}

Distinct

A slight extension of Random, Distinct shuffles a slice of distinct integers, as if selecting from an infinite pool.
func Distinct(l, x int) []int {
	return rand.Perm(l)
}

Measurements

I measured the time taken (median of 51 runs) to sort slices of length 100,000. I also counted the number of calls to Swap and Less that were made, by embedding the slice in a struct and providing counters for those methods. Note that the methods have to be defined on the pointer receiver in order to modify the counters during sorting.
type profiledInts struct {
	lessCounter int
	swapCounter int
	sort.IntSlice
}

func (p *profiledInts) Less(i, j int) bool {
	p.lessCounter++
	return p.IntSlice.Less(i, j)
}
func (p *profiledInts) Swap(i, j int) {
	p.swapCounter++
	p.IntSlice.Swap(i, j)
}

x

The independent variable, or "horizontal axis" has a subtle interpretation that makes sense for all the distributions. As x increases the input data contains more distinct values, the runs become longer, the repetitions less frequent. x doesn't have any units, but at x=1 all the functions return a uniform slice with a single value, at the maximum value of x, the values will almost all be distinct.

Results


Previous (Amazon Banking)
Next (N Queens)