Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 13800] ファイルの概要

このコミットは、Goコンパイラ（cmd/gc）において、ポインタサイズの型からインターフェースへの変換（T2I変換）をインライン化することで、パフォーマンスを大幅に向上させることを目的としています。また、AST（抽象構文木）内のIFノードに「可能性（likelyness）」のヒントを付与する機能を追加し、コンパイラが条件分岐の最適化をより効果的に行えるようにしています。特に、インターフェース変換における「遅いパス（slow path）」を「可能性が低い（unlikely）」とマークすることで、コンパイラがより効率的なコードを生成できるようになります。

コミット

commit 8fd65b0e1d6b737072982a1cf846ff76b1353f02
Author: Daniel Morsing <daniel.morsing@gmail.com>
Date:   Tue Sep 11 21:42:30 2012 +0200

    cmd/gc: Inline pointer sized T2I interface conversions
    
    This CL also adds support for marking the likelyness of IF nodes in the AST being true. This feature is being used here to mark the slow path as unlikely.
    
    src/pkg/runtime:
    benchmark                  old ns/op    new ns/op    delta
    BenchmarkConvT2IUintptr           16            1  -91.63%
    
    test/bench/go1:
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBinaryTree17    5416917000   5461355000   +0.82%
    BenchmarkFannkuch11      3810355000   3842609000   +0.85%
    BenchmarkGobDecode         19950950     19855420   -0.48%
    BenchmarkGobEncode         11301220     11308530   +0.06%
    BenchmarkGzip             548119600    546869200   -0.23%
    BenchmarkGunzip           176145400    180208300   +2.31%
    BenchmarkJSONEncode        93117400     70163100  -24.65%
    BenchmarkJSONDecode       406626800    409999200   +0.83%
    BenchmarkMandelbrot200      6300992      6317866   +0.27%
    BenchmarkParse              7664396      7451625   -2.78%
    BenchmarkRevcomp         1189424000   1412332000  +18.74%
    BenchmarkTemplate         491308400    458654200   -6.65%
    
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkGobDecode            38.47        38.66    1.00x
    BenchmarkGobEncode            67.92        67.87    1.00x
    BenchmarkGzip                 35.40        35.48    1.00x
    BenchmarkGunzip              110.16       107.68    0.98x
    BenchmarkJSONEncode           20.84        27.66    1.33x
    BenchmarkJSONDecode            4.77         4.73    0.99x
    BenchmarkParse                 7.56         7.77    1.03x
    BenchmarkRevcomp             213.69       179.96    0.84x
    BenchmarkTemplate              3.95         4.23    1.07x
    
    R=rsc, dave, nigeltao
    CC=golang-dev
    https://golang.org/cl/6351090

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/8fd65b0e1d6b737072982a1cf846ff76b1353f02

元コミット内容

このコミットの主な目的は、Goコンパイラ（cmd/gc）において、ポインタサイズの型（例: *int, string, []byteなど）からインターフェース型への変換（T2I変換）の性能を向上させることです。具体的には、これらの変換処理をインライン化することで、関数呼び出しのオーバーヘッドを削減し、実行速度を高速化します。

さらに、このコミットでは、AST（抽象構文木）内のIFノード（条件分岐）に対して、その条件が真になる「可能性（likelyness）」をマークする機能が追加されています。この機能は、コンパイラが条件分岐の最適化を行う際に、どちらのパスがより頻繁に実行されるかを予測するのに役立ちます。今回の変更では、特にインターフェース変換における「遅いパス」を「可能性が低い（unlikely）」とマークすることで、コンパイラがより効率的なコードを生成し、高速なパスに最適化のリソースを集中させることが可能になります。

ベンチマーク結果を見ると、BenchmarkConvT2IUintptrが91.63%という劇的な改善を示しており、この最適化がインターフェース変換の性能に大きな影響を与えていることがわかります。他のベンチマークでは、BenchmarkJSONEncodeが24.65%の改善、BenchmarkTemplateが6.65%の改善を見せていますが、BenchmarkRevcompのように18.74%の性能低下が見られるものもあります。これは、コンパイラの最適化が全体的なパフォーマンスに与える影響が複雑であることを示唆しています。

変更の背景

