6 min read

In this two part post, you’ll learn the basics of how to benchmark and optmize go code. You’ll do this by trying out a few different implementations for calculating a specific element in Pascal’s Triangle (a.k.a. the binomial coeffecient). I’ll assume that you are already familiar with go, but if you aren’t, I recommend the interactive tutorial.

All of the code for these two posts is available on github.

Installation & Set Up

To follow along, you will need to install go version 1.2 or later.

Also, make sure that you follow these instructions for setting up your go work environment. In particular, you will need to have the GOPATH environment variable pointing to a directory where all your go code will reside.

The Goal

Our goal is to write a function to calculate a specific element of Pascal’s Triangle.

In case you aren’t familiar with Pascal’s Triangle, it looks something like this:

Pascal’s Triangle follows these simple rules:

  1. The first row contains a single element (1)
  2. Every subsequent element is the sum of the two elements directly above it (one above and to the left, and the other above and to the right).
  3. If either the element above and to the left or the one above and to the right are absent, consider them to be equal to zero.

For convenience, we’ll index all of the rows and columns in Pascal’s Triangle, starting with 0. So the element at the very top of the triangle is at index (0, 0). The element at index (4, 1) would be at row 4 and column 1, which is 1 + 3 = 4.

The function we’ll be writing will return the element at row n, column m of Pascal’s Triangle and has the following signature:

func Pascal(n, m int) int

So Pascal(0, 0) should return 1 and Pascal(5, 2) would return 10. In these posts, we’ll write several different implementations of the Pascal function, test each one for correctness, and benchmark them to see which is the fastest.

Project Structure

Now’s a good time to setup the directory where your code for this project will reside. Somehwere in $GOPATH/src, create a new directory and call it whatever you want. I recommend $GOPATH/src/github.com/your-github-username/go-benchmark-example. Our basic project structure is going to look like this:

go-benchmark-example
    common
        common.go
    implementations
        builtin.go
        naive.go
        recursive.go
    test
        benchmark_test.go
        pascal_test.go

The implementations package will hold a few different implementations of the Pascal function, each in their own file. The test package is where we will test the implementations for corectness (in pascal_test.go) and then benchmark their performance (in benchmark_test.go).

Without further ado, let’s start writing code!

The Pascaler Interface

To make comparing different implementations easier, we’ll create an interface that all of the implementations should implement. (You’ll see why this is handy when we write the tests and benchmarks).

Add the following to common/common.go:

package common

type Pascaler interface {
         Pascal(int, int) int
}

That’s it! All we’ve done is declare an interface that consists of one method, Pascal, which takes two ints as arguments (the row and column) and returns the value of the specified element in Pascal’s Triangle. The seemingly odd name “Pascaler” is just the convention in go for an interface with only one method.

Naive Implementation

The first implementation we’ll write is a naive iterative one. The basic idea is to generate the triangle from top to bottom until we reach row n and column m. We call this implementation “naive” because it does not attempt to do anything clever and will probably not perform the best.

Add the following to implementations/naive.go:

package implementations

type naiveType struct{}

var Naive = naiveType{}

func (p naiveType) Pascal(n, m int) int {
     // Instantiate a slice to hold n+1 rows
     rows := make([][]int, n+1)
     // Start by hard-coding the first two rows
     if n < 2 {
          rows = make([][]int, 2)
     }
     rows[0] = []int{1}
     rows[1] = []int{1, 1}
     // Iterate from top to bottom until we reach row n
     for i := 2; i <= n; i++ {
          numColumns := i + 1
          rows[i] = make([]int, numColumns)
          rows[i][0] = 1
          rows[i][numColumns-1] = 1
          for j := 1; j < numColumns-1; j++ {
               // Element (i, j) is equal to the sum of the two elements
               // directly above it
               rows[i][j] = rows[i-1][j-1] + rows[i-1][j]
          }
     }
     return rows[n][m]
}

// Implement the Stringer interface so we can print the Naive
// object directly with fmt.Print and friends
func (p naiveType) String() string {
     return "Naive Implementation"
}

Testing for Correctness

The next thing we’ll do is test our implementation to make sure it is correct. Since we want to test each implementation the same way, we’ll write a small utility function called testPascaler, which takes a Pascaler as an argument. The function will iterate through an array of test cases and run each case against the given implementation.

Add the following to test/pascal_test.go:

import (
     "github.com/albrow/go-benchmark-example/common"
     "github.com/albrow/go-benchmark-example/implementations"
     "reflect"
     "testing"
)

func TestNaive(t *testing.T) {
     testPascaler(t, implementations.Naive)
}

// testPascaler can be used to test any implementation. It uses a
// series of test cases and reports any errors using t.Error.
func testPascaler(t *testing.T, p common.Pascaler) {
     // cases is an array of test cases, each consisting of two inputs
     // n and m and the expected output.
     cases := []struct {
          n        int
          m        int
          expected int
     }{
          {0, 0, 1},
          {1, 0, 1},
          {1, 1, 1},
          {4, 1, 4},
          {6, 4, 15},
          {7, 3, 35},
          {7, 0, 1},
          {7, 7, 1},
          {32, 16, 601080390},
          {64, 32, 1832624140942590534},
     }

     // Iterate through each test case and check the result
     for _, c := range cases {
          if reflect.TypeOf(p) == reflect.TypeOf(implementations.Recursive) && c.n > 30 {
               // Skip cases where n is too large for the recursive implementation.
               // It takes too long and might even timeout.
               continue
          }
          got := p.Pascal(c.n, c.m)
          if got != c.expected {
               t.Errorf("Incorrect result for %s with inputs (%d, %d).nExpected %d
                   but got %d.", p, c.n, c.m, c.expected, got)
          }
     }
}

To run the test, just run the following command from your project directory: go test ./….

If everything works as expected and the test passes, you should see the following output:

?        github.com/albrow/go-benchmark-example/common     [no test files]
?        github.com/albrow/go-benchmark-example/implementations     [no test files]
ok       github.com/albrow/go-benchmark-example/test     0.005s

Conclusion

Follow along in Part 2 where we will cover benchmarking for performance, a recursive implementation, and a bultin implementation.

About the Author

Alex Browne is a programmer and entrepreneur with about 4 years of product development experience and 3 years experience working on small startups. He has worked with a wide variety of technologies and has single-handedly built many production-grade applications. He is currently working with two co-founders on an early stage startup exploring ways of applying machine learning and computer vision to the manufacturing industry.His favorite programming language is Go.

Alex Browne

LEAVE A REPLY

Please enter your comment!
Please enter your name here