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 では以下のようなコードがあります。

reflect/value.go :

 1// emptyInterface is the header for an interface{} value.
 2type emptyInterface struct {
 3    typ  *rtype
 4    word unsafe.Pointer
 5}
 6
 7// nonEmptyInterface is the header for a interface value with methods.
 8type nonEmptyInterface struct {
 9    // see ../runtime/iface.go:/Itab
10    itab *struct {
11        ityp   *rtype // static interface type
12        typ    *rtype // dynamic concrete type
13        link   unsafe.Pointer
14        bad    int32
15        unused int32
16        fun    [100000]unsafe.Pointer // method table
17    }
18    word unsafe.Pointer
19}

コメントに書かれているように実態は runtime/iface.go ですがこちらのほうが簡略化されていてわかりやすいでしょう。1個目のポインタは 「空のインタフェース( iterface{} )」(これを eface という)の場合、型情報、そうでない場合(これを iface という)の場合 itab と呼ばれるC++における仮想テーブルのようなものです。2個目に値が格納されます。2個目はどちらもポインタであることに注意してください。

インターフェース経由のメソッド呼び出し

ここで、インターフェースを使用するとどの程度パフォーマンスペナルティがあるのか、様々なケースで見てみます。

まずは、直接メソッドを呼び出すのと、インタフェース経由で呼び出す場合の違いを見てみましょう。

 1type MyError struct{}
 2func (e *MyError) Error() string { return "error" }
 3
 4func BenchmarkNoInterface(b *testing.B) {
 5    for i := 0; i < b.N; i++ {
 6        err := &MyError{}
 7        err.Error()
 8    }
 9}
10
11func BenchmarkInterface(b *testing.B) {
12    for i := 0; i < b.N; i++ {
13        var err error = &MyError{}
14        err.Error()     
15    }
16}

結果は以下のようになります。10倍程度遅くなります。単位が単位なので微々たる違いですが極限までパフォーマンスを追求したい場合は考慮しておいたほうがいいかもしれませんね。

1BenchmarkNoInterface    2000000000               0.73 ns/op
2BenchmarkInterface      200000000                9.56 ns/op

しかし実はこの中には *MyError を error インタフェースに変換するコストも含まれていて、そのコストを除くと5倍くらいの遅さです。次はそのインタフェースへの変換コストを詳しく見ていこうと思います。

インターフェースへの変換コスト(非ポインタ型)

Goにおけるインタフェースの変換時はC++におけるキャストよりも複雑なことが発生します。

Goでは「なんでも」を表すために interface{} を使いますね。 int などの組み込み型かつ非ポインタ型を interface{} として処理するとなにが起こるでしょうか？以下のようにフィボナッチを計算させてみます。

 1func IntFibNoInterface(n int) int {
 2    if n < 2 {
 3        return n
 4    }
 5    return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
 6}
 7
 8func IntFibInterface(o interface{}) interface{} {
 9    n := o.(int)
10    if n < 2 {
11        return o
12    }
13    return IntFibInterface(n-1).(int) + IntFibInterface(n-2).(int)
14}
15
16func BenchmarkNoInterface(b *testing.B) {
17    for i := 0; i < b.N; i++ {
18        IntFibNoInterface(20)
19    }
20}
21
22func BenchmarkInterface(b *testing.B) {
23    for i := 0; i < b.N; i++ {
24        IntFibInterface(20)
25    }
26}

結果は以下。40 - 50倍くらいおそくなりますね。これを見ると気軽にインタフェースを使いたくなくなるかもしれません。

1BenchmarkNoInterface       30000             57938 ns/op               0 B/op          0 allocs/op
2BenchmarkInterface           500           2448250 ns/op          525376 B/op      32836 allocs/op

はじめに書いたように、インタフェースは ポインタとして値を保持します 。 そのためコード上アロケートしていなくても、内部的に int をアロケートしそこに値をコピーせねばなりません。

どのような処理が実行されたか、プロファイルを見てみましょう。

 11.46s of 1.46s total (  100%)
 2Showing top 20 nodes out of 35 (cum >= 0.01s)
 3      flat  flat%   sum%        cum   cum%
 4     0.37s 25.34% 25.34%      0.68s 46.58%  runtime.mallocgc
 5     0.26s 17.81% 43.15%      1.44s 98.63%  12.IntFibInterface
 6     0.20s 13.70% 56.85%      0.20s 13.70%  runtime.memmove
 7     0.16s 10.96% 67.81%      0.16s 10.96%  runtime.mSpan_Sweep.func1
 8     0.12s  8.22% 76.03%      0.96s 65.75%  runtime.convT2E
 9     0.11s  7.53% 83.56%      0.31s 21.23%  runtime.typedmemmove
