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

Golang パフォーマンスチューニング

More than 3 years have passed since last update.

この記事は Go Advent Calendar 2014 17 日目の記事です。

Go におけるパフォーマンスチューニングの話をします。
これらは DencoKocha などでのパフォーマンスチューニングの経験などから得た知見です。
処理系の話ではありませんのでご了承ください。

前提

  • プロファイリングを取った後、じゃあどうやって最適化するかというところの話です

    「推測するな、計測せよ」

  • アルゴリズムやデータ構造は最適なものが選択されていると仮定します

    小手先の最適化を行うよりアルゴリズム自体を変えたほうが圧倒的に良くなります。

  • この記事の各ベンチマークは Go 1.4 (go version go1.4 linux/amd64)で下記のコマンドにて取っています

    go test -run NONE -bench . -benchmem
    
  • ベンチマークの結果は環境に左右されるので、あくまで筆者の環境での結果です

メモリのアロケーション回数を減らす

Go のコードの中で、パフォーマンス低下の割合が大きいのがメモリのアロケーションです。
つまり、メモリのアロケーション回数を減らすとパフォーマンスが大幅に改善します。

package bench_test

import "testing"

func BenchmarkMemAllocOndemand(b *testing.B) {
    n := 10
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s := make([]string, 0)
        for j := 0; j < n; j++ {
            s = append(s, "alice")
        }
    }
}

func BenchmarkMemAllocAllBeforeUsing(b *testing.B) {
    n := 10
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s := make([]string, 0, n)
        for j := 0; j < n; j++ {
            s = append(s, "alice")
        }
    }
}
BenchmarkMemAllocOndemand        1000000              1953 ns/op             496 B/op         5 allocs/op
BenchmarkMemAllocAllBeforeUsing  3000000               571 ns/op             160 B/op         1 allocs/op

要素数が事前にわかっている場合には append を使わない

スライスに要素を詰めていく場合、append で追加していくよりインデックスを使ってスライスに代入してくほうが速くなります。

package bench_test

import "testing"

func BenchmarkFillSliceByAppend(b *testing.B) {
    n := 100
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s := make([]int, 0, n)
        for j := 0; j < n; j++ {
            s = append(s, j)
        }
    }
}

func BenchmarkFillSliceByIndex(b *testing.B) {
    n := 100
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s := make([]int, n)
        for j := 0; j < n; j++ {
            s[j] = j
        }
    }
}
BenchmarkFillSliceByAppend        500000              2694 ns/op             896 B/op         1 allocs/op
BenchmarkFillSliceByIndex         500000              2487 ns/op             896 B/op         1 allocs/op

例えば、channel を使わない

channel を使った排他制御より sync.Mutexsync.RWMutex を使ったほうが速くなります。

package bench_test

import (
    "sync"
    "testing"
)

func BenchmarkExclusiveWithChannel(b *testing.B) {
    c := make(chan struct{}, 1)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        c <- struct{}{}
        // do something.
        <-c
    }
}

func BenchmarkExclusiveWithMutex(b *testing.B) {
    mu := new(sync.Mutex)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        mu.Lock()
        // do something.
        mu.Unlock()
    }
}
BenchmarkExclusiveWithChannel   20000000                70.2 ns/op             0 B/op         0 allocs/op
BenchmarkExclusiveWithMutex     100000000               21.1 ns/op             0 B/op         0 allocs/op

同様に同期処理も sync.WaitGroup を使ったほうが速くなります。

package bench_test

import (
    "sync"
    "testing"
)

func BenchmarkSyncWithChannel(b *testing.B) {
    n := 10
    c := make(chan struct{}, n)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        for j := 0; j < n; j++ {
            go func() {
                // do something.
                c <- struct{}{}
            }()
        }
        for j := 0; j < n; j++ {
            <-c
        }
    }
}

func BenchmarkSyncWithWaitGroup(b *testing.B) {
    n := 10
    var wg sync.WaitGroup
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(n)
        for j := 0; j < n; j++ {
            go func() {
                // do something.
                wg.Done()
            }()
        }
        wg.Wait()
    }
}
BenchmarkSyncWithChannel          500000              3511 ns/op             160 B/op        10 allocs/op
BenchmarkSyncWithWaitGroup        500000              3086 ns/op             164 B/op        11 allocs/op

