この記事は Chapter II: Interfaces を翻訳、加筆したものです。

$ go version
go version go1.10 linux/amd64

この章ではGoのinterfaceが内部でどのように機能しているかを解説する

例を挙げるなら

関数やメソッドが実行時にどのようにコールされるか
interfaceがどのように形成されるか
dynamic dispatch がいつ、どのように、どれくらいのコストを伴って機能するか
空のインターフェース interface{} やその他の特殊なインターフェースが通常のインターフェースとどう異なるか
インターフェースの合成について
Type assertion(型アサーション)がどう実行されコストはどの程度か

などだ。

掘り進めていくと、Goコンパイラによる様々な最適化手法や現代のCPUの実装の詳細などの低レイヤの技術に触れることになるだろう

Table of Contents

Interface 入門

Goアセンブリを知っていることを前提とする (Goアセンブリ入門 or chapter I).
動作環境は全て、linux/amd64
コンパイラの最適化は常に有効なものとする

関数とメソッドの呼び出し

Russ Cox氏が関数呼び出しについての設計ドキュメントで指摘しているように、Goは

4種類の関数を持っている:

トップレベル関数

実体をレシーバとするメソッド

ポインタをレシーバとするメソッド

関数リテラル

そして5種類の関数コールのパターンがある:

トップレベル関数の直接呼び出し (func TopLevel(x int) {})

実体をレシーバとするメソッドの直接呼び出し (func (Value) M(int) {})

ポインタをレシーバとするメソッドの直接呼び出し (func (*Pointer) M(int) {})

interfaceごしのメソッド間接呼び出し (type Interface interface { M(int) })

関数リテラルごしの間接呼び出し (var literal = func(x int) {})

関数と関数コールを全て組み合わせた場合、全部で10通りになる:

トップレベル関数の直接呼び出し /

実体をレシーバとするメソッドの直接呼び出し /

ポインタをレシーバとするメソッドの直接呼び出し /

interfaceのメソッドの間接呼び出し / containing value with value method

interfaceのメソッドの間接呼び出し / containing pointer with value method

interfaceのメソッドの間接呼び出し / containing pointer with pointer method

関数リテラルの間接呼び出し / set to top-level func

関数リテラルの間接呼び出し / set to value method

関数リテラルの間接呼び出し / set to pointer method

関数リテラルの間接呼び出し / set to func literal

(スラッシュ(/) はコンパイル時に認識されるものと実行時にのみ検出されるものを区切っている)

まず3種類の直接呼び出しについて見て行った後で残りの interface と間接呼び出しについて見ていく

ここでは関数リテラルについては説明しない。なぜなら関数リテラルを説明するには、クロージャの仕組みについて深く知っていることが必要だからだ。

直接呼び出し

直接呼び出しとは要は、インターフェースや関数リテラルが介在しない通常の関数呼び出しのことである

次のコードを考えてみよう (direct_calls.go):

//go:noinline
func Add(a, b int32) int32 { return a + b }

type Adder struct{ id int32 }
//go:noinline
func (adder *Adder) AddPtr(a, b int32) int32 { return a + b }
//go:noinline
func (adder Adder) AddVal(a, b int32) int32 { return a + b }

func main() {
    Add(10, 32) // トップレベル関数の直接呼び出し

    adder := Adder{id: 6754}
    adder.AddPtr(10, 32) // ポインタをレシーバとするメソッドの直接呼び出し
    adder.AddVal(10, 32) // 実体をレシーバとするメソッドの直接呼び出し

    (&adder).AddVal(10, 32) // implicit dereferencing
}

これら4つの関数呼び出しを1つずつ見ていこう

トップレベル関数の直接呼び出し

Add(10, 32)の出力するアセンブリは次のようになる:

0x0000 TEXT	"".main(SB), $40-0
  ;; ...omitted everything but the actual function call...
  0x0021 MOVQ	$137438953482, AX
  0x002b MOVQ	AX, (SP)
  0x002f CALL	"".Add(SB)
  ;; ...omitted everything but the actual function call...

Goアセンブリ入門または A Primer on Go Assembly で見たようにこの擬似アセンブリは .textセクションのグローバルな関数シンボルに直接ジャンプするバイナリに変換される。
また引数と返り値はcallerのスタックフレームに格納されるようになっている。

Russ Cox は自身のドキュメントでこう述べている:

トップレベル関数の直接呼び出し:
トップレベル関数の直接呼び出しはすべての引数をスタックを通して渡し、返り値が引数と連続するスタックの位置に格納されていることを期待している。

ポインタをreceiverとするメソッドの直接呼び出し

始めに receiver は adder := Adder{id: 6754} で初期化されている:

0x0034 MOVL	$6754, "".adder+28(SP)  ;; SP+28(adderのアドレス)に $6754を格納する

(28byte分のスタックフレームの余分なスペースはフレームポインタpreambleの一部として割り当てられたものである。ここでは割愛する)

実際のメソッドコールである adder.AddPtr(10, 32) は以下のようになる:

0x0057 LEAQ	"".adder+28(SP), AX	        ;; &adderを
0x005c MOVQ	AX, (SP)		            ;; スタックにPUSH (1個目の引数として)
0x0060 MOVQ	$137438953482, AX	        ;; (32,10)を
0x006a MOVQ	AX, 8(SP)		            ;; スタックにPUSH (2,3個目の引数として)
0x006f CALL	"".(*Adder).AddPtr(SB)

アセンブリを見ると、メソッドのコールはレシーバが実体だろうとポインタだろうと関数のそれとほぼ同じだということがわかる。

唯一違う点はメソッドの場合はレシーバが1個目の引数として扱われているということだ。

このケースでは、スタックフレームの先頭から28バイトほど下にある "".adder+28(SP) つまり adder のポインタを LEAQ によって取得している。
よって1個目の引数は &adder となる。

LEA命令は対象の実効アドレスを取得する命令で MOV命令とは違うことに注意

mov eax, var       == lea eax, [var]    ; i.e. mov r32, imm32
lea eax, [var+16]  == mov eax, var+16
lea eax, [eax*4]   == shl eax, 2        ; but without setting flags

[What is the difference between MOV and LEA?.]

コンパイラがレシーバの型をエンコードする方法と、それが値であるかポインタであるかをシンボルの名前("".(*Adder).AddPtr)に直接明記することに注意しよう

メソッドの直接呼び出し:
直接呼び出しと関数リテラルの間接呼び出しに対して同じコードを生成できるように、メソッドに対するコード生成は、receiver が実体だろうとポインタだろうと receiver を1個目の引数としたトップレベル関数と同じ呼び出し規約を持つように行われます。

実体をレシーバとするメソッドの直接呼び出し

実体をレシーバとするメソッドの直接呼び出しはポインタのそれと非常に似ている。

adder.AddVal(10, 32) を見てみよう:

0x003c MOVQ	$42949679714, AX	    ;; (10,6754) を
0x0046 MOVQ	AX, (SP)		        ;; スタックにPUSH(引数の1個目と2個目)
0x004a MOVL	$32, 8(SP)		        ;; 32をPUSH(引数の3個目)
0x0052 CALL	"".Adder.AddVal(SB)

奇妙なことに、生成されたアセンブリは adder のある "".adder+28(SP) を参照していない。

今回はレシーバが実体であり、コンパイラはこのことをコンパイル時に推測することが可能なので、28(SP)から adderのコピーは行われず、代わりに、新しく同一のAdderオブジェクトをスタック上に生成する、そしてその命令を2個目の引数の生成とひとまとめにすることで命令を1つ分節約している

暗黙の参照外し

最後の関数コール (&adder).AddVal(10, 32) を見ていこう

このメソッドは実体をレシーバとして受け取るはずだがポインタをレシーバとしている

不思議なことに、Goはポインタの参照外しをしてこのメソッドをコールしてくれる。

コンパイラが参照外しをする際に、ポインタの指す値(今回はadder)がスタックにあるのかヒープにあるのかによってどのように対応が変わってくるのかを見ていこう

Case A: レシーバがスタックにある場合

もしレシーバがスタック上に存在し、今回のように2,3個の命令でコピーできるくらいポインタの指す実体のサイズが小さいなら、コンパイラは単純にその実体をスタックの一番上にコピーし、"".Adder.AddValのメソッドコールとして扱う。

(&adder).AddVal(10, 32)がどのようにアセンブリのコードになるかを見てみよう

0x0074 MOVL	"".adder+28(SP), AX	    ;; adderの実体を.. (今回は実体なのでleaじゃなくてmov)
0x0078 MOVL	AX, (SP)		        ;; スタックにPUSH (1個目の引数)
0x007b MOVQ	$137438953482, AX	    ;; (32,10)を..
0x0085 MOVQ	AX, 4(SP)		        ;; スタックにPUSH (2,3個目の引数)
0x008a CALL	"".Adder.AddVal(SB)

Case B: レシーバがヒープにある場合

レシーバがヒープにある場合、コンパイラはずる賢い方法で対処する

コンパイラは "".Adder.AddVal(wrappee)をラップする新しいメソッドを生成する。このメソッドは今回はポインタをレシーバとする "".(*Adder).AddVal (wrapper)を生成する。そして、wrappeeをwrapperで置換する。

wrapperの役割は、

wrappeeにレシーバが渡される前に適切にポインタの実体が取得されること
引数と返り値がcallerとwrappeeの間で適切にコピーされることを確実なものにすること

の2つだけだ。

(NOTE: アセンブリでは, これらのwrapperには<autogenerated>というタグが付けられる)

わかりづらいかもしれないので、実際のアセンブリの出力を補足のコメントと共に見ていこう

0x0000 TEXT	"".(*Adder).AddVal(SB), DUPOK|WRAPPER, $32-24
  ;; ...omitted preambles...

  ; レシーバが nil なら 0x005c (panic) にジャンプ
  0x0026 MOVQ	""..this+40(SP), AX
  0x002b TESTQ	AX, AX
  0x002e JEQ	92

  0x0030 MOVL	(AX), AX                ;; ポインタの指す実体を取得して
  0x0032 MOVL	AX, (SP)                ;; スタックにPUSH(1個目の引数)

  ;; 2,3個目の引数をwrapperのスタックにPUSHして、wrappeeをコール
  0x0035 MOVL	"".a+48(SP), AX         ;; wrapperのスタックフレームに引数としていれられている？2個目の引数を..
  0x0039 MOVL	AX, 4(SP)               ;; wrappee用の引数としてPUSH
  0x003d MOVL	"".b+52(SP), AX
  0x0041 MOVL	AX, 8(SP)
  0x0045 CALL	"".Adder.AddVal(SB)     ;; call the wrapped method

  ;; wrapeeの返り値をwrapperの返り値としてコピーし、return
  0x004a MOVL	16(SP), AX
  0x004e MOVL	AX, "".~r2+56(SP)
  ;; ...omitted frame-pointer stuff...
  0x005b RET

  ;; 詳細なエラー内容と共にpanic
  0x005c CALL	runtime.panicwrap(SB)

  ;; ...omitted epilogues...

引数や返り値のやりとりのためにコピーをする必要があることを考えると、このwrapperを使うことによる負荷は無視できない。特にwrappeeが2,3の命令で終わるような関数のときはこの負荷は顕著になる。

しかし実際の場合はコンパイラは wrappee を wrapper内でインライン展開してくれるのでこれらのコストは考えなくてよい。(されない場合もあるが)

0x0000 の "".(*Adder).AddVal(SB) に存在する WRAPPERディレクティブは、ユーザーが混乱しないようにこのwrapperをスタックトレース上では表示しないことと wrappee内で起きたpanicからはリカバリすべきでないことを指示している。

WRAPPER: This is a wrapper function and should not count as disabling recover.

wrapperのレシーバが nil のときに panicを投げる runtime.panicwrap関数は説明の必要はないだろうから、内部実装がどのようにされているかを見ていく (src/runtime/error.go):

// panicwrap generates a panic for a call to a wrapped value method
// with a nil pointer receiver.
//
// It is called from the generated wrapper code.
func panicwrap() {
    pc := getcallerpc()
    name := funcname(findfunc(pc))
    // name is something like "main.(*T).F".
    // We want to extract pkg ("main"), typ ("T"), and meth ("F").
    // Do it by finding the parens.
    i := stringsIndexByte(name, '(')
    if i < 0 {
        throw("panicwrap: no ( in " + name)
    }
    pkg := name[:i-1]
    if i+2 >= len(name) || name[i-1:i+2] != ".(*" {
        throw("panicwrap: unexpected string after package name: " + name)
    }
    name = name[i+2:]
    i = stringsIndexByte(name, ')')
    if i < 0 {
        throw("panicwrap: no ) in " + name)
    }
    if i+2 >= len(name) || name[i:i+2] != ")." {
        throw("panicwrap: unexpected string after type name: " + name)
    }
    typ := name[:i]
    meth := name[i+2:]
    panic(plainError("value method " + pkg + "." + typ + "." + meth + " called using nil *" + typ + " pointer"))
}

これらはすべて関数やメソッドの呼び出しのためのものである。

今回の主題のinterfaceにフォーカスして見ていこう。

詳解interface

データ構造の概要

インターフェースについての解説に入る前に、まずやるべきことは、インターフェースのデータ構造とそれがメモリ上にどのように配置されるかについて理解することだ

インターフェースがどのように表されるのかを理解するために、Goの実装をスタート地点としてruntimeパッケージのコードを覗いてみよう。

iface 構造体

ifaceは runtime内でインターフェースを表すデータ構造のルートとなる型だ。(src/runtime/runtime2.go).

次のように定義されている。

type iface struct { // 16 bytes on a 64bit arch
    tab  *itab
    data unsafe.Pointer
}

このように interface は2つのポインタを持っているだけのシンプルなデータ構造だ。

tab は itabオブジェクトのポインタを保持する。itabオブジェクトはインターフェースがラップしているデータの型だけではなくインターフェースそれ自体の型の挙動を定義しているオブジェクトだ
dataは interfaceが保持している値を指す生ポインタだ

