はじめに

これはGo Advent Calendar 2017 - Qiitaの3日目の記事です。

当初はコンパイラの最適化を話すつもりだったのですが…

GoConでParallel Compilationの話をしたからコンパイラ最適化のところをアドベントカレンダーで出そうと思ってたんだけど結構内容が濃すぎてなんか間に合わなさそうな雰囲気を感じていているのでどうしようか考えている
— 井手康貴/Koki Ide (@niconegoto) 2017年12月2日

こんな感じでつらいなということになり、アンケートを行いました。

というわけで何が読みたいのかアンケート
— 井手康貴/Koki Ide (@niconegoto) 2017年12月2日

その結果、上記の通りInterfaceとは何なのかの記事を書くことになりました。(異論は認めません)

コンパイラ最適化に関しては30%くらい書き進めているのと、Go2についても書き始めてはいるのでどこかで日の目をみることになると思います。(皆さんからの圧力が力になります)

導入

GoのInterfaceはGoの特徴の一つでInterfaceを制する者はGoを制するとも言われています。

そこで今回はRuss Coxによる解説記事を参考にし、2009年の記事のため古くなってしまっている部分を補足しつつInterfaceの正体をさくっと解き明かしていきたいと思います。

この記事ではInterfaceの使い方等は取り上げません。 そういうのが気になる方はぜひtenntennさんによる勉強になるエントリがあるのでそちらを読んでみてください。

qiita.com

インタフェース値

メソッドを持つ言語は通常

C++やJavaのように静的にすべてのメソッド呼び出し用のテーブルを準備する
JavaScriptやPythonのように各呼び出しでメソッド検索を行い、その呼び出しを効率的にするためにキャッシュを行う

という手法をとるのですが、 Goは両者の中間をとったような感じになっており、メソッドテーブルを実行時に検索するというようなことをしています。

