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

このコミットで変更された src/cmd/gc/swt.c ファイルは、Goコンパイラのバックエンドの一部であり、特にGo言語の switch ステートメントの処理を担当しています。gc はGoコンパイラの主要な部分であり、ソースコードを抽象構文木（AST）に変換し、最終的に機械語にコンパイルする過程で、このような制御フロー構造の最適化を行います。swt.c は、switch 文を効率的な分岐命令のシーケンスに変換するためのロジックを含んでいます。

コミット

binary search for constant case statements.

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

https://github.com/golang/go/commit/820f42d977817785ff198425292cddd5f6900083

元コミット内容

binary search for constant case statements.

R=r
OCL=25890
CL=25890

変更の背景

Go言語の switch ステートメントは、多くのプログラミング言語と同様に、複数の異なる値に対して条件分岐を行うための強力な構文です。しかし、コンパイラがこの switch ステートメントをどのように機械語に変換するかは、そのパフォーマンスに大きな影響を与えます。

このコミット以前のGoコンパイラ（gc）では、switch ステートメントの case が定数である場合、コンパイラは通常、一連の if-else if ステートメントに変換していました。例えば、以下のような switch 文があったとします。

switch x {
case 1:
    // do something
case 5:
    // do something else
case 100:
    // do another thing
default:
    // default action
}

これは、コンパイル時に概念的には以下のようなコードに変換されていました。

if (x == 1) {
    // do something
} else if (x == 5) {
    // do something else
} else if (x == 100) {
    // do another thing
} else {
    // default action
}

この線形探索（linear search）のアプローチは、case の数が少ない場合には問題ありませんが、case の数が非常に多くなると、最悪の場合、すべての case をチェックするまで比較を続ける必要があり、パフォーマンスが O(N)（Nはケースの数）に劣化します。これは、特に大規模な switch ステートメントにおいて、コンパイルされたコードの実行速度を低下させる要因となります。

このコミットの目的は、定数 case ステートメントを持つ switch 文のコンパイル戦略を改善し、より効率的な二分探索（binary search）アルゴリズムを導入することによって、実行時のパフォーマンスを向上させることでした。二分探索は、ソートされたデータに対して O(log N) の時間計算量で要素を検索できるため、case の数が多い場合に大幅な高速化が期待できます。

前提知識の解説

このコミットの変更内容を理解するためには、以下の前提知識が役立ちます。

1. Goコンパイラ (gc) の構造:

   • Goコンパイラは、src/cmd/gc ディレクトリに位置する主要なコンパイラです。これは、Goソースコードを解析し、抽象構文木（AST）を構築し、型チェックを行い、最終的にアセンブリコードを生成する役割を担っています。
   • コンパイラのフロントエンドはソースコードをASTに変換し、バックエンドはASTを最適化し、ターゲットアーキテクチャの機械語に変換します。swt.c はこのバックエンドの一部として機能します。

2. 抽象構文木 (AST):

   • コンパイラはソースコードを直接操作するのではなく、まずその構造をASTとしてメモリ上に表現します。ASTは、プログラムの構造を木構造で表現したもので、各ノードが演算子、変数、関数呼び出しなどのプログラム要素に対応します。
   • Node 構造体は、Goコンパイラ内でASTの各ノードを表すために使用されます。Node->left, Node->right, Node->nbody などのフィールドは、ノード間の関係や、そのノードが表すコードブロック（例えば if 文の本体や switch 文のケースリスト）を指します。

3. switch ステートメントの内部表現:

   • Goコンパイラは、switch ステートメントを内部的に一連の比較とジャンプ命令に変換します。従来の線形探索では、これは if (expr == val1) goto L1; else if (expr == val2) goto L2; ... のような構造に対応します。