とてもシンプルな定義だが、この定義はとても重要な情報を含んでいる。インターフェースはポインタしか保持できないので、インターフェースを満たす具体的な値と結びつけるにはそのアドレスを取得する必要があるということだ。

多くの場合、コンパイラは保守的な方法をとり、レシーバをヒープ内にエスケープする。これはスカラー型の場合でもそうなる。(スカラー型: i16, i32, i64, string, slice)

このことはたった数行のコードで証明できる。(escape.go)

type Addifier interface{ Add(a, b int32) int32 }

type Adder struct{ name string }
//go:noinline
func (adder Adder) Add(a, b int32) int32 { return a + b }

func main() {
    adder := Adder{name: "myAdder"}
    adder.Add(10, 32)	              // この時点ではヒープへの退避は起きない
    Addifier(adder).Add(10, 32)       // インターフェースにラップされた時点でヒープに退避される
}

$ GOOS=linux GOARCH=amd64 go tool compile -m escape.go
escape.go:13:10: Addifier(adder) escapes to heap
# ...

簡単なベンチマークを使ってヒープの割り当てを可視化することもできる。 (escape_test.go)

func BenchmarkDirect(b *testing.B) {
    adder := Adder{id: 6754}
    for i := 0; i < b.N; i++ {
        adder.Add(10, 32)
    }
}

func BenchmarkInterface(b *testing.B) {
    adder := Adder{id: 6754}
    for i := 0; i < b.N; i++ {
        Addifier(adder).Add(10, 32)
    }
}

$ GOOS=linux GOARCH=amd64 go tool compile -m escape_test.go 
# ...
escape_test.go:22:11: Addifier(adder) escapes to heap
# ...

$ GOOS=linux GOARCH=amd64 go test -bench=. -benchmem ./escape_test.go

# 実行した回数 | 1回あたりの実行に掛かった時間(ns/op) | 1回あたりのアロケーションで確保した容量(B/op) | 1回あたりのアロケーション回数(allocs/op)
BenchmarkDirect-8      	2000000000	         1.60 ns/op	       0 B/op	       0 allocs/op
BenchmarkInterface-8   	100000000	         15.0 ns/op	       4 B/op	       1 allocs/op

この結果をみると、 Addifierインターフェースを作ってadderで初期化するたびに、sizeof(Adder) のヒープ割り当てが実際にどのように行われるのかはっきりわかる。

この章の後半で、単純なスカラー型がインターフェースでラップされたときにどのようにヒープ割り当てされていくのか見ていくつもりだ。

今度は itab の構造を見ていこう。

itab構造体

itab構造体の定義は次のようになっている (src/runtime/runtime2.go):

