効率の悪い append は prealloc という linter で見つけることができるぞ

本稿は、[Go2 Advent Calendar 2019](https://qiita.com/advent-calendar/2019/go2) の 2 日目の記事です。
[@pankona](https://github.com/pankona) という名前でやっています。よろしくお願いします！

`prealloc` という linter について紹介します。

## 効率の悪い append

さて、Go を書いていると一度はやってしまうであろう "あまりよくないプラクティス" のひとつとして、いわゆる "append の連打" があるかと思います。
`append` を何度も何度も繰り返すようなコードは、ひらたく言えば "処理効率の悪いコード" になってしまう可能性があります。

```go
package main

// append を繰り返すことによって効率が悪くなってしまう例

func AppendAndAppend() {
    var a []int

    // 1000 万回の append が行われていく
    for i := 0; i < 10000000; i++ {
        a = append(a, i)
    }
}
```

上記のスニペットには、以下のような問題点・改善点があります。

- `append` の際、配列の `cap` が足りないときは内部配列が確保しなおされます。内部配列の確保し直しは比較的コストの高い処理であり、何度も行うと時間が掛かります。
- 可能限り少ない回数で済ますのが (できれば一度で済ますのが)、処理効率の観点では良いと考えられます。

この例の場合は繰り返しの回数 (＝作られる配列の長さ) が分かっているので、以下のように書き換えることができます。

```go
package main

// append による内部配列の再確保を抑える書き方

func MakeEnoughLen() {
    // make にて len をあらかじめ確保しておく
    a := make([]int, 10000000)

    for i := 0; i < 10000000; i++ {
        // append せずに直接代入する
        a[i] = i
    }
}
```

あるいは、以下のように書いても同等の処理速度が得られそうです。

```go
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`](https://github.com/golangci/golangci-lint) です。
`golangci-lint` は、最大で 40 個弱くらい (2019/12 現在) の Go の linter を一気に実行してくれる便利ツールです。

`golangci-lint` の中には `prealloc` と呼ばれる linter が含まれています (ただし、デフォルトでは無効になっています) 。

`prealloc` は、前項で紹介したような "ループ内で `append` を行っている、かつ繰り返し回数が明らかである" ような **append にまつわる効率を改善できそうなコード** を検出します。

まず、デフォルトで無効にされてしまっている `prealloc` を有効にするための `golangci-lint` の設定ファイルを紹介します。

```yaml
# prealloc はデフォルトで無効なので、設定ファイルで有効にする
# prealloc を有効にするような golangci-lint の設定ファイルはたとえば以下

linters:
  enable:
    - prealloc

linters-settings:
  prealloc:
    simple: true
    range-loops: true
    for-loops: true
```

いざ、以下のソースコードを実験台にしてみます。

```go
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 に怒られることはなくなりました。

```go
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](https://github.com/golangci/golangci-lint) の 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](https://qiita.com/shibukawa) さんです！