Go言語は、その設計思想としてシンプルさとパフォーマンスの両立を目指しています。インターフェースはGoの強力な機能の一つであり、ポリモーフィズムを実現するために広く利用されています。しかし、インターフェースの内部表現と、具体的な型からインターフェースへの変換（T2I変換）には、実行時コストが伴います。特に、ポインタサイズの型は頻繁にインターフェースに変換されるため、この部分のオーバーヘッドがアプリケーション全体のパフォーマンスに影響を与える可能性がありました。

このコミットが行われた2012年当時、Goコンパイラはまだ初期段階にあり、様々な最適化の余地がありました。インターフェース変換のインライン化は、関数呼び出しのコストを削減し、より効率的な機械語コードを生成するための一般的なコンパイラ最適化手法です。

また、条件分岐の「可能性」をコンパイラに伝える機能は、プロファイルに基づく最適化（PGO）や、静的なコード解析に基づくヒューリスティックな最適化において非常に重要です。コンパイラがどのパスが「ホットパス」（頻繁に実行されるパス）であるかを事前に知っていれば、そのパスに特化した最適化を施し、全体の実行速度を向上させることができます。インターフェース変換の文脈では、型が既にインターフェースに適合している場合の「速いパス」と、適合していない場合の「遅いパス」（ランタイムでの型チェックやItab検索が必要なパス）が存在します。この「遅いパス」を「unlikely」とマークすることで、コンパイラは「速いパス」を優先的に最適化し、全体的な性能向上を図ることができます。

前提知識の解説

GoのインターフェースとT2I変換

Goのインターフェースは、メソッドのシグネチャの集合を定義する型です。Goのインターフェースは、動的なディスパッチを可能にするために、内部的には2つのワードで構成される構造体として表現されます。

  1. 型情報（Type Word）: インターフェースに格納されている具体的な値の型情報（_type構造体へのポインタ）。
  2. 値情報（Value Word）: インターフェースに格納されている具体的な値そのもの（またはその値へのポインタ）。

**T2I変換（Type-to-Interface Conversion）**とは、具体的な型（例: int, string, MyStructなど）の値をインターフェース型に代入する際に発生する変換処理です。この変換では、ランタイムが具体的な型の情報と値情報を抽出し、インターフェースの内部構造に格納します。

ポインタサイズの型（例: *int, string, []byte）の場合、値情報は直接インターフェースのValue Wordに格納されます。しかし、値がポインタサイズでない場合（例: int, struct{}など）、値はヒープにアロケートされ、そのポインタがValue Wordに格納されます。

T2I変換のプロセスには、以下のステップが含まれます。

  • 型チェック: 具体的な型がインターフェースのすべてのメソッドを実装しているかどうかのチェック。
  • Itab（Interface Table）の検索/生成: インターフェース型と具体的な型のペアに対応するItabを探します。Itabは、その具体的な型がインターフェースのメソッドをどのように実装しているか（メソッドテーブル）の情報を含んでいます。Itabはキャッシュされ、同じペアの変換が再度行われる際に再利用されます。
  • 値の格納: 具体的な値をインターフェースのValue Wordに格納します。

これらのステップは、特にItabの検索やヒープアロケーション（値がポインタサイズでない場合）がパフォーマンスのボトルネックとなることがあります。

AST（抽象構文木）とコンパイラ最適化

**AST（Abstract Syntax Tree）**は、ソースコードの構造を木構造で表現したものです。コンパイラは、ソースコードをパースしてASTを生成し、このASTに対して様々な解析や変換（最適化）を行います。

コンパイラ最適化は、生成される機械語コードの実行速度やサイズを改善するためのプロセスです。これには、以下のような様々な手法があります。

  • インライン化（Inlining）: 関数呼び出しを、呼び出し元のコードに直接展開することで、関数呼び出しのオーバーヘッド（スタックフレームのセットアップ、レジスタの保存/復元など）を削減します。
  • デッドコード削除（Dead Code Elimination）: 決して実行されないコードを削除します。
  • 定数畳み込み（Constant Folding）: コンパイル時に計算可能な式を事前に計算し、その結果で置き換えます。
  • ループ最適化（Loop Optimization）: ループの実行を高速化するための様々な手法（ループアンローリング、ループ不変コードの移動など）。

条件分岐の「可能性（Likelyness）」ヒント

コンパイラは、if文やswitch文のような条件分岐の最適化を行う際に、どちらの分岐がより頻繁に実行されるかを知っていると、より効率的なコードを生成できます。例えば、頻繁に実行されるパス（ホットパス）を、CPUのキャッシュに乗りやすいように配置したり、分岐予測器が正しく予測できるようにコードを並べ替えたりすることができます。