4. 二分探索アルゴリズム:

   • 二分探索は、ソートされた配列（またはリスト）から特定の要素を探し出すための効率的なアルゴリズムです。
   • 基本的な考え方は、配列の中央の要素と目的の値を比較し、目的の値が中央の要素より小さい場合は左半分を、大きい場合は右半分を探索するというものです。このプロセスを繰り返すことで、探索範囲を半分ずつ絞り込み、対数時間で要素を見つけ出します。
   • switch ステートメントに適用する場合、case の値をソートし、二分探索ツリーのような構造を構築することで、効率的な分岐を実現します。

5. Iter 構造体:

   • Goコンパイラ内部でリストやツリー構造を走査するためのイテレータとして使用される可能性があります。このコミットでは、prepsw 関数内で Iter save; として使用され、switch ケースのリストを走査するために使われています。

技術的詳細

このコミットは、src/cmd/gc/swt.c に新しい関数とロジックを導入し、定数 case ステートメントを持つ switch 文のコンパイル方法を根本的に変更します。

1. prepsw 関数の変更:

   • prepsw 関数は、switch ステートメントを処理する主要な関数です。この変更により、prepsw は switch 式が定数であるかどうかを判断し、定数である場合は新しく追加された binarysw 関数を呼び出すようになりました。
   • 変更前は、すべての case に対して OIF (if) ノードを生成し、線形に比較を行っていました。
   • 変更後、binarysw(t, &save, name) が呼び出され、もし binarysw が非NULLの Node を返した場合（つまり、二分探索による最適化が適用された場合）、その結果が使用されます。そうでなければ、従来の線形探索の OIF ノードが生成されます。

2. binarysw 関数の導入:

   • この関数は、定数 case ステートメントのリストを受け取り、それらを二分探索に適した形式に変換します。
   • まず、countcase を呼び出して定数ケースの数を数えます。
   • Ncase (定数4) よりもケースの数が少ない場合は、二分探索のオーバーヘッドが線形探索のメリットを上回る可能性があるため、最適化を行わず N (NULL) を返します。
   • ケースの数が Ncase 以上の場合、Case 構造体のリンクリストを構築し、各 case ステートメントのノードを格納します。
   • csort 関数を呼び出して、この Case リストを casecmp 関数を使ってソートします。二分探索はソートされたデータに対してのみ機能するため、このステップは不可欠です。
   • ソートされたリストとケースの数、switch 式の評価結果を保持する変数 (name) を constsw 関数に渡し、二分探索ツリーのASTを構築させます。

3. Case 構造体と関連ヘルパー関数:

   • Case 構造体は、switch の各 case ステートメントの情報を保持するために導入されました。具体的には、Node* node (元の case ステートメントのASTノード) と Case* link (リンクリストのためのポインタ) を持ちます。
   • iscaseconst(Node *t): 与えられたノードが定数リテラル（浮動小数点、整数、文字列）である case 値を表しているかどうかをチェックします。
   • countcase(Node *t, Iter save): switch 文内の定数 case ステートメントの数を数えます。Iter はイテレータのコピーであるため、元のイテレータの状態は変更されません。

4. csort と casecmp によるソート:

   • csort(Case *l, int(*f)(Case*, Case*)) は、リンクリストをソートするためのマージソートの実装です。これは再帰的にリストを分割し、ソートされたサブリストをマージすることで、効率的にリスト全体をソートします。
   • casecmp(Case *c1, Case *c2) は、2つの Case 構造体に含まれる定数値を比較するための関数です。whatis 関数を使って定数の型（浮動小数点、整数、文字列）を識別し、それぞれの型に応じた比較関数（mpcmpfltflt, mpcmpfixfix, cmpslit）を呼び出します。これにより、switch ケースが正しくソートされます。

