Makuake Advent Calendar 2022の9日目の記事です！

Goで始めるコードのパフォーマンス改善

自作HTTP Routerのgoblinのパフォーマンス改善をしよう思った際に、Goのパフォーマンス改善について取り組んでみたので、その際のアプローチと実践した取り組みについて書く。

前提知識

より奥深いチューニングをする上ではもっと必要な知識があると思うが、最低限必要なことだけリストアップ。

ガベージコレクション
- プログラムが実行時に確保したメモリ領域のうち、不要になった領域を自動で解放する機能のこと
メモリ領域
- テキスト領域
  - 機械語に変換されたプログラムが可能される領域
- スタック領域
  - プログラム実行時に確保されるメモリ領域
  - 実行時にサイズが決まっているデータが対象
  - 自動的に解放される（関数の実行が終了して不要になったときなど）
  - ex. 引数、戻り値、一時変数など
- ヒープ領域
  - プログラム実行時に確保されるメモリ領域
  - 動的にサイズを決まるデータが対象
  - ガベージコレクションの対象
- 静的領域
  - プログラム実行時に確保されるメモリ領域
  - プログラムが終了されるまで確保される
  - ex. グローバル変数や静的（static）変数など

パフォーマンス改善のアプローチ

前提として、パフォーマンスを改善する必要性がある（可読性を犠牲にする価値があるか、そもそもアプリケーションがボトルネックだと断定できているのか、など改善すべき理由があるか）かどうかという部分があるが、必要性があるという前提のもとで話を進める。

コードのパフォーマンスを改善する方法として、

アルゴリズムの最適化　
データ構造の最適化
キャッシュの利用
並列処理の適用
コンパイルの最適化

などいくつか思い浮かぶことがあるが、改善策を講じる前に計測や分析を行う。（計測よりもそもそもパフォーマンス改善が必要性というのが前提にあるが各々のニーズによるのでここでは触れない。）

Goで計測や分析を行うパッケージやツールの紹介をする。

Benchmark

Goではコードのベンチマークを取得するためのBenchmarksが標準パッケージであるtestingに含まれている。

例えば次のようなコードをgo test -bench=. -benchmemというコマンドで実行するとベンチマークを取得することできる。

package main

import (
    "math/rand"
    "testing"
)

func BenchmarkRandIn(b *testing.B) {
    for i := 0; i < b.N; i++ { // b.Nはベンチマークが信頼できる回数を自動的に指定する
        rand.Int() // 計測したい関数
    }
}

出力結果は次のような形になる。

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

ここから読み取れるベンチマークの結果は次の通り。

87550500
- 関数の実行回数
- 実行回数が多いほどパフォーマンスが良いと考えられる
13.53 ns/op
- 関数の1回あたりの実行に要した時間
- 時間が少ないほどパフォーマンスが良いと考えられる
0 B/op
- 関数の実行ごとに割当されたメモリのサイズ
- 少なければ少ないほどパフォーマンスが良いと考えられる
0 allocs/op
- 関数の1回あたりの実行で行われたメモリアロケーションの回数
- 少なければ少ないほどパフォーマンスが良いと考えられる

Goではこのように簡単にベンチマークを取得することができる。

その他のGoのベンチマークの機能についてはドキュメント参照。 Benchmarks

ベンチマークの結果を比較するツールとしてbenchstatというパッケージが使うと、ベンチマークの結果がどれくらい改善されたか割合を表示してくれるので良い。

自分が管理しているbmf-san/goblinではCIに組み込んでコミット前後の結果を比較できるようにしている。

// これは何も改善されていない例だが・・
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)

パフォーマンス劣化を絶対に許さない！みたいな場合はCIをFailさせるような仕組みにすると良いかもしれない。

このようなベンチマークの結果を見て、実際のメモリ割り当ての様子を確認したい場合には、buildオプションを指定してビルドすることで確認することできる。 -gcflagsに指定する-mの数を増やすとより詳細な結果が得られる。

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

go build -o example -gcflags '-m' gcflagsexample.goと実行すると次のような出力が得られる。

# 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

これは単純な例なので一目瞭然だが、このようにしてヒープへの割当を特定し、ヒープ割当を減らすことによりメモリアロケーションを改善することができるため、分析の方法としても有用である。

Profiling

関数レベルでどこにボトルネックがあるかというのを分析するためのツールとしてGoにはpprofというツールがある。

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

CPUのプロファイルがみたいとき以下を実行。

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

cpu_profile

メモリのプロファイルがみたいときは以下を実行。

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

memory_profile

pprofのUIを活用することでどこの処理にボトルネックがあるか特定しやすくなる。

実践

自作HTTP Routerのgoblinの改善例を上げる。

