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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ (exp/ssa) における、パッケージのビルドフェーズの並列化に関するものです。具体的には、複数のパッケージのSSA構築処理を並行して実行することで、コンパイル時間の短縮を図っています。

コミット

commit 3fc8cd054a4dd1bb4eb60da76a595cd509bb20ac
Author: Alan Donovan <adonovan@google.com>
Date:   Wed Feb 27 10:26:24 2013 -0500

    exp/ssa: perform all packages' BUILD phases in parallel.
    
    Details:
    - move Builder.nTo1Vars into package => thread-safe.
    - add BuildSerially builder mode flag to disable concurrency.
    - add Builder.BuildAllPackages method.
    
    Benchmark: BuildAllPackages for $GOROOT/test/append.go drops
    to 83ms from 190ms (GOMAXPROCS=8).
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/7371051

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

https://github.com/golang/go/commit/3fc8cd054a4dd1bb4eb60da76a595cd509bb20ac

元コミット内容

exp/ssa: perform all packages' BUILD phases in parallel.

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージにおいて、全てのパッケージのBUILDフェーズを並列で実行するように変更します。

主な変更点：

• Builder.nTo1Vars をパッケージレベルに移動し、スレッドセーフにする。
• 並行処理を無効にするための BuildSerially ビルダーモードフラグを追加する。
• 全てのパッケージをビルドするための Builder.BuildAllPackages メソッドを追加する。

ベンチマーク結果： $GOROOT/test/append.go の BuildAllPackages において、GOMAXPROCS=8 の場合、処理時間が190msから83msに短縮された。

変更の背景

Go言語のコンパイラは、ソースコードを中間表現に変換する過程でSSA (Static Single Assignment) 形式を利用します。このSSA形式の構築プロセスは、特に大規模なプロジェクトや多数のパッケージを含む場合に、コンパイル時間のボトルネックとなる可能性があります。

このコミット以前は、SSAのBUILDフェーズ（ASTからSSA命令を生成する段階）がパッケージごとに逐次的に実行されていました。しかし、異なるパッケージ間のSSA構築は、依存関係が適切に管理されていれば、本質的に並列化が可能です。

この変更の主な背景は、SSA構築プロセスのパフォーマンスを向上させ、コンパイル時間を短縮することにあります。特に、マルチコアプロセッサの恩恵を最大限に受けるために、並列処理を導入することが目標とされました。

また、並列化を安全に行うためには、共有されるデータ構造に対するスレッドセーフティの確保が不可欠でした。特に Builder.nTo1Vars のような、複数のゴルーチンからアクセスされる可能性のあるデータ構造は、競合状態を避けるためにパッケージレベルに移動し、各パッケージが自身の状態を持つように変更する必要がありました。

前提知識の解説

1. SSA (Static Single Assignment) 形式

SSA (Static Single Assignment) は、コンパイラ最適化の中間表現で広く用いられる形式です。SSA形式では、各変数が一度だけ代入されるという特性を持ちます。これにより、データフロー解析や最適化が容易になります。

• 特性:
  • 各変数は一度だけ定義（代入）される。
  • 複数の制御フローパスが合流する点（例: if文の終わり、ループの終わり）では、φ (phi) 関数と呼ばれる特殊な命令が導入され、異なるパスから来る同じ変数の値を結合する。
• 利点:
  • データフロー解析が単純化される。
  • 共通部分式除去、定数伝播、デッドコード除去などの最適化が効率的に行える。
  • レジスタ割り当てが容易になる。

Goコンパイラでは、AST (Abstract Syntax Tree) からSSA形式の中間表現を生成し、その上で様々な最適化を適用してから最終的な機械語コードを生成します。exp/ssa パッケージは、このSSA形式の構築と操作を行うための実験的なライブラリでした。

2. Go言語のコンカレンシーモデル

Go言語は、軽量なスレッドである「ゴルーチン (goroutine)」と、ゴルーチン間の通信のための「チャネル (channel)」を核とした強力なコンカレンシーモデルを提供します。

• ゴルーチン (goroutine):
  • go キーワードを使って関数呼び出しの前に置くことで、その関数を新しいゴルーチンとして並行実行させることができます。
  • OSのスレッドよりもはるかに軽量で、数千、数万のゴルーチンを同時に実行することが可能です。
  • Goランタイムのスケジューラが、利用可能なOSスレッドにゴルーチンをマッピングし、効率的に実行を管理します。
• sync パッケージ:
  • sync.WaitGroup: 複数のゴルーチンの完了を待つためのメカニズムを提供します。Add でカウンタを増やし、Done で減らし、Wait でカウンタがゼロになるまでブロックします。
  • sync.Mutex: 相互排他ロックを提供し、共有リソースへのアクセスを同期します。
