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

このコミットは、Goコンパイラのバックエンドにおける最適化に関するものです。具体的には、cmd/5g (ARM), cmd/6g (x86-64), cmd/8g (x86) の各アーキテクチャ向けコンパイラにおいて、コード生成後の最適化フェーズ（peephole optimizer）で利用されるデータ構造の初期化方法を変更することで、コンパイル速度の向上を図っています。従来のリンクリストを辿る初期化処理をmemsetによる一括初期化に置き換えることで、go install -a stdコマンドの実行時間を約10%削減することに成功しています。

コミット

cmd/5g, cmd/6g, cmd/8g: faster compilation Replace linked list walk with memset. This reduces CPU time taken by 'go install -a std' by ~10%.

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

https://github.com/golang/go/commit/06e686def67297a08ecb75e3543fde1284c1ee61

元コミット内容

commit 06e686def67297a08ecb75e3543fde1284c1ee61
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed Aug 21 14:20:28 2013 +0400

    cmd/5g, cmd/6g, cmd/8g: faster compilation
    Replace linked list walk with memset.
    This reduces CPU time taken by 'go install -a std' by ~10%.
    Before:
    real            user            sys
    0m23.561s       0m16.625s       0m5.848s
    0m23.766s       0m16.624s       0m5.846s
    0m23.742s       0m16.621s       0m5.868s
    after:
    0m22.714s       0m14.858s       0m6.138s
    0m22.644s       0m14.875s       0m6.120s
    0m22.604s       0m14.854s       0m6.081s
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/13084043

変更の背景

Goコンパイラは、ソースコードを機械語に変換する過程で様々な最適化を行います。その中でも、peephole optimizer（ピーフホール最適化）は、生成された機械語コードの小さな連続した部分（「ピーフホール」と呼ばれる）を検査し、より効率的な命令シーケンスに置き換えることで、コードの品質と実行速度を向上させる役割を担っています。

このコミットの背景には、コンパイル時間の最適化という明確な目標がありました。Go言語は高速なコンパイルを特徴の一つとしていますが、大規模なプロジェクトや標準ライブラリ全体をコンパイルする際には、わずかな改善でも全体的な開発体験に大きな影響を与えます。

コミットメッセージに示されているように、go install -a stdコマンド（標準ライブラリ全体を再コンパイルしてインストールするコマンド）の実行時間が約10%削減されたことは、この最適化が非常に効果的であったことを示しています。これは、コンパイラのボトルネックとなっていた部分を特定し、より効率的なアルゴリズムに置き換えることで達成されました。具体的には、peephole optimizer内で使用されるactiveフラグの初期化処理が、リンクリストの走査からmemsetによるメモリ一括クリアに変更されたことが、この性能向上に寄与しています。

前提知識の解説

Goコンパイラ (cmd/5g, cmd/6g, cmd/8g)

Goコンパイラは、Go言語のソースコードを各アーキテクチャの機械語に変換するツールです。cmd/5gはARMアーキテクチャ、cmd/6gはx86-64アーキテクチャ、cmd/8gはx86アーキテクチャ向けのコンパイラを指します。これらはGoの初期のコンパイラであり、C言語で記述されていました。

Peephole Optimizer (ピーフホール最適化)

peephole optimizerは、コンパイラのバックエンドで行われる最適化手法の一つです。コード生成の最終段階で、生成された機械語命令列を小さな「窓（peephole）」を通して見て、非効率な命令シーケンスをより効率的なものに置き換えます。例えば、冗長なロード/ストア命令の削除、不要なジャンプ命令の削除、より短い命令への置き換えなどを行います。

この最適化は、通常、命令の局所的なパターンに焦点を当てるため、コンパイラの他の最適化フェーズ（例えば、レジスタ割り当てやループ最適化など）とは独立して適用されることが多いです。

Flow構造体とactiveフラグ

