Go の Generator を channel と closure で速度比較(または Go でのアトミック処理イディオム)

追記

この記事は元々 Go のイディオムとして、いわゆるジェネレータの実装がどうできるのかを軽い気持ちで書いただけで、速いから「Closure を使いましょう」などと一言も言ってなかったのですが、一方が channel であったため原子性についての言及がいくつかありました。

自分としては、ローカルのちょっとしたツール(shell の代わりくらい) の中で使ってただけなので、並行性には言及するつもりがそもそも無かったのですが、自分もそうした前提を書いていなかったのにも原因があります。

例えばこの記事が「グローバルシーケンス」の実装例として参考にされ Web アプリにでもコピペされて、バグの原因になったりでもしたらマズイので大幅に追記します。 (正直ロックを使った排他制御はあまり得意では無いですが。。)

Intro

無限に連番を生成するロジックをジェネレータとして組むときに、 Go の場合は二つの方法が考えられます。 Closure を使う方法と Channel を読みだす方法です。

Closure (goroutine unsafe)

まずは Closure を用いた単純な実装をしてみます。

func Closure() func() int {
    i := 0
    return func() int {
        i = i + 1
        return i
    }
}

今回のベンチマークではこの実装が最速です(後述)。 ただし、この実装は複数の Goroutine から呼び出される場合、インクリメントと取得の部分がクリティカルセクションになっています。 スレッドモデルの場合 "スレッドセーフ" といいますが、 Go ではスレッドではないので "Goroutine セーフ" と呼ぶことにします。この例は Goroutine セーフではない実装です。

Closure (mutex locked)

クリティカルセクションを守る方法としては、ロックを取る方法が多くの言語で使われてきました。 Go では、 sync.Mutex を用いてそれが実現できます。

func MutexClosure() func() int {
    var mutex = new(sync.Mutex)
    i := 0
    return func() int {
        mutex.Lock()
        defer mutex.Unlock()
        i = i + 1
        return i
    }
}

sync.Mutex を用いると Lock() と Unlock() を用いて排他制御が実行できます。 操作の前に Lock() を取得し、defer を用いて関数終了時に Unlock() を実行しています。

一般的に、ロックを用いた排他制御を実施する場合、必ずデッドロックに注意する必要があります。 上記の実装では使っていませんが、 Lock()、 Unlock() などが別の Goroutine で実行されていたり、その間に Channel による同期などを別途行っているような場合は特に注意が必要です。

おまけ Closure (atomic increment)

より低レベルの操作については、 sync/atomic パッケージも提供されています。 例えば CAS やアトミックなインクリメントなどが提供されています。

今回の場合、ここまでは int で実装していますが、 int の API はないために int32 を使うことを許容できるなら、今回のクリティカルセクションのロジックが単なるインクリメントであることから、 AddInt32 を用いることができるかも。と思いましたが、これは return がロックされていないのでダメですね。 これを使うなら、ユーザランドでグローバルにある値を直接インクリメントすればいいのかな。

func AtomicClosure() func() int32 {
    var n int32 = 0
    var i int32 = 1
    return func() int32 {
        return atomic.AddInt32(&n, i)
    }
}

また、このパッケージのドキュメント冒頭には以下の説明があります。

These functions require great care to be used correctly.
Except for special, low-level applications,
synchronization is better done with channels or the facilities of the sync package.
Share memory by communicating; don't communicate by sharing memory.

要するに、普通にアプリやツールを書くような用途での使用には推奨されておらず、(明示はされていませんが)より高度な実装で必要なケースに向けて提供されています。

Channel

sync パッケージを全く使用しなくてもアトミックな処理を実装することができます。 Go には channel という言語に組み込まれた MQ のような機能があり、 この channel を使用して、メッセージングにより同期をとる方法です。

func Channel() <-chan int {
    ch := make(chan int)
    go func() {
        i := 1
        for {
            ch <- i
            i = i + 1
        }
    }()
    return ch
}

この実装では外側の Channel() は読み取り専用の channel を返しており、これを持つ側は channel の読み出しを行うことで数値を取得できます。 この i は Channel() 実行時に生成される goroutine の中にしか存在せず、その goroutine と唯一繋がった channel に対しても書込することはできないため、外からは一切操作できません。

また、 channel には make 時に buffer を設定していないため、当時に一つの値しかそこを通ることができません。 つまり、channel に値があればそれが読み出されるまで書き込みはブロックし、 channle に値がなければ書き込まれるまでは読み出しはブロックします。