5. constsw による二分探索ツリーの構築:

   • constsw(Case *c0, int ncase, Node *name) は、ソートされた Case リストから、二分探索のロジックを表現するASTを再帰的に構築します。
   • ncase < Ncase (ケース数が4未満) の場合、線形探索（一連の OIF ノード）を生成します。これは、二分探索のオーバーヘッドが小さいケースでは不利になるためです。
   • ケース数が十分にある場合、リストの中央の要素を見つけます。
   • 中央の要素を基準に、OLE (less than or equal) 演算子を使った OIF ノードを生成します。
     • a->ntest = nod(OLE, name, c->node->left); は、「name の値が中央の case 値以下であるか？」をテストします。
     • a->nbody = constsw(c0, n+1, name); は、テストが真の場合（値が中央以下の場合）に、リストの左半分（中央の要素を含む）に対して再帰的に constsw を呼び出します。
     • a->nelse = constsw(c->link, ncase-n-1, name); は、テストが偽の場合（値が中央より大きい場合）に、リストの右半分（中央の要素を含まない）に対して再帰的に constsw を呼び出します。
   • この再帰的なプロセスにより、最終的に二分探索ツリーの構造がASTとして構築されます。

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

このコミットの主要な変更は、src/cmd/gc/swt.c ファイルに集中しています。

1. binarysw 関数の前方宣言の追加:

   +Node*	binarysw(Node *t, Iter *save, Node *name);
   

   これにより、prepsw 関数から binarysw を呼び出すことが可能になります。

2. prepsw 関数内の変更:

   --- a/src/cmd/gc/swt.c
   +++ b/src/cmd/gc/swt.c
   @@ -309,21 +311,29 @@ loop:
    	\tgoto loop;
    	}\
    \
   -\ta = nod(OIF, N, N);\
   -\ta->nbody = t->right;\t\t\t\t// then goto l
   +\ta = binarysw(t, &save, name);\
   +\tif(a != N)\
   +\t\tbreak;\
   +\
   +\ta = nod(OIF, N, N);\
    \tswitch(arg) {
    \tdefault:
    \t\t// not bool const
   +\t\ta = nod(OIF, N, N);\
    \t\ta->ntest = nod(OEQ, name, t->left);\t// if name == val
   +\t\ta->nbody = t->right;\t\t\t// then goto l
    \t\tbreak;
    \
    \tcase Strue:
   +\t\ta = nod(OIF, N, N);\
    \t\ta->ntest = t->left;\t\t\t// if val
   +\t\ta->nbody = t->right;\t\t\t// then goto l
    \t\tbreak;
    \
    \tcase Sfalse:
   +\t\ta = nod(OIF, N, N);\
    \t\ta->ntest = nod(ONOT, t->left, N);\t// if !val
   +\t\ta->nbody = t->right;\t\t\t// then goto l
    \t\tbreak;
    \t}
    \tcas = list(cas, a);
   

   binarysw の呼び出しが追加され、その結果が利用されるようになりました。これにより、定数ケースの処理が分岐します。

3. 新しい構造体と定数の定義:

   +enum
   +{
   +\tNcase	= 4,\t// needed to binary search
   +};
   +\
   +typedef	struct	Case	Case;
   +struct	Case
   +{
   +\tNode*	node;\t\t// points at case statement
   +\tCase*	link;\t\t// linked list to link
   +};
   +#define	C	((Case*)nil)
   

   二分探索の閾値 Ncase と、ケース情報を保持する Case 構造体が定義されています。

4. 新しい関数の追加:

   • iscaseconst(Node *t)
   • countcase(Node *t, Iter save)
   • csort(Case *l, int(*f)(Case*, Case*))
   • casecmp(Case *c1, Case *c2)
   • constsw(Case *c0, int ncase, Node *name)
   • binarysw(Node *t, Iter *save, Node *name)

   これらの関数が swt.c の末尾に追加され、二分探索ロジックの全体を構成しています。

コアとなるコードの解説

このコミットの核となるのは、binarysw、csort、constsw の3つの関数です。