Goコンパイラのpeephole optimizerでは、プログラムの制御フローグラフ（Control Flow Graph, CFG）を表現するためにFlowのようなデータ構造が使用されます。Flow構造体は、プログラムの各命令（Prog）間の関係や、最適化の過程で必要となる様々な情報を保持します。

activeフラグは、peephole optimizerが特定の最適化（例えば、冗長なコピーの伝播 copyprop）を行う際に、既に処理済みであるか、または現在処理中であるかをマークするために使用されるフラグです。これにより、無限ループを防いだり、重複した処理を避けたりします。最適化の各イテレーションの開始時には、このactiveフラグをリセット（通常は0に設定）する必要があります。

リンクリストの走査とmemset

• リンクリストの走査 (Linked list walk): 従来のactiveフラグのリセット方法では、Flow構造体のリンクリストを先頭から順に辿り、各Flow要素のactiveフィールドを個別に0に設定していました。これは、リストの要素数に比例して時間がかかる処理です。
• memset: memsetはC言語の標準ライブラリ関数で、指定されたメモリ領域を特定の値で埋めるために使用されます。このコミットでは、activeフラグを保持する配列（uchar *active）を導入し、その配列全体をmemsetを使って一括で0に初期化するように変更されました。memsetは通常、非常に高速に動作し、特に大きなメモリブロックを初期化する場合には、個々の要素をループで設定するよりもはるかに効率的です。

技術的詳細

このコミットの核心は、peephole optimizerのcopyprop関数内で使用されるactiveフラグの初期化方法の変更です。

従来のcopyprop関数では、Flow構造体のリンクリストをfor(r=g->start; r!=nil; r=r->link)のように走査し、各r->active = 0;と設定していました。これは、Flow構造体の数が多くなると、その走査と個別の書き込みに時間がかかるボトルネックとなっていました。

新しいアプローチでは、activeフラグをFlow構造体から分離し、uchar *activeという独立した配列として管理するように変更されました。この配列のサイズは、制御フローグラフのノード数（g->num）に基づいて動的に確保されます（reallocを使用）。そして、このactive配列の初期化には、memset(active, 0, g->num);が使用されます。

さらに、Flow構造体にはactiveフィールドが残されていますが、これはactive配列のインデックスとして利用されるようになりました。具体的には、peep関数の冒頭で、リンクリストを一度走査し、各Flow要素のr->activeにその要素のインデックス（t）を割り当てています。これにより、copy1関数内でr->activeを参照する際に、active[r->active]という形でactive配列の対応するフラグにアクセスできるようになります。

この変更により、copypropが呼び出されるたびに、activeフラグのリセットがリンクリストの走査ではなく、高速なmemsetによって行われるようになり、コンパイル時間の短縮に貢献しました。

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

変更はsrc/cmd/5g/peep.c, src/cmd/6g/peep.c, src/cmd/8g/peep.cの3つのファイルに共通して適用されています。

peep関数内での変更

// Before: (no explicit initialization of r->active here)
// After:
+	for(r=g->start, t=0; r!=nil; r=r->link, t++)
+		r->active = t;

peep関数の冒頭で、Flowリンクリストを一度走査し、各Flow要素のactiveフィールドに、その要素のリスト内でのインデックスを割り当てています。これにより、Flow構造体のactiveフィールドが、active配列へのオフセットとして機能するようになります。

グローバル変数/静的変数の追加

+static uchar *active;
+static int nactive;

activeフラグを保持するためのuchar型ポインタactiveと、その配列の現在のサイズを保持するnactiveが追加されました。これらはファイルスコープの静的変数として宣言されています。

copyprop関数内での変更

// Before:
// 	for(r=g->start; r!=nil; r=r->link)
// 		r->active = 0;
// After:
+	if(nactive < g->num) {
+		nactive = g->num;
+		active = realloc(active, g->num);
+	}
+ 	memset(active, 0, g->num);