10     0.10s  6.85% 90.41%      0.26s 17.81%  runtime.heapBitsSweepSpan
11     0.05s  3.42% 93.84%      0.22s 15.07%  runtime.assertE2T
12     0.02s  1.37% 95.21%      0.70s 47.95%  runtime.newobject
13     0.02s  1.37% 96.58%      0.02s  1.37%  runtime.prefetchnta
14     0.01s  0.68% 97.26%      0.01s  0.68%  runtime.(*gcControllerState).findRunnableGCWorker
15     0.01s  0.68% 97.95%      0.01s  0.68%  runtime.lock
16     0.01s  0.68% 98.63%      0.01s  0.68%  runtime.mSpanList_InsertBack
17     0.01s  0.68% 99.32%      0.01s  0.68%  runtime.xadd64
18     0.01s  0.68%   100%      0.01s  0.68%  runtime.xchg
19         0     0%   100%      1.44s 98.63%  12.BenchmarkInterface
20         0     0%   100%      0.01s  0.68%  runtime.GC
21         0     0%   100%      0.01s  0.68%  runtime.deductSweepCredit
22         0     0%   100%      0.01s  0.68%  runtime.gc
23         0     0%   100%      0.01s  0.68%  runtime.gc.func4

非ポインタ型のインターフェースへの変換コスト

では、ということで自分でアロケーションしてみましょう。 int ではなく *int を使ってみます。

 1func IntFibNoInterface(n int) int {
 2    if n < 2 {
 3        return n
 4    }
 5    return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
 6}
 7
 8func IntFibPointer(i *int) *int {
 9    n := *i
10    if n < 2 {
11        return i
12    }
13    a1 := new(int)
14    *a1 = n - 1
15    a2 := new(int)
16    *a2 = n - 2
17    v1 := IntFibPointer(a1)
18    v2 := IntFibPointer(a2)
19    ret := new(int)
20    *ret = *v1 + *v2
21    return ret
22}
23
24func IntFibInterface(o interface{}) interface{} {
25    n := *(o.(*int))
26    if n < 2 {
27        return o
28    }
29    a1 := new(int)
30    *a1 = n - 1
31    a2 := new(int)
32    *a2 = n - 2
33    v1 := IntFibInterface(a1).(*int)
34    v2 := IntFibInterface(a2).(*int)
35    ret := new(int)
36    *ret = *v1 + *v2
37    return ret
38}
39
40func BenchmarkNoInterface(b *testing.B) {
41    for i := 0; i < b.N; i++ {
42        IntFibNoInterface(20)
43    }
44}
45
46func BenchmarkPointer(b *testing.B) {
47    for i := 0; i < b.N; i++ {
48        a := new(int)
49        *a = 20
50        IntFibPointer(a)
51    }
52}
53
54func BenchmarkInterface(b *testing.B) {
55    for i := 0; i < b.N; i++ {
56        a := new(int)
57        *a = 20
58        IntFibInterface(a)
59    }
60}

結果は以下のようになります。20-30倍というところでしょうか。こちらのほうがコードだけ見ると遅そうですが、なんと int を使った場合より速いのです。そして、インタフェースへの変換コストは少ない、ということがわかります。

1BenchmarkNoInterface       30000             55558 ns/op               0 B/op          0 allocs/op
2BenchmarkPointer            1000           1297598 ns/op          525376 B/op      32836 allocs/op
3BenchmarkInterface          1000           1357172 ns/op          525376 B/op      32836 allocs/op

 11.54s of 1.54s total (  100%)
 2Showing top 20 nodes out of 37 (cum >= 0.01s)
 3      flat  flat%   sum%        cum   cum%
 4     0.75s 48.70% 48.70%      1.24s 80.52%  runtime.mallocgc
 5     0.22s 14.29% 62.99%      0.22s 14.29%  runtime.mSpan_Sweep.func1
 6     0.16s 10.39% 73.38%      0.38s 24.68%  runtime.heapBitsSweepSpan
 7     0.14s  9.09% 82.47%      1.38s 89.61%  runtime.newobject
 8     0.11s  7.14% 89.61%      1.49s 96.75%  12.IntFibInterface
 9     0.08s  5.19% 94.81%      0.08s  5.19%  runtime.prefetchnta