この「可能性」のヒントは、以下のような方法でコンパイラに与えられます。

  • プロファイルに基づく最適化（PGO: Profile-Guided Optimization）: 実際のプログラム実行時のプロファイルデータ（どのコードパスがどれくらいの頻度で実行されたか）を収集し、それに基づいて最適化を行います。
  • 静的なヒューリスティック: コードのパターンや特定のAPIの使用状況から、コンパイラが経験的に「この条件は真になりやすい/なりにくい」と判断します。

このコミットでは、後者の静的なヒューリスティックに近い形で、ASTノードにlikelyというフィールドを追加し、コンパイラが明示的に条件の可能性をマークできるようにしています。likely = -1は「unlikely」（可能性が低い）を意味し、コンパイラはそれに応じて最適化戦略を調整します。

技術的詳細

このコミットの技術的詳細は、主に以下の2つの側面から構成されます。

  1. ポインタサイズのT2I変換のインライン化:

    • Goのインターフェース変換は、通常、ランタイム関数（例: runtime.convT2I）への呼び出しを伴います。この関数は、型チェック、Itabの検索/生成、値の格納といった処理を行います。
    • ポインタサイズの型の場合、値のコピーが比較的単純であり、ヒープアロケーションも不要なため、この変換処理をコンパイラが直接生成するコード（インラインコード）に置き換えることで、関数呼び出しのオーバーヘッドを排除し、大幅な高速化が期待できます。
    • インライン化されたコードは、Itabのキャッシュを直接参照し、もしキャッシュミスが発生した場合は、runtime.typ2Itabという新しいランタイム関数を呼び出してItabを検索/生成し、キャッシュを更新します。この「キャッシュミス時のランタイム呼び出し」が「遅いパス」となります。

  2. ASTにおけるIFノードのlikelynessマーキング:

    • src/cmd/gc/go.hのNode構造体にschar likely;フィールドが追加されました。これは、if文の条件が真になる可能性を示すために使用されます。
    • likelyの値は、0（不明）、1（likely、可能性が高い）、-1（unlikely、可能性が低い）などを表すと考えられます。
    • src/cmd/gc/gen.cでは、bgen関数（条件分岐のコード生成を行う関数）がn->likelyフィールドを考慮するように変更されました。これにより、コンパイラは条件分岐のコードを生成する際に、その条件が真になる可能性に基づいて、より効率的な分岐命令やコード配置を選択できるようになります。
    • 今回のT2I変換の最適化では、インライン化されたコード内でItabキャッシュがnilであるかどうかのチェック（つまり、キャッシュミスが発生した場合）のif文に対して、n2->likely = -1;と設定されています。これは、キャッシュミスが頻繁に発生するわけではないため、このパスが「unlikely」であることをコンパイラに明示的に伝えています。これにより、コンパイラはキャッシュヒットの「速いパス」を優先的に最適化し、キャッシュミスの「遅いパス」にはあまりリソースを割かないようにします。

Itabとruntime.typ2Itab

Goのインターフェースは、内部的にItab（Interface Table）という構造体を利用して、具体的な型がインターフェースのメソッドをどのように実装しているかを管理します。Itabは、インターフェース型と具体的な型のペアごとに一意に存在し、その型が実装するメソッドへのポインタの配列を含んでいます。

T2I変換の際、ランタイムはまず、変換対象の具体的な型とインターフェース型に対応するItabが既に存在するかどうかをキャッシュで検索します。存在すればそれを利用し、存在しなければ新しく生成してキャッシュに格納します。

このコミットで追加されたruntime.typ2Itab関数は、このItabの検索と生成、そしてキャッシュへの格納を行うランタイム関数です。インライン化されたT2I変換コードは、キャッシュミスが発生した場合にこのruntime.typ2Itabを呼び出すことで、必要なItabを取得します。

コアとなるコードの変更箇所

このコミットにおける主要なコード変更は以下のファイルに集中しています。

  • src/cmd/gc/builtin.c:

    • runtimeimport文字列に新しいランタイム関数typ2Itabのシグネチャが追加されています。これは、コンパイラがこのランタイム関数を認識し、呼び出せるようにするためです。
    +	"func @\"\\\".typ2Itab(@\"\\\".typ *byte, @\"\\\".typ2 *byte, @\"\\\".cache **byte) (@\"\\\".ret *byte)\\n"

  • src/cmd/gc/gen.c:

    • gen関数内のbgen呼び出しで、n->likelyフィールドが使用されるように変更されています。これにより、条件分岐のコード生成時にlikelynessヒントが考慮されます。
    -	bgen(n->ntest, 0, 0, p2);		//	if(!test) goto p2
