Go Advent Calendar 2015 その3 11日目です。その3まであるなんてGo大人気ですね。
Gopherというのはいろいろな人がいてLLからGoへ、という方も多いかと思います。
LLではそもそも全てがオブジェクトだったりで話題になりませんが、よりマシンに近く変態的に速度を重視される方が多いC++では例えば仮想関数や実行時キャストのコストが議論になります。
Goにおいてこういう多態性はインタフェースで表現されます。結論からいうと、 Goのインタフェースにもそれなりのコストがあります。 なので極限までパフォーマンスを要求される場合には 例えばインターフェースを使わない というも選択肢に入ってくるのではないかと思います。
Go言語におけるインタフェースの内部表現
さて、Goはブートストラップ化(言語処理系をその言語自身で実装する)を進めており、1.5ではGoのコンパイラ、ランタイムはほぼほぼGoで実装されています。ということはインターフェースもGoで実装されているはずですね。
Goのインタフェースは２個のポインタを持った struct です。例えば、 reflect/value.go では以下のようなコードがあります。
// emptyInterface is the header for an interface{} value.
type emptyInterface struct {
typ *rtype
word unsafe.Pointer
}
// nonEmptyInterface is the header for a interface value with methods.
type nonEmptyInterface struct {
// see ../runtime/iface.go:/Itab
itab *struct {
ityp *rtype // static interface type
typ *rtype // dynamic concrete type
link unsafe.Pointer
bad int32
unused int32
fun [100000]unsafe.Pointer // method table
}
word unsafe.Pointer
}
コメントに書かれているように実態は runtime/iface.go ですがこちらのほうが簡略化されていてわかりやすいでしょう。1個目のポインタは 「空のインタフェース( iterface{} )」(これを eface という)の場合、型情報、そうでない場合(これを iface という)の場合 itab と呼ばれるC++における仮想テーブルのようなものです。2個目に値が格納されます。2個目はどちらもポインタであることに注意してください。
インターフェース経由のメソッド呼び出し
ここで、インターフェースを使用するとどの程度パフォーマンスペナルティがあるのか、様々なケースで見てみます。
まずは、直接メソッドを呼び出すのと、インタフェース経由で呼び出す場合の違いを見てみましょう。
type MyError struct{}
func (e *MyError) Error() string { return "error" }
func BenchmarkNoInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
err := &MyError{}
err.Error()
}
}
func BenchmarkInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
var err error = &MyError{}
err.Error()
}
}
結果は以下のようになります。10倍程度遅くなります。単位が単位なので微々たる違いですが極限までパフォーマンスを追求したい場合は考慮しておいたほうがいいかもしれませんね。
BenchmarkNoInterface 2000000000 0.73 ns/op
BenchmarkInterface 200000000 9.56 ns/op
しかし実はこの中には *MyError を error インタフェースに変換するコストも含まれていて、そのコストを除くと5倍くらいの遅さです。次はそのインタフェースへの変換コストを詳しく見ていこうと思います。
インターフェースへの変換コスト(非ポインタ型)
Goにおけるインタフェースの変換時はC++におけるキャストよりも複雑なことが発生します。
Goでは「なんでも」を表すために interface{} を使いますね。 int などの組み込み型かつ非ポインタ型を interface{} として処理するとなにが起こるでしょうか？以下のようにフィボナッチを計算させてみます。
func IntFibNoInterface(n int) int {
if n < 2 {
return n
}
return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
}
func IntFibInterface(o interface{}) interface{} {
n := o.(int)
if n < 2 {
return o
}
return IntFibInterface(n-1).(int) + IntFibInterface(n-2).(int)
}
func BenchmarkNoInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibNoInterface(20)
}
}
func BenchmarkInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibInterface(20)
}
}
結果は以下。40 - 50倍くらいおそくなりますね。これを見ると気軽にインタフェースを使いたくなくなるかもしれません。
BenchmarkNoInterface 30000 57938 ns/op 0 B/op 0 allocs/op
BenchmarkInterface 500 2448250 ns/op 525376 B/op 32836 allocs/op
はじめに書いたように、インタフェースは ポインタとして値を保持します 。 そのためコード上アロケートしていなくても、内部的に int をアロケートしそこに値をコピーせねばなりません。
どのような処理が実行されたか、プロファイルを見てみましょう。
1.46s of 1.46s total ( 100%)
Showing top 20 nodes out of 35 (cum >= 0.01s)
flat flat% sum% cum cum%
0.37s 25.34% 25.34% 0.68s 46.58% runtime.mallocgc
0.26s 17.81% 43.15% 1.44s 98.63% 12.IntFibInterface
0.20s 13.70% 56.85% 0.20s 13.70% runtime.memmove
0.16s 10.96% 67.81% 0.16s 10.96% runtime.mSpan_Sweep.func1
0.12s 8.22% 76.03% 0.96s 65.75% runtime.convT2E
0.11s 7.53% 83.56% 0.31s 21.23% runtime.typedmemmove
0.10s 6.85% 90.41% 0.26s 17.81% runtime.heapBitsSweepSpan
0.05s 3.42% 93.84% 0.22s 15.07% runtime.assertE2T
0.02s 1.37% 95.21% 0.70s 47.95% runtime.newobject
0.02s 1.37% 96.58% 0.02s 1.37% runtime.prefetchnta
0.01s 0.68% 97.26% 0.01s 0.68% runtime.(*gcControllerState).findRunnableGCWorker
0.01s 0.68% 97.95% 0.01s 0.68% runtime.lock
0.01s 0.68% 98.63% 0.01s 0.68% runtime.mSpanList_InsertBack
0.01s 0.68% 99.32% 0.01s 0.68% runtime.xadd64
0.01s 0.68% 100% 0.01s 0.68% runtime.xchg
0 0% 100% 1.44s 98.63% 12.BenchmarkInterface
0 0% 100% 0.01s 0.68% runtime.GC
0 0% 100% 0.01s 0.68% runtime.deductSweepCredit
0 0% 100% 0.01s 0.68% runtime.gc
0 0% 100% 0.01s 0.68% runtime.gc.func4
非ポインタ型のインターフェースへの変換コスト
では、ということで自分でアロケーションしてみましょう。 int ではなく *int を使ってみます。
func IntFibNoInterface(n int) int {
if n < 2 {
return n
}
return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
}
func IntFibPointer(i *int) *int {
n := *i
if n < 2 {
return i
}
a1 := new(int)
*a1 = n - 1
a2 := new(int)
*a2 = n - 2
v1 := IntFibPointer(a1)
v2 := IntFibPointer(a2)
ret := new(int)
*ret = *v1 + *v2
return ret
}
func IntFibInterface(o interface{}) interface{} {
n := *(o.(*int))
if n < 2 {
return o
}
a1 := new(int)
*a1 = n - 1
a2 := new(int)
*a2 = n - 2
v1 := IntFibInterface(a1).(*int)
v2 := IntFibInterface(a2).(*int)
ret := new(int)
*ret = *v1 + *v2
return ret
}
func BenchmarkNoInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibNoInterface(20)
}
}
func BenchmarkPointer(b *testing.B) {
for i := 0; i < b.N; i++ {
a := new(int)
*a = 20
IntFibPointer(a)
}
}
func BenchmarkInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
a := new(int)
*a = 20
IntFibInterface(a)
}
}
結果は以下のようになります。20-30倍というところでしょうか。こちらのほうがコードだけ見ると遅そうですが、なんと int を使った場合より速いのです。そして、インタフェースへの変換コストは少ない、ということがわかります。
BenchmarkNoInterface 30000 55558 ns/op 0 B/op 0 allocs/op
BenchmarkPointer 1000 1297598 ns/op 525376 B/op 32836 allocs/op
BenchmarkInterface 1000 1357172 ns/op 525376 B/op 32836 allocs/op
1.54s of 1.54s total ( 100%)
Showing top 20 nodes out of 37 (cum >= 0.01s)
flat flat% sum% cum cum%
0.75s 48.70% 48.70% 1.24s 80.52% runtime.mallocgc
0.22s 14.29% 62.99% 0.22s 14.29% runtime.mSpan_Sweep.func1
0.16s 10.39% 73.38% 0.38s 24.68% runtime.heapBitsSweepSpan
0.14s 9.09% 82.47% 1.38s 89.61% runtime.newobject
0.11s 7.14% 89.61% 1.49s 96.75% 12.IntFibInterface
0.08s 5.19% 94.81% 0.08s 5.19% runtime.prefetchnta
0.02s 1.30% 96.10% 0.02s 1.30% runtime.heapBitsForObject
0.01s 0.65% 96.75% 0.01s 0.65% runtime.(*bucket).mp
0.01s 0.65% 97.40% 0.01s 0.65% runtime.atomicload64
0.01s 0.65% 98.05% 0.41s 26.62% runtime.mCentral_CacheSpan
0.01s 0.65% 98.70% 0.03s 1.95% runtime.scanblock
0.01s 0.65% 99.35% 0.01s 0.65% runtime.schedule
0.01s 0.65% 100% 0.01s 0.65% runtime.xchg
0 0% 100% 1.49s 96.75% 12.BenchmarkInterface
0 0% 100% 0.04s 2.60% runtime.backgroundgc
0 0% 100% 0.01s 0.65% runtime.deductSweepCredit
0 0% 100% 0.04s 2.60% runtime.gc
0 0% 100% 0.02s 1.30% runtime.gc.func1
0 0% 100% 0.01s 0.65% runtime.gc.func3
0 0% 100% 0.01s 0.65% runtime.gc.func4
非ポインタ型とポインタ型の違いは？
プロファイルをみるとわかりますが、 runtime.convT2E , runtime.assertE2T が非ポインタ型の場合重荷になっています。ここまで「ポインタ型」「非ポインタ型」という曖昧な表現をしていましたが、正確には これは isdirectiface という関数の結果が true かどうかです。これによりインターフェス変換の処理が変わります。
// Can this type be stored directly in an interface word?
// Yes, if the representation is a single pointer.
func isdirectiface(t *Type) bool {
switch t.Etype {
case TPTR32,
TPTR64,
TCHAN,
TMAP,
TFUNC,
TUNSAFEPTR:
return true
// Array of 1 direct iface type can be direct.
case TARRAY:
return t.Bound == 1 && isdirectiface(t.Type)
// Struct with 1 field of direct iface type can be direct.
case TSTRUCT:
return t.Type != nil && t.Type.Down == nil && isdirectiface(t.Type.Type)
}
return false
}
これが false になるオブジェクトをインタフェースとして利用する際は注意です。
時にはインタフェースを使わない、という選択も
以上のことから、特に性能が必要な場合、インタフェースを使わず擬似共用体(Goに共用体はないので)のような実装をしたほうがよい場合が出てきます。フィボナッチの例を struct で書いてみましょう。
const (
TypeInt int = iota
TypeBool
)
type Object struct {
Type int
IntValue int
BoolValue bool
}
func IntFibNoInterface(n int) int {
if n < 2 {
return n
}
return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
}
func IntFibStruct(o Object) Object {
if o.IntValue < 2 {
return o
}
return Object{TypeInt,
IntFibStruct(Object{TypeInt, o.IntValue - 1, false}).IntValue +
IntFibStruct(Object{TypeInt, o.IntValue - 2, false}).IntValue,
false}
}
func BenchmarkNoInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibNoInterface(20)
}
}
func BenchmarkStruct(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibStruct(Object{TypeInt, 20, false})
}
}
速度ですが、インタフェースを使うより断然早く、2-3倍程度しか遅くなりません。当たり前ですが、暗黙的なメモリアロケーションも発生しません。
BenchmarkNoInterface 30000 58491 ns/op 0 B/op 0 allocs/op
BenchmarkStruct 10000 139924 ns/op 0 B/op 0 allocs/op
reflect を使えば・・・というのもありますが、結局 reflect.ValueOf の引数が interface{} なので素直に使うと interface{} の場合と同様の遅さです。
func IntFibNoInterface(n int) int {
if n < 2 {
return n
}
return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
}
func IntFibReflect(r reflect.Value) reflect.Value {
n := r.Int()
if n < 2 {
return r
}
return reflect.ValueOf(IntFibReflect(reflect.ValueOf(n-1)).Int() + IntFibReflect(reflect.ValueOf(n-2)).Int())
}
func BenchmarkNoInterface(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibNoInterface(20)
}
}
func BenchmarkReflect(b *testing.B) {
for i := 0; i < b.N; i++ {
IntFibReflect(reflect.ValueOf(20))
}
}
BenchmarkNoInterface 30000 56238 ns/op 0 B/op 0 allocs/op
BenchmarkReflect 1000 2271026 ns/op 525376 B/op 32836 allocs/op
ちなみにGopherLuaでは
拙作のGo言語によるLua実装 GopherLua では一番おそい、非ポインタ型をインタフェースとして使う実装になっています。なのでGopherLuaはおそらく現在でもGo上で動くスクリプト言語としては最速の部類ですがさらに速くしようと思えばできたのかもなあと思っています(まぁこの例ほど言語実装は単純ではないし、擬似共用体にするにしてもサイズが大きくなるので、速くなるかどうかはやってみないとなんともいえないのですが。あとサイズがおおきくなるのでスタック型のAPIにするよりないでしょうね)。
これは使い易さや実装のし易さやメモリ効率、そして「Goらしさ」とのトレードオフだと思っています。私は、とにかく使い易いものがほしかったので一番使い易く、そして実装が楽なものを選びました。
とはいえ、特に数値型をインタフェースに変換する負荷を軽減するために、独自のアロケータを実装しています。これは一定数の float64 をまとめてアロケートすることでインタフェース変換コストを減らしています。かなり強引なのですが興味のある方は gopher-lua/alloc.go をご参照ください。
最後に
インタフェースはGoで中心的な役割を果たしていますが、時に大幅なパフォーマンス劣化を起こす可能性があります。 特に、非ポインタ型を interface{} などとして引数に渡す場合が要注意です。
Go Advent Calendar 2015 その3 12日目は Ladicle さんです。