10     0.02s  1.30% 96.10%      0.02s  1.30%  runtime.heapBitsForObject
11     0.01s  0.65% 96.75%      0.01s  0.65%  runtime.(*bucket).mp
12     0.01s  0.65% 97.40%      0.01s  0.65%  runtime.atomicload64
13     0.01s  0.65% 98.05%      0.41s 26.62%  runtime.mCentral_CacheSpan
14     0.01s  0.65% 98.70%      0.03s  1.95%  runtime.scanblock
15     0.01s  0.65% 99.35%      0.01s  0.65%  runtime.schedule
16     0.01s  0.65%   100%      0.01s  0.65%  runtime.xchg
17         0     0%   100%      1.49s 96.75%  12.BenchmarkInterface
18         0     0%   100%      0.04s  2.60%  runtime.backgroundgc
19         0     0%   100%      0.01s  0.65%  runtime.deductSweepCredit
20         0     0%   100%      0.04s  2.60%  runtime.gc
21         0     0%   100%      0.02s  1.30%  runtime.gc.func1
22         0     0%   100%      0.01s  0.65%  runtime.gc.func3
23         0     0%   100%      0.01s  0.65%  runtime.gc.func4

非ポインタ型とポインタ型の違いは？

プロファイルをみるとわかりますが、 runtime.convT2E , runtime.assertE2T が非ポインタ型の場合重荷になっています。ここまで「ポインタ型」「非ポインタ型」という曖昧な表現をしていましたが、正確には これは isdirectiface という関数の結果が true かどうかです。これによりインターフェス変換の処理が変わります。

 1// Can this type be stored directly in an interface word?
 2// Yes, if the representation is a single pointer.
 3func isdirectiface(t *Type) bool {
 4    switch t.Etype {
 5    case TPTR32,
 6        TPTR64,
 7        TCHAN,
 8        TMAP,
 9        TFUNC,
10        TUNSAFEPTR:
11        return true
12
13        // Array of 1 direct iface type can be direct.
14    case TARRAY:
15        return t.Bound == 1 && isdirectiface(t.Type)
16
17        // Struct with 1 field of direct iface type can be direct.
18    case TSTRUCT:
19        return t.Type != nil && t.Type.Down == nil && isdirectiface(t.Type.Type)
20    }
21
22    return false
23}

これが false になるオブジェクトをインタフェースとして利用する際は注意です。

時にはインタフェースを使わない、という選択も

以上のことから、特に性能が必要な場合、インタフェースを使わず擬似共用体(Goに共用体はないので)のような実装をしたほうがよい場合が出てきます。フィボナッチの例を struct で書いてみましょう。

 1const (
 2    TypeInt int = iota
 3    TypeBool
 4)
 5
 6type Object struct {
 7    Type      int
 8    IntValue  int
 9    BoolValue bool
10}
11
12func IntFibNoInterface(n int) int {
13    if n < 2 {
14        return n
15    }
16    return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
17}
18
19func IntFibStruct(o Object) Object {
20    if o.IntValue < 2 {
21        return o
22    }
23    return Object{TypeInt,
24        IntFibStruct(Object{TypeInt, o.IntValue - 1, false}).IntValue +
25            IntFibStruct(Object{TypeInt, o.IntValue - 2, false}).IntValue,
26        false}
27}                                                               
28
29func BenchmarkNoInterface(b *testing.B) {                       
30    for i := 0; i < b.N; i++ {
31        IntFibNoInterface(20)
32    }
33}
34
35func BenchmarkStruct(b *testing.B) {
36    for i := 0; i < b.N; i++ {
37        IntFibStruct(Object{TypeInt, 20, false})
38    }  
39}

速度ですが、インタフェースを使うより断然早く、2-3倍程度しか遅くなりません。当たり前ですが、暗黙的なメモリアロケーションも発生しません。

1BenchmarkNoInterface       30000             58491 ns/op               0 B/op          0 allocs/op
2BenchmarkStruct            10000            139924 ns/op               0 B/op          0 allocs/op