大量の goroutine がこの channel を保持していて、同時に読み出しでブロックしていても、書き込まれた値は一番最初に読み出しブロックに入った goroutine にしか読み出されません。

こうして、ロックを一切使わずにアトミックな処理が実現できるのです。

ベンチ

ベンチマークを取ってみます。

func BenchmarkClosure(b *testing.B) {
    cl := Closure()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        cl()
    }
}

func BenchmarkMutexClosure(b *testing.B) {
    cl := MutexClosure()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        cl()
    }
}

func BenchmarkChannel(b *testing.B) {
    ch := Channel()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        <-ch
    }
}

実行結果

Mac Book Air (OSX 10.7.5) 1.6 GHz Intel Core i5 Memory 4GB

$ go test -bench .
PASS
BenchmarkClosure        100000000    11.5 ns/op
BenchmarkMutexClosure   50000000     35.3 ns/op
BenchmarkChannel        5000000      251 ns/op
ok  /path/to/bench  6.747s

ベンチマークの実行回数は、ベンチマークソースの中の b.N の値の部分になり、 関数の実行時間に応じて go test コマンドが適宜調整してくれます。 いずれも十分回数実行されているとみなし、 ns/op に注目して一実行あたりの平均実行時間を比較します。 (数回実行したところ、だいたい同じでした)

implimentation	time (ns/op)	ratio
closure	11.5	1
mutex	35.3	3.07
channel	251	21.8

最後の列が、 closure 実装を 1 とした場合の比率です。 (書き直す前は channel は 50 倍だったのですが、 channel の速度は変わらないのに closure の速度が何故が落ちたので、 20 倍に縮まりました。 元々の記事は、この結果が予想していたよりも大きかったなぁという趣旨でした。)

考察

ちょっとしたツールなどで、 1 つの Goroutine の中でしか使わないような実装であればどれでも構いませんが、 複数の Goroutine が共有する、いわゆるグローバルシーケンサを実装するような場合には、今回の Closure 実装は使えません。

同じことは、シーケンサでなくともグローバルカウンタや、もっと広く言えば複数の goroutine で共有するロジックでは共通です。 しかし、途中で解説したように sync/atomic は、理由がない限り積極的に使うべきでは無いでしょう。

mutex と channel の実装については、今回 7 倍の速度差が出ていますが、 mutex にはロックを伴う排他制御につきものな種々の難しさが、他の言語同様に伴います。

sync/atomic のドキュメントでも出ていた以下はその選択の指針になります。

Share memory by communicating;
don\'t communicate by sharing memory.

これは、意訳すると「メモリの共有(sync) ではなく、メッセージング(channle) でデータの共有をしましょう」という意味で、 Go はこうしたメッセージングによるイディオムを強く推奨しています。

一般的にロックでの排他制御は難易度が高く、デバッグもしづらいという経験則があり、メッセージングを用いた実装がシンプルで堅牢かつ柔軟なプログラミングが可能であるという理由からです。

同様な主張を元にした、 Go の並行処理については以下の様にドキュメント群でも散々言及されています。

• http://golang.org/doc/effective_go.html#sharing
• http://golang.org/doc/faq#What_operations_are_atomic_What_about_mutexes

一方で channel も、読み出しが競合してデッドロックするなど、慣れないと上手く書けない場合はあるでしょう。 そうした場合は、この辺が参考になると思います。

• http://talks.golang.org/2012/concurrency.slide
• http://talks.golang.org/2013/bestpractices.slide#27

過去にこのブログでも言及しています。

• http://jxck.hatenablog.com/entry/20130623/1371999576

結論

• Goroutine をまたがないで、とにかく速度が欲しい場合: Closure
• 複数の Goroutine から使い、ロックのプログラミングに慣れている場合: Mutex
• 複数の Goroutine から使い、 Go の思想に則りたい、プログラムをシンプルにしたいetc: Channel
• 筆者のおすすめ: Channel
• 前提を書かずに記事を書かない

おまけ

実は Slice や Map の操作もアトミックではありません。 なので、今回行ったようなことを用いて、 Slice や Map の操作を自分でアトミックにする必要があります。 それを含むロジック全体をアトミックにすることもできますが、単体の追加/削除などをアトミックにするライブラリをいくつか作っているので、そのうちそれを紹介します。

ソースコード

使用したコードは以下にあります。

https://gist.github.com/Jxck/9184764

Go でベンチマーク

Intro

Go にはベンチマークを取る仕組みが標準で備わっています。

テストを書く仕組みも標準で備わっており、
testing モジュールと go test コマンドで行いますが、
ベンチも同じような形で実行することができます。

