This article is from bmf-tech.com - Goで始めるコードのパフォーマンス改善.

Day 9 of Makuake Advent Calendar 2022!

Improving the performance of your code starting with Go

When I decided to improve the performance of 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 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.

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.

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

The package benchstat 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, which I manage, is incorporated into CI so that the results can be compared before and after a commit.

// 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.

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.

# 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 to analyze where the bottlenecks are at the function level.

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

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

Utilizing the UI of pprof makes it easier to identify where the bottleneck is in the process.

Practice

Raise an example of improving goblin, a home-made HTTP Router.

The PR on the subject is here.
Reduce the memory allocation by refactoring explodePath method #68

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

Benchmarks

First, we run a benchmark test to measure performance.

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:

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.

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

Graph output results.
! pprof_graph

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.

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.

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.

// 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.

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.

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()
}

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.

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.

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.

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()
}

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

# 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's top.

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.
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

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
• github.com - dgryski/go-perfbook
• dave.cheney.net - High Perfomance Go Workshop
• go.dev - Profiling Go Programs
• go.dev - A Guide to the Go Garbage Collector
• developer.so-tech.co.jp
• segment.com - Allocation efficiency in high-performance Go services
• blog.logrocket.com - Benchmarking in Golang: Improving function performance
• medium.com - Go code refactoring : the 23x performance hunt
• medium.com - Go言語のプロファイリングツール、pprofのWeb UIがめちゃくちゃ便利なので紹介する
• teivah.medium.com - Good Code vs Bad Code in Golang
• hnakamur.github.io - goで書いたコードがヒープ割り当てになるかを確認する方法
• glog.kazu69.net - Goのメモリ管理を眺めてみた
• dsas.blog.klab.org - Goでアロケーションに気をつけたコードを書く方法
• tech.speee.jp - Goのロギングライブラリから見たゼロアロケーション
• kawasin73.hatenablog.com - メモリアロケーションに対する罪悪感