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

bmf-san パフォーマンス
#Golang

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

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

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

前提知識

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

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

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

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

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

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

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

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

Benchmark

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

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

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

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

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

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

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

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

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

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

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

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

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

Profiling

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

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

ベンチマーク

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

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

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

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

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

出力結果は以下の通り。

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

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

プロファイリング

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

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

Graphの出力結果。 pprof_graph

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

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

pprof_top

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

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

pprof_source

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

チューニング

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

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

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

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

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

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

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

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

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

効果測定

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

ベンチーマーク

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

プロファイリング

pprofのGraph。

pprof_graph_after

pprofのTop。

pprof_top_after

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

さらなる改善

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

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

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

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

bmf-san/go-router-benchmark

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

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

まとめ

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

参考