+	bgen(n->ntest, 0, -n->likely, p2);		//	if(!test) goto p2
    • cgen_eface関数（インターフェース値のコード生成）のロジックが変更され、n->leftとn->rightの評価順序が入れ替わっています。これは、efaceの右側のノードがresを引数として使用する関数呼び出しを含む可能性があるため、resが先に準備されるようにするためです。
    -	cgen(n->left, &dst);
 	dst.xoffset += widthptr;
 	cgen(n->right, &dst);
+	dst.xoffset -= widthptr;
+	cgen(n->left, &dst);

  • src/cmd/gc/go.h:

    • Node構造体にschar likely;フィールドが追加されています。これは、if文の条件が真になる可能性をマークするために使用されます。
    +	schar	likely; // likeliness of if statement

  • src/cmd/gc/runtime.go:

    • typ2Itabランタイム関数のGo側の宣言が追加されています。これは、コンパイラがこの関数をGoコードから呼び出せるようにするためです。
    +func typ2Itab(typ *byte, typ2 *byte, cache **byte) (ret *byte)

  • src/cmd/gc/walk.c:

    • walkexpr関数内で、ポインタサイズのT2I変換に対する特殊な最適化ロジックが追加されています。
    • このロジックは、Itabキャッシュを直接参照し、キャッシュミスの場合にruntime.typ2Itabを呼び出すコードを生成します。
    • 特に重要なのは、キャッシュミスをチェックするif文に対してn2->likely = -1;が設定されている点です。
    +			if(n->left->type->width == widthptr &&
+			   isint[simsimtype(n->left->type)]) {
+				/* For pointer types, we can make a special form of optimization
+				 *
+				 * These statements are put onto the expression init list:
+				 * 	Itab *tab = atomicloadtype(&cache);
+				 * 	if(tab == nil)
+				 * 		tab = typ2Itab(type, itype, &cache);
+				 *
+				 * The CONVIFACE expression is replaced with this:
+				 * 	OEFACE{tab, ptr};
+				 */
+				l = temp(ptrto(types[TUINT8]));
+
+				n1 = nod(OAS, l, sym->def);
+				typecheck(&n1, Etop);
+				*init = list(*init, n1);
+
+				fn = syslook("typ2Itab", 1);
+				n1 = nod(OCALL, fn, N);
+				n1->list = ll;
+				typecheck(&n1, Erv);
+				walkexpr(&n1, init);
+
+				n2 = nod(OIF, N, N);
+				n2->ntest = nod(OEQ, l, nodnil());
+				n2->nbody = list1(nod(OAS, l, n1));
+				n2->likely = -1; // Mark this slow path as unlikely
+				typecheck(&n2, Etop);
+				*init = list(*init, n2);
+
+				l = nod(OEFACE, l, n->left);
+				l->typecheck = n->typecheck;
+				l->type = n->type;
+				n = l;
+				goto ret;
+			}

  • src/pkg/runtime/iface.c:

    • 新しいランタイム関数runtime.typ2Itabの実装が追加されています。この関数は、指定された型とインターフェース型に対応するItabを検索または生成し、キャッシュに格納します。
    +#pragma textflag 7
+void
+runtime·typ2Itab(Type *t, InterfaceType *inter, Itab **cache, Itab *ret)
+{
+	Itab *tab;
+
+	tab = itab(inter, t, 0);
+	runtime·atomicstorep(cache, tab);
+	ret = tab;
+	FLUSH(&ret);
+}

コアとなるコードの解説

src/cmd/gc/builtin.c と src/cmd/gc/runtime.go の変更

これらのファイルは、Goコンパイラが認識する組み込み関数やランタイム関数の定義に関連しています。builtin.cでは、コンパイラがC言語で書かれたランタイム関数を呼び出すための「外部関数」としてtyp2Itabのシグネチャが追加されています。一方、runtime.goでは、Go言語側からこのランタイム関数を呼び出すためのGoの関数シグネチャが追加されています。これにより、コンパイラはGoコード内でtyp2Itabを呼び出す際に、その型情報を正しく解決できるようになります。

src/cmd/gc/go.h の変更