reflect を使えば・・・というのもありますが、結局 reflect.ValueOf の引数が interface{} なので素直に使うと interface{} の場合と同様の遅さです。

 1func IntFibNoInterface(n int) int {
 2    if n < 2 {
 3        return n
 4    }
 5    return IntFibNoInterface(n-1) + IntFibNoInterface(n-2)
 6}
 7
 8func IntFibReflect(r reflect.Value) reflect.Value {
 9    n := r.Int()
10    if n < 2 {
11        return r
12    }     
13    return reflect.ValueOf(IntFibReflect(reflect.ValueOf(n-1)).Int() + IntFibReflect(reflect.ValueOf(n-2)).Int())
14}                         
15
16func BenchmarkNoInterface(b *testing.B) {
17    for i := 0; i < b.N; i++ {
18        IntFibNoInterface(20)
19    }     
20}         
21
22func BenchmarkReflect(b *testing.B) {
23    for i := 0; i < b.N; i++ {
24        IntFibReflect(reflect.ValueOf(20))
25    }                        
26}         

1BenchmarkNoInterface       30000             56238 ns/op               0 B/op          0 allocs/op
2BenchmarkReflect            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 さんです。

コマンドラインランチャー iceberg のv0.9.7 をリリースしました。 GitHubの リリース一覧 よりダウンロードできます。

今回からLinuxに対応しました。私は普段、ほぼWindowsがホストでVirtualbox上のUbuntuで開発を行っておりそこではLaunchyを使ってお茶をにごして？いたのです。がやはり慣れているicebergを使いたいと思っていたのでがんばって対応してみました。

Macを使っている人はそもそもAlfredなどを使っているでしょうけど、Windowsだと私と同じかたちの人も多いのではないかと思います。ぜひ使ってみてください。Linuxのコマンドラインランチャーでmigemo対応しているものはなかなか無いのではないでしょうか。

icebergはQtやGTKではなくfltkというミニマリストなGUIフレームワークなのでGUI以外の機能はほとんどフレームワークにありません。かといって、ここでQtやGTKに依存するのも癪だったのでLinuxではアイコンのルックアップなどを自分で実装したんですが結構しんどかったですね･･･。ただ、あらかじめマルチプラットフォームを視野にいれたつくりにしてあったので、ゴリゴリ書いていくだけで動くのは動いたのでよかったです。

内部的にはfltkのバージョンもあげました。これでWindows8以降でも互換モードなしで動いたりしないかなあ、と思っているのですが、いかんせん実機をもっていないのでどうにも。次はWindows10にすると思うので結局Windows8系は確認できないまま終わりそうです。

あと、ここまできたらなんでMacに対応しないんだ、となりそうですが単純に私がMacを持っていないからです。それに、icebergはMacの文化に合わない気がします。ただ、icebergは作者の私が一番の愛用者であるソフトなのでもし私がMacを手に入れることがあったら、対応すると思います。まぁイケてる会社のプログラマーに転職でもしないとMacを使うようなことはないと思いますが。

なにか問題ありましたらGithubの Issues までどうぞ。

GopherLua で設定ファイルを書くためのライブラリを書きました。設定ファイル以外にも使えますけど。

モノとしてはGopherLuaのテーブルをGoの構造体にマップしてくれます。といっても、内部動作的にはHashicorpの mapstructure を使っているだけだったりします。一度GopherLuaのテーブルを map[string]interface{} に変換してあげて、あとはmapstructureにおまかせ。

ただ、一般的なLuaの命名規則とGoの命名規則が違うので名前を変換する関数が指定できます。デフォルトでは snake_case を CamelCase に変換します。

 1type Role struct {
 2    Name string
 3}
 4
 5type Person struct {
 6    Name      string
 7    Age       int
 8    WorkPlace string
 9    Role      []*Role
10}
11
12L := lua.NewState()
13if err := L.DoString(`
14person = {
15  name = "Michel",
16  age  = "31", -- weakly input
17  work_place = "San Jose",
18  role = {
19    {
20      name = "Administrator"
21    },
22    {
23      name = "Operator"
24    }
25  }
26}
27`); err != nil {
28    panic(err)
29}
30var person Person
31if err := gluamapper.Map(L.GetGlobal("person").(*lua.LTable), &person); err != nil {
32    panic(err)
33}
34fmt.Printf("%s %d", person.Name, person.Age)

のように非常に簡単にLuaを設定ファイルとして使うことができます。Luaは可読性が高く、JSONと異なりコメントが書けて、YAMLよりも簡単に値を変数化できるので設定ファイルにすると便利です(なんでも出来てしまう、というのがネックと言えばネックですが)。