type itab struct {   // 40 bytes on a 64bit arch
    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構造体は、interfaceの中核となる場所だ。(interface table 略して itab)

まず itab は _type というフィールドを持っている。これはランタイム内でGoが型を表すときに用いる内部表現だ。

_type は型の全部の付随情報を記録している。

これはサイズやアラインメントなどの特徴に限った話ではなく、比較やハッシュといった型の挙動すらある程度だが記録している。

例えば、_typeフィールドはインターフェースがラップしている値の型を保持している。この値というのは iface の dataフィールドが指しているものだ。

次に目に付くのは interfacetype だ。これはインターフェースでのみ必要とされる情報を _type に加えるために _type をラップした型だ。

もう予想はついているだろうが、interフィールドはインターフェース本体の型情報を保持するフィールドだ。

最後に、funという配列はインターフェースの vtable を構成する関数のポインタを保持したものだ。

// variable sized というコメントに注意して欲しい。これは配列宣言時のサイズ([1]uintptrの1)は無関係な値であるということを意味している。

この章の後半で、コンパイラがこの配列をバックアップするメモリの割り当てを担当し、ここに示されているサイズとは関係なく割り当てが行われていることを確認する。

また、ランタイムはこの配列に常に生ポインタを使ってアクセスするので、境界チェックはここでは行われることはない。

_type構造体

上で述べたように、 _type構造体は Goの型の完全な情報を保持した構造体だ。

次のように定義されている (src/runtime/type.go):

type _type struct {    // 48 bytes on a 64bit arch
    size       uintptr
    ptrdata    uintptr // size of memory prefix holding all pointers
    hash       uint32
    tflag      tflag
    align      uint8
    fieldalign uint8
    kind       uint8
    alg        *typeAlg
    // gcdata stores the GC type data for the garbage collector.
    // If the KindGCProg bit is set in kind, gcdata is a GC program.
    // Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    gcdata    *byte
    str       nameOff
    ptrToThis typeOff
}

ありがたいことに、フィールドの大半は見ればわかるものばかりだ。

nameOff と typeOff という型はリンカによって実行ファイルに埋め込まれるメタデータのオフセットを表す int32型だ。

このメタデータは実行時に runtime.moduledata構造体にロードされる。(src/runtime/symtab.go)

ELFファイルの中身を見たことがあるなら、とてもよく似たものに見えるだろう。

ランタイムは、moduledata構造体を介してこれらのオフセットから必要な値(name, _type)を得るために必要な以下のヘルパーを提供している

// nameOff から nameを導く 
func resolveNameOff(ptrInModule unsafe.Pointer, off nameOff) name {}

// typeOff から _typeを導く
func resolveTypeOff(ptrInModule unsafe.Pointer, off typeOff) *_type {}

例: t を _type として resolveTypeOff(t, t.ptrToThis) を呼び出すと tのコピーが返る。

interfacetype構造体

最後は interfacetype構造体だ。 (src/runtime/type.go):

type interfacetype struct { // 80 bytes on a 64bit arch
    typ     _type
    pkgpath name
    mhdr    []imethod
}

type imethod struct {
    name nameOff
    ityp typeOff
}

上で述べたように、interfacetype は _type にインターフェースに必要なメタデータを加えてラップした単なる_typeのラッパーだ。

現在の実装では、このメタデータは

それぞれの名前を指すオフセット(pkgpath: name)
インターフェースが実装すべきメソッドの型のリスト(mhdr: []imethod)

から構成される。

まとめ

最後に今までのことを全部おさらいできるように、ifaceのネストを全部解決して表したときにどのようになるか見てみよう。

// `iface`
type iface struct {

    // `itab` インターフェースの中核
    tab *struct {

        // `interfacetype` `_type`にメタデータを加えたラッパー
        inter *struct {

            // `_type`
            typ struct {
                size       uintptr
                ptrdata    uintptr
                hash       uint32
                tflag      tflag
                align      uint8
                fieldalign uint8
                kind       uint8
                alg        *typeAlg
                gcdata     *byte
                str        nameOff
                ptrToThis  typeOff
            }
            pkgpath name

            // `imethod` メソッドの名前と型のリスト
            mhdr    []struct {
                name nameOff
                ityp typeOff
            }
        }

        // `_type` Goの型を表す内部表現
        _type *struct {
            size       uintptr
            ptrdata    uintptr
            hash       uint32
            tflag      tflag
            align      uint8
            fieldalign uint8
            kind       uint8
            alg        *typeAlg
            gcdata     *byte
            str        nameOff
            ptrToThis  typeOff
        }
        hash uint32
        _    [4]byte
        fun  [1]uintptr
    }
    data unsafe.Pointer
}

このセクションではインターフェースを構成する様々な部品に親しみを持てるように、インターフェースを構成する様々なデータ型と、それらがどのように相互作用するかをざっと見ていった。

次のセクションでは、これらのデータ構造が実際にどう処理されていくか見ていく。

インターフェースの構築

関係のあるデータ構造については一通り見て行ったので、実際にそれらがどのように割り当てられ初期化されているのかに注目しよう。

次のプログラムを考える。 (iface.go)

type Mather interface {
    Add(a, b int32) int32
    Sub(a, b int64) int64
}

type Adder struct{ id int32 }
//go:noinline
func (adder Adder) Add(a, b int32) int32 { return a + b }
//go:noinline
func (adder Adder) Sub(a, b int64) int64 { return a - b }

func main() {
    m := Mather(Adder{id: 6754})

    // この関数呼び出しはインターフェースが実際にどのように利用されるかを確認するためだけのもの
    // この関数呼び出しがないと、リンカは Matherインターフェース が決して使われていないということを検知して実行ファイルに含めないように最適化してしまう
    m.Add(10, 32)
}

NOTE: 以降では、IインターフェースがT型を含んでいることを <I,T> と表す。例えば Mather(Adder{id: 6754}) は　iface<Mather, Adder>と表記する

iface<Mather, Adder>のインスタンスに注目していく

m := Mather(Adder{id: 6754})

コンパイラによって生成されるアセンブリから分かるように、この1行のGoのコードはたくさんの中身を持っている。

;; part 1: レシーバーを割り当てる
0x001d MOVL	$6754, ""..autotmp_1+36(SP)

;; part 2: itabをセットアップ
0x0025 LEAQ	go.itab."".Adder,"".Mather(SB), AX
0x002c MOVQ	AX, (SP)

;; part 3: dataをセットアップ
0x0030 LEAQ	""..autotmp_1+36(SP), AX
0x0035 MOVQ	AX, 8(SP)
0x003a CALL	runtime.convT2I32(SB)
0x003f MOVQ	16(SP), AX
0x0044 MOVQ	24(SP), CX

3つのパートに分割して解説していく

Part 1: レシーバの確保

0x001d MOVL	$6754, ""..autotmp_1+36(SP)

Adder のIDに相当する定数 6754 は現在のスタックフレームの最初に格納される。

そうすることで、コンパイラがアドレスを使って後々参照できるようになる。これについては part3 で理由を見ていく。

Part 2: itabのセットアップ

ifaceは itab と data からなる構造体だがここでは itabの初期化を行っている

0x0025 LEAQ	go.itab."".Adder,"".Mather(SB), AX
0x002c MOVQ	AX, (SP)

コンパイラはすでに iface<Mather, Adder> を表現するのに必要な itab を生成しており、グローバルなシンボル go.itab."".Adder,"".Mather を通して我々がそれを利用できるようにしているように見える

iface<Mather, Adder>インターフェースはこの時点でまだ作成中であり、これを完成されるためにグローバルシンボル go.itab."".Adder,"".Mather の実行アドレスを現在のスタックフレームの一番上にPUSHしている。

これも、part3 で理由を見ていく

Goの疑似コードで表すなら意味的には以下のコードのようになる

tab := getSymAddr(`go.itab.main.Adder,main.Mather`).(*itab)

これでインターフェースの半分は完成だ。

今度は go.itab."".Adder,"".Matherシンボルをより深く見ていこう

いつものように -Sフラグをコンパイル時につけて得られる情報を増やそう

-S: Print assembly listing to standard output (code and data).

$ GOOS=linux GOARCH=amd64 go tool compile -S iface.go | grep -A 7 '^go.itab."".Adder,"".Mather'
go.itab."".Adder,"".Mather SRODATA dupok size=40
    0x0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
    0x0010 8a 3d 5f 61 00 00 00 00 00 00 00 00 00 00 00 00  .=_a............
    0x0020 00 00 00 00 00 00 00 00                          ........
    rel 0+8 t=1 type."".Mather+0
    rel 8+8 t=1 type."".Adder+0
    rel 24+8 t=1 "".(*Adder).Add+0
    rel 32+8 t=1 "".(*Adder).Sub+0

1つずつ分けて解説していこう。

最初の部分は、シンボルとその属性について宣言している。

go.itab."".Adder,"".Mather SRODATA dupok size=40

これは、リンカを実行する前のコンパイラによって生成されるオブジェクトファイルなのでシンボル名にパッケージ名は結び付けられていない。この時点では新しいことは何もないだろう。

さらに見ていくと、生成するバイナリの .rodataセクションに40byteのグローバルなオブジェクトシンボルが格納されることがわかる。

dupokディレクティブは、duplicate OKの略で、リンカにそのシンボルがリンク時に複数回出てきても問題ないことを教えている。このとき、リンカは1つ任意のシンボルを選択する必要がある。

Go開発者がなぜこのシンボルが重複するかもしれないと考えるようになったかについての明確な理由は思いつかない。もし何か知っているなら気軽にissueを出して欲しい。

[UPDATE: We've discussed about this matter in issue #7: How you can get duplicated go.itab interface definitions.]

次に、シンボルと結びついた40byteのhexdumpされたデータを見ていこう。これは itab構造体をシリアライズしたものだ。

0x0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
0x0010 8a 3d 5f 61 00 00 00 00 00 00 00 00 00 00 00 00  .=_a............
0x0020 00 00 00 00 00 00 00 00                          ........

この時点では、大半のフィールドの中身はゼロ値だ。すぐ見ることになるがリンカはこれらのフィールドを埋める役割を持っている。

ほぼ全てが 0 だが、0x10から 0x10+4までの4byteまでに0以外の値がセットされているのが見える。

itab構造体の定義を振り返ってどのフィールドがこの4byteに対応するかチェックしよう

itabの定義を振り返って、各フィールドに相対オフセットを付与したものがこちらだ。

type itab struct {          // 40 bytes on a 64bit arch
    inter *interfacetype    // offset 0x00 ($00)
    _type *_type	        // offset 0x08 ($08)
    hash  uint32	        // offset 0x10 ($16)
    _     [4]byte	        // offset 0x14 ($20)
    fun   [1]uintptr	    // offset 0x18 ($24)
}

0x10から 0x10+4までの4byte は hash uint32に対応していることがわかる。つまり main.Adder に対応するハッシュ値はオブジェクトファイルの時点で設定されている。

最後の部分はリンカに再配置の情報を伝えるためのディレクティブのリストだ。

rel 0+8 t=1 type."".Mather+0
rel 8+8 t=1 type."".Adder+0
rel 24+8 t=1 "".(*Adder).Add+0
rel 32+8 t=1 "".(*Adder).Sub+0

rel 0+8 t=1 type."".Mather+0は、最初の8byte(0+8)にグローバルなオブジェクトシンボルtype."".Matherのアドレスを配置することをリンカに指示している。

次に、rel 8+8 t=1 type."".Adder+0では次の8byteにtype."".Adderのアドレスを配置するように示している。

リンカがこのディレクティブどおりに実行されれば、このシリアライズされたitabの40byteにすべてデータが配置される。

疑似コードをみてどのようなことをしているかおさらいしよう

tab := getSymAddr(`go.itab.main.Adder,main.Mather`).(*itab)

// NOTE: 実行ファイルをビルドするときにリンカはこれらのシンボルから `type.`プレフィックスを引き剥がす。
// なのでバイナリの.rodataセクションの最終的なシンボル名は、 
// `type.main.Mather` と `type.main.Adder` ではなく `main.Mather` と `main.Adder`
// になる
// objdumpをいじるときに、これにつまずかないように注意
tab.inter = getSymAddr(`type.main.Mather`).(*interfacetype)
tab._type = getSymAddr(`type.main.Adder`).(*_type)

tab.fun[0] = getSymAddr(`main.(*Adder).Add`).(uintptr)
tab.fun[1] = getSymAddr(`main.(*Adder).Sub`).(uintptr)

itabの準備はできた。あとはdataがあれば、itabは完全なインターフェースとなる。

Part 3: dataのセットアップ

前も述べたように、ifaceは itab と dataからなる構造体だ

Part2では itab の初期化を行なったので Part3では data の初期化を行い、ifaceを完成させる

0x0030 LEAQ	""..autotmp_1+36(SP), AX
0x0035 MOVQ	AX, 8(SP)
0x003a CALL	runtime.convT2I32(SB)
0x003f MOVQ	16(SP), AX
0x0044 MOVQ	24(SP), CX

Part1で定数$6754 を ""..autotmp_1+36(SP)にしたが、これをスタックの上から2番目8(SP) に格納している。

また、Part2で go.itab."".Adder,"".Mather(1個目の引数)をスタックの一番上(SP) に格納している。

つまり arg1 = &(go.itab."".Adder,"".Mather), arg2 = &($6754)

これらの2つのポインタは runtime.convT2I32 に引数として渡される。 runtime.convT2I32 は interfaceを完成させてそれを返り値として返す役割を持った関数だ。

内部実装を見てみよう。 (src/runtime/iface.go):

func convT2I32(tab *itab, elem unsafe.Pointer) (i iface) { // 1

    // 3
    t := tab._type
    /* ...omitted debug stuff... */
    var x unsafe.Pointer
    if *(*uint32)(elem) == 0 {
        x = unsafe.Pointer(&zeroVal[0])
    } else {
        x = mallocgc(4, t, false)        // 3-1
        *(*uint32)(x) = *(*uint32)(elem) // 3-2
    }

    i.tab = tab // 2
    i.data = x
    return // 4
}

runtime.convT2I32 は以下の4つのことを行っている

新しい iface構造体 i を生成している。
インターフェースのitabポインタフィールドi.tab に引数として渡されたtab をセットしている
型を表すオブジェクト i.tab._typeを新たにヒープ上に確保している。(3-1) そしてそのヒープ上に確保したオブジェクトに第2引数elemが指す値をコピーしている(3-2)
最後に完成したインターフェースiをリターンする

全体的に平易なプロセスだったが、3番目だけは少々トリッキーな実装だったかもしれない。

これはAdder構造体がスカラー型であることに起因している。

スカラー型とインターフェースがどのように作用し合うかについてはスカラー型を保持するインターフェースで詳細を見ていく。

いつものように、疑似コードを使って内容をおさらいしよう。

tab := getSymAddr(`go.itab.main.Adder,main.Mather`).(*itab)
elem := getSymAddr(`""..autotmp_1+36(SP)`).(*int32)

i := runtime.convTI32(tab, unsafe.Pointer(elem))

assert(i.tab == tab)
assert(*(*int32)(i.data) == 6754) // same value..
assert((*int32)(i.data) != elem)  // ..but different (al)locations!

おさらいとしてコメントで補足したアセンブリを使って振り返ろう

0x001d MOVL	$6754, ""..autotmp_1+36(SP)         ;; create an addressable $6754 value at 36(SP)
0x0025 LEAQ	go.itab."".Adder,"".Mather(SB), AX  ;; set up go.itab."".Adder,"".Mather..
0x002c MOVQ	AX, (SP)                            ;; ..as first argument (tab *itab)
0x0030 LEAQ	""..autotmp_1+36(SP), AX            ;; set up &36(SP)..
0x0035 MOVQ	AX, 8(SP)                           ;; ..as second argument (elem unsafe.Pointer)
0x003a CALL	runtime.convT2I32(SB)               ;; call convT2I32(go.itab."".Adder,"".Mather, &$6754)
0x003f MOVQ	16(SP), AX                          ;; AX now holds i.tab (go.itab."".Adder,"".Mather)
0x0044 MOVQ	24(SP), CX                          ;; CX now holds i.data (&$6754, somewhere on the heap)

このアセンブリがたった1行のコード m := Mather(Adder{id: 6754}) から生成されたことを覚えておこう

interfaceの生成についてはこれで完了だ。

実行ファイルから `itab`を再構築する

前のセクションで、コンパイラによって出力されたオブジェクトファイルから go.itab."".Adder,"".Mather の内容をダンプし、hashを除いたフィールドがゼロ値であることを確認した。

$ GOOS=linux GOARCH=amd64 go tool compile -S iface.go | grep -A 3 '^go.itab."".Adder,"".Mather'
go.itab."".Adder,"".Mather SRODATA dupok size=40
    0x0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
    0x0010 8a 3d 5f 61 00 00 00 00 00 00 00 00 00 00 00 00  .=_a............
    0x0020 00 00 00 00 00 00 00 00                          ........

リンカによって最終的に生成される実行ファイルにデータがどのように配置されていくのかをよく見るには、実行ファイルであるELFファイルの中を見て、iface<Mather, Adder> の itabを構成するバイトデータを自分たちの手で再構築していくのがよい方法だ。

幸運なことに、リンカによって処理がされた後の itab の内容を見ることは容易にできる。

最初に ifaceバイナリをビルドしよう: GOOS=linux GOARCH=amd64 go build -o iface.bin iface.go

Step 1: .rodataを探す

.rodataセクションはELFファイルの中でもconst宣言したデータや文字列リテラルなどの読み取り専用のデータが配置されるセクションだ。

.rodata を探すために、セクションヘッダを見てみよう。それには readelf を使う:

$ readelf -St -W iface.bin
There are 22 section headers, starting at offset 0x190:

セクションヘッダ:
  [番] 名前
       型              アドレス         Off    サイズ ES   Lk Inf Al
       フラグ
  [ 0] 
       NULL            0000000000000000 000000 000000 00   0   0  0
       [0000000000000000]: 
  [ 1] .text
       PROGBITS        0000000000401000 001000 04b3cf 00   0   0 16
       [0000000000000006]: ALLOC, EXEC
  [ 2] .rodata
       PROGBITS        000000000044d000 04d000 028ac4 00   0   0 32
       [0000000000000002]: ALLOC
## ...omitted rest of output...

readelf 補足

-S: セクションヘッダを表示
-t: セクションの詳細を表示
-W: 出力幅が 80 文字を超えることを許可

ここで本当に必要なのはセクションの10進数でのオフセットだ。そこで以下のようにしてオフセットを得る。

$ readelf -St -W iface.bin | \
  grep -A 1 .rodata | \
  tail -n +2 | \
  awk '{print "ibase=16;"toupper($3)}' | \
  bc
315392

必要なのは3列目(Off)の値なので、toupper($3) で取り出している。

ELFファイルの315392バイト目から .rodataセクションが始まることがわかる。

次にやることは、このファイルの位置をメモリ上の仮想アドレスにマッピングすることだ。

Step 2: .rodataセクションが配置される仮想アドレス(VMA)を探す

VMAは Virtual Memory Address の略でバイナリがOSによってメモリ上にロードされる時にセクションがマッピングされる仮想アドレスのことだ。
(正確にはこれはLMA。VMAはセクションをリンクするときにベースとなるアドレスだが基本 VMA = LMA なので問題ない)

実行時にシンボルを参照するのにもこの仮想アドレスを用いて参照する

ここではVMAだけを考えればよい。なぜなら readelf や objdump から直接特定のシンボルのオフセットを知ることは不可能だからだ。

しかし、特定のシンボルのVMAを知ることは可能だ。

いくつかの単純な計算を行えば、VMAとオフセットの間のマッピングができ、そして探しているシンボルのオフセットがわかるはずだ。

readelfで出力される内容の2列目(アドレス)がセクションのVMAを表している。

$ readelf -St -W iface.bin | \
  grep -A 1 .rodata | \
  tail -n +2 | \
  awk '{print "ibase=16;"toupper($2)}' | \
  bc
4509696

この時点でわかったことは、.rodataセクションはELFファイルの$315392 (=0x04d000) にマッピングされ、実行時にプロセスの仮想アドレス$4509696 (=0x44d000)にロードされるということだ。

次に必要なのは、シンボルのサイズとVMAだ:

VMAがわかれば間接的にシンボルが実行ファイルのどこに配置されたのかがわかる
サイズがわかれば、オフセットがわかったときにオフセットから何バイトまでのデータを見ればいいのかわかる

Step 3: go.itab.main.Adder,main.MatherのVMAとサイズを取得する

ここでobjdumpを使う。

まずシンボルを見つける

$ objdump -t -j .rodata iface.bin | grep "go.itab.main.Adder,main.Mather"
0000000000475140 g     O .rodata	0000000000000028 go.itab.main.Adder,main.Mather

各カラムの値はWhat does each column of objdump's Symbol table mean?を参照

シンボルのVMAは1列目(1から数えて)なので

$ objdump -t -j .rodata iface.bin | \
  grep "go.itab.main.Adder,main.Mather" | \
  awk '{print "ibase=16;"toupper($1)}' | \
  bc
4673856

シンボルのサイズは5列目なので

$ objdump -t -j .rodata iface.bin | \
  grep "go.itab.main.Adder,main.Mather" | \
  awk '{print "ibase=16;"toupper($5)}' | \
  bc
40

これらから、go.itab.main.Adder,main.Mather は実行時に仮想アドレス$4673856 (=0x475140)にマップされそのサイズは40byte(これは既に見たitab構造体のサイズと一致する)だということがわかった。

Step 4: go.itab.main.Adder,main.Matherのデータを取得する

バイナリ中のgo.itab.main.Adder,main.Matherを特定するのに必要なピースが全て揃った

今までわかったことをもう一度まとめよう

.rodata offset: 0x04d000 == $315392
.rodata VMA: 0x44d000 == $4509696

go.itab.main.Adder,main.Mather VMA: 0x475140 == $4673856
go.itab.main.Adder,main.Mather size: 0x24 = $40

セクションの内容はELFファイルの中でも実行時のメモリの中でも変わらない。

よって.rodataセクションを開始地点としたシンボルのオフセット$4673856 - $4509696 をrodataセクションのELF内オフセットに足してあげることでシンボルのELF内オフセットを得ることができる。

sym.offset = sym.vma - section.vma + section.offset = $4673856 - $4509696 + $315392 = $479552

やっとシンボルのサイズとオフセットがわかったので、ddコマンドを使ってELFファイルから、実際のバイトデータをダンプしてみよう。

$ dd if=iface.bin of=/dev/stdout bs=1 count=40 skip=479552 2>/dev/null | hexdump
0000000 bd20 0045 0000 0000 ed40 0045 0000 0000
0000010 3d8a 615f 0000 0000 c2d0 0044 0000 0000
0000020 c350 0044 0000 0000                    
0000028

念のため、このダンプしたバイトが本当にgo.itab.main.Adder,main.Matherの中身を表しているかを確認しよう。

ダンプしたデータがitabだと仮定してhashフィールドの内容を実際にランタイムにロードされる値と比べてみる。(iface_type_hash.go)

// simplified definitions of runtime's iface & itab types
type iface struct {
    tab  *itab
    data unsafe.Pointer
}
type itab struct {
    inter uintptr
    _type uintptr
    hash  uint32
    _     [4]byte
    fun   [1]uintptr
}

func main() {
    m := Mather(Adder{id: 6754})

    iface := (*iface)(unsafe.Pointer(&m))
    fmt.Printf("iface.tab.hash = %#x\n", iface.tab.hash) // 0x615f3d8a
}

ダンプしたデータによると、hashフィールドはオフセットが0x10+4 なので0x615f3d8aだが、これは実際の値と一致する。

まとめ

iface<Mather, Adder>インターフェースのitabの内容をELFファイルから抽出した。

その結果、実行ファイルにはランタイムがインターフェースに期待通りの挙動をさせるのに必要な情報が全て含まれていることがわかった。

実行ファイルには itab の他にもデータ構造のポインタもたくさん含まれているので、ddコマンドでitabをサルベージするにはVMAを使ってやる必要があった。

ポインタについて言えば、iface<Mather, Adder>の vtable を明確に表示できるようになった。

おさらいとして go.itab.main.Adder,main.Mather の内容に注釈で補足をつけた。

$ dd if=iface.bin of=/dev/stdout bs=1 count=40 skip=479552 2>/dev/null | hexdump
0000000 bd20 0045 0000 0000 ed40 0045 0000 0000
0000010 3d8a 615f 0000 0000 c2d0 0044 0000 0000
#                           ^^^^^^^^^^^^^^^^^^^
#                       offset 0x18+8: itab.fun[0]
0000020 c350 0044 0000 0000                    
#       ^^^^^^^^^^^^^^^^^^^
# offset 0x20+8: itab.fun[1]
0000028

itab.fun[0] は 0x0044c2d0 を指しているので

$ objdump -t -j .text iface.bin | grep 000000000044c2d0
000000000044c2d0 g     F .text	0000000000000079 main.(*Adder).Add

itab.fun[1] は 0x0044c350 を指しているので

$ objdump -t -j .text iface.bin | grep 000000000044c350
000000000044c350 g     F .text	000000000000007f main.(*Adder).Sub

特に驚くことでもないが、iface<Mather, Adder> のvirtual tableは2つのメソッドのポインタ(main.(*Adder).add と main.(*Adder).sub)を保持している。

といっても、少し予想外のこともある。よく見てみると、この2つのメソッドはレシーバーとしてポインタを受け取るようになっている。(iface.goでレシーバは実体だったことを思い出そう)

インターフェースはポインタしか保持できず、iface.goで実装したAdderは実体をレシーバーとして受け取るメソッドしか実装していないので、これらのメソッドをインターフェースのvtable を通して呼び出すにはどこかの時点でラッパーを噛ませる必要がある。

そこで暗黙の参照外しのセクションで説明したように、コンパイラは自分自身でこれらのラッパーを生成してくれる。

次のセクションで見ていくことになるが、このことは実行時にどのように dynamic dispatch 行われるかについての重要な視点を与えてくれる。

Dynamic dispatch

このセクションでは、インターフェースの一番の特徴である dynamic dispatch について説明する。

まず dynamic dispatch がどのように機能し、どれくらいのコストがあるのか見ていこう

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

以前にも載せたこのコードを見て欲しい (iface.go)

type Mather interface {
    Add(a, b int32) int32
    Sub(a, b int64) int64
}

type Adder struct{ id int32 }
//go:noinline
func (adder Adder) Add(a, b int32) int32 { return a + b }
//go:noinline
func (adder Adder) Sub(a, b int64) int64 { return a - b }

func main() {
    m := Mather(Adder{id: 6754})
    m.Add(10, 32)
}

このコードの一部は上のセクションでじっくりと解説をしてきた。そこでは iface<Mather, Adder> がどのように生成され、実行ファイルにどのように配置され、そして実行時にどのようにロードされるかを見た。

残ったのは、実際に間接呼び出しを行っている部分の m.Add(10, 32) だ

おさらいとして、メソッドの呼び出しだけでなくインターフェースの作成にも焦点を当てよう。

m := Mather(Adder{id: 6754})
m.Add(10, 32)

ありがたいことに、インスタンス生成を行うm := Mather(Adder{id: 6754})についてはアセンブリも含めてすでに解説済みだ。

;; m := Mather(Adder{id: 6754})
0x001d MOVL	$6754, ""..autotmp_1+36(SP)         ;; 36(SP)に即値$6754(Adder)を格納
0x0025 LEAQ	go.itab."".Adder,"".Mather(SB), AX  ;; go.itab."".Adder,"".Matherを..
0x002c MOVQ	AX, (SP)                            ;; 1個目の引数に (tab *itab)
0x0030 LEAQ	""..autotmp_1+36(SP), AX            ;; &36(SP)、つまり&Adderを..
0x0035 MOVQ	AX, 8(SP)                           ;; 2個目の引数に (elem unsafe.Pointer)
0x003a CALL	runtime.convT2I32(SB)               ;; runtime.convT2I32(go.itab."".Adder,"".Mather, &$6754) を呼び出す
0x003f MOVQ	16(SP), AX                          ;; AX に i.tab (go.itab."".Adder,"".Mather) を格納
0x0044 MOVQ	24(SP), CX                          ;; CX に i.data (&$6754, ヒープのどこかにある) を格納

そして、今回はインターフェースごしにメソッドの呼び出す部分(m.Add(10, 32))のアセンブリを記した。

;; m.Add(10, 32)
0x0049 MOVQ	24(AX), AX
0x004d MOVQ	$137438953482, DX
0x0057 MOVQ	DX, 8(SP)
0x005c MOVQ	CX, (SP)
0x0060 CALL	AX

ここまで読んだ人ならいくつかの命令はもう意味がわかるだろう。

0x0049 MOVQ	24(AX), AX

runtime.convT2I32から返った時点で、AXにはitabのポインタであるi.tabが格納されている。もっと正確にいうならば、この場合はgo.itab."".Adder,"".Matherのポインタだ。

24(AX) でAXの参照外し(AXは i.tab のアドレスを指している)を行ってさらに24バイト進めたことになるつまり、これによってi.tabのオフセット24である i.tab.fun を取得したことになる

念のため、itab構造体の中身を確認する

type itab struct { // 32 bytes on a 64bit arch
    inter *interfacetype // offset 0x00 ($00)
    _type *_type	 // offset 0x08 ($08)
    hash  uint32	 // offset 0x10 ($16)
    _     [4]byte	 // offset 0x14 ($20)
    fun   [1]uintptr	 // offset 0x18 ($24)
			 // offset 0x20 ($32)
}

前のセクションで iface.tab.fun[0] は ELFファイルの中で、コンパイラがポインタをレシーバとしてとるようにラップしたメソッドである main.(*Adder).add を指していることを突き止めたことを思い出しておこう。

0x004d MOVQ	$137438953482, DX
0x0057 MOVQ	DX, 8(SP)

10 と 32 を2,3個目の引数としてスタックに積んでいる

0x005c MOVQ	CX, (SP)
0x0060 CALL	AX

また、runtime.convT2I32から返った時点で、CXにはAdderインスタンスのポインタであるi.dataが格納されている。

これを1個目の引数としてスタックの一番上にセットすることで呼び出し規約を満たす。(レシーバは常に1個目の引数として渡される)

あとは関数(m.Add(10, 32))をCALLで呼ぶだけだ。

最後に注釈を施したアセンブリでおさらいしてこのセクションを締めくくろう。

;; m := Mather(Adder{id: 6754})
0x001d MOVL	$6754, ""..autotmp_1+36(SP)         ;; 36(SP)に即値$6754(Adder)を格納
0x0025 LEAQ	go.itab."".Adder,"".Mather(SB), AX  ;; go.itab."".Adder,"".Matherを..
0x002c MOVQ	AX, (SP)                            ;; 1個目の引数に (tab *itab)
0x0030 LEAQ	""..autotmp_1+36(SP), AX            ;; &36(SP)、つまり&Adderを..
0x0035 MOVQ	AX, 8(SP)                           ;; 2個目の引数に (elem unsafe.Pointer)
0x003a CALL	runtime.convT2I32(SB)               ;; runtime.convT2I32(go.itab."".Adder,"".Mather, &$6754) を呼び出す
0x003f MOVQ	16(SP), AX                          ;; AX に i.tab (go.itab."".Adder,"".Mather) を格納
0x0044 MOVQ	24(SP), CX                          ;; CX に i.data (&$6754, ヒープのどこかにある) を格納

;; m.Add(10, 32)
0x0049 MOVQ	24(AX), AX                          ;; AX に (*iface.tab)+0x18 これは iface.tab.fun[0] に相当する
0x004d MOVQ	$137438953482, DX                   ;; (32,10)
0x0057 MOVQ	DX, 8(SP)                           ;; スタックにPUSH (引数 #3 & #2)
0x005c MOVQ	CX, (SP)                            ;; CX が保持している &$6754(つまり&Adder)をスタックにPUSH(引数 #1)
0x0060 CALL	AX                                  ;; AXに格納された`Add`を呼び出す

インターフェース越しのメソッドの呼び出しがどのように機能するかについてはこれで以上だ。

次のセクションでは、この仕組みがどれだけのコストを要するかを、理論と実行の両方の面から見ていこう。

Overhead

これまで見たようにインターフェースの実装は、大半の部分をコンパイラとリンカにまかせている。

つまり、厄介な作業を実行時ではなくビルド時にやってくれるので、実行時のパフォーマンスという観点から見たときこれは非常によいことだ。

それほど一般的ではないが、runtime.convT2*関連の関数など、インターフェイスをインスタンス化するためにランタイムが機能する必要なときもある。

このような一般的でないケースは section dedicated to the special cases of interfaces で取り扱う。

結局、我々はインスタンス化時に生じる一度きりのコストではなく、dynamic dispatchのオーバーヘッドだけに集中すればよい。

補足:

Goのdynamic dispatchはコンパイル時ではなく、ランタイム時に行われます。

This is not pure duck typing, because when possible the Go compiler will statically check whether the type implements the interface. However, Go does have a purely dynamic aspect, in that you can convert from one interface type to another. In the general case, that conversion is checked at runtime.

インターフェースのインスタンスが生成されてしまえば、メソッドの呼び出しは、通常のメソッド呼び出しに1枚レイヤーを噛ませただけのものに過ぎない。(ここでのレイヤーとは、itab.funから指定したインデックスの関数の参照を外すこと)

そのため、メソッド呼び出しのコストは無いも同然であると考えたくなるが、実際には少し違う。

これを説明するには理論と実装面の両方で少々難しいことを説明する必要がある

The theory: 現代のCPUの機能について

インターフェース越しのメソッド呼び出しに伴って追加された処理は、CPUがある程度予測可能な場合に限って実質ノーコストで行うことができる。

現代のCPUはメモリのキャッシュや命令やデータのプリフェッチ、命令の事前実行、Out-Of-Orderやスーパースカラなど非常に積極的な最適化を行っている。

これらの最適化処理は望まなくても勝手にされてしまうので、プログラマはCPUの最適化の邪魔をしないように常に努力する必要がある。つまりCPUが何もせず待機する時間をなるべく増やさないようにする必要があるのだ。

これはdynamic dispatch時に問題になってくる。

static dispatch の場合は、プログラムの今後の条件分岐の結果(つまり呼び出すメソッド)を事前に知っておき、それに応じた必要な命令をプリフェッチする。

事前に結果がわかっていれば、条件分岐でジャンプするとしてもパフォーマンスへの影響はないも同然だ。

一方で dynamic dispatch の場合は実行時にどのメソッドを呼び出すかをチェックするのでCPUはどのプログラムを実行するか事前に知りようがない。それらは全て実行してみるまでわからない。

これへの対処法として、次にどちらの分岐にいくべきかを予想するため、CPUは様々なアルゴリズムと経験則に基づく予想を適用している。(分岐予測)

予測がうまく行けば、命令はプリフェッチされキャッシュされるので、dynamic dispatchのコストは static dispatchのそれとほぼ変わらない。

しかし、うまくいかなかった場合は、厄介な事態になる。まず当然だが、命令はキャッシュされていないので、メモリからL1iキャッシュに命令をロードする必要がある。この間、CPUは実質ストールしている。

さらに、CPUを予測を間違えた分岐の時点まで巻き戻してあげる必要もある。パイプラインの内容も全て取り消す必要がある。

dynamic dispatch のもう1つの重要な欠点は、定義上インライン化が不可能ということだ。

まとめると、理論上では、インライン化された関数F に対する static dispatch な関数呼び出しと、インライン化できずさらに外れる可能性のある分岐予測を伴う dynamic dispatch な関数呼び出しの間には大きな違いが存在する。

現代のCPUに関しては、常にこれらの理論のことを念頭に入れておく必要がある。

The practice: ベンチマーク

今回ベンチマーク測定に使うCPUに関する情報を予め記載しておく

$ lscpu | sed -nr '/Model name/ s/.*:\s*(.* @ .*)/\1/p'
Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

今回ベンチマークの測定に使うインターフェースの定義だ。(iface_bench_test.go)

type identifier interface {
    idInline() int32
    idNoInline() int32
}

type id32 struct{ id int32 }

// NOTE: 今回はwrapperの自動生成によるオーバーヘッドの増加が結果に影響を与えないようにポインタをレシーバとする

func (id *id32) idInline() int32 { return id.id }
//go:noinline
func (id *id32) idNoInline() int32 { return id.id }

Benchmark suite A: 単一のインスタンス + 数度の関数呼び出し + インライン関数と通常の関数の場合

ベンチマーク測定の1つ目は、インライン化されていないメソッドを *Adderポインタと iface<Mather, *Adder>インターフェースからで呼び出してみる

var escapeMePlease *id32

// escapeToHeap は `id`がちゃんとheapに退避されるようにするための関数
//
// 今回のファイルのベンチマークテストのような場合では、コンパイラはインターフェースがラップしている型を
// 推測して dynamic dispatch で本来呼び出す部分を static dispatchに最適化してしまう。
// `id`をヒープに逃すことでこの最適化を防ぐことができる。
//
//go:noinline
func escapeToHeap(id *id32) identifier {
    escapeMePlease = id
    return escapeMePlease
}

var myID int32

func BenchmarkMethodCall_direct(b *testing.B) {
    b.Run("single/noinline", func(b *testing.B) {
        m := escapeToHeap(&id32{id: 6754}).(*id32)
        for i := 0; i < b.N; i++ {
            // CALL "".(*id32).idNoInline(SB)
            // MOVL 8(SP), AX
            // MOVQ "".&myID+40(SP), CX
            // MOVL AX, (CX)
            myID = m.idNoInline()
        }
    })
}

func BenchmarkMethodCall_interface(b *testing.B) {
    b.Run("single/noinline", func(b *testing.B) {
        m := escapeToHeap(&id32{id: 6754})
        for i := 0; i < b.N; i++ {
            // MOVQ 32(AX), CX
            // MOVQ "".m.data+40(SP), DX
            // MOVQ DX, (SP)
            // CALL CX
            // MOVL 8(SP), AX
            // MOVQ "".&myID+48(SP), CX
            // MOVL AX, (CX)
            myID = m.idNoInline()
        }
    })
}

今回のベンチマーク測定では、 A) と B)　がどちらも非常に速く実行されると想定される

ループの回数を考えると今回のベンチマーク測定では、インターフェースが指すデータ(レシーバと vtable) と命令列("".(*id32).idNoInline) は CPUのL1d/L1i(d:データ, i:命令)キャッシュにすでに全部格納されていて、CPU以外にパフォーマンスへ影響を及ぼすものはないと考えられる。

それでもインターフェース越しに呼び出す BenchmarkMethodCall_interface のほうがほんの少しだが遅くなっている。L1キャッシュからとはいえ、vtableからメソッドのポインタを見つけてコピーするオーバーヘッドの分遅くなっている。

CALL CX命令は、vtableからのフェッチ結果を必要とするので、プロセッサはフェッチ処理とCALL CXを並列に実行することはできず、同期的にvtableからのフェッチ処理を行う必要がある。

これがインターフェースを使った場合にベンチマークが悪くなる理由だ。

インターフェースを介さず直接メソッドを呼び出した場合の結果を見てみよう。

$ go test -run=NONE -o iface_bench_test.bin iface_bench_test.go && \
  perf stat --cpu=1 \
  taskset 2 \
  ./iface_bench_test.bin -test.cpu=1 -test.benchtime=1s -test.count=3 \
      -test.bench='BenchmarkMethodCall_direct/single/noinline'
BenchmarkMethodCall_direct/single/noinline         	2000000000	         1.81 ns/op
BenchmarkMethodCall_direct/single/noinline         	2000000000	         1.80 ns/op
BenchmarkMethodCall_direct/single/noinline         	2000000000	         1.80 ns/op

 Performance counter stats for 'CPU(s) 1':

      11702.303843      cpu-clock (msec)          #    1.000 CPUs utilized          
             2,481      context-switches          #    0.212 K/sec                  
                 1      cpu-migrations            #    0.000 K/sec                  
             7,349      page-faults               #    0.628 K/sec                  
    43,726,491,825      cycles                    #    3.737 GHz                    
   110,979,100,648      instructions              #    2.54  insn per cycle         
    19,646,440,556      branches                  # 1678.852 M/sec                  
           566,424      branch-misses             #    0.00% of all branches        

      11.702332281 seconds time elapsed

今度はインターフェースを介した場合の結果だ。

$ go test -run=NONE -o iface_bench_test.bin iface_bench_test.go && \
  perf stat --cpu=1 \
  taskset 2 \
  ./iface_bench_test.bin -test.cpu=1 -test.benchtime=1s -test.count=3 \
      -test.bench='BenchmarkMethodCall_interface/single/noinline'
BenchmarkMethodCall_interface/single/noinline         	2000000000	         1.95 ns/op
BenchmarkMethodCall_interface/single/noinline         	2000000000	         1.96 ns/op
BenchmarkMethodCall_interface/single/noinline         	2000000000	         1.96 ns/op

 Performance counter stats for 'CPU(s) 1':

      12709.383862      cpu-clock (msec)          #    1.000 CPUs utilized          
             3,003      context-switches          #    0.236 K/sec                  
                 1      cpu-migrations            #    0.000 K/sec                  
            10,524      page-faults               #    0.828 K/sec                  
    47,301,533,147      cycles                    #    3.722 GHz                    
   124,467,105,161      instructions              #    2.63  insn per cycle         
    19,878,711,448      branches                  # 1564.097 M/sec                  
           761,899      branch-misses             #    0.00% of all branches        

      12.709412950 seconds time elapsed

結果は予想通り、インターフェースを介した場合の方が8%ほど遅くなった。

8%はかなりの差があるように感じるが、

ナノ秒単位の測定であること
呼ばれたメソッドはほとんど処理をしないメソッド

の2点を考えると、今回のベンチマークテストでは関数呼び出しのオーバーヘッドによる影響が誇張されていると考えるのが妥当だ。

ベンチマークごとに実行した命令の数をみてみると、どちらのベンチマークテストも全部で6,000,000,000イテレーションほど実行したとはいえ、インターフェースごしに呼び出したときは直接呼び出した場合に比べて命令実行数が約140億命令増加していた。(110,979,100,648 vs. 124,467,105,161)

以前述べたように、CALLの依存関係のせいでCPUはインターフェースを迂回する命令を並列に実行することができない。このことは、サイクルごとに実行する命令率(IPC)に如実に影響を与えている。

インターフェースごしのほうが全体でははるかに多くの作業をこなしているが、両方とも、IPCは同じくらいの結果になっている。(2.54 vs. 2.63)

また、並列処理が行えないインターフェースごしの場合は最大35億CPUサイクルほど実行時間が伸びている。
インターフェースごしの測定では0.15nsだけ実行時間が伸びているが、この35億CPUサイクル分の伸びがこの0.15nsの遅れの原因となっている。

コンパイラにメソッド呼び出しをインライン化をさせた場合はどうなるだろうか？

var myID int32

func BenchmarkMethodCall_direct(b *testing.B) {
    b.Run("single/inline", func(b *testing.B) {
        m := escapeToHeap(&id32{id: 6754}).(*id32)
        b.ResetTimer()
        for i := 0; i < b.N; i++ {
            // MOVL (DX), SI
            // MOVL SI, (CX)
            myID = m.idInline()
        }
    })
}

func BenchmarkMethodCall_interface(b *testing.B) {
    b.Run("single/inline", func(b *testing.B) {
        m := escapeToHeap(&id32{id: 6754})
        b.ResetTimer()
        for i := 0; i < b.N; i++ {
            // MOVQ 32(AX), CX
            // MOVQ "".m.data+40(SP), DX
            // MOVQ DX, (SP)
            // CALL CX
            // MOVL 8(SP), AX
            // MOVQ "".&myID+48(SP), CX
            // MOVL AX, (CX)
            myID = m.idNoInline()
        }
    })
}

2つのことがまずわかる。

BenchmarkMethodCall_direct: インライン化したことで、このメソッド呼び出しは2回の単純なメモリ移動へと変化する
BenchmarkMethodCall_interface: dynamic dispatch のせいでコンパイラはこのメソッド呼び出しをインライン化することができない。結果として生成されるアセンブリは前と全く同じものになる。

後者(BenchmarkMethodCall_interface)は全く中身が変わっていないので、今回考慮すべきは直接メソッドを呼び出した時のベンチマークだ。

$ go test -run=NONE -o iface_bench_test.bin iface_bench_test.go && \
  perf stat --cpu=1 \
  taskset 2 \
  ./iface_bench_test.bin -test.cpu=1 -test.benchtime=1s -test.count=3 \
      -test.bench='BenchmarkMethodCall_direct/single/inline'
BenchmarkMethodCall_direct/single/inline         	2000000000	         0.35 ns/op
BenchmarkMethodCall_direct/single/inline         	2000000000	         0.34 ns/op
BenchmarkMethodCall_direct/single/inline         	2000000000	         0.34 ns/op

 Performance counter stats for 'CPU(s) 1':

       2464.353001      cpu-clock (msec)          #    1.000 CPUs utilized          
               629      context-switches          #    0.255 K/sec                  
                 1      cpu-migrations            #    0.000 K/sec                  
             7,322      page-faults               #    0.003 M/sec                  
     9,026,867,915      cycles                    #    3.663 GHz                    
    41,580,825,875      instructions              #    4.61  insn per cycle         
     7,027,066,264      branches                  # 2851.485 M/sec                  
         1,134,955      branch-misses             #    0.02% of all branches        

       2.464386341 seconds time elapsed

予想通り、関数呼び出しのオーバーヘッドがなくなったので異常に速くなっている。

インライン化された直接呼び出しの場合は、最大0.35nsでインターフェースごしに呼び出した時に比べて475%速い。インライン化されていないときは8%しか違いがなかったことを考えるとすごい差になっている。

メソッド呼び出し時に生じる不確定な分岐がなくなったので、CPUは並列化と分岐予測による投機的実行を残りの命令に対して効率的に行うことができる。その結果IPCは4.61と大幅に上昇している。

Benchmark suite B: 大量のインスタンス + インライン化されない関数呼び出し + 様々な種類のイテレーション

今回のベンチマークでは各イテレーションごとに、メソッドがすべてPublicなオブジェクトのスライスを1つ1つ見ていって、各オブジェクトのそのメソッドを呼び出していくという、より現実に即した状況で測定を行う。

実際使われているプログラムで、このような方法で呼び出されるメソッドのほとんどはコンパイラによってインライン化できないほど複雑である可能性が高いので、今回はインライン化を無効にする。

ここではキャッシュとの相性が変わる(1 > 2 > 3)ことを期待して、オブジェクトのスライスへのアクセス方法が異なる3つのよく似たケースを用意した。

最初のケースではイテレータはスライスの中のオブジェクトのメソッドを前から順に呼び出していき、オブジェクトのサイズ分だけインクリメントされる。(1つずつ進む)
2番目のケースでは、イテレータはスライスのオブジェクトを前から呼び出していくが、キャッシュラインのサイズより大きいサイズずつインクリメントされていく。
最後のケースでは、イテレータはランダムな順番でスライスのオブジェクトを呼び出していく。

CPUとメモリに負荷がかかるようなサーバーの状況をシミュレートするために、3つのケース全部で配列はCPUのキャッシュに収まりきらない大きさにする

キャッシュを含めた今回使うプロセッサの詳細がこちら

$ lscpu | sed -nr '/Model name/ s/.*:\s*(.* @ .*)/\1/p'
Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

$ lscpu | grep cache
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K

$ getconf LEVEL1_DCACHE_LINESIZE
64

$ getconf LEVEL1_ICACHE_LINESIZE
64

$ find /sys/devices/system/cpu/cpu0/cache/index{1,2,3} -name "shared_cpu_list" -exec cat {} \;
# (annotations are mine)
0,4 # L1 (hyperthreading)
0,4 # L2 (hyperthreading)
0-7 # L3 (shared + hyperthreading)

以下のコードが今回直接呼び出しのベンチマーク測定で行う内容だ。

baselineと付いているベンチマークは、レシーバを個別に探すコストを計算する。よって最後の測定結果(call)からこのコストを引くことで純粋なcallのベンチマークがわかる。

const _maxSize = 2097152             // 2^21
const _maxSizeModMask = _maxSize - 1 // avoids a mod (%) in the hot path

var _randIndexes = [_maxSize]int{}
func init() {
    rand.Seed(42)
    for i := range _randIndexes {
        _randIndexes[i] = rand.Intn(_maxSize)
    }
}

func BenchmarkMethodCall_direct(b *testing.B) {
    adders := make([]*id32, _maxSize)
    for i := range adders {
        adders[i] = &id32{id: int32(i)}
    }
    runtime.GC()

    var myID int32

    b.Run("many/noinline/small_incr", func(b *testing.B) {
        var m *id32
        b.Run("baseline", func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                m = adders[i&_maxSizeModMask]
            }
        })
        b.Run("call", func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                m = adders[i&_maxSizeModMask]
                myID = m.idNoInline()
            }
        })
    })
    b.Run("many/noinline/big_incr", func(b *testing.B) {
        var m *id32
        b.Run("baseline", func(b *testing.B) {
            j := 0
            for i := 0; i < b.N; i++ {
                m = adders[j&_maxSizeModMask]
                j += 32
            }
        })
        b.Run("call", func(b *testing.B) {
            j := 0
            for i := 0; i < b.N; i++ {
                m = adders[j&_maxSizeModMask]
                myID = m.idNoInline()
                j += 32
            }
        })
    })
    b.Run("many/noinline/random_incr", func(b *testing.B) {
        var m *id32
        b.Run("baseline", func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                m = adders[_randIndexes[i&_maxSizeModMask]]
            }
        })
        b.Run("call", func(b *testing.B) {
            for i := 0; i < b.N; i++ {
                m = adders[_randIndexes[i&_maxSizeModMask]]
                myID = m.idNoInline()
            }
        })
    })
}

