In this section, I will show you a basic benchmarking example that will measure the performance of three algorithms that generate numbers belonging to the Fibonacci sequence. The good news is that such algorithms require lots of mathematical calculations, which make them perfect candidates for benchmarking.
For the purposes of this section, I will create a new main package, which will be saved as benchmarkMe.go and presented in three parts.
The first part of benchmarkMe.go is as follows:
package main
import (
"fmt"
)
func fibo1(n int) int {
if n == 0 {
return 0
} else if n == 1 {
return 1
} else {
return fibo1(n-1) + fibo1(n-2)
}
}
The preceding code contains the implementation of the fibo1() function that uses recursion in order to calculate the numbers of the Fibonacci sequence. Although the algorithm works fine, this is a relatively simple and somehow slow approach.
The second code segment of benchmarkMe.go is shown in the following Go code:
func fibo2(n int) int {
if n == 0 || n == 1 {
return n
}
return fibo2(n-1) + fibo2(n-2)
}
In this part, you see the implementation of the fibo2() function that is almost identical to the fibo1() function that you saw earlier. However, it will be interesting to see whether a small code change—a single if statement as opposed to an if else if block—has any impact to the performance of the function.
The third code portion of benchmarkMe.go contains yet another implementation of a function that calculates numbers that belong to the Fibonacci sequence:
func fibo3(n int) int {
fn := make(map[int]int)
for i := 0; i <= n; i++ {
var f int
if i <= 2 {
f = 1
} else {
f = fn[i-1] + fn[i-2]
}
fn[i] = f
}
return fn[n]
}
The fibo3() function presented here uses a totally new approach that requires a Go map and has a for loop. It remains to be seen whether this approach is indeed faster than the other two implementations. The algorithm presented in fibo3() will be also used in Chapter 13, Network Programming – Building Servers and Clients, where it will be explained in greater detail. As you will see in a while, choosing an efficient algorithm can save you from a lot of trouble!
The remaining code of benchmarkMe.go follows next:
func main() {
fmt.Println(fibo1(40))
fmt.Println(fibo2(40))
fmt.Println(fibo3(40))
}
Executing benchmarkMe.go will generate the following output:
$ go run benchmarkMe.go 102334155 102334155 102334155
The good news is that all three implementations returned the same number. Now it is time to add some benchmarks to benchmarkMe.go in order to understand the efficiency of the each one of the three algorithms.
As the Go rules require, the version of benchmarkMe.go containing the benchmark functions will be saved as benchmarkMe_test.go. This program is presented in five parts.
The first code segment of benchmarkMe_test.go contains the following Go code:
package main
import (
"testing"
)
var result int
func benchmarkfibo1(b *testing.B, n int) {
var r int
for i := 0; i < b.N; i++ {
r = fibo1(n)
}
result = r
}
In the preceding code, you can see the implementation of a function with a name that begins with the benchmark string instead of the Benchmark string. As a result, this function will not run automatically because it begins with a lowercase b instead of an uppercase B.
The reason for storing the result of fibo1(n) in a variable named r and using another global variable named result afterwards is tricky. This technique is used for preventing the compiler from performing any optimizations that will exclude the function that you want to measure because its result are never used! The same technique will be applied in functions benchmarkfibo2() and benchmarkfibo3(), which will be presented next.
The second part of benchmarkMe_test.go is shown in the following Go code:
func benchmarkfibo2(b *testing.B, n int) {
var r int
for i := 0; i < b.N; i++ {
r = fibo2(n)
}
result = r
}
func benchmarkfibo3(b *testing.B, n int) {
var r int
for i := 0; i < b.N; i++ {
r = fibo3(n)
}
result = r
}
The preceding code defines two more benchmark functions that will not run automatically because they begin with a lowercase b instead of an uppercase B.
Now I will tell you a big secret: even if these three functions were named BenchmarkFibo1(), BenchmarkFibo2(), and BenchmarkFibo3(), they would not have been invoked automatically by the go test command because their signature is not func(*testing.B). So, the reason for naming them with a lowercase b is this! However, there is nothing that prevents you from invoking them from other benchmark functions afterwards, as you will see shortly.
The third part of benchmarkMe_test.go follows next:
func Benchmark30fibo1(b *testing.B) {
benchmarkfibo1(b, 30)
}
This is a correct benchmark function with the correct name and the correct signature, which means that it will get executed by go tool.
Note that although Benchmark30fibo1() is a valid benchmark function name, BenchmarkfiboIII() is not because there is no uppercase letter or a number after the Benchmark string. This is very important because a benchmark function with an incorrect name will not get executed automatically.
The fourth code segment of benchmarkMe_test.go contains the following Go code:
func Benchmark30fibo2(b *testing.B) {
benchmarkfibo2(b, 30)
}
func Benchmark30fibo3(b *testing.B) {
benchmarkfibo3(b, 30)
}
Both the Benchmark30fibo2() and Benchmark30fibo3() benchmark functions are similar to Benchmark30fibo1().
The last part of benchmarkMe_test.go is as follows:
func Benchmark50fibo1(b *testing.B) {
benchmarkfibo1(b, 50)
}
func Benchmark50fibo2(b *testing.B) {
benchmarkfibo2(b, 50)
}
func Benchmark50fibo3(b *testing.B) {
benchmarkfibo3(b, 50)
}
In this part, you see three additional benchmark functions that calculate the 50th number in the Fibonacci sequence.
Executing benchmarkMe_test.go will generate the following output:
$ go test -bench=. benchmarkMe.go benchmarkMe_test.go goos: darwin goarch: amd64 Benchmark30fibo1-8 300 4494213 ns/op Benchmark30fibo2-8 300 4463607 ns/op Benchmark30fibo3-8 500000 2829 ns/op Benchmark50fibo1-8 1 67272089954 ns/op Benchmark50fibo2-8 1 67300080137 ns/op Benchmark50fibo3-8 300000 4138 ns/op PASS ok command-line-arguments 145.827s
There are two important points here: first, the value of the -bench parameter specifies the benchmark functions that will be executed. The . value used is a regular expression that matches all valid benchmark functions. The second point is that if you omit the -bench parameter, no benchmark function will be executed!
So, what does this output tell us? First of all, -8 at the end of each benchmark function (Benchmark10fibo1-8) signifies the number of goroutines used during its execution, which is essentially the value of the GOMAXPROCS environment variable. You will recall that we talked about the GOMAXPROCS environment variable back in Chapter 10, Go Concurrency – Advanced Topics. Similarly, you can see the values of GOOS and GOARCH, which show the operating system and the architecture of your machine.
The second column in the output displays the number of times that the relevant function was executed. Faster functions are executed more times than slower functions. As an example, function Benchmark30fibo3() was executed 500,000 times, while function Benchmark50fibo2() was executed only once! The third column in the output shows the average time of each run.
As you can see, the fibo1() and fibo2() functions are really slow compared to the fibo3() function. Should you wish to include memory allocation statistics in the output, you can execute the following command:
$ go test -benchmem -bench=. benchmarkMe.go benchmarkMe_test.go goos: darwin goarch: amd64 Benchmark30fibo1-8 300 4413791 ns/op 0 B/op 0 allocs/op Benchmark30fibo2-8 300 4430097 ns/op 0 B/op 0 allocs/op Benchmark30fibo3-8 500000 2774 ns/op 2236 B/op 6 allocs/op Benchmark50fibo1-8 1 71534648696 ns/op 0 B/op 0 allocs/op Benchmark50fibo2-8 1 72551120174 ns/op 0 B/op 0 allocs/op Benchmark50fibo3-8 300000 4612 ns/op 2481 B/op 10 allocs/op PASS ok command-line-arguments 150.500s
The preceding output is similar to the one without the -benchmem command-line parameter, but it includes two more columns in its output. The fourth column shows the amount of memory that was allocated on average in each execution of the benchmark function. The fifth column shows the number of allocations used for allocating the memory value of the fourth column. So, Benchmark50fibo3() allocated 2481 bytes in 10 allocations on average.
As you can understand, functions fibo1() and fibo2() do not need any special kind of memory apart from the expected one, because neither of them is using any kind of data structure, which is not the case with fibo3() which uses a map variable; hence the larger than zero values in both the fourth and fifth columns of the output of Benchmark10fibo3-8.