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

このコミットは、Goランタイムにおけるスタックフレームのゼロ初期化処理の効率化を目的としています。特に、Duff's Device（ダフのデバイス）と呼ばれる最適化手法を導入し、隣接するメモリ領域のゼロ初期化を結合することで、パフォーマンスの向上を図っています。

コミット

commit 383963b50622d9e0a28a3deb75aba8533e5ad949
Author: Keith Randall <khr@golang.org>
Date:   Tue Apr 1 19:44:07 2014 -0700

    runtime: zero at start of frame more efficiently.
    
    Use Duff's device for zeroing.  Combine adjacent regions.
    
    Update #7680
    Update #7624
    
    LGTM=rsc
    R=rsc
    CC=golang-codereviews
    https://golang.org/cl/83200045

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

https://github.com/golang/go/commit/383963b50622d9e0a28a3deb75aba8533e5ad949

元コミット内容

Goランタイムにおいて、スタックフレームの開始時にメモリをより効率的にゼロ初期化する。 ゼロ初期化にDuff's Deviceを使用し、隣接する領域を結合する。

変更の背景

Go言語のガベージコレクタは、ポインタを探索する際に、初期化されていない可能性のあるメモリ領域に誤ったポインタが含まれていることを避けるため、スタックフレーム上の曖昧にライブな変数（ambiguously live variables）をゼロ初期化する必要があります。これは、ガベージコレクタが常に初期化された値のみを参照するようにするための重要なステップです。

以前の実装では、このゼロ初期化処理が非効率的でした。特に、小さな領域のゼロ初期化が繰り返し行われたり、大きな領域に対しては単純なループが使用されたりしていました。これにより、関数呼び出しのオーバーヘッドが増加し、パフォーマンスに影響を与えていました。

このコミットは、このゼロ初期化の効率を改善し、特に大量のメモリをゼロ初期化する必要がある場合に、より高速な実行を可能にすることを目的としています。具体的には、以下の2つの主要な改善が導入されました。

1. Duff's Deviceの導入: 効率的なループアンローリング手法であるDuff's Deviceを利用して、ゼロ初期化のループオーバーヘッドを削減します。
2. 隣接領域の結合: ゼロ初期化が必要な隣接するメモリ領域を結合し、一度の操作でより大きなブロックをゼロ初期化することで、処理の回数を減らします。

これらの変更により、Goプログラムの実行時パフォーマンス、特にスタックフレームのセットアップに関連するオーバーヘッドが削減されます。

前提知識の解説

Goランタイムとスタックフレーム

Go言語のプログラムは、Goランタイム上で実行されます。各Goroutine（Goにおける軽量スレッド）は独自のスタックを持っており、関数呼び出しごとにスタックフレームが作成されます。スタックフレームには、関数のローカル変数、引数、戻りアドレスなどが格納されます。

ガベージコレクションとゼロ初期化

Goは自動メモリ管理（ガベージコレクション）を採用しています。ガベージコレクタは、到達可能なオブジェクトを特定し、到達不能なオブジェクトが占めるメモリを解放します。このプロセスにおいて、スタック上の変数がポインタである場合、ガベージコレクタはそれらのポインタが有効なメモリを指していることを確認する必要があります。

しかし、新しく確保されたスタックメモリには、以前の関数の実行によって残された「ゴミ」データが含まれている可能性があります。このゴミデータの中に、たまたま有効なポインタのように見えるビットパターンが含まれていると、ガベージコレクタが誤ってその領域を「ライブ」であると判断し、本来解放されるべきメモリを保持し続けてしまう可能性があります（「偽の参照」または「スプリアスルート」）。これを防ぐため、Goランタイムは、ガベージコレクタがスキャンする前に、スタックフレーム上のポインタを含む可能性のある領域をゼロ初期化することで、すべてのポインタがnil（またはゼロ値）であることを保証します。これにより、ガベージコレクタは常に明確な状態のメモリをスキャンし、正確なガベージコレクションを実行できます。

