Go言語でのインターフェースの遅さ #Go

TL;DR

Go 言語において:

関数のパラメータに構造体を渡したい場合、実体コピーで渡すよりポインタを使用したほうが速い。
ポインタのダウンキャストはオーバーヘッドが存在する。
インターフェースを介したメソッド呼び出しはかなり高コスト。

これらはどれも C/C++ や Java で同様の思い当たることがあるだろう。3 に関しては少し影響が大きいように見受けられ、パフォーマンスを目的として Go 言語を採用したのであればオブジェクト指向や責務の分担といった設計と両立が難しいコストとなるかもしれない。

なお筆者は Go 言語やランタイムの構造にあまり詳しくない点に注意。

経緯

以下のようなコードでパラメータの型 Image が比較的大きな構造体のポインタとなるインターフェースの場合にパフォーマンスはどうなのかという話がまずあり。

func (n Entity) LessThan(other Image) bool {
  return n.Value < other.(*Entity).Value
}

Go 言語でのスライス (配列) のソート実装に対して「評価関数のパラメータはポインタやインターフェースではなく実体で渡すべき」という指摘を見かけた (Go における interface は実質的にポインタと同じと認識)。これは経験的な直感に反する意見であったため、論議されていた内容からテストコードを起こしてみたところ、たしかに実体で渡す方が速いという結果が出た。

この github.com に載せたテストコードを go test -bench . -benchtime で実行すれば以下のような結果が得られるだろう。

BenchmarkQuickSort/Entity-8         1000000000         0.182 ns/op
BenchmarkQuickSort/Image-8          1000000000         0.644 ns/op
BenchmarkQuickSort/ImageRef-8       1000000000         0.631 ns/op

このケースに対する結果は実体コピーで渡すよりポインタで渡すほうが 3.5 倍ほど遅いことを示しているように見える。マジか。

その論議での見立てとしては、ポインタの多用はキャッシュのヒット率を低下させ (特にソートでは実体のメモリ上の配置が頻繁に入れ替わるため)、実体渡しによる一時的な構造体全体のメモリコピーのコストより、キャッシュを効率的に活用できないコストのほうが大きくなるのだろうということだった。

個人的に「構造体はポインタで渡すもの」という認識はメモリ制約の厳しい MS-DOS (16bit) 時代にヒューリスティックに身に着けたものだった。確かに配列全体がキャッシュに乗るような現代的な CPU では事情が違っているかもしれない。ここは設計に関わる転換点かもしれないのでもっと詳しく調べてみよう、というのがこの記事を書くに至った動機。

方法

何度か試行錯誤し、前述のテストコードは 3 つの観点に分解することが適切であろうという見立てができた。これはそのまま TL;DR の内容である。

Entity Copy: 関数のパラメータを実体コピーで渡す方法とポインタで渡す方法の比較。
Downcast: インターフェースをダウンキャストして使用する方法とダウンキャストしないで使用する方法の比較。
Interface Method: フィールドやメソッドの参照をインターフェースに対して行うか実体に対して行うかの比較。

これらを評価するテストコードは github.com に置いてある。

結果

以下は前述のテストコードを go test -bench . -benchtime 30s で実行した結果を表している。実行時間は評価関数を math.MaxInt32=2G 回呼び出した時間、コストはポインタを使った呼び出しを 0 として実コードを鑑みて加算されているだろう想定。

No.	評価した関数	実行時間[sec/2G回]	コスト
1.	func(a, b Entity) bool { return a.Value < b.Value }	0.561844478	0 (コンパイラ最適化?)
2.	func(a, b *Entity) bool { return a.Value < b.Value }	0.559486798	0
3.	func(a, b Image) bool { return a.(Entity).Value < b.(Entity).Value }	49.346256905	Downcast + EntityCopy
4.	func(a, b Image) bool { return a.(Entity).Value < b.(Entity).Value }	1.154817580	Downcast
5.	func(a, b Entity) bool { return a.Priority() < b.Priority() }	12.049262425	EntityCopy
6.	func(a, b *Entity) bool { return a.Priority() < b.Priority() }	0.627853464	0
7.	func(a, b Image) bool { return a.(Entity).Priority() < b.(Entity).Priority() }	48.182371678	Downcast + EntityCopy
8.	func(a, b Image) bool { return a.(Entity).Priority() < b.(Entity).Priority() }	1.212487740	Downcast
9.	func(a, b Image) bool { return a.Priority() < b.Priority() }	206.816625555	EntityCopy + InterfaceMethod
10.	func(a, b Image) bool { return a.Priority() < b.Priority() }	24.386049284	InterfaceMethod