copyprop関数内で、active配列のサイズが現在の制御フローグラフのノード数（g->num）よりも小さい場合、reallocを使って配列を拡張します。その後、memsetを使ってactive配列全体を0で初期化します。これにより、リンクリストの走査が不要になりました。

copy1関数内での変更

// Before:
// 	if(r->active) {
// After:
+	if(active[r->active]) {

// Before:
// 	r->active = 1;
// After:
+	active[r->active] = 1;

copy1関数内でactiveフラグを参照・設定する箇所が、r->activeからactive[r->active]に変更されました。これは、r->activeがもはやブール値のフラグではなく、active配列へのインデックスとして機能するためです。

コアとなるコードの解説

このコミットの主要な変更点は、copyprop関数におけるactiveフラグの初期化ロジックです。

1. Flow構造体へのインデックス割り当て: peep関数の冒頭で、一度だけFlowリンクリストを走査し、各Flowノードに一意のインデックスを割り当て、それをr->activeに格納します。このr->activeは、もはやブール値のフラグではなく、active配列へのオフセットとして機能します。この処理は、peephole optimizerの開始時に一度だけ行われます。

2. active配列の動的確保とmemsetによる初期化: copyprop関数が呼び出されるたびに、まずactive配列の現在のサイズ（nactive）が、現在の制御フローグラフのノード数（g->num）よりも小さいかどうかをチェックします。 if(nactive < g->num): もしactive配列が小さすぎる場合、reallocを使ってg->numバイトのメモリを確保し、nactiveを更新します。これにより、active配列は常に現在のグラフのノード数をカバーできる十分なサイズを持つことが保証されます。 memset(active, 0, g->num);: その後、memset関数を使って、active配列の先頭からg->numバイト分をすべて0で埋めます。これにより、すべてのactiveフラグが効率的にリセットされます。memsetは通常、アセンブリ言語で最適化されており、CPUのキャッシュラインを効率的に利用するため、リンクリストを個別に走査するよりもはるかに高速です。

3. activeフラグへのアクセス方法の変更: copy1関数内では、activeフラグのチェックと設定がif(r->active)からif(active[r->active])へ、そしてr->active = 1;からactive[r->active] = 1;へと変更されました。これにより、Flow構造体内のactiveフィールドが指すインデックスを使って、グローバルなactive配列の対応する要素にアクセスするようになります。

この一連の変更により、peephole optimizerの重要な部分であるactiveフラグのリセット処理が大幅に高速化され、結果としてGoコンパイラ全体のコンパイル時間が短縮されました。これは、データ構造の選択とアルゴリズムの最適化が、ソフトウェアの性能に大きな影響を与える良い例と言えます。

関連リンク

• Go言語の公式リポジトリ: https://github.com/golang/go
• Goのコンパイラに関するドキュメント (古い情報も含む): https://golang.org/doc/install/source
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/
  • このコミットのGerritチェンジリスト: https://golang.org/cl/13084043

参考にした情報源リンク

• memsetに関するC言語のドキュメント: https://www.cplusplus.com/reference/cstring/memset/
• コンパイラ最適化に関する一般的な情報源 (例: Dragon Book - Compilers: Principles, Techniques, and Tools)
• Go言語のコンパイラ設計に関する議論やドキュメント (Goの公式ブログやデザインドキュメントなど)
• Goの初期のコンパイラ（cmd/5g, 6g, 8g）のソースコード
• 制御フローグラフ (CFG) に関する情報
• Peephole Optimizationに関する情報
• reallocに関するC言語のドキュメント: https://www.cplusplus.com/reference/cstdlib/realloc/
• Goのコンパイラ開発者コミュニティの議論 (golang-devメーリングリストなど)
• GoのIssue Tracker (Goのバグや機能リクエストが管理されている場所)
• Goのソースコード内のコメントやREADMEファイル
• Goの歴史的なコミットログ