Benchmark testing in Go

I really like that the Go standard library is including so many testing options right out of the box.

In this post I will introduce the benchmark testing option in Go.

As in many cases in Go there are some conventions to follow to use the Benchmark feature. They are very similar to the ones used for writing unit tests.

First, the Benchmark tests are placed in files with the _test.go suffix. Next rule is that the benchmark test uses the prefix Benchmark instead of Test, so the signature of the function looks like this,

func BenchmarkXxx(*testing.B) {

To run benchmark tests you use the regular test command, but with an extra flag;

go test -bench=.

With this information we are ready to write some tests. The example code that we will try to benchmark is two sorting algorithms, BubbleSort and QuickSort.

func BubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

func QuickSort(arr []int) {
    quickSort(arr, 0, len(arr)-1)
}

func quickSort(arr []int, low, high int) {
    if low < high {
        pivot := partition(arr, low, high)
        quickSort(arr, low, pivot-1)
        quickSort(arr, pivot+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

I will create a new file, sorting_benchmark_test.go, and begin adding some helper code for the benchmark tests.

func makeRandomNumberSlice(n int) []int {
    numbers := make([]int, n)
    for i := range n {
        numbers[i] = rand.Intn(n)
    }
    return numbers
}

const LENGTH = 10_000

This function, makeRandomNumberSlice, will be used for generating slices that can be sorted in the benchmarks. The variable, LENGTH, represents the length of the slices we are going to sort.

Now lets add two benchmark tests, one for each sorting algorithm.

func BenchmarkBubbleSort(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b.StopTimer()
        numbers := makeRandomNumberSlice(LENGTH)

        b.StartTimer()
        sorting.BubbleSort(numbers)
    }
}

func BenchmarkQuickSort(b *testing.B) {
    for i := 0; i < b.N; i++ {
        b.StopTimer()
        numbers := makeRandomNumberSlice(LENGTH)

        b.StartTimer()
        sorting.QuickSort(numbers)
    }
}

The testing.B struct is providing a field called, N, which is needed so that the tool will be able measure correctly. This is from the Go documentation.

The benchmark function must run the target code b.N times. During benchmark execution, b.N is adjusted until the benchmark function lasts long enough to be timed reliably.

Both tests are using the same pattern. For each loop we are creating a new random slice of length, LENGTH, and then sort it. We are also making sure that the timer is not running while we are generating the slice so it's not included in the measurement.

When running this with, go test -bench=., the result will look something like this.

The output starts with telling us what kind of machine the benchmark is running on. Then there is two lines representing each benchmark test that we have written.

The suffix, -16, in the first column (BenchmarkBubbleSort-16/BenchmarkQuickSort-16), tells us how many CPUs is used to run the tests. The second column is how many loops that was used during the test, b.N. The last column gives us the speed for each loop.

From this test we can clearly see who is the winner, QuickSort. Quicksort has an average-case time complexity of O(n log n), while BubbleSort has a worst-case and average-case time complexity of O(n^2).

As you can see it's easy to get started with benchmark testing in Go, the difficulties lie in what and how to benchmark the code. There is also of course more flags and features to explore and use when writing benchmark tests in Go, please check the documentation for more information.

Happy benchmarking!