例えば、関数(メソッド)を呼ばない

Go は関数やメソッドの呼び出しが遅いです。数行程度のものであればコンパイラがインライン展開してくれるのですが、そうでないものが遅いです。
Denco のコード を例に上げると、再帰呼び出しにしたほうがすっきり書けるところを、敢えて goto を使うようにしてパフォーマンスを上げています。

正規表現はスイスアーミーナイフではない

Go の regexp パッケージは Ruby や Python などとは異なり、必ず線形時間で処理が完了するアルゴリズムを採用しています。

https://groups.google.com/forum/#!msg/golang-nuts/6d1maef4jQ8/yg4NY5qRtsMJ

しかし、その代わりにとても遅くなってしまっているので、他の言語のように気軽に使ってしまうとかなりパフォーマンスが落ちてしまいます。
ですので、読みやすさなどとのトレードオフにはなりますが、本当に速度が必要な時には文字列のマッチングや置換などはできるだけ自前で書いたほうが懸命です。

package bench_test

import (
    "regexp"
    "testing"
)

func BenchmarkStringMatchWithRegexp(b *testing.B) {
    s := "0xDeadBeef"
    re := regexp.MustCompile(`^0[xX][0-9A-Fa-f]+$`)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        re.MatchString(s)
    }
}

func BenchmarkStringMatchWithoutRegexp(b *testing.B) {
    s := "0xDeadBeef"
    isHexString := func(s string) bool {
        if len(s) < 3 || s[0] != '0' || s[1] != 'x' && s[1] != 'X' {
            return false
        }
        for _, c := range s[2:] {
            if c < '0' || '9' < c && c < 'A' || 'F' < c && c < 'a' || 'f' < c {
                return false
            }
        }
        return true
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        isHexString(s)
    }
}
BenchmarkStringMatchWithRegexp      2000000               643 ns/op             0 B/op         0 allocs/op
BenchmarkStringMatchWithoutRegexp   30000000               55.0 ns/op           0 B/op         0 allocs/op

番外編 1

パフォーマンスチューニングとは違いますが、goroutine を起動するにもコストがかかるので、何でも go を付ければ速くなるということはなく、軽い処理であればあるほどシーケンシャルに処理したほうが速くなります。

package bench_test

import (
    "sync"
    "testing"
)

func BenchmarkGoroutine(b *testing.B) {
    n := 10
    var wg sync.WaitGroup
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(n)
        for j := 0; j < n; j++ {
            go func() {
                wg.Done()
            }()
        }
        wg.Wait()
    }
}

func BenchmarkSequential(b *testing.B) {
    n := 10
    var wg sync.WaitGroup
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        wg.Add(n)
        for j := 0; j < n; j++ {
            func() {
                wg.Done()
            }()
        }
        wg.Wait()
    }
}
BenchmarkGoroutine        500000              3097 ns/op             164 B/op       11 allocs/op
BenchmarkSequential     10000000               224 ns/op               0 B/op        0 allocs/op

これがどの程度のしきい値で逆転するのかは興味があるところです。

番外編 2

for ループを回す際に条件式の部分に直接 len() を書いても、事前に変数に入れたものを使っても有意な差は出ません。

package bench_test

import "testing"

func BenchmarkLenDirect(b *testing.B) {
    n := 1000
    s := make([]string, n)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        for j := 0; j < len(s); j++ {
            _ = s[j]
        }
    }
}

func BenchmarkLenCached(b *testing.B) {
    n := 1000
    s := make([]string, n)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        for j, length := 0, len(s); j < length; j++ {
            _ = s[j]
        }
    }
}
BenchmarkLenDirect       1000000              1221 ns/op               0 B/op        0 allocs/op
BenchmarkLenCached       1000000              1221 ns/op               0 B/op        0 allocs/op

まとめ

こういう記事を鵜呑みにせず君だけのベンチマークを取ろう!

* この記事で使用したベンチマークは https://github.com/naoina/go-adventcalendar-2014-bench にあります。

Why do not you register as a user and use Qiita more conveniently?
  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
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