インターフェースごしに呼び出す場合のベンチマーク測定の内容は以下のようになる。配列が具体的なポインタ(&id32)ではなく、インターフェース値で初期化されていることを除けば直接呼び出しの場合と全く同じだ。

func BenchmarkMethodCall_interface(b *testing.B) {
    adders := make([]identifier, _maxSize)
    for i := range adders {
        adders[i] = identifier(&id32{id: int32(i)})
    }
    runtime.GC()

    /* ... */
}

直接呼び出しの場合は次のような結果になる

$ go test -run=NONE -o iface_bench_test.bin iface_bench_test.go && \
  benchstat <(
    taskset 2 ./iface_bench_test.bin -test.cpu=1 -test.benchtime=1s -test.count=3 \
      -test.bench='BenchmarkMethodCall_direct/many/noinline')
name                                                  time/op
MethodCall_direct/many/noinline/small_incr/baseline   0.99ns ± 3%
MethodCall_direct/many/noinline/small_incr/call       2.32ns ± 1% # 2.32 - 0.99 = 1.33ns
MethodCall_direct/many/noinline/big_incr/baseline     5.86ns ± 0%
MethodCall_direct/many/noinline/big_incr/call         17.1ns ± 1% # 17.1 - 5.86 = 11.24ns
MethodCall_direct/many/noinline/random_incr/baseline  8.80ns ± 0%
MethodCall_direct/many/noinline/random_incr/call      30.8ns ± 0% # 30.8 - 8.8 = 22ns