Goランタイムは、パフォーマンス最適化のために、スタックフレーム全体をデフォルトでゼロ初期化するわけではありません。代わりに、ポインタを含む可能性のある特定の領域（曖昧にライブな変数）のみをゼロ初期化します。これは、スタックメモリの割り当てがヒープメモリの割り当てよりも高速であるため、不要なゼロ初期化を避けることでさらにパフォーマンスを向上させるためです。

Duff's Device（ダフのデバイス）

Duff's Deviceは、1983年にトム・ダフによって考案されたC言語のプログラミングテクニックで、ループアンローリングを手動で実装するためのものです。これは、do-whileループとswitchステートメントを巧妙に組み合わせることで、ループのオーバーヘッド（条件チェックや分岐）を削減し、データ転送などの繰り返し処理を高速化します。

動作原理:

1. ループアンローリング: 1回のループイテレーションで複数の操作を実行することで、ループの条件チェックの回数を減らします。
2. switchとdo-whileの組み合わせ:
   • switchステートメントは、処理すべき残りの要素数に応じて、do-whileループの途中にジャンプするために使用されます。これにより、処理の開始位置を調整し、最初の部分的なバッチを効率的に処理します。
   • C言語のswitchステートメントのフォールスルー（breakがない場合に次のcaseに処理が継続する）特性を利用して、複数の操作を連続して実行します。
   • 一度do-whileループに入ると、switchロジックは再評価されず、ループは完全なバッチで処理を続行します。

Duff's Deviceは、コンパイラの最適化が現在ほど高度でなかった時代に、リアルタイムアニメーションなどのパフォーマンスが重要なアプリケーションで特に有効でした。現代のコンパイラは非常に洗練されており、Duff's Deviceのような手動の最適化よりも効果的にループアンローリングを行うことができるため、現在では主に歴史的な興味の対象となっていますが、その巧妙な設計は今でも学ぶ価値があります。

技術的詳細

このコミットは、Goコンパイラのバックエンド（src/cmd/6g/ggen.c for amd64 and src/cmd/8g/ggen.c for 386）におけるスタックフレームのゼロ初期化ロジックを変更しています。

変更の核心は、defframe関数内で呼び出される新しいヘルパー関数zerorangeの導入と、既存のゼロ初期化ロジックの置き換えです。

zerorange関数の導入

zerorange関数は、指定されたメモリ範囲（loからhiまで）をゼロ初期化する責任を負います。この関数は、ゼロ初期化するバイト数（cnt）に応じて、異なる最適化戦略を採用します。

1. 小さな領域 (cnt <= 4*widthreg):

   • widthregはレジスタの幅（amd64では8バイト、386では4バイト）を表します。
   • このケースでは、AMOVQ（amd64）またはAMOVL（386）命令を使用して、レジスタ幅単位で直接ゼロをメモリに書き込みます。これは、非常に小さな領域に対しては最も効率的な方法です。

2. 中程度の領域 (4*widthreg < cnt <= 128*widthreg):

   • この範囲のゼロ初期化には、Duff's Deviceが使用されます。
   • ADUFFZEROという擬似命令が導入され、これはGoランタイムのduffzero関数へのジャンプとして解決されます。duffzeroは、Duff's Deviceの原理に基づいて、効率的なループアンローリングによってメモリをゼロ初期化するアセンブリコードです。
   • p = appendpp(p, ADUFFZERO, D_NONE, 0, D_ADDR, 2*(128-cnt/widthreg)); のように、ADUFFZERO命令のオフセットにcntに応じた値が渡され、duffzeroルーチンの適切なエントリポイントにジャンプすることで、残りのバイト数を効率的にゼロ初期化します。