では、さっそく [src/runtime/iface.go](https://golang.org/src/runtime/iface.go)を見ていきましょう。 cmd/compile/internal 辺りとかと同じく汚いコードな気がしなくもないですが量が少ない分わりと読めます。

インタフェースは

インタフェースに格納された型に関する情報へのポインタ
関連データへのポインタ

として表されています。

例としてまず、Stringer型のインタフェースにbを代入したとします。すると、以下の様になります。

間違って(in C)となっているのは昔Cで書かれていた時代の名残でミスなので許してください。

f:id:niconegoto:20171203210828j:plain

1つ目のポインタはitabを参照します。 itabは以下の様に定義されています。

type itab struct {
    inter *interfacetype
    _type *_type
    hash  uint32 // copy of _type.hash. Used for type switches.
    _     [4]byte
    fun   [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
}

itabは型に関するいくつかのメタデータや関数ポインタのリストで構成されます。この例ではStringerインターフェースをを満たすためのメソッドのバイナリ型のリストを保持しています。

もう一方のポインタは実際のデータを参照します。この場合、bのコピーです。

var s Stringer = b

は、

var c uint64 = b

がコピーを作成するのと同じ理由で、bの実体を参照するのではなくbのコピーを作成します。そのため、bを後で変更した場合、sとcは元の値のままになります。インターフェイスに格納された値は任意の大きさまで大きくなる可能性があるのですが、上記の様にすることによってインターフェイス構造体内で値を保持するための記憶領域は少なくて済むので割り当てによってヒープにメモリが割り当てられ、ポインタが記憶されます。（値がスロットに収まるときは明らかに最適化されていますが、後でその点を説明します）

インターフェースの呼び出し側は、それが指しているデータの量に関知しません。また、多くのメソッドを持つインターフェースは、itabの一番下にあるfunリストに多くのデータを保持することになります。

itabの計算

Goコンパイラまたはリンカが全てのitabを事前計算するのはほぼ不可能です。そのため、コンパイラはBinaryまたはintまたはfunc（map [int] string）のような具体的な型ごとに型記述構造体を生成します。メタデータの中の型記述構造にはその型によって実装されたmethodのリストが含まれていて、コンパイラは各インタフェースに対してそれぞれ別の型記述構造を生成します。ランタイムは、それを利用してインタフェースのmethod表にリストされている各メソッドを検索して、itabを作成します。ランタイムは生成したitabを生成した後にキャッシュするので、この対応関係を作成するのは一度だけで済むのです。

メモリ最適化

ここからどのようにメモリ最適化してくのでしょうか。まず、関係するインタフェースの型が空の場合（メソッドがない場合）、itabは削除することができるので値は直接型を指すことができます。

f:id:niconegoto:20171203210903j:plain

そして、インタフェースに関連する値が単一の機械語に収まるサイズの場合は間接割り当てやヒープ割り当てを用いる必要がないため、Binary32をBinaryのように定義してuint32として実装すると、実際の値をインターフェース内に格納することができます。

コンパイラは値がインライン化されるかポインタを用いるのかを型のメソッドテーブル（itabにコピーされるもの）にリストされている関数を見て判断します。上記の図において、itabのメソッドは（* Binary）.Stringですが、下記のBinary32の例では、itabのメソッドはBinary32.Stringであり、（* Binary32）.Stringにはなりません。

f:id:niconegoto:20171203210941j:plain f:id:niconegoto:20171203210956j:plain

メソッド検索のパフォーマンス

JavaScriptやPythonなどはメソッドが呼び出されるたびにメソッドの検索を行います。そのため、多くの場合でパフォーマンスのために単純なキャッシュを使用します。マルチスレッド環境下では複数のスレッドが同時に存在する可能性があるためキャッシュを慎重に管理する必要があり、キャッシュはメモリ競合の原因にもなります。

その一方でGoは実行時にメソッドの検索を行うために型のヒントを保持しているため、メソッドの検索を効率的に行うことができます。

1   var any interface{}  // initialized elsewhere
2   s := any.(Stringer)  // dynamic conversion
3   for i := 0; i < 100; i++ {
4       fmt.Println(s.String())
5   }

Goでは2行目の代入中にitabが計算されるか、キャッシュが適用されます。そのため、4行目で実行されるs.String（）呼び出しの際には2回のメモリfetchと1回の間接呼び出し命令が必要です。

これとは対照的に、JavaScript、Pythonのような動的言語でのこのプログラムの実装は、ループ内で何度も不要に4行目のメソッド検索を実行します。前述のキャッシュを用いたとしても1回の間接呼び出し命令よりもコストがかかってしまいます。(プログラミング言語ガチ勢には突っ込まれそうな表現ですみません)

コード解説

下記のコードで解説すると

package main

import (
 "fmt"
 "strconv"
)

type Stringer interface {
 String() string
}

type Binary uint64

func (i Binary) String() string {
 return strconv.Uitob64(i.Get(), 2)
}

func (i Binary) Get() uint64 {
 return uint64(i)
}

func main() {
 b := Binary(200)
 s := Stringer(b)
 fmt.Println(s.String())
}

0045 (x.go:25) LEAL    s+-24(SP),BX
0046 (x.go:25) MOVL    4(BX),BP
0047 (x.go:25) MOVL    BP,(SP)
0048 (x.go:25) MOVL    (BX),BX
0049 (x.go:25) MOVL    20(BX),BX
0050 (x.go:25) CALL    ,BX

LEALはsのアドレスをレジスタBXにロードし、次の2つのMOVL命令は、インタフェースから値を取り出してそれを最初の関数呼び出し引数（SP）にセットします。最後の2つのMOVL命令は、その関数を呼び出すための準備として、itabと関数ポインタをitabから取得します。

まとめ

とこんな感じでとりあえず調べていったのですが、ちょっと時間がなくて調べ足りていないのでマサカリをどんどんください。重ね重ねですが、コンパイラ最適化とGo2については皆さんからの圧力が力になるので圧力の方お願い致します。

株式会社FlattではGoを書く仲間を募集しています！ランチからでも大丈夫なのでぜひ興味あるかたはTwitterでもWantedlyでもいいので連絡ください。

niconegoto Blog

niconegoto's journal

GoのInterfaceとは何者なのか #golang #go