見たところ、今回の結果に驚くようなところはない

small_incrはキャッシュのヒット率が非常に高く、1つのインスタンスをループさせていた前回のベンチマークと似た結果が得られた
big_incrはキャッシュに各ループで新しいキャッシュラインからデータをとることを強制しているので、関数呼び出しのコストを考慮しない状態でも実行速度の大幅な低下が見られる。callの実行時間の内、最大6nsほどの実行時間はbaselineの処理にかかる時間であり、残りの実行時間はidフィールドを取得するため、レシーバの参照を外すコストと戻り値をコピーするコストの組み合わせということがわかる
random_incrはbig_incrよりさらにベンチマークが悪くなっている。これはランダムアクセスと事前に計算されたインデックスの配列(_randIndexes)から次のインデックスを取得する処理(これもキャッシュミスを引き起こす)のコストに起因する。

論理的には、CPUのキャッシュのスラッシングは直接呼び出しの場合にはインライン化されていようがいまいが大きな実行速度の低下を引き起こすことはないはずだが、実際には全部のケースで速度の低下を引き起こしている。

dynamic dispatch の場合を見ていこう

$ go test -run=NONE -o iface_bench_test.bin iface_bench_test.go && \
  benchstat <(
    taskset 2 ./iface_bench_test.bin -test.cpu=1 -test.benchtime=1s -test.count=3 \
      -test.bench='BenchmarkMethodCall_interface/many/inline')
name                                                     time/op
MethodCall_interface/many/noinline/small_incr/baseline   1.38ns ± 0%
MethodCall_interface/many/noinline/small_incr/call       3.48ns ± 0% # 3.48 - 1.38 = 2.1ns
MethodCall_interface/many/noinline/big_incr/baseline     6.86ns ± 0%
MethodCall_interface/many/noinline/big_incr/call         19.6ns ± 1% # 19.6 - 6.86 = 12.74ns
MethodCall_interface/many/noinline/random_incr/baseline  11.0ns ± 0%
MethodCall_interface/many/noinline/random_incr/call      34.7ns ± 0% # 34.7 - 11.0 = 23.7ns