1. binarysw 関数:

   Node*
   binarysw(Node *t, Iter *save, Node *name)
   {
       Case *c, *c1;
       int i, ncase;
       Node *a;
   
       ncase = countcase(t, *save); // 定数ケースの数を数える
       if(ncase < Ncase) // ケース数が閾値未満なら最適化しない
           return N;
   
       c = C;
       // ケースノードをCase構造体のリンクリストに格納
       for(i=1; i<ncase; i++) {
           c1 = mal(sizeof(*c1));
           c1->link = c;
           c1->node = t;
           c = c1;
           t = listnext(save); // イテレータを進める
       }
       // 最後のケースをリストに追加
       c1 = mal(sizeof(*c1));
       c1->link = c;
       c1->node = t;
       c = c1;
   
       c = csort(c, casecmp); // ケースリストをソート
       a = constsw(c, ncase, name); // ソートされたリストから二分探索ツリーを構築
       return a;
   }
   

   この関数は、switch 文の定数ケースを二分探索可能な形式に変換するエントリポイントです。まずケース数をチェックし、十分な数があれば、各ケースを Case 構造体のリンクリストに格納します。その後、csort でリストをソートし、最終的に constsw を呼び出して二分探索のASTを生成します。

2. csort 関数 (マージソート):

   Case*
   csort(Case *l, int(*f)(Case*, Case*))
   {
       // ... (マージソートの実装) ...
   }
   

   これは、標準的なリンクリストに対するマージソートの実装です。casecmp 関数を比較関数として使用し、Case 構造体のリンクリストをソートします。二分探索を行うためには、対象となるデータ（ここでは case の値）がソートされている必要があります。

3. constsw 関数 (二分探索ツリー構築):

   Node*
   constsw(Case *c0, int ncase, Node *name)
   {
       Node *cas, *a;
       Case *c;
       int i, n;
   
       if(ncase < Ncase) { // 小さい数なら線形探索
           cas = N;
           for(i=0; i<ncase; i++) {
               a = nod(OIF, N, N);
               a->ntest = nod(OEQ, name, c0->node->left); // name == val
               a->nbody = c0->node->right; // then goto l
               cas = list(cas, a);
               c0 = c0->link;
           }
           return rev(cas); // リストを逆順にして返す
       }
   
       // 中央の要素を見つける
       c = c0;
       n = ncase>>1; // ncase / 2
       for(i=0; i<n; i++)
           c = c->link;
   
       a = nod(OIF, N, N);
       a->ntest = nod(OLE, name, c->node->left); // if name <= center_val
       a->nbody = constsw(c0, n+1, name); // 左半分（中央含む）を再帰的に探索
       a->nelse = constsw(c->link, ncase-n-1, name); // 右半分（中央含まない）を再帰的に探索
       return a;
   }
   

   この関数は、ソートされた Case リストを受け取り、再帰的に二分探索のASTを構築します。

   • ベースケースとして、ケース数が Ncase 未満の場合は、従来の線形探索（OEQ を使った一連の if 文）を生成します。
   • それ以外の場合、リストの中央の case を見つけます。
   • OLE (Less than or Equal) 演算子を使って、switch 式の値が中央の case 値以下であるかをテストする if ノードを生成します。
   • テストが真の場合（値が中央以下）、リストの左半分（中央の要素を含む）に対して再帰的に constsw を呼び出し、その結果を if ノードの nbody (then ブロック) に設定します。
   • テストが偽の場合（値が中央より大きい）、リストの右半分（中央の要素を含まない）に対して再帰的に constsw を呼び出し、その結果を if ノードの nelse (else ブロック) に設定します。
   • この再帰により、switch 文は効率的な二分探索ツリーに変換されます。

これらの変更により、Goコンパイラは、多数の定数 case を持つ switch ステートメントを、線形探索よりもはるかに高速な二分探索にコンパイルできるようになり、Goプログラムの実行時パフォーマンスが向上しました。

関連リンク

• Go言語の switch ステートメントに関する公式ドキュメント: https://go.dev/ref/spec#Switch_statements
• Goコンパイラのソースコードリポジトリ: https://github.com/golang/go
• 二分探索アルゴリズムに関する一般的な情報: https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

参考にした情報源リンク

• Goコンパイラのソースコード (src/cmd/gc/swt.c)
• Go言語の仕様書
• 二分探索アルゴリズムに関する一般的な知識
• Go言語のコンパイラ最適化に関する一般的な議論 (Web検索)
• Go言語の初期のコミット履歴 (GitHub)