3. 大きな領域 (cnt > 128*widthreg):

   • このケースでは、REP STOSQ（amd64）またはREP STOSL（386）命令が使用されます。
   • REP STOSQは、CXレジスタに指定された回数だけ、AXレジスタの内容（この場合はゼロ）をDIレジスタが指すメモリ位置に書き込み、DIを自動的にインクリメントするアセンブリ命令です。これは、OSレベルで最適化された非常に高速なメモリゼロ初期化方法です。
   • cnt/widthregがCXレジスタにロードされ、DIレジスタにはゼロ初期化を開始するメモリアドレスがロードされます。

隣接領域の結合

defframe関数内のループでは、curfn->dcl（現在の関数の宣言リスト）を反復処理し、ゼロ初期化が必要な変数（n->needzeroが真の場合）を特定します。

以前の実装では、各変数に対して個別にゼロ初期化コードを生成していました。しかし、このコミットでは、loとhiという変数を使用して、ゼロ初期化が必要な連続したメモリ領域を追跡します。

• 変数が現在のゼロ初期化範囲（loからhi）に隣接している場合（n->xoffset + n->type->width >= lo - 2*widthptr）、その変数を既存の範囲にマージし、loを更新して範囲を拡張します。
• 変数が現在の範囲に隣接していない場合、まずzerorange関数を呼び出して現在の範囲をゼロ初期化し、その後、新しい変数のための新しいゼロ初期化範囲を設定します。

この「隣接領域の結合」により、複数の小さなゼロ初期化操作が、より少ない回数の大きなゼロ初期化操作にまとめられ、関数呼び出しや命令のオーバーヘッドが削減されます。

変更されたファイル

• src/cmd/6g/ggen.c: AMD64アーキテクチャ用のGoコンパイラバックエンド。
• src/cmd/8g/ggen.c: 386アーキテクチャ用のGoコンパイラバックエンド。

これらのファイルは、GoコンパイラがGoソースコードをアセンブリコードに変換する際に、スタックフレームのセットアップとゼロ初期化に関する命令を生成する部分を担当しています。

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

src/cmd/6g/ggen.c および src/cmd/8g/ggen.c の変更点

1. zerorange関数の追加: 新しい静的関数zerorangeが追加されました。この関数は、指定されたメモリ範囲を効率的にゼロ初期化するためのロジックを含んでいます。

   static Prog *zerorange(Prog *p, vlong frame, vlong lo, vlong hi, uint32 *ax);
   

2. defframe関数の変更:

   • defframe関数内のゼロ初期化ロジックが大幅に変更されました。
   • 以前の、変数のサイズに応じた複数のappendpp呼び出しによるゼロ初期化ロジックが削除され、zerorange関数を呼び出す形に置き換えられました。
   • loとhi変数が導入され、ゼロ初期化が必要な隣接するメモリ領域を結合するロジックが追加されました。

   // 変更前 (例: 6g/ggen.c)
   // if(n->type->width <= 2*widthreg) { ... }
   // else if(n->type->width <= 16*widthreg) { ... }
   // else { ... }
   
   // 変更後 (例: 6g/ggen.c)
   // merge with range we already have
   if(n->xoffset + n->type->width >= lo - 2*widthptr) {
       lo = n->xoffset;
       continue;
   }
   // zero old range
   p = zerorange(p, frame, lo, hi, &ax);
   
   // set new range
   hi = n->xoffset + n->type->width;
   lo = n->xoffset;
   // zero final range
   zerorange(p, frame, lo, hi, &ax);
   

コアとなるコードの解説

defframe関数におけるゼロ初期化範囲の管理

defframe関数は、関数のスタックフレームをセットアップする際に呼び出されます。この関数内で、curfn->dcl（現在の関数の宣言リスト）を逆順に（xoffsetの降順で）走査します。これは、スタック上の変数が通常、高アドレスから低アドレスへと配置されるため、隣接する領域を効率的に結合するためです。

loとhi変数は、現在ゼロ初期化を検討しているメモリ範囲の下限と上限を追跡します。

• loは範囲の開始オフセット（スタックフレームのベースからの相対オフセット）。
• hiは範囲の終了オフセット。