結果は直接呼び出しのときと非常に似ているが、各イテレーションごとに、直接呼び出しのときはポインタ1つ(&id32)のコピーだったが、今回は2つのquad-word(i.tab.funの中身とi.data)をコピーするコストの分ベンチマーク結果が悪くなっている

直接呼び出しのときと同じような実行速度が出たのは、スライス内の全部のインターフェイス(iface<Mather, Adder>)が全部同じitabを参照していたため、itabと結びついたvtableがキャッシュに留まり続けその結果、各イテレーションでポインタを取ってくる処理にともなう遅延が実質ゼロだったからである。

補足:
C++は(確証を取れていないがおそらくGoも)vtableはクラス(or インターフェイス)ごとに1つだけ作られ、それをインスタンスで参照するということになっている。

同様の理由で、main.(*id32).idNoInlineメソッドを構成する命令もL1iキャッシュに留まり続けている。

実際にはインターフェースのスライスはvtableなどの様々な型のデータを含んでいるため、様々なvtableがキャッシュに収まりきらず互いにキャッシュから押し出しあって、スラッシングするのではと考える人もいるだろう。

この主張は理論的に正しい。このような考え方はC++などの古いオブジェクト指向の言語に長年触れてきた場合にありがちなことだ。

C++のようなインスタンスが深い階層構造をとるようなたくさんの仮想クラス(入れ子になった内部クラス)を含むデータ構造をインスタンス化するとき、各インスタンスと関連づいたvtableの数はCPUのスラッシングを起こしてしまうほど大きなものになる。(例: すべてがグラフ構造に格納されているWidgetであるGUIフレームワークなど)

少なくともC++の場合には仮想クラスはとても複雑な動作を定義する傾向にあり、たくさんメソッドがある場合はとても巨大なvtableを持つようになってしまい、その結果インスタンスはL1dキャッシュに負荷をかけることになる。

一方GoではC++とは全く異なった文法である。OOP指向を排除し、型システムはフラット(継承がない)になり、インターフェースは多くとも2,3個程度のメソッドだけという最低限の情報しかもたず挙動も制限される。

実際Goでは、各イテレーションでインターフェース自身が含んでいる様々な型をコピーすることは非常に稀だった。

インライン化が有効な場合の直接呼び出しの結果も興味があると思うので見てみよう。

name                                                time/op
MethodCall_direct/many/inline/small_incr            0.97ns ± 1% # 0.97ns
MethodCall_direct/many/inline/big_incr/baseline     5.96ns ± 1%
MethodCall_direct/many/inline/big_incr/call         11.9ns ± 1% # 11.9 - 5.96 = 5.94ns
MethodCall_direct/many/inline/random_incr/baseline  9.20ns ± 1%
MethodCall_direct/many/inline/random_incr/call      16.9ns ± 1% # 16.9 - 9.2 = 7.7ns

直接呼び出しのほうが、インタフェースごしにインラインでメソッドを呼び出した場合に比べて2,3倍速くなることがわかる

上で述べたように、現在のGoコンパイラが複雑な関数をインライン化をすることは稀であり、vtableを介したインライン化のされない関数呼び出しを使う必要のある場面のほうが圧倒的に多い。

まとめ

インターフェースごしの呼び出しによる遅延の測定は非常に複雑な作業になった。そのほとんどは現代ののハードウェアの非常に複雑な実装に起因する副作用によって生じた。

GOでは、言語の文法設計とインライン化に関するコンパイラの現在の能力を考えると、 dynamic dispatch　にともなうコストが実質的にないものとみなせるようになった。

これは

dynamic dispatchに必要なインターフェースのvtableはキャッシュにあることが多い
dynamic dispatchを行う場合、インライン化はされないがそもそも通常の場合もインライン化はあまり行われない
dynamic dispatchを行う際、呼び出すメソッドを見つける条件分岐(の予測に失敗するかもしれないこと)とそのメソッドのCall時のデータハザードによってパフォーマンスの低下が確かに生じるが影響が出るほどの遅延は生じない

ことからわかる

しかし時には、パフォーマンスが芳しくないときに dynamic dispatch が問題になっていないか検証する必要があるときもある。

Special cases & compiler tricks

このセクションでは、特殊ではあるがよく見るであろうインターフェースを個別に見ていく。

今までの説明でインターフェースがどう機能するかについてだいぶわかってきたはずなので、がんばってみていこう。

空のinterface

itabはインタフェースの挙動を定義するインターフェースの中核とも言えるデータ構造だったことを思い出そう。

空のインターフェース(interface{})のデータ構造は、直感的に想像できる。つまり、itab のないifaceだ。

こうなるのには2つの理由がある:

空のインターフェースはメソッドを持たないので、dynamic dispatchに関するデータは全てデータ構造から省くことができる
vtableがないので、空のインターフェース自体の型(インターフェースの保持するデータの型と間違えないように注意)は常に同じになる(ここでは空のインターフェース自体ではなく、空のインターフェース型でラップされた値のことを指していることにも注意)

NOTE: ifaceに使用した表記と同様に、タイプTを保持する空のインターフェイスをeface <T>と表記する

efaceはランタイムで空のinterfaceを表すルート型となる型だ。(src/runtime/runtime2.go)

定義は以下のようになっている。

type eface struct { // 16 bytes on a 64bit arch
    _type *_type
    data  unsafe.Pointer
}

_typeフィールドは、dataが指している値の型情報を保持している。

想像した通り、itabはdataの型情報を持つ_typeを除いて、完全になくなっている。

(ifaceがefaceのスーパーセットであることからわかるように)空のインターフェースはifaceを再利用している一方で、ランタイムは容量とコードの綺麗さという2つの理由によってこれら2つを区別するようにしている。

スカラー型を保持するインターフェース

ドキュメントの最初のところ #詳解interface で、int型のような単純なスカラー型でもインターフェースが保持する場合それはヒープに割り当てられるということを述べた。

今こそ、その理由を説明する時だ。

次の2つのベンチマーク測定を考えてみよう (eface_scalar_test.go)

func BenchmarkEfaceScalar(b *testing.B) {
    var Uint uint32
    b.Run("uint32", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            Uint = uint32(i)
        }
    })
    var Eface interface{}
    b.Run("eface32", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            Eface = uint32(i)
        }
    })
}

$ go test -benchmem -bench=. ./eface_scalar_test.go
BenchmarkEfaceScalar/uint32-8         	2000000000	   0.54 ns/op	  0 B/op     0 allocs/op
BenchmarkEfaceScalar/eface32-8        	 100000000	   12.3 ns/op	  4 B/op     1 allocs/op

単純な代入操作の比較だが、パフォーマンスに2桁ほどの違い(0.54 vs 12.3)が出ている
2個目の測定(空インターフェースへの代入)は各イテレーションごとに4バイトほどヒープ割り当てを行なっている

目には見えない何か重い処理が2個目の測定で行われていることは明らかだ。アセンブリを出力して見てみよう。

最初のベンチマークの方は、予想通り、通常の代入に伴うアセンブリが出力された。

;; Uint = uint32(i)
0x000d MOVL	DX, (AX)

2つ目のベンチマークは、想像以上に複雑なアセンブリを出力した。

;; Eface = uint32(i)
0x0050 MOVL	CX, ""..autotmp_3+36(SP)
0x0054 LEAQ	type.uint32(SB), AX
0x005b MOVQ	AX, (SP)
0x005f LEAQ	""..autotmp_3+36(SP), DX
0x0064 MOVQ	DX, 8(SP)
0x0069 CALL	runtime.convT2E32(SB)
0x006e MOVQ	24(SP), AX
0x0073 MOVQ	16(SP), CX
0x0078 MOVQ	"".&Eface+48(SP), DX
0x007d MOVQ	CX, (DX)
0x0080 MOVL	runtime.writeBarrier(SB), CX
0x0086 LEAQ	8(DX), DI
0x008a TESTL	CX, CX
0x008c JNE	148
0x008e MOVQ	AX, 8(DX)
0x0092 JMP	46
0x0094 CALL	runtime.gcWriteBarrier(SB)
0x0099 JMP	46

コードを区切りながら解説していこう。

Step 1: インターフェースの作成

; 36(SP)に i を格納
0x0050 MOVL	CX, ""..autotmp_3+36(SP)

; convT2E32の引数として、&i(data), &type.uint32(_type)をスタックにPUSH
0x0054 LEAQ	type.uint32(SB), AX
0x005b MOVQ	AX, (SP)
0x005f LEAQ	""..autotmp_3+36(SP), DX
0x0064 MOVQ	DX, 8(SP)

; 以前見たようにインターフェースを構築
0x0069 CALL	runtime.convT2E32(SB)
0x006e MOVQ	24(SP), AX
0x0073 MOVQ	16(SP), CX

まず空のインターフェースeface<uint32>のインスタンス化を行うコードを見ていこう。

すでに前のセクションの #インターフェースの構築で似たコードを扱っている。唯一違う点があるとするなら、runtime.convT2E32の代わりにruntime.convT2I32を呼んでいる点だ。

runtime.convT2I32 と runtime.convT2E32 は特定のインターフェースまたは空のインタフェースのインスタンスをスカラー型(+string型とslice型)から作成する関数の一種のようだ。

スカラー型が5個、efaceとifaceで2個なので5×2でインスタンス作成関数の組み合わせは10通りある

// empty interface from scalar value
func convT2E16(t *_type, elem unsafe.Pointer) (e eface) {}
func convT2E32(t *_type, elem unsafe.Pointer) (e eface) {}
func convT2E64(t *_type, elem unsafe.Pointer) (e eface) {}
func convT2Estring(t *_type, elem unsafe.Pointer) (e eface) {}
func convT2Eslice(t *_type, elem unsafe.Pointer) (e eface) {}

// interface from scalar value
func convT2I16(tab *itab, elem unsafe.Pointer) (i iface) {}
func convT2I32(tab *itab, elem unsafe.Pointer) (i iface) {}
func convT2I64(tab *itab, elem unsafe.Pointer) (i iface) {}
func convT2Istring(tab *itab, elem unsafe.Pointer) (i iface) {}
func convT2Islice(tab *itab, elem unsafe.Pointer) (i iface) {}

(convT2E8 と convT2I8はコンパイラの最適化の結果ここに存在していない　詳しくはもう少しあとで触れる)

これらの関数は、返す値の型(iface vs. eface)と確保するヒープのサイズが違うこと以外は同じ挙動をする

試しにruntime.convT2E32の実装を見てみよう (src/runtime/iface.go)

func convT2E32(t *_type, elem unsafe.Pointer) (e eface) {
    /* ...omitted debug stuff... */
    var x unsafe.Pointer
    if *(*uint32)(elem) == 0 {
        x = unsafe.Pointer(&zeroVal[0])
    } else {
        x = mallocgc(4, t, false)
        *(*uint32)(x) = *(*uint32)(elem)
    }
    e._type = t
    e.data = x
    return
}

この関数はefaceの_typeフィールドを最初の引数で与えられたtで初期化する。(返り値eは呼び出し側のスタックフレームに割り当てられていることを思い出そう)

efaceのdataフィールドは2つ目の引数elemに完全に依存している

elemの指す値が 0 のとき、e.dataはランタイムがゼロ値を表すのに使うグローバルな変数runtime.zeroValで初期化される (runtime.zeroValはあとで詳細をみていく)
elemの指す値が 0 でないとき、関数はヒープに4バイトの領域を確保(x = mallocgc(4, t, false))し、elemが指す値(uint32)をその4バイトに入れ、その4バイトを指すポインタ(x)をe.dataに格納する

今回は、e._typeはtype.uint32のアドレスを保持(LEAQ type.uint32(SB), AX)している。

type.uint32は標準ライブラリ(stdlib)によって実装されており、そのアドレスはstdlibに対してリンクをする場合に解決可能になる。

$ go tool nm eface_scalar_test.o | grep 'type\.uint32'
         U type.uint32

(Uはシンボルがこのオブジェクトファイルで定義されておらず、リンク時に他のオブジェクトファイル(今回は標準ライブラリ)によって定義が提供されることを期待していることを示す)

Step 2: 返り値の格納 (part 1)

0x0078 MOVQ	"".&Eface+48(SP), DX
0x007d MOVQ	CX, (DX)		;; Eface._type = ret._type

runtime.convT2E32の結果は変数Efaceに格納されているように見える。

しかし実際には、現時点では、返り値の内_typeがEface._typeに格納されただけでdataのほうはまだ格納されていない。

Step 3: 返り値の格納 (part 2)

0x0080 MOVL	runtime.writeBarrier(SB), CX
0x0086 LEAQ	8(DX), DI	;; Eface.data = ret.data (indirectly via runtime.gcWriteBarrier)
0x008a TESTL	CX, CX
0x008c JNE	148
0x008e MOVQ	AX, 8(DX)	;; Eface.data = ret.data (direct)
0x0092 JMP	46
0x0094 CALL	runtime.gcWriteBarrier(SB)
0x0099 JMP	46

最後のパートが見るからに複雑そうなのは、efaceのdataポインタをEface.dataに割り当てるときの副作用によるものだ。

今回の処理では、プログラム中のメモリの参照関係を変更するので、GCがバックグラウンドで実行されている可能性に備えて参照関係の変更をGCに通知する必要がある。これが副作用だ。

これはwrite barrierとして知られていて、Goの並列に動作するGCの実行結果に直接作用する。

今のところは、runtime.gcWriteBarrierを呼び出すようなアセンブリを見た時は、ポインタを操作してGCに変更を伝える必要があるということを考えておけば十分だ。

結局最後のパートでは以下の2つのうちのどちらかの処理を行う。

もしwrite-barrierが機能していないなら、ret.dataをEface.dataに割り当てている(MOVQ AX, 8(DX))
write-barrierが機能しているなら、GCに割り当てを行うように要請する(LEAQ 8(DX), DI + CALL runtime.gcWriteBarrier(SB))

これでuint32を保持するインターフェースが完成した。