今回は簡単なベンチ取り方を紹介します。
テストについては、そのうちちゃんと触れます。

参考ソースとして、こちらを使います。

https://github.com/Jxck/swrap

対象のコード

例えば以下のようなコードがあって、そのベンチを取るとします。

// swrap.go

type SWrap []byte

func (sw *SWrap) Add(a byte) {
	*sw = append(*sw, a)
}

func (sw *SWrap) Len() int {
	return len(*sw)
}

Slice にメソッドを生やしただけです。

ベンチマーク関数

ベンチマークは、 *_test.go ファイルに書きます。
関数名は Bench で始め、引数として *testing.B を渡す関数として定義します。
(このへんはテストと同じです。)

// swrap_test.go

import (
	"testing"
)

func BenchmarkAdd(b *testing.B) {
	for i := 0; i < b.N; i++ {
		sw := New(Fixture())
		sw.Add(0xFF)
	}
}

func BenchmarkLen(b *testing.B) {
	sw := New(Fixture())
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		sw.Len()
	}
}

b.N が勝手に設定されるので、それをループの条件とするだけです。
ループにかかる時間を測るので、ループに入る前の準備処理などに時間がかかる場合は、
ループの前に b.ResetTimer() を呼ぶと準備処理分を引くことができます。

実行方法

実行は go test にオプションを追加するだけです。($GOPATH を通しておいて下さい)

$ go test -bench Add   # Add とつくものだけ実行
$ go test -bench .     # 全て実行

全ての実行例はこんな感じです。(インデントだけ整形済み)

$ go test -bench .
PASS
BenchmarkNew      2000000000   0.64 ns/op
BenchmarkBytes    2000000000   1.09 ns/op
BenchmarkLen      2000000000   1.23 ns/op
BenchmarkAdd      5000000      334 ns/op
BenchmarkMerge    10000000     254 ns/op
BenchmarkDelete   20000000     148 ns/op
BenchmarkCompare  50000000     32.8 ns/op
BenchmarkPush     5000000      354 ns/op
BenchmarkPop      10000000     114 ns/op
BenchmarkShift    10000000     234 ns/op
BenchmarkUnShift  20000000     109 ns/op
BenchmarkReplace  5000000      614 ns/op
ok    swrap 27.847s

実行回数が違うのは、 b.N の値が変わっているからですね。
この b.N は直接指定するのではなく、ベンチの実行時間からの逆算です。
デフォルトは 1 秒間実行しているようです。
この実行時間は -benchtime で指定できます。
十分な時間を指定し、性能自体は ns/op で見るのが良さそうです。

benchmem

"-benchmem" オプションをつけるとメモリアロケート回数がわかります。
変数をポインタに変更するなどの改善ポイントが見つけられます。

PASS
BenchmarkLen	2000000000	0.95 ns/op	0 B/op	0 allocs/op
BenchmarkAdd	 5000000	370 ns/op	48 B/op	2 allocs/op

比較

実はこの結果を比較するツールがひっそりと同梱されています。

まったくいいサンプルが無いんだけど手元にあったもので、
例えば以下の様な超地味なチューニングに成功したとします。

PASS
BenchmarkNew	2000000000	0.47 ns/op	0 B/op	0 allocs/op
ok  	swrap	1.000s

PASS
BenchmarkNew	2000000000	0.44 ns/op	0 B/op	0 allocs/op
ok  	swrap	0.954s

それぞれ before after で保存して
これを misc 以下にある benchcmp に渡します。

$ $GOROOT/misc/benchcmp before after
benchmark       old ns/op    new ns/op    delta
BenchmarkNew            0            0   +6.82%

こうした値をパッチに添えて PR とかすると話が速くていいかもしれませんね。

オプション

オプションを簡単(適当)に訳しておきます。
(まだ使ったことがないものが多いです)

http://golang.org/cmd/go/#hdr-Description_of_testing_flags

-bench regexp       対象の指定
-benchmem           メモリアロケーションの表示
-benchtime          ベンチ実行時間
-blockprofile       goroutine のブロックプロファイルを出力
-blockprofilerate   runtime.SetBlockProfileRate の値を指定
-cpu                GOMAXPROCS の値を指定
-cpuprofile         CPU プロファイルを出力
-memprofile         メモリプロファイルを出力
-memprofilerate     runtime.MemProfileRate の値を指定
-parallel           並列実行の指定(デフォルトは GOMAXPROCS)
-run                テストと example の実行対象指定
-short              時間を短縮して簡易実行
-timeout            タイムアウト
-v                  詳細出力