Improving the performance of your code starting with Go
Tags: go, performance, pprof, benchmark
Published: 2022-12-09 14:29:19

This article is from [bmf-tech.com - Goで始めるコードのパフォーマンス改善](https://bmf-tech.com/posts/Go%e3%81%a7%e5%a7%8b%e3%82%81%e3%82%8b%e3%82%b3%e3%83%bc%e3%83%89%e3%81%ae%e3%83%91%e3%83%95%e3%82%a9%e3%83%bc%e3%83%9e%e3%83%b3%e3%82%b9%e6%94%b9%e5%96%84).

Day 9 of [Makuake Advent Calendar 2022](https://adventar.org/calendars/8496)!

# Improving the performance of your code starting with Go
When I decided to improve the performance of [goblin](https://github.com/bmf-san/goblin), a homebrew HTTP Router, I tried to work on performance improvement in Go, so I write about my approach and the efforts I put into practice.

# Prerequisites
I'm sure there is more knowledge needed for more in-depth tuning, but I'll just list the bare minimum required.

- Garbage Collection
  - A function that automatically releases memory areas allocated by a program at runtime that are no longer needed.
- Memory area
  - Text area
      - Area where a program converted into machine language can be stored
  - Stack area
      - Memory area Memory area allocated at program execution
      - Data whose size is fixed at runtime is targeted
      - Automatically released.e.g., when a function finishes executing and is no longer needed)
      - Ex. arguments, return values, temporary variables, etc. 
  - Heap area
      - Memory area allocated during program execution
      - Data whose size is dynamically determined
      - Subject to garbage collection
  - Static area
      - Memory area allocated during program execution
      - Allocated until the program is terminated
      - Ex. global variables, static variables, etc.

# Approach to Performance Improvement
The assumption is that there is a need to improve performance (is it worth sacrificing readability, can we determine that the application is the bottleneck in the first place, etc.), but we will proceed under the assumption that there is a need.

Some ways to improve the performance of the code include as follows:

- Algorithm optimization　
- Optimization of data structures
- Use of cache
- Application of parallel processing
- Compile optimization

There are a number of things that come to mind, but before implementing improvements, measurement and analysis should be performed.
(It is assumed that the need for performance improvement is more important than measurement, but that depends on the needs of each individual, and is not discussed here.)

We will introduce some of the packages and tools for measurement and analysis in Go.

## Benchmarks
Go includes [Benchmarks](https://pkg.go.dev/testing#hdr-Benchmarks) in the standard package testing to get a benchmark of your code.

You can run the command `go test -bench=. -benchmem` to obtain a benchmark.

```go
package main

import (
	"math/rand"
	"testing"
)

func BenchmarkRandIn(b *testing.B) {
	for i := 0; i < b.N; i++ { // b.N automatically specifies the number of times the benchmark can be trusted
		rand.Int() // Function to be measured
	}
}
```

The output result will look like this.

```sh
goos: darwin
goarch: amd64
pkg: bmf-san/go-perfomance-tips
cpu: VirtualApple @ 2.50GHz
BenchmarkRandIn-8       87550500                13.53 ns/op            0 B/op          0 allocs/op
PASS
ok      bmf-san/go-perfomance-tips      1.381s
```

The benchmark results that can be read from this are as follows:

- 87550500
  - Number of function executions
  - The higher the number of executions, the better the performance is considered
- 13.53 ns/op
  - Time required per function execution
  - Less time is considered better performance
- 0 B/op
  - Size of memory allocated per function execution
  - The smaller the number, the better the performance is considered to be
- 0 allocs/op
  - Number of memory allocations made per function execution
  - The fewer the number of allocations, the better the performance

Go allows for easy benchmarking in this way.

For other Go benchmarking features, see the documentation.
[Benchmarks](https://pkg.go.dev/testing#hdr-Benchmarks)

The package [benchstat](https://pkg.go.dev/golang.org/x/perf/cmd/benchstat#section-readme) is a good tool to compare benchmark results, showing the percentage of improvement in the benchmark results. The package [benchstat]() is a good tool to compare benchmark results, as it shows the percentage of improvement.

The package [bmf-san/goblin](https://github.com/bmf-san/goblin), which I manage, is incorporated into CI so that the results can be compared before and after a commit.

```sh
// This is an example where nothing has improved...
go test -bench . -benchmem -count 1 > new.out
benchstat old.out new.out
name           old time/op    new time/op    delta
Static1-36        248ns ± 0%     246ns ± 0%   ~     (p=1.000 n=1+1)
Static5-36        502ns ± 0%     495ns ± 0%   ~     (p=1.000 n=1+1)
Static10-36       874ns ± 0%     881ns ± 0%   ~     (p=1.000 n=1+1)
WildCard1-36     1.60µs ± 0%    1.50µs ± 0%   ~     (p=1.000 n=1+1)
WildCard5-36     4.49µs ± 0%    4.92µs ± 0%   ~     (p=1.000 n=1+1)
WildCard10-36    7.68µs ± 0%    7.58µs ± 0%   ~     (p=1.000 n=1+1)
Regexp1-36       1.38µs ± 0%    1.48µs ± 0%   ~     (p=1.000 n=1+1)
Regexp5-36       4.30µs ± 0%    4.11µs ± 0%   ~     (p=1.000 n=1+1)
Regexp10-36      7.66µs ± 0%    7.18µs ± 0%   ~     (p=1.000 n=1+1)
```

Absolutely no performance degradation allowed! In such a case, it may be a good idea to use a mechanism to make CI fail.

If you want to check the actual memory allocation by looking at the results of such a benchmark, you can check it by building with the build option.

```go
package main

import "fmt"

// Run build with go build -o example -gcflags '-m' gcflagsexample.go
func main() {
	a := "hello"
	b := "world"
	fmt.Println(a + b)
}
```

Running `go build -o example -gcflags '-m' gcflagsexample.go` produces the following output.

```sh
# command-line-arguments
./gcflagsexample.go:9:13: inlining call to fmt.Println
./gcflagsexample.go:9:13: ... argument does not escape
./gcflagsexample.go:9:16: a + b escapes to heap
./gcflagsexample.go:9:16: a + b escapes to heap
```

This is a simple example that is obvious, but it is also a useful method of analysis because memory allocation can be improved by identifying allocations to the heap in this way and reducing heap allocations.

## Profiling
Go has a tool called [pprof](https://pkg.go.dev/net/http/pprof) to analyze where the bottlenecks are at the function level.

```go
package main

import (
	"sort"
	"testing"
)

func sortAlphabetically() {
	s := []string{"abc", "aba", "cba", "acb"}
	sort.Strings(s)
}

func BenchmarkSortAlphabetically(b *testing.B) {
	for i := 0; i < b.N; i++ {
		sortAlphabetically()
	}
}
```

If you want to see the CPU profile, run the following.

`go test -test.bench=BenchmarkSortAlphabetically -cpuprofile cpu.out && go tool pprof -http=":8888" cpu.out`

![cpu_profile](https://user-images.githubusercontent.com/13291041/206718659-bc8b2df8-30d6-4d3c-819f-2846fd3b2c71.png)

If you want to see the memory profile, run the following.

`go test -test.bench=BenchmarkSortAlphabetically profilingexample_test.go -memprofile mem.out && go tool pprof -http=":8889" mem.out`

![memory_profile](https://user-images.githubusercontent.com/13291041/206716765-b62ab1a9-9bad-4cdb-8dd7-966c714fe940.png)

Utilizing the UI of [pprof](https://pkg.go.dev/net/http/pprof) makes it easier to identify where the bottleneck is in the process.

# Practice
Raise an example of improving [goblin](https://github.com/bmf-san/goblin), a home-made HTTP Router.

The PR on the subject is here.
[Reduce the memory allocation by refactoring explodePath method #68](https://github.com/bmf-san/goblin/pull/68)

[goblin](https://github.com/bmf-san/goblin) is an HTTP Router that works well with the net/http interface based on a tri-tree.

As for functionality, it has the minimum that is considered necessary for routing.
cf. [goblin#features](https://github.com/bmf-san/goblin#features)

### Benchmarks
First, we run a benchmark test to measure performance.

```sh
go test -bench=. -cpu=1 -benchmem
```

The benchmark test has about three patterns for each test case: static routing (ex. /foo/bar), dynamic routing (ex. /foo/:bar), and routing using regular expressions (ex. /foo/:bar[^\d+$]).

The routing process involves

1. put data into the tree structure (≒define routing)
2. search for data from the tree structure (return data based on the requested path)

In this test case, only the latter is measured.

The output results are as follows:

```sh
goos: darwin
goarch: amd64
pkg: github.com/bmf-san/goblin
cpu: VirtualApple @ 2.50GHz
BenchmarkStatic1         5072353               240.1 ns/op           128 B/op          4 allocs/op
BenchmarkStatic5         2491546               490.0 ns/op           384 B/op          6 allocs/op
BenchmarkStatic10        1653658               729.6 ns/op           720 B/op          7 allocs/op
BenchmarkWildCard1       1602606               747.3 ns/op           456 B/op          9 allocs/op
BenchmarkWildCard5        435784              2716 ns/op            1016 B/op         23 allocs/op
BenchmarkWildCard10       246729              5033 ns/op            1680 B/op         35 allocs/op
BenchmarkRegexp1         1647258               733.2 ns/op           456 B/op          9 allocs/op
BenchmarkRegexp5          456652              2641 ns/op            1016 B/op         23 allocs/op
BenchmarkRegexp10         251998              4780 ns/op            1680 B/op         35 allocs/op
PASS
ok      github.com/bmf-san/goblin       14.304s
```

Several trends can be read into each of the number of executions, number of executions per run, memory size per run, and number of memory allocations.

I am personally concerned that memory allocations are occurring even for static routing. (Other HTTP Router benchmarks show 0 allocs.)

## Profiling
Next, use pprof to obtain a profile.

This time, we focus only on memory to obtain a profile.

```sh
go test -bench . -memprofile mem.out && go tool pprof -http=":8889" mem.out
```

Graph output results.
! [pprof_graph](https://user-images.githubusercontent.com/13291041/206716778-8c5b2ad6-2e6a-444f-8f4c-7267a253446f.png)

We can see that the process with the largest box (using the most memory) is `explodePath`.

Even if you look at the Top (list in order of longest execution time), `explodePath` is at the top of the list.

![pprof_top](https://user-images.githubusercontent.com/13291041/206716793-08c464a8-db4c-4838-b872-dc6b2c51b154.png)

Flat is the processing time of the function, and Cum is the processing time including waiting time.

Furthermore, check Source to see where in the function the processing is actually heavy.

![pprof_source](https://user-images.githubusercontent.com/13291041/206716787-c1be565d-9364-40d1-b555-70836d056832.png)

Since `Search` is the core process responsible for the router's matching process, I thought it would be the bottleneck there, but it turns out that a specific process within it, `explodePath`, is the bottleneck.

## Tuning
The process of `explodePath` is to split the received string by `/` and return it as a []string type.

```go
// explodePath removes an empty value in slice.
func explodePath(path string) []string {
	s := strings.Split(path, pathDelimiter)
	var r []string
	for _, str := range s {
		if str != "" {
			r = append(r, str)
		}
	}
	return r
}
```

Test code is also included for easy understanding of the specifications.

```go
func TestExplodePath(t *testing.T) {
	cases := []struct {
		actual   []string
		expected []string
	}{
		{
			actual:   explodePath(""),
			expected: nil,
		},
		{
			actual:   explodePath("/"),
			expected: nil,
		},
		{
			actual:   explodePath("//"),
			expected: nil,
		},
		{
			actual:   explodePath("///"),
			expected: nil,
		},
		{
			actual:   explodePath("/foo"),
			expected: []string{"foo"},
		},
		{
			actual:   explodePath("/foo/bar"),
			expected: []string{"foo", "bar"},
		},
		{
			actual:   explodePath("/foo/bar/baz"),
			expected: []string{"foo", "bar", "baz"},
		},
		{
			actual:   explodePath("/foo/bar/baz/"),
			expected: []string{"foo", "bar", "baz"},
		},
	}

	for _, c := range cases {
		if !reflect.DeepEqual(c.actual, c.expected) {
			t.Errorf("actual:%v expected:%v", c.actual, c.expected)
		}
	}
}
```

Since the variable `r` defined in the [[]string type has no capacity defined, it is inferred that memory efficiency is likely to be poor.

The following is a benchmark test and results of adding append to slice prepared for verification.

```go
package main

import "testing"

func BenchmarkSliceLen0Cap0(b *testing.B) {
	var s []int

	b.StartTimer()
	for i := 0; i < b.N; i++ {
		s = append(s, i)
	}
	b.StopTimer()
}

func BenchmarkSliceLenN(b *testing.B) {
	var s = make([]int, b.N)

	b.StartTimer()
	for i := 0; i < b.N; i++ {
		s = append(s, i)
	}
	b.StopTimer()
}

func BenchmarkSliceLen0CapN(b *testing.B) {
	var s = make([]int, 0, b.N)

	b.StartTimer()
	for i := 0; i < b.N; i++ {
		s = append(s, i)
	}
	b.StopTimer()
}
```

```sh
goos: darwin
goarch: amd64
pkg: example.com
cpu: VirtualApple @ 2.50GHz
BenchmarkSliceLen0Cap0  100000000               11.88 ns/op           45 B/op          0 allocs/op
BenchmarkSliceLenN      78467056                23.60 ns/op           65 B/op          0 allocs/op
BenchmarkSliceLen0CapN  616491007                5.057 ns/op           8 B/op          0 allocs/op
PASS
ok      example.com     6.898s
bmf@bmfnoMacBook-Air:~/Desktop$
```

This result suggests that the code could be somewhat more efficient by specifying the capacity.

Therefore, modify `explodePath` as follows.

```go
func explodePath(path string) []string {
	s := strings.Split(path, "/")
	// var r []string
	r := make([]string, 0, strings.Count(path, "/")) // Specify capacity
	for _, str := range s {
		if str != "" {
			r = append(r, str)
		}
	}
	return r
}
```

A little more in-depth and improved implementation.

```go
func explodePath(path string) []string {
	splitFn := func(c rune) bool {
		return c == '/'
	}
	return strings.FieldsFunc(path, splitFn)
}
```

We will compare benchmarks with three patterns: the original `explodePath` implementation, an implementation with reserved slice capacity, and an implementation using `strings.FieldFunc`.

```go
package main

import (
	"strings"
	"testing"
)

func explodePath(path string) []string {
	s := strings.Split(path, "/")
	var r []string
	for _, str := range s {
		if str != "" {
			r = append(r, str)
		}
	}
	return r
}

func explodePathCap(path string) []string {
	s := strings.Split(path, "/")
	r := make([]string, 0, strings.Count(path, "/"))
	for _, str := range s {
		if str != "" {
			r = append(r, str)
		}
	}
	return r
}

func explodePathFieldsFunc(path string) []string {
	splitFn := func(c rune) bool {
		return c == '/'
	}
	return strings.FieldsFunc(path, splitFn)
}

func BenchmarkExplodePath(b *testing.B) {
	paths := []string{"", "/", "///", "/foo", "/foo/bar", "/foo/bar/baz"}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		for _, v := range paths {
			explodePath(v)
		}
	}
	b.StopTimer()
}

func BenchmarkExplodePathCap(b *testing.B) {
	paths := []string{"", "/", "///", "/foo", "/foo/bar", "/foo/bar/baz"}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		for _, v := range paths {
			explodePathCap(v)
		}
	}
	b.StopTimer()
}

func BenchmarkExplodePathFieldsFunc(b *testing.B) {
	paths := []string{"", "/", "///", "/foo", "/foo/bar", "/foo/bar/baz"}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		for _, v := range paths {
			explodePathFieldsFunc(v)
		}
	}
	b.StopTimer()
}
```

```sh
goos: darwin
goarch: amd64
pkg: example.com
cpu: VirtualApple @ 2.50GHz
BenchmarkExplodePath             1690340               722.2 ns/op           432 B/op         12 allocs/op
BenchmarkExplodePathCap          1622161               729.5 ns/op           416 B/op         11 allocs/op
BenchmarkExplodePathFieldsFunc   4948364               239.5 ns/op            96 B/op          3 allocs/op
PASS
ok      example.com     5.685s
```

The implementation using `strings.PathFieldFunc` seems to have the best performance, so it is adopted.

## Measuring Effectiveness
Check the results after improving the implementation of `explodePath`.

### Benchmarks

```sh
# Before
goos: darwin
goarch: amd64
pkg: github.com/bmf-san/goblin
cpu: VirtualApple @ 2.50GHz
BenchmarkStatic1         5072353               240.1 ns/op           128 B/op          4 allocs/op
BenchmarkStatic5         2491546               490.0 ns/op           384 B/op          6 allocs/op
BenchmarkStatic10        1653658               729.6 ns/op           720 B/op          7 allocs/op
BenchmarkWildCard1       1602606               747.3 ns/op           456 B/op          9 allocs/op
BenchmarkWildCard5        435784              2716 ns/op            1016 B/op         23 allocs/op
BenchmarkWildCard10       246729              5033 ns/op            1680 B/op         35 allocs/op
BenchmarkRegexp1         1647258               733.2 ns/op           456 B/op          9 allocs/op
BenchmarkRegexp5          456652              2641 ns/op            1016 B/op         23 allocs/op
BenchmarkRegexp10         251998              4780 ns/op            1680 B/op         35 allocs/op
PASS
ok      github.com/bmf-san/goblin       14.304s

# After
go test -bench=. -cpu=1 -benchmem -count=1
goos: darwin
goarch: amd64
pkg: github.com/bmf-san/goblin
cpu: VirtualApple @ 2.50GHz
BenchmarkStatic1        10310658               117.7 ns/op            32 B/op          1 allocs/op
BenchmarkStatic5         4774347               258.1 ns/op            96 B/op          1 allocs/op
BenchmarkStatic10        2816960               435.8 ns/op           176 B/op          1 allocs/op
BenchmarkWildCard1       1867770               653.4 ns/op           384 B/op          6 allocs/op
BenchmarkWildCard5        496778              2484 ns/op             928 B/op         13 allocs/op
BenchmarkWildCard10       258508              4538 ns/op            1560 B/op         19 allocs/op
BenchmarkRegexp1         1978704               608.4 ns/op           384 B/op          6 allocs/op
BenchmarkRegexp5          519240              2394 ns/op             928 B/op         13 allocs/op
BenchmarkRegexp10         280741              4309 ns/op            1560 B/op         19 allocs/op
PASS
ok      github.com/bmf-san/goblin       13.666s
```

Comparing before and after improvements, we can say that the overall trend is toward improvement.

### Profiling
pprof's graph.

![pprof_graph_after](https://user-images.githubusercontent.com/13291041/206716776-7cee0600-6cb4-4d82-b534-e9b2e2ff72ac.png)

pprof's top.

![pprof_top_after](https://user-images.githubusercontent.com/13291041/206716789-1ef3cbae-c638-4935-a6fa-22907fe30633.png)

You can see that the bottleneck has moved to `strings.FieldsFunc`, which is called in the `explodePath`.

## Further Improvements
Here is the tag released after making other improvements to [goblin](https://github.com/bmf-san/goblin).
[6.0.0](https://github.com/bmf-san/goblin/releases/tag/6.0.0)

Unfortunately, there are no significant improvements in the data structure and algorithms, so to speak, so there are no remarkable improvements.

I have a feeling that the data structure and algorithms they are using now are still difficult to use. (I have seen other routers that use more advanced trees, so I guess that's true...)

This is somewhat off topic, but I created a bench marker to compare with other routers and see if I can get some hints for improvement.

[bmf-san/go-router-benchmark](https://github.com/bmf-san/go-router-benchmark)

It was interesting to compare them and see how ragged they are.

I would like to improve it by studying other router implementations, learning about advanced tree structures, etc., which I failed to do before.

# Summary
- Go makes benchmarking and profiling easy.
- Don't guess, measure!
- It is hard to get big results with small improvements (that's true)

# Reference
- [github.com - google/pprof](https://github.com/google/pprof/blob/main/doc/README.md)
- [github.com - dgryski/go-perfbook](https://github.com/dgryski/go-perfbook)
- [dave.cheney.net - High Perfomance Go Workshop](https://dave.cheney.net/high-performance-go-workshop/dotgo-paris.html)
- [go.dev - Profiling Go Programs](https://go.dev/blog/pprof)
- [go.dev - A Guide to the Go Garbage Collector](https://go.dev/doc/gc-guide)
- [developer.so-tech.co.jp](https://developer.so-tech.co.jp/entry/2022/07/28/112845)
- [segment.com - Allocation efficiency in high-performance Go services](https://segment.com/blog/allocation-efficiency-in-high-performance-go-services/)
- [blog.logrocket.com - Benchmarking in Golang: Improving function performance](https://blog.logrocket.com/benchmarking-golang-improve-function-performance/)
- [medium.com - Go code refactoring : the 23x performance hunt](https://medium.com/@val_deleplace/go-code-refactoring-the-23x-performance-hunt-156746b522f7)
- [medium.com - Go言語のプロファイリングツール、pprofのWeb UIがめちゃくちゃ便利なので紹介する](https://medium.com/eureka-engineering/go%E8%A8%80%E8%AA%9E%E3%81%AE%E3%83%97%E3%83%AD%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%84%E3%83%BC%E3%83%AB-pprof%E3%81%AEweb-ui%E3%81%8C%E3%82%81%E3%81%A1%E3%82%83%E3%81%8F%E3%81%A1%E3%82%83%E4%BE%BF%E5%88%A9%E3%81%AA%E3%81%AE%E3%81%A7%E7%B4%B9%E4%BB%8B%E3%81%99%E3%82%8B-6a34a489c9ee)
- [teivah.medium.com - Good Code vs Bad Code in Golang
](https://teivah.medium.com/good-code-vs-bad-code-in-golang-84cb3c5da49d)
- [hnakamur.github.io - goで書いたコードがヒープ割り当てになるかを確認する方法](https://hnakamur.github.io/blog/2018/01/30/go-heap-allocations/)
- [glog.kazu69.net - Goのメモリ管理を眺めてみた](https://blog.kazu69.net/2017/08/20/memory-management-go/)
- [dsas.blog.klab.org - Goでアロケーションに気をつけたコードを書く方法](http://dsas.blog.klab.org/archives/52191778.html)
- [tech.speee.jp - Goのロギングライブラリから見たゼロアロケーション](https://tech.speee.jp/entry/2022/07/12/134605)
- [kawasin73.hatenablog.com - メモリアロケーションに対する罪悪感
](https://kawasin73.hatenablog.com/entry/2019/11/10/112301)