ヒープ

そもそもなぜuint32をヒープに退避したがるのか？

これはインターフェースがuint32変数のポインタを欲しがっているからであり、スタック上に確保してしまうと、スタックが解放されたときにインターフェースの指す値が安全な値でなくなってしまうからであると考えられる。

ヒープに確保していれば、少なくともそれを参照しているインターフェース変数が生存している限りは安全に参照できていることが保証される。

まとめ

スカラー型をインターフェースでラップするのは実際にはあまりないことだが、様々な原因が重なった結果コストのかかる操作になる可能性があるので、背後で何が起きているかに目を向けておくのはいつか役に立つだろう。

コストと言えば、コンパイラは様々な状況でヒープ割り当てを避けるためのいろいろな工夫を行っていることを習ったばかりだ。

最後にこれらの工夫の内、3つほど見ていってこのセクションを終わりにしよう。

Interface trick 1: Byte-sized values

eface<uint8>のインスタンス化のベンチマークを測定する(eface_scalar_test.go)

func BenchmarkEfaceScalar(b *testing.B) {
    b.Run("eface8", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            Eface = uint8(i)
        }
    })
}

uint32のときとアセンブリを比較してみよう

;; Eface = uint32(i)
0x0050 MOVL	CX, ""..autotmp_3+36(SP)
0x0054 LEAQ	type.uint32(SB), AX
0x005b MOVQ	AX, (SP)
0x005f LEAQ	""..autotmp_3+36(SP), DX
0x0064 MOVQ	DX, 8(SP)
0x0069 CALL	runtime.convT2E32(SB)
0x006e MOVQ	24(SP), AX
0x0073 MOVQ	16(SP), CX

0x0078 MOVQ	"".&Eface+48(SP), DX
0x007d MOVQ	CX, (DX)

0x0080 MOVL	runtime.writeBarrier(SB), CX
0x0086 LEAQ	8(DX), DI
0x008a TESTL	CX, CX
0x008c JNE	148
0x008e MOVQ	AX, 8(DX)
0x0092 JMP	46
0x0094 CALL	runtime.gcWriteBarrier(SB)
0x0099 JMP	46

;; Eface = uint8(i)
LEAQ    type.uint8(SB), BX
MOVQ    BX, (CX)
MOVBLZX AL, SI
LEAQ    runtime.staticbytes(SB), R8
ADDQ    R8, SI
MOVL    runtime.writeBarrier(SB), R9
LEAQ    8(CX), DI
TESTL   R9, R9
JNE     100
MOVQ    SI, 8(CX)
JMP     40
MOVQ    AX, R9
MOVQ    SI, AX
CALL    runtime.gcWriteBarrier(SB)
MOVQ    R9, AX
JMP     40

$ go test -benchmem -bench=BenchmarkEfaceScalar/eface8 ./eface_scalar_test.go
BenchmarkEfaceScalar/eface8-8         	2000000000	   0.88 ns/op	  0 B/op     0 allocs/op

1バイトの値の場合(i8, u8)、コンパイラは、runtime.convT2E/runtime.convT2Iを呼び出さない、つまりヒープ割り当てを避けることがわかった。

ヒープにuint8の値を指す領域を確保してそのポインタを利用する代わりに、ランタイムがすでに用意しているグローバルな値のアドレスを再利用している。(LEAQ runtime.staticbytes(SB), R8)

runtime.staticbytesはランタイムによって事前に用意された1バイトの値が全部定義されたグローバルなテーブルで、src/runtime/iface.goで定義されており、実際のコードは以下のようになっている。

// staticbytes is used to avoid convT2E for byte-sized values.
var staticbytes = [...]byte{
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
    0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
    0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
    0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
    0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
    0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
}

この配列から対象の値を表すオフセットを見つけてそれを用いることで、コンパイラは余計なヒープ割り当ての回避と、1byteで表現可能な値の参照を効果的に行うことができる。

今回生成されたコードは、操作するポインタがプログラム本体(main)と同じ生存期間を持つグローバル変数を指しているのに、write-barrierに関連するコードを含んでいる(ヒープに割り当てを行ったuint32と違って、runtime.staticbytesは参照されていなくてもGCによって回収されない)

この理由は現時点では不明だ。

Interface trick 2: Static inference

コンパイル時に値が判明している値(定数)をラップするeface<uint64>をインスタンス化する際のベンチマークを測定してみよう。(eface_scalar_test.go)

func BenchmarkEfaceScalar(b *testing.B) {
    b.Run("eface-static", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            // LEAQ  type.uint64(SB), BX
            // MOVQ  BX, (CX)
            // MOVL  runtime.writeBarrier(SB), SI
            // LEAQ  8(CX), DI
            // TESTL SI, SI
            // JNE   92
            // LEAQ  "".statictmp_0(SB), SI
            // MOVQ  SI, 8(CX)
            // JMP   40
            // MOVQ  AX, SI
            // LEAQ  "".statictmp_0(SB), AX
            // CALL  runtime.gcWriteBarrier(SB)
            // MOVQ  SI, AX
            // LEAQ  "".statictmp_0(SB), SI
            // JMP   40
            Eface = uint64(42)
        }
    })
}

$ go test -benchmem -bench=BenchmarkEfaceScalar/eface-static ./eface_scalar_test.go
BenchmarkEfaceScalar/eface-static-8    	2000000000	   0.81 ns/op	  0 B/op     0 allocs/op

生成されたアセンブリを見ると、コンパイラがruntime.convT2E64の呼び出しを完璧に最適化して、代わりに42を保持する自動生成されたグローバル変数のアドレスをセットして空のインスタンスを直接生成していることがわかる。(LEAQ "".statictmp_0(SB), SI参照 SBはグローバルなシンボルであることに注意)

以前用いたdump_sym.shを使うとこのことがよりはっきりわかるだろう。

$ GOOS=linux GOARCH=amd64 go tool compile eface_scalar_test.go
$ GOOS=linux GOARCH=amd64 go tool link -o eface_scalar_test.bin eface_scalar_test.o
$ ./dump_sym.sh eface_scalar_test.bin .rodata main.statictmp_0
.rodata file-offset: 655360
.rodata VMA: 4849664
main.statictmp_0 VMA: 5145768
main.statictmp_0 SIZE: 8

0000000 002a 0000 0000 0000                    
0000008

予想通り、main.statictmp_0は8バイトの$42を表す値だ。(0x000000000000002a)

Interface trick 3: Zero-values

コンパイラが行う最後の最適化について紹介する。以下のゼロ値からeface<uint32>をインスタンス化するベンチマーク測定を見て欲しい。(eface_scalar_test.go)

func BenchmarkEfaceScalar(b *testing.B) {
    b.Run("eface-zeroval", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            // MOVL  $0, ""..autotmp_3+36(SP)
            // LEAQ  type.uint32(SB), AX
            // MOVQ  AX, (SP)
            // LEAQ  ""..autotmp_3+36(SP), CX
            // MOVQ  CX, 8(SP)
            // CALL  runtime.convT2E32(SB)
            // MOVQ  16(SP), AX
            // MOVQ  24(SP), CX
            // MOVQ  "".&Eface+48(SP), DX
            // MOVQ  AX, (DX)
            // MOVL  runtime.writeBarrier(SB), AX
            // LEAQ  8(DX), DI
            // TESTL AX, AX
            // JNE   152
            // MOVQ  CX, 8(DX)
            // JMP   46
            // MOVQ  CX, AX
            // CALL  runtime.gcWriteBarrier(SB)
            // JMP   46
            Eface = uint32(i - i) // outsmart the compiler (avoid static inference)
        }
    })
}

$ go test -benchmem -bench=BenchmarkEfaceScalar/eface-zero ./eface_scalar_test.go
BenchmarkEfaceScalar/eface-zeroval-8  	 500000000	   3.14 ns/op	  0 B/op     0 allocs/op

今回は、Interface trick 2: Static inferenceで述べた最適化(以後、static inferenceと呼ぶ)を適用したくないので、uint32(0)の代わりに、uint32(i - i)を使っていることに注意して欲しい。

生成されたコードは、通常の割り当てを行うケースとまったく同じように見えるが、実際には割り当ては行われない(0 B/op)。何が起きているのだろうか？

runtime.convT2E32のコードを解説したときに述べたように、ここで行われるヒープ割り当てはInterface trick 1: Byte-sized valuesでやった手法と同様の方法で最適化できる。つまり、ゼロ値を持った変数を参照するとき、コンパイラはランタイムが保持するグローバルな変数のアドレスを代わりに与える。

runtime.staticbytesと同様に、この変数はランタイムのコード内でも見ることができる (src/runtime/hashmap.go):

const maxZero = 1024 // must match value in ../cmd/compile/internal/gc/walk.go
var zeroVal [maxZero]byte

スカラー型のインターフェースの最適化に関してざっと紹介したがそれももう終わりだ。

最後に、今まで見てきたベンチマーク測定の結果をまとめて終えよう。

$ go test -benchmem -bench=. ./eface_scalar_test.go
BenchmarkEfaceScalar/uint32-8         	2000000000	   0.54 ns/op	  0 B/op     0 allocs/op
BenchmarkEfaceScalar/eface32-8        	 100000000	   12.3 ns/op	  4 B/op     1 allocs/op
BenchmarkEfaceScalar/eface8-8         	2000000000	   0.88 ns/op	  0 B/op     0 allocs/op
BenchmarkEfaceScalar/eface-zeroval-8  	 500000000	   3.14 ns/op	  0 B/op     0 allocs/op
BenchmarkEfaceScalar/eface-static-8    	2000000000	   0.81 ns/op	  0 B/op     0 allocs/op

ゼロ値について

上で見たように、runtime.convT2*系の関数はインターフェースがラップするデータがゼロ値を指しているとき、ヒープ割り当てを最適化して避けてくれる。

この最適化は、インターフェースに特有のものではない。

Goランタイムはゼロ値へのポインタが必要になったときに、ランタイムによって用意された常にゼロ値である値のアドレスをとることで不必要なアロケーションを避けている。

このことは割とシンプルなプログラムを使って確認できる。(zeroval.go):

どちらのケースも最後には0になる変数のアドレスを表示している

//go:linkname zeroVal runtime.zeroVal
var zeroVal uintptr

type eface struct{ _type, data unsafe.Pointer }

func main() {
    x := 42
    var i interface{} = x - x // static inference最適化を避ける

    fmt.Printf("zeroVal = %p\n", &zeroVal)                              // ランタイムに用意されるゼロ値のアドレス
    fmt.Printf("      i = %p\n", ((*eface)(unsafe.Pointer(&i))).data)   // 自前で用意したゼロ値のアドレス
}

$ go run zeroval.go
zeroVal = 0x5458e0
      i = 0x5458e0

予想通り自分で用意したゼロ値のアドレスも、ランタイムが用意したグローバルなゼロ値のアドレスにすり替えられている

また//go:linknameというディレクティブを使うことで外部のシンボルへの参照ができるようになる。

The //go:linkname directive instructs the compiler to use “importpath.name” as the object file symbol name for the variable or function declared as “localname” in the source code. Because this directive can subvert the type system and package modularity, it is only enabled in files that have imported "unsafe".

サイズが 0 のオブジェクト

ゼロ値に関する似たような最適化手法として、Goプログラムはstruct{}{}のようなサイズが0のオブジェクトをインスタンス化するときに、割り当てを行わないようにしている。

Goの公式ドキュメントではこう説明されている:

サイズが0より大きいフィールド(or 要素)を持たない構造体や配列のサイズは0となる。
サイズが0の変数は複数あったとしても、メモリ上で同じアドレス上に存在するだろう。

2つ目の項目の語尾が『だろう』なのは、現在のGoコンパイラ(gc)の実装では常にそうなっているが、今後のアップデートでもそれが守られる保証がないからだ。

今回も単純なプログラムを用いて確認しよう (zerobase.go):

func main() {
    var s struct{}
    var a [42]struct{}

    fmt.Printf("s = % p\n", &s)
    fmt.Printf("a = % p\n", &a)
}

$ go run zerobase.go
s = 0x546fa8
a = 0x546fa8

このアドレスに実際に何があるか、バイナリを覗いて調べてみよう。

$ go build -o zerobase.bin zerobase.go && objdump -t zerobase.bin | grep 546fa8
0000000000546fa8 g     O .noptrbss	0000000000000008 runtime.zerobase

runtime.zerobaseという変数はランタイムのソースコードの中で定義されている。(src/runtime/malloc.go):

// base address for all 0-byte allocations
var zerobase uintptr

本当に全てzerobaseのアドレスを指しているのか、もう一度確認してみよう。

//go:linkname zerobase runtime.zerobase
var zerobase uintptr

func main() {
    var s struct{}
    var a [42]struct{}

    fmt.Printf("zerobase = %p\n", &zerobase)
    fmt.Printf("       s = %p\n", &s)
    fmt.Printf("       a = %p\n", &a)
}

$ go run zerobase.go
zerobase = 0x546fa8
       s = 0x546fa8
       a = 0x546fa8

インターフェースの合成

インターフェースの合成は特別なことは何もない、コンパイラによって提供されているシンタックスシュガーである。

次のプログラムを考えよう (compound_interface.go):

type Adder interface{ Add(a, b int32) int32 }
type Subber interface{ Sub(a, b int32) int32 }
type Mather interface {
    Adder
    Subber
}

type Calculator struct{ id int32 }
func (c *Calculator) Add(a, b int32) int32 { return a + b }
func (c *Calculator) Sub(a, b int32) int32 { return a - b }

func main() {
    calc := Calculator{id: 6754}
    var m Mather = &calc
    m.Sub(10, 32)
}

今回も、コンパイラはiface<Mather, *Calculator>に対応するitabを生成している。

$ GOOS=linux GOARCH=amd64 go tool compile -S compound_interface.go | \
  grep -A 7 '^go.itab.\*"".Calculator,"".Mather'
