Help us understand the problem. What is going on with this article?

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

本稿は、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 さんです!

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした