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

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

コミット

commit f056daf075f303918343fd79af7ee0bfdcf6738e
Author: Carl Shapiro <cshapiro@google.com>
Date:   Thu Dec 5 17:35:22 2013 -0800

    cmd/5g, cmd/5l, cmd/6g, cmd/6l, cmd/8g, cmd/8l, cmd/gc, runtime: generate pointer maps by liveness analysis
    
    This change allows the garbage collector to examine stack
    slots that are determined as live and containing a pointer
    value by the garbage collector.  This results in a mean
    reduction of 65% in the number of stack slots scanned during
    an invocation of "GOGC=1 all.bash".
    
    Unfortunately, this does not yet allow garbage collection to
    be precise for the stack slots computed as live.  Pointers
    confound the determination of what definitions reach a given
    instruction.  In general, this problem is not solvable without
    runtime cost but some advanced cooperation from the compiler
    might mitigate common cases.
    
    R=golang-dev, rsc, cshapiro
    CC=golang-dev
    https://golang.org/cl/14430048

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

https://github.com/golang/go/commit/f056daf075f303918343fd79af7ee0bfdcf6738e

元コミット内容

このコミットは、Goコンパイラ（cmd/5g, cmd/6g, cmd/8g, cmd/gc）とリンカ（cmd/5l, cmd/6l, cmd/8l）、およびランタイム（runtime）に変更を加え、ガベージコレクタがライブネス解析に基づいてポインタマップを生成できるようにするものです。

主な目的は、ガベージコレクタがスタックスロットをスキャンする際に、実際にライブ（到達可能）であり、かつポインタ値を含むスロットのみを対象とすることで、スキャン対象のスタックスロット数を平均で65%削減することです。

ただし、この変更だけでは、ライブと判定されたスタックスロットに対するガベージコレクションの精度を完全に高めることはできないと述べられています。ポインタが、特定の命令に到達する定義の決定を複雑にするため、この問題は一般的にランタイムコストなしでは解決が困難であり、コンパイラからの高度な協力が必要となる可能性があるとされています。

変更の背景

Go言語のガベージコレクションは、プログラムのメモリ管理において重要な役割を担っています。特に、スタック上のポインタの正確な識別は、ガベージコレクタの効率と精度に直結します。従来のGoのガベージコレクタは、スタック上のすべてのスロットをスキャンしてポインタを探す必要があり、これは特に大きなスタックを持つ関数において、パフォーマンスのボトルネックとなる可能性がありました。

このコミットの背景には、ガベージコレクションのパフォーマンスを向上させるという明確な目標があります。具体的には、スタック上の「ライブなポインタ」のみを識別し、それ以外の領域をスキャン対象から除外することで、ガベージコレクションのオーバーヘッドを削減しようとしています。これは、ガベージコレクタが不要なメモリ領域を探索する時間を短縮し、アプリケーション全体の実行速度を向上させることに貢献します。

また、Go言語のガベージコレクタは、当初は「正確なGC（Precise GC）」ではなく、「保守的なGC（Conservative GC）」の要素を持っていました。保守的なGCは、メモリ上の値がポインタであるかどうかを確実に判断できない場合でも、それがポインタである可能性があると仮定してマークします。これにより、誤ってライブなオブジェクトを回収してしまうリスクは減りますが、実際にはポインタではない値をポインタとして扱うことで、不要なオブジェクトを保持し続ける（メモリリークではないが、メモリ使用量が増える）可能性があります。このコミットは、ライブネス解析を導入することで、より正確なポインタ識別を目指し、将来的には完全な正確なGCへの道を開く一歩と位置づけられます。

前提知識の解説

ガベージコレクション (Garbage Collection, GC)

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはやどの部分からも参照されなくなった領域（ガベージ）を自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ管理から解放され、メモリリークなどのバグを減らすことができます。Go言語のGCは、並行マーク＆スイープ方式をベースとしており、プログラムの実行と並行してガベージコレクションが行われることで、アプリケーションの一時停止（Stop-the-World）時間を最小限に抑えるように設計されています。

ポインタ (Pointer)

ポインタは、メモリ上の特定のアドレスを指し示す変数です。Go言語では、変数のアドレスを取得するために&演算子を使用し、ポインタが指す値にアクセスするために*演算子を使用します。ガベージコレクタは、メモリ上のどの領域がまだ使用されているかを判断するために、ポインタを追跡します。

スタック (Stack)

スタックは、関数呼び出しやローカル変数の格納に使用されるメモリ領域です。関数が呼び出されるたびに、その関数のローカル変数や引数、戻りアドレスなどがスタックフレームとしてスタックに積まれます。関数が終了すると、そのスタックフレームは解放されます。

ライブネス解析 (Liveness Analysis)

ライブネス解析は、コンパイラのデータフロー解析の一種で、プログラムの特定のポイントにおいて、どの変数が「ライブ」（将来的に使用される可能性がある）であるかを決定します。変数がライブであるとは、その変数の値が後続の計算で読み取られる可能性があることを意味します。ガベージコレクションの文脈では、ライブネス解析は、スタック上のどのスロットがポインタを含み、かつそのポインタが将来的に参照される可能性があるかを特定するために使用されます。これにより、ガベージコレクタは不要なスキャンを避けることができます。

ポインタマップ (Pointer Map)

ポインタマップは、ガベージコレクタがメモリ領域（特にスタックやヒープ）内のどこにポインタが存在するかを効率的に識別するためのデータ構造です。ポインタマップは通常、ビットマップとして表現され、各ビットが特定のメモリワードがポインタであるかどうかを示します。このコミットでは、ライブネス解析の結果に基づいて、スタック上のポインタマップを生成するアプローチが導入されています。これにより、ガベージコレクタはスタック全体をスキャンする代わりに、ポインタマップを参照してポインタのみを効率的に見つけることができます。

精確なGC (Precise GC) と 保守的なGC (Conservative GC)

  • 精確なGC: メモリ上の値がポインタであるか否かを常に正確に識別できるガベージコレクタです。これにより、ガベージコレクタはライブなオブジェクトのみを保持し、不要なオブジェクトを確実に回収できます。Go言語は、ヒープ上では精確なGCを実現していますが、スタック上では歴史的に保守的な要素を持っていました。
  • 保守的なGC: メモリ上の値がポインタであるか否かを確実に識別できない場合、それがポインタである可能性があると仮定してマークするガベージコレクタです。これにより、誤ってライブなオブジェクトを回収してしまうことはありませんが、実際にはポインタではない値をポインタとして扱うことで、不要なオブジェクトを保持し続ける可能性があります。

このコミットは、スタック上のポインタ識別をより精確にすることで、GoのGCをより精確な方向に進化させる一歩となります。

技術的詳細

このコミットの核心は、Goコンパイラが関数のスタックフレーム内のポインタのライブネス情報をより正確に追跡し、その情報をガベージコレクタが利用できる「ポインタマップ」として生成することにあります。

ライブネス解析の導入

src/cmd/gc/plive.cという新しいファイルが追加されており、これがスタック上のライブネス解析の主要なロジックを実装しています。このファイルには、制御フローグラフ（CFG）の構築、基本ブロックの定義、そしてデータフロー解析のためのユーティリティ関数が含まれています。

  • 制御フローグラフ (CFG) の構築: newcfg関数は、Goの命令列から基本ブロックを抽出し、それらの間の制御フローエッジを構築します。これにより、プログラムの実行パスをグラフとして表現できます。
  • 逆ポストオーダー (RPO) 順序付け: reversepostorder関数は、CFGの基本ブロックに逆ポストオーダー番号を割り当てます。これは、データフロー解析を効率的に行うための標準的な手法です。
  • データフロー解析: progeffects関数は、個々の命令が変数セットに与える影響（uevar: upward exposed variables、varkill: variables killed）を計算します。これらの情報は、ライブネス方程式を解くために使用されます。
  • ライブネス方程式の解決: liveness関数（src/cmd/gc/go.hで宣言され、src/cmd/gc/pgen.cから呼び出される）は、各基本ブロックのlivein（ブロックに入る時点でライブな変数）とliveout（ブロックから出る時点でライブな変数）のセットを反復的に計算します。これは、データフロー方程式 LiveIn(B) = Use(B) U (LiveOut(B) - Def(B)) および LiveOut(B) = U_{S in Succ(B)} LiveIn(S) を解くことで行われます。

ポインタマップの生成

ライブネス解析の結果は、関数のスタックフレーム内のどのオフセットにポインタが存在し、かつそれが特定のプログラムポイントでライブであるかを示すビットマップとしてエンコードされます。

  • FUNCDATA_GCArgs と FUNCDATA_GCLocals: これらの定数は、ランタイムが関数の引数とローカル変数のポインタマップを識別するために使用されます。
  • gfatvardef: この新しい関数は、コンパイラが「fat」な変数（構造体や配列など、複数のワードを占める可能性のある変数）の定義をマークするために使用されます。これにより、ガベージコレクタはこれらの変数の内部構造をより詳細に理解できます。
  • defframe の変更: src/cmd/{5,6,8}g/ggen.c の defframe 関数は、スタックフレームの初期化ロジックが簡素化されています。以前は、ポインタを含む可能性のあるスタックスロットをゼロクリアしていましたが、ライブネス解析によってポインタマップが生成されるようになったため、この明示的なゼロクリアは不要になりました。ガベージコレクタはポインタマップを参照して、どのスロットがポインタであるかを判断できるようになります。
  • dumpgcargs と dumpgclocals の削除と liveness の導入: src/cmd/gc/pgen.c から dumpgcargs と dumpgclocals 関数が削除され、代わりに liveness 関数が呼び出されています。これは、従来の静的なポインタマップ生成から、ライブネス解析に基づく動的なポインタマップ生成への移行を示しています。

コンパイラとリンカの変更

  • AFATVARDEF 命令: 新しい擬似命令 AFATVARDEF が導入され、コンパイラが「fat」な変数の定義をマークするために使用されます。これは、src/cmd/{5,6,8}g/prog.c および src/cmd/{5,6,8}l/{5,6,8}.out.h で定義されています。
  • regopt の変更: src/cmd/{5,6,8}g/reg.c の regopt 関数から fixjmp の呼び出しが削除されています。これは、ライブネス解析が制御フローグラフをより正確に扱うようになったため、ジャンプ命令の修正ロジックが不要になったか、あるいはより適切な場所に移されたことを示唆しています。
  • src/cmd/dist/build.c の変更: src/cmd/gc/plive.c がビルドプロセスに追加されています。

ランタイムの変更

  • src/pkg/runtime/mgc0.c: ガベージコレクタのコアロジックが含まれるこのファイルも変更されています。ライブネス解析によって生成されたポインタマップを利用して、スタックのスキャン方法が改善されています。

影響と課題

この変更により、ガベージコレクタはスタック上のポインタをより効率的に識別できるようになり、スキャン対象のスタックスロット数が大幅に削減されます。しかし、コミットメッセージにもあるように、ポインタが複雑なデータフローを持つ場合（例えば、ポインタが計算によって生成される場合など）、ライブネス解析だけでは完全に正確なポインタ情報を取得できない場合があります。これは、コンパイラが実行時にポインタの正確な型を常に把握できるわけではないためです。この問題は、将来的にコンパイラとランタイムのさらなる連携によって解決される可能性があります。

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

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

  1. src/cmd/gc/plive.c (新規追加):

    • このファイルは、ライブネス解析の主要なロジックを実装しています。
    • BasicBlock 構造体と関連する関数（newblock, freeblock, addedge, printblock, blockany）が定義され、制御フローグラフ（CFG）の基本ブロックを表現します。
    • Liveness 構造体は、ライブネス解析のグローバルな状態（関数ノード、命令リスト、変数リスト、CFG、ビットベクトルなど）を保持します。
    • newcfg 関数は、命令列からCFGを構築します。
    • reversepostorder 関数は、CFGの基本ブロックに逆ポストオーダー番号を割り当てます。
    • progeffects 関数は、個々の命令が変数セットに与える影響（uevar, varkill）を計算します。
    • liveness 関数（このファイル内で定義されているが、go.hで宣言され、pgen.cから呼び出される）は、ライブネス解析を実行し、ポインタマップを生成します。

  2. src/cmd/gc/pgen.c:

    • compile 関数内で、従来の dumpgcargs と dumpgclocals の呼び出しが削除され、新しく導入された liveness 関数が呼び出されるようになりました。これにより、スタック上のポインタマップの生成がライブネス解析に基づいて行われるようになります。
    • makefuncdatasym 関数が追加され、FUNCDATA_GCArgs, FUNCDATA_GCLocals, FUNCDATA_DeadPointerMaps のシンボルを生成します。
    • gfatvardef 関数が追加され、AFATVARDEF 命令を挿入して「fat」な変数をマークします。
    • removefatvardef 関数が追加され、命令ストリームから AFATVARDEF 命令を削除します。

  3. src/cmd/{5,6,8}g/ggen.c:

    • defframe 関数から、スタック上のポインタ領域をゼロクリアするロジックが削除されました。これは、ライブネス解析によってポインタマップが生成されるため、明示的なゼロクリアが不要になったためです。
    • appendp ヘルパー関数が削除されました。

  4. src/cmd/gc/go.h:

    • Array および Bvec 構造体の宣言と、それらを操作する新しい関数（arraynew, arrayfree, arrayget, arrayset, arrayadd, arraysort、bvandnot, bvcmp, bvcopy, bvconcat, bvnot, bvor, bvprint, bvreset, bvresetall, bvsetなど）のプロトタイプが追加されました。これらはライブネス解析の実装で利用されるデータ構造です。
    • liveness 関数のプロトタイプが追加されました。
    • defframe 関数のシグネチャが変更され、Bvec* 引数が削除されました。

  5. src/cmd/gc/array.c (新規追加):

    • 動的配列を実装する汎用的なArrayデータ構造と、その操作関数（arraynew, arrayfree, arraylength, arrayget, arrayset, arrayadd, arrayindexof, arraysort）が定義されています。これはライブネス解析のCFG構築などで利用されます。

  6. src/cmd/gc/bv.c:

    • ビットベクトルを操作する関数（bvalloc, bvset, bvres, bvget, bvisempty, bvcmp）に加えて、新しいビットベクトル操作関数（bvandnot, bvcopy, bvconcat, bvnot, bvor, bvprint, bvreset, bvresetall）が追加されました。これらはライブネス解析のデータフロー方程式を解くために使用されます。

  7. src/cmd/{5,6,8}g/prog.c および src/cmd/{5,6,8}l/{5,6,8}.out.h:

    • 新しい擬似命令 AFATVARDEF が追加され、コンパイラが「fat」な変数をマークするために使用されます。

コアとなるコードの解説

src/cmd/gc/plive.c の liveness 関数 (概念)

このコミットの最も重要な部分は、src/cmd/gc/plive.c で実装されているライブネス解析と、それを利用してポインタマップを生成する liveness 関数（pgen.c から呼び出される）です。

liveness 関数は、以下の主要なステップを実行します。

  1. 制御フローグラフ (CFG) の構築:

    • 関数の命令列を走査し、ジャンプ命令や関数呼び出しのターゲット、フォールスルーなどを分析して、基本ブロック（BasicBlock）を識別します。
    • 各基本ブロックの開始命令 (first) と終了命令 (last) を設定し、基本ブロック間の前任者 (pred) と後任者 (succ) の関係を構築します。
    • newcfg 関数がこの処理を担当します。

  2. 変数リストの収集:

    • 関数内のすべての引数とローカル変数（Node*）を収集し、それらを配列 (Array *vars) に格納します。この配列のインデックスは、ビットベクトル内の変数を参照するために使用されます。

  3. データフロー方程式の初期化:

    • 各基本ブロックに対して、以下のビットベクトルを初期化します。
      • uevar (Upward Exposed Variables): そのブロック内で定義される前に使用される変数。
      • varkill (Variables Killed): そのブロック内で定義される変数。
      • livein (Live-in Variables): そのブロックに入る時点でライブな変数。
      • liveout (Live-out Variables): そのブロックから出る時点でライブな変数。
    • progeffects 関数が個々の命令レベルで uevar と varkill を計算します。

  4. ライブネス方程式の反復的解決:

    • CFGを逆ポストオーダー（RPO）順に走査し、livein と liveout のビットベクトルが安定するまで反復的に計算します。
    • 各基本ブロック B について、以下のデータフロー方程式を適用します。
      • LiveOut(B) = U_{S in Succ(B)} LiveIn(S) (後続ブロックの Live-in の和集合)
      • LiveIn(B) = Use(B) U (LiveOut(B) - Def(B)) (ブロック内で使用される変数と、ブロックから出てライブな変数のうちブロック内で定義されない変数の和集合)
    • この反復プロセスは、bvor (ビットベクトルのOR演算) や bvandnot (ビットベクトルのAND NOT演算) などのビットベクトル操作関数を使用して効率的に行われます。

  5. ポインタマップの生成と出力:

    • ライブネス解析が完了すると、各プログラムポイント（特にガベージコレクションのセーフポイント）におけるライブなポインタの情報が livein および liveout ビットベクトルに含まれます。
    • liveness 関数は、これらのビットベクトルを基に、ランタイムが利用できる形式のポインタマップ（FUNCDATA_GCArgs, FUNCDATA_GCLocals, FUNCDATA_DeadPointerMaps）を生成し、対応するシンボルに書き込みます。
    • これにより、ガベージコレクタは、スタック上のどのオフセットにポインタが存在し、かつそれがライブであるかを正確に知ることができます。

src/cmd/{5,6,8}g/ggen.c の defframe 関数の変更

変更前:

void
defframe(Prog *ptxt, Bvec *bv)
{
    // ...
    // insert code to clear pointered part of the frame,
    // so that garbage collector only sees initialized values
    // when it looks for pointers.
    // ... (スタックのポインタ領域をゼロクリアするコード)
}

変更後:

void
defframe(Prog *ptxt)
{
    // ...
    // スタックのポインタ領域をゼロクリアするコードが削除された
}

この変更は、ライブネス解析によってポインタマップが生成されるようになったことの直接的な結果です。以前は、ガベージコレクタがスタック上のポインタを識別するために、ポインタを含む可能性のある領域を明示的にゼロクリアする必要がありました。これは、未初期化のメモリ領域にゴミデータが含まれている場合、それが誤ってポインタと解釈されるのを防ぐためです。しかし、ライブネス解析が導入され、どのスタックスロットが実際にライブなポインタを含むかを正確に識別できるようになったため、このゼロクリアは不要になりました。ガベージコレクタはポインタマップを参照して、必要なスロットのみを検査するようになります。これにより、コンパイルされたコードのサイズと実行時のオーバーヘッドが削減されます。

関連リンク

  • Go言語のガベージコレクションに関する公式ドキュメントやブログ記事
  • コンパイラのデータフロー解析、特にライブネス解析に関する学術論文や教科書
  • Go言語のコンパイラとランタイムの内部構造に関する資料

参考にした情報源リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • Go言語のガベージコレクションに関するブログ記事やドキュメント (具体的なURLはWeb検索結果に基づく)
  • コンパイラ設計に関する一般的な情報源 (Web検索結果に基づく)
  • Go CL 14430048: https://golang.org/cl/14430048 (コミットメッセージに記載)