ループ内で新しい変数nが見つかったとき、その変数が既存のゼロ初期化範囲に隣接しているかどうかをチェックします。 n->xoffset + n->type->width >= lo - 2*widthptr この条件は、新しい変数の領域が、既存のloの開始位置から2*widthptr（ポインタ2つ分のサイズ）以内に収まるかどうかをチェックしています。これは、わずかなギャップがあっても結合を試みるためのヒューリスティックです。もし隣接していれば、loを新しい変数の開始オフセットに更新し、ループを続行してさらに領域を結合します。

隣接していない場合、これまでのloからhiまでの範囲をzerorange関数に渡してゼロ初期化を実行します。その後、新しい変数の領域を新しいloとhiとして設定します。

ループの最後に、残っている最終的なゼロ初期化範囲をzerorange関数で処理します。

zerorange関数における最適化戦略

zerorange関数は、実際にメモリをゼロ初期化するアセンブリ命令を生成します。

• *ax == 0 のチェック: axは、ゼロ値がAXレジスタにロードされているかどうかを示すフラグです。AXレジスタにゼロがまだロードされていない場合、AMOVQ D_CONST, 0, D_AX, 0（amd64）またはAMOVL D_CONST, 0, D_AX, 0（386）命令を生成してゼロをロードします。これにより、不要なAXレジスタへのゼロロードを避けます。

• cnt <= 4*widthreg (小さな領域): forループを使用して、widthreg（レジスタ幅）単位でAMOVQまたはAMOVL命令を生成し、AXレジスタのゼロ値をスタック上の対応するオフセットに直接書き込みます。これは、命令のセットアップコストがDuff's DeviceやREP STOSよりも低い場合に効率的です。

• cnt <= 128*widthreg (中程度の領域 - Duff's Device): leaptr命令（LEA命令のポインタ版）でスタック上の開始アドレスをDIレジスタにロードし、ADUFFZERO命令を生成します。ADUFFZEROは、Goランタイムのアセンブリコードにあるduffzeroルーチンへのジャンプを生成します。duffzeroルーチンは、Duff's Deviceの原理に基づいて、ループアンローリングされたコードパスを実行し、効率的にメモリをゼロ初期化します。2*(128-cnt/widthreg)のようなオフセットは、duffzeroルーチン内の適切なエントリポイントにジャンプするためのもので、これにより残りのバイト数に応じた最適なアンローリングパスが選択されます。

• cnt > 128*widthreg (大きな領域 - REP STOS): AMOVQまたはAMOVL命令でゼロ初期化するワード数（cnt/widthreg）をCXレジスタにロードします。 leaptr命令でスタック上の開始アドレスをDIレジスタにロードします。 AREP命令（REPプレフィックス）とASTOSQ（amd64）またはASTOSL（386）命令を生成します。これにより、CPUのハードウェアレベルで最適化されたREP STOS命令が実行され、非常に高速に大量のメモリをゼロ初期化します。

これらの最適化戦略を組み合わせることで、Goランタイムはスタックフレームのゼロ初期化を、そのサイズに応じて最も効率的な方法で実行できるようになります。

関連リンク

• Go言語のガベージコレクションに関するドキュメントやブログ記事
• Duff's Deviceに関する技術記事や解説
• Goコンパイラのソースコード（特にsrc/cmd/ディレクトリ）

参考にした情報源リンク

• Duff's Device - Wikipedia
• Go runtime: zeroing stack frame - Stack Overflow / Go.dev documentation (Web search results provided by the tool)
• Go runtime: zero at start of frame more efficiently. - Go Gerrit Code Review (Provided in the commit message)
• Go言語のメモリ管理とガベージコレクション (Go公式ドキュメント)
• Goのスタック管理 (Medium記事)
• Goのコンパイラ最適化 (Go 101)
• REP STOS instruction (x86 Instruction Set Reference)
• LEA instruction (x86 Instruction Set Reference)
• Goのソースコード (GitHub)