• sync/atomic パッケージ:
  • アトミック操作（不可分操作）を提供します。これは、複数のゴルーチンから同時にアクセスされても、操作が中断されずに完全に実行されることを保証する低レベルのプリミティブです。
  • 例: atomic.CompareAndSwapInt32 は、指定されたメモリ位置の値が期待値と一致する場合にのみ、新しい値に更新します。これは、ロックを使わずにスレッドセーフなカウンタやフラグを実装するのに役立ちます。

3. Goのパッケージビルドプロセス

Goのビルドプロセスでは、ソースファイルがパッケージにまとめられ、各パッケージが個別にコンパイルされます。パッケージ間の依存関係は、インポートパスによって解決されます。

• AST (Abstract Syntax Tree): ソースコードはまずASTにパースされます。
• 型チェック: go/types パッケージなどを用いて、ASTに対して型チェックが行われます。
• SSA構築: 型チェックされたASTからSSA形式の中間表現が構築されます。この段階が本コミットの対象です。
• 最適化: SSA形式に対して様々な最適化が適用されます。
• コード生成: 最適化されたSSAから最終的な機械語コードが生成されます。

このコミットは、特に「SSA構築」フェーズにおいて、複数のパッケージの処理を並列化することで、全体のビルド時間を短縮しようとしています。

技術的詳細

このコミットの核心は、GoコンパイラのSSA構築フェーズにおけるパッケージごとの並列処理の導入です。これまでの逐次処理から、sync.WaitGroup とゴルーチンを用いた並列処理へと移行することで、マルチコア環境でのパフォーマンス向上を目指しています。

1. Builder.nTo1Vars の移動とスレッドセーフティ

• 変更前: Builder 構造体内に nTo1Vars map[*ast.ValueSpec]bool が存在していました。これは、var x, _, y = f() のような多値代入（n:1 代入）において、ValueSpec が既にビルドされたかどうかを追跡するためのマップでした。
• 問題点: Builder はSSA構築の全体を管理するオブジェクトであり、複数のパッケージを並列でビルドする場合、異なるゴルーチンが同じ Builder.nTo1Vars マップに同時にアクセスし、競合状態（race condition）を引き起こす可能性がありました。コメントにも [not threadsafe] と明記されていました。
• 変更後: nTo1Vars マップは Package 構造体 (src/pkg/exp/ssa/ssa.go で定義) の内部に移動されました。

  // src/pkg/exp/ssa/ssa.go
  type Package struct {
      // ...
      nTo1Vars map[*ast.ValueSpec]bool // set of n:1 ValueSpecs already built
  }
  

  これにより、各パッケージが自身の nTo1Vars マップを持つことになり、異なるパッケージのビルドが並列で実行されても、それぞれのゴルーチンが独立したマップにアクセスするため、スレッドセーフティが確保されます。builder.go 内の globalValueSpec メソッドでのアクセスも b.nTo1Vars[spec] から init.Pkg.nTo1Vars[spec] に変更されています。

2. BuildSerially フラグの追加

• BuilderMode (src/pkg/exp/ssa/builder.go) に BuildSerially という新しいフラグが追加されました。

  // src/pkg/exp/ssa/builder.go
  const (
      // ...
      BuildSerially // Build packages serially, not in parallel.
  )
  

• このフラグは、デバッグや特定のテストシナリオのために、並列ビルドを無効にして逐次ビルドに戻すことを可能にします。ssadump.go のコマンドラインオプションにも -build=L として追加され、ユーザーがこの動作を制御できるようになっています。

3. Builder.BuildAllPackages メソッドの導入

• 新しいメソッド BuildAllPackages() が Builder 構造体に追加されました。

  // src/pkg/exp/ssa/builder.go
  func (b *Builder) BuildAllPackages() {
      var wg sync.WaitGroup
      for _, p := range b.Prog.Packages {
          if b.mode&BuildSerially != 0 {
              b.BuildPackage(p) // 逐次ビルド
          } else {
              wg.Add(1)
              go func(p *Package) {
                  b.BuildPackage(p) // 並列ビルド
                  wg.Done()
              }(p)
          }
      }
      wg.Wait() // 全てのゴルーチンの完了を待つ
  }
  

• このメソッドは、Builder が認識している全てのパッケージ (b.Prog.Packages) をループし、各パッケージに対して BuildPackage を呼び出します。
• BuildSerially フラグが設定されていない場合、各 BuildPackage 呼び出しは新しいゴルーチンで実行され、sync.WaitGroup を使用して全ての並列ビルドが完了するのを待ちます。これにより、パッケージのSSA構築が並列で実行されます。

4. Package.started フラグとアトミック操作