Entity Copy 問題

構造体の実体に対するフィールドアクセスの 1 と 2 でほとんど差異が見られない一方で、メソッド呼び出しの 5 と 6 とでは 20 倍近い大きな差が出ている (構造体サイズに比例すると想定すると何倍かに意味はないが)。1 の関数では引数の構造体がポインタでも影響がないことが明らかであることを Go コンパイラが認識してポインタ呼び出しに最適化されているのではないだろうかと考え 5 と 6 の差異を実体コピーのコストの差とする。

このテストにおける実体コピーのオーバーヘッドを 5 と 6 の差÷2 の $t_e=5.71$ [sec] としておく (多分パラメータ 2 つのコピーコストだろう)。

Downcast 問題

6 と 8 の差異からダウンキャストによるコストが見られる。Go 言語はダウンキャストでの変換の妥当性を実行時に検証しており、これは Java で ClassCastException を発生させるチェックや C/C++ での dynamic_cast のような実行時情報評価と類似したコストであろう。2 と 4 の差異÷2からこのコストを $t_d=0.29$ [sec] と仮置く。これは構造体のサイズには依存しないだろう。

3 と 7 は非常に大きな時間がかかっているが、これはキャスト先が実体であるためにダウンキャストのコストに加えてメモリコピーのコストが加算されているものと推測される。$t_3 \simeq t_4 + t_e \times 8$ とすると実体コピー 4 回分が加算されているように見える。

Interface Method 問題

9 と 10 は同じコードだが、実際にパラメータとして渡している値が構造体の実体そのものか構造体のポインタかの違いがある (つまり 9 は Entity Copy 問題を含んでいる)。6 と 10 を比較すると、同じメソッドであってもインターフェースに対するメソッド呼び出しのほうに非常に大きなコストが発生していることが分かる。6 と 10 の差÷2より $t_i=16.88$ [sec] と仮置く。これは構造体のサイズには依存しないだろう。

例えば Java ではインターフェースに対するメソッドの呼び出しは若干コストが高いことが知られている。これは、Java で複数のインターフェースを implements する事が可能であるため仮想関数テーブル内の該当メソッドの位置をコンパイル時に決定できず、メソッド呼び出しのたびに仮想関数テーブルを探す必要があるためだ。いまのところ Go でも同様のことを行っているのだろうという予想だが、詳しく知っている人が居たら教えてほしいところ。

とにかく、Go 言語ではインターフェースのメソッド呼び出しに関しては (Java における差異と比較しても) 負荷が大きいようである。パフォーマンスが重要な部分ではインターフェースを使ったオブジェクト指向設計や責務の分担といった上位概念の導入は Go 言語では避ける必要があるように見える。

9 のケースがかなり大きなコストである理由は分からない。

結論

基準ケースを $t_2=0.56$ [sec] とする。実体コピー $t_e=5.71$ [sec] は 10 倍以上だが構造体のサイズに依存するコスト (このテストコードでは構造体サイズ 108 バイト) なので一概には比較できない。ただ構造体サイズが 64bit/32bit を超えるなら実体コピーを伴う呼び出しよりポインタでの呼び出しの方が速いだろう。ダウンキャスト $t_d=0.29$ は基準ケースの 1/2 も低く無視できるケースもあるだろう。しかしインターフェースのメソッド呼び出し $t_i=16.88$ [sec] は 30 倍もあり大きな影響となりうる。

まあ、一例での絶対値を用いた比較はあまり意味がないが、今回の結果として Go プログラミングで注意すべき優先順位は以下のようになるのではないだろうか。

Interface Method の使用 >> Entity Copy の発生 > [trivialの壁] > Downcast

附録

元々この検証は実体コピーによる呼び出しとポインタによる呼び出しの差異を調べることから始まった。本当にキャッシュヒットが関係するのであれば C/C++ でも同じ結果になると考えて go と C とで作成したバブルソートで比較していた。

go で実装したテストコードはポインタを使用した方が有意に速かった。

$ go test -bench .
goos: darwin
goarch: amd64
BenchmarkBubbleSort/CallByValue-8         1000000000         0.796 ns/op
BenchmarkBubbleSort/CallByReference-8     1000000000         0.417 ns/op

C で実装したテストコードでも同様にポインタを使用したほうが速かった。

clang$ gcc main.c -o main
clang$ ./main
by value    : 2.129106[sec]
by reference: 0.464097[sec]

どれほどの差があるかは置いておくとして、大きな構造体のコピーを伴う関数呼び出しよりもポインタを使用した呼び出しのほうが高速であることは明らかなようである。