本稿は、Go2 Advent Calendar 2019 の 2 日目の記事です。
@pankona という名前でやっています。よろしくお願いします！
prealloc という linter について紹介します。
効率の悪い append
さて、Go を書いていると一度はやってしまうであろう "あまりよくないプラクティス" のひとつとして、いわゆる "append の連打" があるかと思います。
append を何度も何度も繰り返すようなコードは、ひらたく言えば "処理効率の悪いコード" になってしまう可能性があります。
package main
// append を繰り返すことによって効率が悪くなってしまう例
func AppendAndAppend() {
var a []int
// 1000 万回の append が行われていく
for i := 0; i < 10000000; i++ {
a = append(a, i)
}
}
上記のスニペットには、以下のような問題点・改善点があります。
-
appendの際、配列のcapが足りないときは内部配列が確保しなおされます。内部配列の確保し直しは比較的コストの高い処理であり、何度も行うと時間が掛かります。 - 可能限り少ない回数で済ますのが (できれば一度で済ますのが)、処理効率の観点では良いと考えられます。
この例の場合は繰り返しの回数 (＝作られる配列の長さ) が分かっているので、以下のように書き換えることができます。
package main
// append による内部配列の再確保を抑える書き方
func MakeEnoughLen() {
// make にて len をあらかじめ確保しておく
a := make([]int, 10000000)
for i := 0; i < 10000000; i++ {
// append せずに直接代入する
a[i] = i
}
}
あるいは、以下のように書いても同等の処理速度が得られそうです。
package main
// append による内部配列の再確保を抑える書き方
func MakeEnoughCap() {
// make にて cap をあらかじめ確保しておく
a := make([]int, 0, 10000000)
for i := 0; i < 10000000; i++ {
// append を呼ぶが、cap が十分に確保されているので内部配列の再確保は行われない
a = append(a, i)
}
}
上記の 3 関数を Benchmark すると、以下のような結果が得られます。
BenchmarkAppendAndAppend-12 58911350 18.0 ns/op 42 B/op 0 allocs/op
BenchmarkMakeEnoughLen-12 624822230 3.49 ns/op 8 B/op 0 allocs/op
BenchmarkMakeEnoughCap-12 618240639 3.91 ns/op 8 B/op 0 allocs/op
最初にあげた例 (AppendAndAppend 関数) がダントツで遅いのがお分かりいただけるかと思います…！
golangci-lint で検出できるよ！ (ただし要有効化)
さて、効率の悪い append があるのは分かりましたが、これらは人間が目ヂカラを使って検出し、手ずから直していく必要があるのでしょうか。
否、実はこのパターンは lint によって発見することができます…！(手ずから直す必要はある)
取り出だしたるは、みなさんご存知 golangci-lint です。
golangci-lint は、最大で 40 個弱くらい (2019/12 現在) の Go の linter を一気に実行してくれる便利ツールです。
golangci-lint の中には prealloc と呼ばれる linter が含まれています (ただし、デフォルトでは無効になっています) 。
prealloc は、前項で紹介したような "ループ内で append を行っている、かつ繰り返し回数が明らかである" ような append にまつわる効率を改善できそうなコード を検出します。
まず、デフォルトで無効にされてしまっている prealloc を有効にするための golangci-lint の設定ファイルを紹介します。
# prealloc はデフォルトで無効なので、設定ファイルで有効にする
# prealloc を有効にするような golangci-lint の設定ファイルはたとえば以下
linters:
enable:
- prealloc
linters-settings:
prealloc:
simple: true
range-loops: true
for-loops: true
いざ、以下のソースコードを実験台にしてみます。
package main
func AppendAndAppend() {
var a []int
for i := 0; i < 10000000; i++ {
a = append(a, i)
}
}
件の設定ファイルを置いた状態で golangci-lint を実行すると、以下のような指摘があがります。
$ golangci-lint run
main.go:4:2: Consider preallocating `a` (prealloc)
var a []int
a は事前に確保したほうがええやろ、と怒られました。なるほど便利…。
指摘を踏まえて、以下のように十分な cap を確保するようにしたところ、linter に怒られることはなくなりました。
package main
func AppendAndAppend() {
a := make([]int, 0, 10000000)
for i := 0; i < 10000000; i++ {
a = append(a, i)
}
}
なるほど便利…。
注意事項
prealloc という便利な linter について紹介しましたが、
実は golangci-lint の README.md の prealloc の項には以下のように注意書きがされています。
prealloc:
# XXX: we don't recommend using this linter before doing performance profiling.
# For most programs usage of prealloc will be a premature optimization.
要約すると、
- この linter を使う前に、まずパフォーマンスのプロファイリングをするのが先でしょう
- prealloc を使うのは多くの場合において早すぎる最適化だろう
とのことであります。わかる。
個人的には、常に append を効率良く書いておくことは早すぎる最適化の話とは違うんではないかと思わないでもないですが、
そもそも Go の append が雑な書き方でも割と速いこともあり、気にするのは後にしても良かろうというのはそのとおりかもしれません。
まとめ
prealloc という linter について紹介しました。早すぎる最適化はいかがでしょうか…！
気になった方は、ぜひちょいと試してみたらいいんじゃないかなと思います！Let's give it a try！
Go2 Advent Calendar 2019、3 日目は shibukawa さんです！