• Package 構造体には、started int32 というフィールドが追加されました。

  // src/pkg/exp/ssa/ssa.go
  type Package struct {
      // ...
      started  int32                   // atomically tested and set at start of build phase
      // ...
  }
  

• Builder.BuildPackage(p *Package) メソッドの冒頭で、atomic.CompareAndSwapInt32(&p.started, 0, 1) が使用されています。

  // src/pkg/exp/ssa/builder.go
  func (b *Builder) BuildPackage(p *Package) {
      if !atomic.CompareAndSwapInt32(&p.started, 0, 1) {
          return // already started
      }
      // ...
  }
  

• これは、BuildPackage が複数のゴルーチンから同時に呼び出される可能性があるため、パッケージのビルドが一度だけ開始されることを保証するためのアトミックなチェックです。started が0（未開始）の場合にのみ1（開始済み）に設定し、ビルド処理を続行します。既に1になっている場合は、他のゴルーチンが既にビルドを開始しているため、すぐにリターンします。これにより、二重のビルドを防ぎ、並列処理の安全性を高めます。

5. BuildPackage 内の依存関係処理の変更

• 変更前は、BuildPackage の中でインポートされたパッケージ (p2) に対して b.BuildPackage(p2) を呼び出し、そのパッケージのビルドが完了するのを待っていました。
• 変更後、この明示的な逐次的な依存パッケージのビルド呼び出しが削除されました。

  --- a/src/pkg/exp/ssa/builder.go
  +++ b/src/pkg/exp/ssa/builder.go
  @@ -2760,12 +2765,6 @@ func (b *Builder) BuildPackage(p *Package) {
   	if p2 == nil {
   		panic("Building " + p.Name() + ": CreatePackage has not been called for package " + name)
   	}
  -	// TODO(adonovan): opt: BuildPackage should be
  -	// package-local, so we can run it for all packages in
  -	// parallel once CreatePackage has been called for all
  -	// prerequisites.  Until then, ensure all import
  -	// dependencies are completely built before we are.
  -	b.BuildPackage(p2)
   
   	var v Call
   	v.Func = p2.Init
  

• これは、BuildAllPackages が全てのパッケージを並列で開始するため、個々の BuildPackage が依存パッケージのビルド完了を待つ必要がなくなったことを意味します。依存関係は、BuildAllPackages の外側で、CreatePackage フェーズで適切に解決されているか、あるいはSSA構築の性質上、後続のフェーズで解決されることが期待されます。この変更により、真の並列実行が可能になります。

6. その他の変更点

• Builder.lookup メソッドが from *Package 引数を取るようになり、nTo1Vars の移動と同様に、パッケージ固有のコンテキストでグローバルオブジェクトのルックアップとビルドを行うようになりました。
• demoteSelector, fieldAddr, fieldExpr など、ASTのセレクタ式をSSAに変換するロジックが変更されています。特に demoteSelector は、プロモートされたフィールドの選択を解除し、明示的なセレクタ式に変換する役割を担います。この変更は、Builder.types マップへのアクセスがスレッドセーフではないというコメントを残しつつも、並列化の文脈で安全性を確保するためのステップとして行われています。
• ログ出力 (fmt.Fprintln(os.Stderr, ...) ) の形式が変更され、defer logStack のような複雑なロギングメカニズムが削除されています。これは、並列実行環境でのロギングの複雑さを軽減するためと考えられます。
• BuildPackage の最後に p.files = nil と p.nTo1Vars = nil が追加され、ビルドが完了したパッケージから一時的なデータ構造を解放しています。

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

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

1. src/pkg/exp/ssa/builder.go:

   • Builder 構造体から nTo1Vars フィールドが削除されました。
   • BuilderMode に BuildSerially フラグが追加されました。
   • BuildAllPackages() メソッドが追加され、パッケージの並列ビルドをオーケストレーションします。
   • BuildPackage(p *Package) メソッドが変更され、atomic.CompareAndSwapInt32 を使用してパッケージのビルドが一度だけ行われることを保証します。また、内部での依存パッケージの逐次ビルド呼び出しが削除されました。
   • lookup メソッドのシグネチャが変更され、from *Package 引数が追加されました。
   • globalValueSpec メソッドで b.nTo1Vars ではなく init.Pkg.nTo1Vars を使用するように変更されました。
   • demoteSelector, fieldAddr, fieldExpr などのフィールドアクセス関連のロジックが変更されました。

2. src/pkg/exp/ssa/ssa.go:

   • Package 構造体に started int32 と nTo1Vars map[*ast.ValueSpec]bool フィールドが追加されました。

3. src/pkg/exp/ssa/interp/interp_test.go:

   • テストコード内で b.BuildPackage(mainpkg) の代わりに b.BuildAllPackages() が呼び出されるように変更されました。これにより、テストが新しい並列ビルドパスを使用するようになります。

4. src/pkg/exp/ssa/ssadump.go:

   • コマンドラインオプションに -build=L が追加され、BuildSerially モードを有効にできるようになりました。

コアとなるコードの解説

src/pkg/exp/ssa/builder.go の BuildAllPackages メソッド

func (b *Builder) BuildAllPackages() {
	var wg sync.WaitGroup // 全てのゴルーチンの完了を待つためのWaitGroup
	for _, p := range b.Prog.Packages { // プログラム内の全てのパッケージをイテレート
		if b.mode&BuildSerially != 0 { // BuildSerially フラグが設定されているかチェック
			b.BuildPackage(p) // 逐次ビルドモードの場合、現在のゴルーチンでBuildPackageを呼び出す
		} else {
			wg.Add(1) // 並列ビルドモードの場合、WaitGroupのカウンタをインクリメント
			go func(p *Package) { // 新しいゴルーチンを起動
				b.BuildPackage(p) // ゴルーチン内でBuildPackageを呼び出す
				wg.Done()         // BuildPackageが完了したらWaitGroupのカウンタをデクリメント
			}(p) // ループ変数をゴルーチンに渡す（クロージャのキャプチャを防ぐため）
		}
	}
	wg.Wait() // 全てのゴルーチンがwg.Done()を呼び出すまで待機
}

このメソッドは、SSA構築の並列化の中心です。b.Prog.Packages に含まれる全てのパッケージに対して、BuildSerially フラグが設定されていなければ、それぞれを新しいゴルーチンで BuildPackage を呼び出します。sync.WaitGroup を使用することで、BuildAllPackages は全ての並列ビルドが完了するまでブロックし、呼び出し元に制御を戻します。

src/pkg/exp/ssa/builder.go の BuildPackage メソッド（変更部分）

func (b *Builder) BuildPackage(p *Package) {
	// アトミック操作でパッケージのビルドが一度だけ開始されることを保証
	if !atomic.CompareAndSwapInt32(&p.started, 0, 1) {
		return // 既に開始されている場合は何もしない
	}
	// ... (既存のビルドロジック) ...

	// 以前存在した、インポートされたパッケージの逐次ビルド呼び出しが削除された
	// b.BuildPackage(p2) のような行がなくなった

	// ビルド完了後に一時的なデータ構造を解放
	p.files = nil
	p.nTo1Vars = nil
}

BuildPackage メソッドは、パッケージのSSA構築の具体的な処理を行います。このコミットで最も重要な変更は、atomic.CompareAndSwapInt32 を使用して p.started フラグをチェック・設定する部分です。これにより、複数のゴルーチンが同時に同じパッケージのビルドを開始しようとしても、実際にビルドが実行されるのは一度だけであることが保証されます。また、以前はここで依存パッケージのビルドを逐次的にトリガーしていましたが、BuildAllPackages が全てのパッケージを並列で開始するようになったため、そのロジックは不要となり削除されました。最後に、ビルド完了後に p.files と p.nTo1Vars を nil に設定し、メモリを解放しています。

src/pkg/exp/ssa/ssa.go の Package 構造体

type Package struct {
	// ...
	started  int32                   // ビルドフェーズ開始時にアトミックにテスト・設定される
	files    []*ast.File             // パッケージのASTファイル（一時的なデータ）
	nTo1Vars map[*ast.ValueSpec]bool // n:1 ValueSpecが既にビルドされたかどうかのセット
}

Package 構造体に started と nTo1Vars が追加されたことで、各パッケージが自身のビルド状態と、多値代入の追跡情報を独立して持つことができるようになりました。これにより、Builder 全体で共有されていた nTo1Vars がパッケージごとに分離され、並列ビルド時の競合状態が解消されました。

これらの変更により、GoのSSA構築プロセスは、マルチコア環境でより効率的に動作するようになり、コンパイル時間の短縮に貢献しています。

関連リンク

• Go Gerrit Change-ID: https://golang.org/cl/7371051 - このコミットの元のGerritレビューページ。詳細な議論やレビューコメントが確認できます。

参考にした情報源リンク

• Go言語公式ドキュメント: Go言語のコンカレンシーモデル（ゴルーチン、チャネル、syncパッケージ）に関する基本的な情報。
• SSA (Static Single Assignment) 形式に関する資料: コンパイラ最適化やSSA形式の概念に関する一般的な情報源。
• Goコンパイラの内部構造に関する記事やプレゼンテーション: GoコンパイラのビルドプロセスやSSA生成に関するより詳細な技術情報。
• Goのsyncおよびsync/atomicパッケージのドキュメント: 並列処理とスレッドセーフティに関する具体的なAPIの使用方法。