go.itab.*"".Calculator,"".Mather SRODATA dupok size=40
    0x0000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
    0x0010 5e 33 ca c8 00 00 00 00 00 00 00 00 00 00 00 00  ^3..............
    0x0020 00 00 00 00 00 00 00 00                          ........
    rel 0+8 t=1 type."".Mather+0
    rel 8+8 t=1 type.*"".Calculator+0
    rel 24+8 t=1 "".(*Calculator).Add+0
    rel 32+8 t=1 "".(*Calculator).Sub+0

再配置のディレクティブから、コンパイラによって生成されるvtableはAdderのメソッドとSubberのメソッドの両方を保持していることが確認できた。

rel 24+8 t=1 "".(*Calculator).Add+0
rel 32+8 t=1 "".(*Calculator).Sub+0

この通り、インターフェースの合成はインターフェースが合成元の各インターフェースが保持するvtableを合体させるだけで特別ことは何もしていない

話は逸れるが、今回はレシーバがポインタなので、生成されたitabは実体ではなく、Calculatorへのポインタにちゃんとなっており、このことはシンボル名(go.itab.*"".Calculator,"".Mather)と _typeの両方に反映されている(type.*"".Calculator)

Type check

最後に型アサーションの実装とコストについて見て終わろう。

Type Assertion

次のプログラムを考える (eface_to_type.go):

var j uint32
var Eface interface{} // static inferenceを避ける

func assertion() {
    i := uint64(42)
    Eface = i
    j = Eface.(uint32)
}

j = Eface.(uint32)に対応するアセンブリがこちらだ。

0x0065 00101 MOVQ	"".Eface(SB), AX		;; AX = Eface._type
0x006c 00108 MOVQ	"".Eface+8(SB), CX		;; CX = Eface.data
0x0073 00115 LEAQ	type.uint32(SB), DX		;; DX = type.uint32
0x007a 00122 CMPQ	AX, DX				    ;; Eface._type == type.uint32 ?
0x007d 00125 JNE	162				        ;; no? panic our way outta here
0x007f 00127 MOVL	(CX), AX			    ;; AX = *Eface.data
0x0081 00129 MOVL	AX, "".j(SB)			;; j = AX = *Eface.data
;; exit
0x0087 00135 MOVQ	40(SP), BP
0x008c 00140 ADDQ	$48, SP
0x0090 00144 RET
;; panic: interface conversion: <iface> is <have>, not <want>
0x00a2 00162 MOVQ	AX, (SP)			        ;; have: Eface._type
0x00a6 00166 MOVQ	DX, 8(SP)			        ;; want: type.uint32
0x00ab 00171 LEAQ	type.interface {}(SB), AX	;; AX = type.interface{} (eface)
0x00b2 00178 MOVQ	AX, 16(SP)			        ;; iface: AX
0x00b7 00183 CALL	runtime.panicdottypeE(SB)	;; func panicdottypeE(have, want, iface *_type)
0x00bc 00188 UNDEF
0x00be 00190 NOP

想像できたかもしれないが、出力したアセンブリはEface._typeの保持するアドレスをtype.uint32のアドレスと比較している。

以前見たように、type.uint32はuint32の型の内容を保持するシンボルで標準ライブラリによってグローバルシンボルとして提供されている。

_typeのポインタが一致すれば *Eface.dataをjにアサインできるし、そうでないならruntime.panicdottypeEを読んで型が合わない旨のメッセージと共にpanicしている

runtime.panicdottypeEの実装は予想以上に単純なものだ (src/runtime/iface.go):

// panicdottypeE is called when doing an e.(T) conversion and the conversion fails.
// have = the dynamic type we have.
// want = the static type we're trying to convert to.
// iface = the static type we're converting from.
func panicdottypeE(have, want, iface *_type) {
    haveString := ""
    if have != nil {
        haveString = have.string()
    }
    panic(&TypeAssertionError{iface.string(), haveString, want.string(), ""})
}

パフォーマンスはどうなのか？

もう一度コード(j = *Eface.data)のアセンブリを振り返ってみる。MOV命令を何度か行って、予測が容易い条件分岐があり(JNE 162)、最後は少なくともポインタの参照外し(*Eface.data)を行っている。

そもそも今回はインターフェースを具体的な値で初期化しており、そうでないなら単にEface.dataのポインタを直接コピーするだけで済んだはずなので、このようなコードになるのは今回だけだ。

以前測定したdynamic dispatchのオーバーヘッドと同様に、理論的にはType Assertionのオーバーヘッドは無いも同然だということが容易に推測できるのでベンチマークを測定する必要はないだろう。実際に実行したときにかかるコストは、キャッシュとどれだけ相性がいいかに左右される。

Type Switch

Type-switchesは少しトリッキーな内容になる。以下のコードと共に考えよう (eface_to_type.go):

var j uint32
var Eface interface{} // static inferenceを避けている

func typeSwitch() {
    i := uint32(42)
    Eface = i
    switch v := Eface.(type) {
    case uint16:
        j = uint32(v)
    case uint32:
        j = v
    }
}

このシンプルな Type Switch構文は以下のアセンブリを出力する(注釈を追記しておいた)

;; switch v := Eface.(type)
0x0065 00101 MOVQ	"".Eface(SB), AX    ;; AX = Eface._type
0x006c 00108 MOVQ	"".Eface+8(SB), CX  ;; CX = Eface.data
0x0073 00115 TESTQ	AX, AX              ;; Eface._type == nil ?
0x0076 00118 JEQ	153                 ;; nilならswitchをexit
0x0078 00120 MOVL	16(AX), DX          ;; DX = Eface.type._hash
;; case uint32
0x007b 00123 CMPL	DX, $-800397251     ;; Eface.type._hash == type.uint32.hash ?
0x0081 00129 JNE	163                 ;; 違うなら次のcaseへ (uint16)
0x0083 00131 LEAQ	type.uint32(SB), BX ;; BX = type.uint32
0x008a 00138 CMPQ	BX, AX              ;; type.uint32 == Eface._type ? (ハッシュは一致するか?)
0x008d 00141 JNE	206                 ;; 違うならBXをクリアして次のcaseへ (uint16)
0x008f 00143 MOVL	(CX), BX            ;; BX = *Eface.data
0x0091 00145 JNE	163                 ;; 0x00d3 で行われる間接ジャンプの目印
0x0093 00147 MOVL	BX, "".j(SB)        ;; j = BX = *Eface.data
;; exit
0x0099 00153 MOVQ	40(SP), BP
0x009e 00158 ADDQ	$48, SP
0x00a2 00162 RET
;; case uint16
0x00a3 00163 CMPL	DX, $-269349216     ;; Eface.type._hash == type.uint16.hash ?
0x00a9 00169 JNE	153                 ;; 違うならswitchをexit
0x00ab 00171 LEAQ	type.uint16(SB), DX ;; DX = type.uint16
0x00b2 00178 CMPQ	DX, AX              ;; type.uint16 == Eface._type ? (hash collision?)
0x00b5 00181 JNE	199                 ;; 違うならAXをクリアしてswitchをexit
0x00b7 00183 MOVWLZX	(CX), AX        ;; AX = uint16(*Eface.data)
0x00ba 00186 JNE	153                 ;; 0x00cc で行われる間接ジャンプの目印
0x00bc 00188 MOVWLZX	AX, AX          ;; AX = uint16(AX) (redundant)
0x00bf 00191 MOVL	AX, "".j(SB)        ;; j = AX = *Eface.data
0x00c5 00197 JMP	153                 ;; 処理を終えたのでswitchをexit
;; indirect jump table
0x00c7 00199 MOVL	$0, AX              ;; AX = $0
0x00cc 00204 JMP	186                 ;; indirect jump to 153 (exit)
0x00ce 00206 MOVL	$0, BX              ;; BX = $0
0x00d3 00211 JMP	145                 ;; indirect jump to 163 (case uint16)

これらのコードには目新しいことが何も無いことに気がついただろうか？

前後に処理がジャンプするので、全体のの流れは一見すると複雑に見えるかもしれないが、それ以外は元のGoのコードと照らし合わせると忠実なアセンブリになっている。

とはいえ、いくつか興味深いところもある。

Note 1: レイアウト

生成されたアセンブリは、もとのSwitch文と同じくらい高級な(つまり現代のプログラミング言語の制御構文で見られるような)構造を取っている。

最初のブロックでは調査対象のインターフェースの_typeをロードして、nilチェックを行っている
元のSwitch文のcaseに対応するN個の条件判定ブロックが存在する
最後の1ブロックは使用するレジスタをクリアして、次のcaseにジャンプするための間接ジャンプテーブルを定義している

特に2点目はType switch文が生成する条件判定ブロック(caseブロック)の数は元のGoコードのcaseの数と同じになるということを示しているので重要だ。

このことは実行時にパフォーマンスを驚くほど悪化させる要因になるかもしれない。なぜなら、大量のcase文を抱えたType Switch文は非常に大きな命令数を持つことになり、その結果L1iキャッシュのスラッシングを引き起こす可能性があるからである。

switch文のレイアウトで次に興味深いのは、生成されたアセンブリのcase文の順序だ。

元のGoコードでは case uint16 -> case uint32 の順だったが、
出力されたアセンブリでは、 case uint32 -> case uint16 とcase文の順序が逆転している

今回のケースではこの並び替えが起きたおかげで早めに正しいcase文に入ることができたが、これは単なる偶然にすぎないと考えられる。

筆者は試しに他のType Switchをコンパイルしてみたが、コンパイラは何らかの法則に基づいてcase文の並び替えを行っていることがわかった。

どういう法則でcase文の並び替えを行っているのかは不明だ。(私はいつかgcの内部実装を見てみるつもりだが...)

Note 2: O(n)

今回のswitch構文は、trueになるcaseにたどり着くか全てのcase文の検証を終えるまで、1つずつcaseをジャンプしていって検証するような制御フローになっている。

実際に立ち止まって「他にどのようにcase文の検証をしたらうまくいくのか」と考えてみると明らかなのだが、アセンブリより高いレベルで推論するときには見落としがちなことだ。

実行時には、Type Switchを評価するコストはcase文の数に対して線形に増えていき O(n)の計算量となる。

また、N個のcaseがあるType Switch文を評価するのには、実質N個のType Assertionを評価するのに等しい時間がかかるとも同様に考えられる。

ここでも特別なことはしておらず、愚直に処理を行っている

いくつかのベンチマークを用いてこのことを実際に目で見て確認しよう (eface_to_type_test.go):

var j uint32
var eface interface{} = uint32(42)

func BenchmarkEfaceToType(b *testing.B) {
    b.Run("switch-small", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            switch v := eface.(type) {
            case int8:
                j = uint32(v)
            case int16:
                j = uint32(v)
            default:
                j = v.(uint32)
            }
        }
    })
    b.Run("switch-big", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            switch v := eface.(type) {
            case int8:
                j = uint32(v)
            case int16:
                j = uint32(v)
            case int32:
                j = uint32(v)
            case int64:
                j = uint32(v)
            case uint8:
                j = uint32(v)
            case uint16:
                j = uint32(v)
            case uint64:
                j = uint32(v)
            default:
                j = v.(uint32)
            }
        }
    })
}

benchstat <(go test -benchtime=1s -bench=. -count=3 ./eface_to_type_test.go)
name                        time/op
EfaceToType/switch-small-8  1.91ns ± 2%
EfaceToType/switch-big-8    3.52ns ± 1%

検証すべきcase文が余計に増えた2個目のType Switchでは各イテレーションに約2倍の時間を要するようになった。

ここでcase uint32をSwitch文のどこかに加えてみる。そうすると興味深いことにパフォーマンスが劇的に向上する。

benchstat <(go test -benchtime=1s -bench=. -count=3 ./eface_to_type_test.go)
name                        time/op
EfaceToType/switch-small-8  1.63ns ± 1%
EfaceToType/switch-big-8    2.17ns ± 1%

これは推測だが、

上記で述べたcase文の並び替えにより、case uint32の検証が早くなる
検証は分岐を伴うのでCPUの最適化が効きにくい

ことが理由として考えられる

Note 3: Type hashes と pointer の比較

最後に各caseにおいて次の2回に分けて行われていた型の比較について説明していく

_type.hashの比較
1の比較結果が一致したなら、それぞれの_typeのアドレスが一致するか比較する

各_typeはコンパイラによって生成され、グローバル変数として.rodataセクションに格納されるので、プログラムの生存期間の間、各_typeのアドレスはずっと一意に定まることが保証される。

この2段階の比較は、1段階目のハッシュの一致が単なるハッシュの衝突(つまり型は違うが、そのハッシュ値が一致してしまった)でないことを確認するのに意味がある。

しかしそれなら、そもそも_typeのアドレスの比較だけを行って_type.hashという概念は切り捨ててしまった方が理にかなっているように思える。

実際、以前見た簡単なType Assertionでは_typeの比較を行っているだけで、ハッシュを検証に用いてはいない。

疑問を投げかけておいて申し訳ないのだが、残念なことに、この疑問に対する答えをまだ筆者は得られていない。

type hashと言えば、すでに $-800397251がtype.uint32.hash に $-269349216 が type.uint16.hash に対応することは見たが、これを実際に確かめてみよう。(eface_type_hash.go)

// simplified definitions of runtime's eface & _type types
type eface struct {
    _type *_type
    data  unsafe.Pointer
}
type _type struct {
    size    uintptr
    ptrdata uintptr
    hash    uint32
    /* omitted lotta fields */
}

var Eface interface{}
func main() {
    Eface = uint32(42)
    fmt.Printf("eface<uint32>._type.hash = %d\n",
        int32((*eface)(unsafe.Pointer(&Eface))._type.hash))

    Eface = uint16(42)
    fmt.Printf("eface<uint16>._type.hash = %d\n",
        int32((*eface)(unsafe.Pointer(&Eface))._type.hash))
}

$ go run eface_type_hash.go
eface<uint32>._type.hash = -800397251
eface<uint16>._type.hash = -269349216

最後に

これでインターフェースに関する説明は終わりだ。

関数呼び出しのアセンブリという浅いところからずいぶん深くまで見ていったと思う。

しかし、いくつかの疑問は明確な答えが得られていないまま残っているのでそこに関しては随時追記をしていく予定だ。

リンク