Node構造体へのschar likely;の追加は、ASTの各ノード、特にif文のような条件分岐を表すノードに、その条件が真になる可能性のヒントを付与できるようにするための基盤となります。scharは符号付き文字型であり、-1（unlikely）、0（不明）、1（likely）などの値を格納できます。この情報は、後続のコード生成フェーズで利用され、より効率的な分岐命令の選択やコード配置に役立ちます。

src/cmd/gc/gen.c の変更

gen.cは、ASTから機械語コードを生成する部分を担当しています。bgen関数は、条件分岐（if文など）のコードを生成する際に呼び出されます。変更点であるbgen(n->ntest, 0, -n->likely, p2);は、n->likelyフィールドの値を考慮して分岐命令を生成することを示しています。例えば、n->likelyが-1（unlikely）の場合、-n->likelyは1となり、コンパイラはこの分岐が真になる可能性が低いと判断し、その情報に基づいて最適化を行います。これにより、CPUの分岐予測器がより正確に予測できるようになり、パイプラインストールを減らすことでパフォーマンスが向上します。

src/cmd/gc/walk.c の変更

walk.cは、ASTを走査し、最適化やコード変換を行う「ウォーカー」の役割を担っています。このファイルへの変更は、今回のコミットの核心部分です。

追加されたコードブロックは、ポインタサイズの型からインターフェースへの変換（CONVIFACEオペレーション）を検出した際に、特別な最適化パスを適用します。

  1. キャッシュ参照: まず、Itabキャッシュ（sym->def）を直接参照し、対応するItabが既にキャッシュされているかどうかを確認します。
  2. キャッシュミス時の処理:
    • もしキャッシュがnil（キャッシュミス）であれば、runtime.typ2Itab関数を呼び出します。この関数は、ランタイムでItabを検索または生成し、キャッシュに格納します。
    • このキャッシュミスをチェックするif文（n2 = nod(OIF, N, N); n2->ntest = nod(OEQ, l, nodnil());）に対して、n2->likely = -1;が設定されています。これは、キャッシュミスが稀にしか発生しない「遅いパス」であることをコンパイラに明示的に伝えます。これにより、コンパイラはキャッシュヒットの「速いパス」を優先的に最適化し、キャッシュミス時のコードはあまり最適化しないようにします。
  3. インライン化されたインターフェース値の構築: キャッシュされたItab（またはruntime.typ2Itabによって取得されたItab）と、元のポインタサイズの値を組み合わせて、新しいインターフェース値（OEFACE）を直接構築します。これにより、従来のランタイム関数呼び出しによるオーバーヘッドが排除されます。

この一連の処理により、ポインタサイズのT2I変換は、ほとんどの場合、関数呼び出しなしでインラインで処理されるようになり、大幅なパフォーマンス向上が実現されます。

src/pkg/runtime/iface.c の変更

このファイルはGoランタイムのインターフェース関連の処理を実装しています。追加されたruntime.typ2Itab関数は、コンパイラがインライン化されたT2I変換の「遅いパス」から呼び出すための実体です。

  • itab(inter, t, 0): この関数は、指定されたインターフェース型interと具体的な型tに対応するItabを検索または生成します。0は、Itabが見つからない場合にパニックしないことを意味します。
  • runtime·atomicstorep(cache, tab): 取得したItabを、コンパイラが渡してきたキャッシュポインタcacheにアトミックに格納します。これにより、複数のゴルーチンが同時にItabを検索/生成しようとした場合でも、キャッシュの一貫性が保たれます。
  • ret = tab; FLUSH(&ret);: 取得したItabを戻り値として設定し、キャッシュをフラッシュします。

このランタイム関数は、インライン化されたコードがキャッシュミスした場合のフォールバックメカニズムとして機能し、必要に応じてItabを効率的に取得・キャッシュします。

関連リンク

参考にした情報源リンク

  • コミットハッシュ: 8fd65b0e1d6b737072982a1cf846ff76b1353f02
  • GitHub上のコミットページ: https://github.com/golang/go/commit/8fd65b0e1d6b737072982a1cf846ff76b1353f02
  • Goのインターフェースの内部構造に関する一般的な知識
  • コンパイラ最適化（インライン化、分岐予測）に関する一般的な知識
  • Go言語のランタイムに関する一般的な知識
  • GoのItabに関する情報（非公式のブログ記事やGoのソースコード解析）
  • Goのベンチマーク結果の解釈に関する一般的な知識