題材としているPRはこちら。 Reduce the memory allocation by refactoring explodePath method #68

goblinはトライ木をベースとしたnet/httpのインターフェースと相性の良いHTTP Routerである。

機能としては、ルーティングに必要と思われる最低限のものは持っている。 cf. goblin#features

ベンチマーク

まずはパフォーマンスを計測するためにベンチマークテストを実行する。

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

ベンチマークテストは、静的なルーティング（ex. /foo/bar）、動的なルーティング（ex. /foo/:bar）、正規表現を使ったルーティング（ex. /foo/:bar[^\d+$]）のテストケースをそれぞれ3パターンほど用意している。

ルーティングの処理として、

木構造にデータを入れる（≒ルーティングを定義する）
木構造からデータを探索する（リクエストされたパスを元にデータを返す）

といった流れになるが、このテストケースでは後者のみを計測するようになっている。

出力結果は以下の通り。

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

実行回数、1回あたりの実行回数、実行ごとのメモリサイズ、メモリアローケーション回数のそれぞれにいくつか傾向が読み取れる。

静的なルーティングであってもメモリアローケーションが発生しているのが個人的には気になるところである。（他のHTTP Routerのベンチマークを見ると0 allocsだったりする。）

プロファイリング

次にpprofを使ってプロファイルを取得する。

今回はメモリだけにフォーカスしてプロファイルを取得。

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

Graphの出力結果。 pprof_graph

ボックスが一番大きい（メモリを一番使っている）処理がexplodePathだと分かる。

Top（実行時間の長い順のリスト）を見てもexplodePathが最上位にいる。

pprof_top

Flatは関数の処理時間、Cumは待ち時間も含めた処理時間となる。

さらにSourceを実際に関数内のどのあたりの処理が重いかの確認。

pprof_source

Searchはルーターのマッチング処理を担う根幹の処理なので、そこが一番ネックだろうとは思っていたが、その中の特定の処理であるexplodePathがネックになっているということが分かった。

チューニング

explodePathは受け取った文字列を/で分割して[]string型にして返すという処理になっている。

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

仕様が分かりやすいようにテストコードも記載。

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

[]string型で定義されている変数rは容量が定義されていないため、メモリ効率が悪そうなことが推測される。

以下は検証用に用意したsliceにappendを追加するベンチマークテストとその結果。

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$

この結果から、容量を指定してあげることでいくらか効率の良いコードになりそうなことが伺える。

そこでexplodePathを次のように修正。

func explodePath(path string) []string {
    s := strings.Split(path, "/")
    // var r []string
    r := make([]string, 0, strings.Count(path, "/")) // 容量を指定
    for _, str := range s {
        if str != "" {
            r = append(r, str)
        }
    }
    return r
}

もう少し踏み込んで実装を改善。

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

元のexplodePathの実装、sliceの容量を確保した実装、strings.FieldFuncを利用した実装の3パターンでベンチマークを比較してみる。

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

strings.PathFieldFuncを使った実装が一番パフォーマンスが良さそうなので採用。

効果測定

explodePathの実装を改善した後の結果を確認してみる。

ベンチーマーク

# 改善前
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

# 改善後
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

改善前後を比較するに全体的に改善された傾向にあると言えそう。

プロファイリング

pprofのGraph。

pprof_graph_after

pprofのTop。

pprof_top_after

ボトルネックがexplodePath内で呼び出しているstrings.FieldsFuncに移動したのが分かる。

さらなる改善

goblinに他にも改善を加えていってリリースされたタグがこちら。 6.0.0

データ構造やアルゴリズムの大きな改善をしていない、いわば小手先の改善ではあるので目を見張るほどの改善は残念ながら見られない。

なんとなく今採用しているデータ構造やアルゴリズムだとやはり難しいのだろうなという感じがする。（他所のルーター見ているともっと高度な木を採用しているのでそれはそうだという気がするが・・）

本題とはややずれるが、他のルーターとの比較をして改善のヒントが得られないかと思ってベンチマーカーを作成した。

bmf-san/go-router-benchmark

比較してみると面白くて、ボロ負けなのがよく分かる。泣いた。

他ルーターの実装を研究したり、以前挫折した高度な木構造についての勉強等やって改善につなげていきたい。

まとめ

Goではベンチマークやプロファイリングが簡単にできる
推測するな、計測せよ
小手先の改善では大きな成果は出づらい（それはそう）

Goで始めるコードのパフォーマンス改善

Goで始めるコードのパフォーマンス改善

前提知識

パフォーマンス改善のアプローチ

Benchmark

Profiling

実践

ベンチマーク

プロファイリング

チューニング

効果測定

ベンチーマーク

プロファイリング

さらなる改善

まとめ

参考