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

このコミットは、Goコンパイラ（cmd/6g および cmd/8g）において、スタックフレームの小さなゼロ初期化処理を最適化するものです。具体的には、REPプレフィックスを用いたSTOS命令（REP STOS）の使用を避け、代わりにストレートラインコード（直接的な命令列）でゼロ初期化を行うように変更しています。これにより、REPプレフィックスが持つ高い起動コストを削減し、パフォーマンスを向上させることを目的としています。

コミット

• コミットハッシュ: 14664050b9dc5284f120faa3ca054eb3d04b77bb
• 作者: Keith Randall khr@golang.org
• 日付: Wed Mar 19 15:41:34 2014 -0700
• コミットメッセージ:

  cmd/6g: do small zeroings with straightline code.
  
  Removes most uses of the REP prefix, which has a high startup cost.
  
  LGTM=iant
  R=golang-codereviews, iant, khr
  CC=golang-codereviews
  https://golang.org/cl/77920043
  

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

https://github.com/golang/go/commit/14664050b9dc5284f120faa3ca054eb3d04b77bb

元コミット内容

cmd/6g: do small zeroings with straightline code.

Removes most uses of the REP prefix, which has a high startup cost.

LGTM=iant
R=golang-codereviews, iant, khr
CC=golang-codereviews
https://golang.org/cl/77920043

変更の背景

この変更の背景には、x86アーキテクチャにおけるREPプレフィックスとSTOS命令の組み合わせ（REP STOS）のパフォーマンス特性があります。REP STOSは、指定された回数だけメモリに値をストアする命令であり、大量のメモリを効率的にゼロ初期化する際に用いられることがあります。しかし、非常に小さなメモリ領域をゼロ初期化する場合、REP STOSには「高い起動コスト（high startup cost）」が存在します。

この起動コストは、現代のCPUがREP STOSのような複雑な命令をマイクロコードで実装していることに起因します。CPUは、この命令を実行するために内部的にマイクロコードルーチンをセットアップし、実行する必要があります。このセットアッププロセスにはオーバーヘッドがあり、処理するデータ量が少ない場合、このオーバーヘッドが実際のデータストアにかかる時間よりも支配的になってしまいます。結果として、少量のゼロ初期化においては、REP STOSを使用するよりも、個別のMOV命令やSTOS命令をループで実行する「ストレートラインコード」の方が高速になることがあります。

Goランタイムでは、関数呼び出し時にスタックフレームをゼロ初期化する処理が行われます。これはガベージコレクタがポインタを正しく認識するために重要です。このゼロ初期化のサイズは、関数のスタック使用量によって様々ですが、比較的小さなサイズであることも少なくありませんでした。そのため、REP STOSの起動コストが全体のパフォーマンスに影響を与える可能性がありました。このコミットは、この非効率性を解消し、Goプログラムの実行効率を向上させることを目的としています。

前提知識の解説

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

Go言語の初期のコンパイラは、ターゲットアーキテクチャごとに異なる名前を持っていました。

• 6g: AMD64 (x86-64) アーキテクチャ向けのGoコンパイラ。
• 8g: x86 (32-bit) アーキテクチャ向けのGoコンパイラ。

これらのコンパイラは、Goのソースコードをアセンブリコードに変換し、最終的に実行可能なバイナリを生成する役割を担っていました。現在では、go buildコマンドが内部的に適切なコンパイラを選択するため、ユーザーが直接これらの名前を意識することは少なくなっています。

x86アセンブリ命令とREPプレフィックス、STOS命令

• STOS (Store String): この命令は、AL/AX/EAX/RAXレジスタの内容をES:DI/EDI/RDIレジスタが指すメモリ位置にストアし、その後DI/EDI/RDIレジスタをインクリメントまたはデクリメントします（方向フラグDFによって決定）。STOSB（バイト）、STOSW（ワード）、STOSD（ダブルワード）、STOSQ（クアッドワード）などがあります。
• REP (Repeat): REPプレフィックスは、文字列操作命令（MOVS, STOS, CMPS, SCASなど）の前に付加され、CX/ECX/RCXレジスタに指定された回数だけその命令を繰り返すようにCPUに指示します。例えば、REP STOSQは、RCX回だけRAXの内容をRDIが指すメモリにストアし、RDIをインクリメントします。これは、memsetのようなメモリ初期化処理でよく使われます。

REP STOSの起動コスト

前述の通り、REP STOSは現代のCPUではマイクロコードによって実装されています。これは、CPUがこの命令を直接ハードウェアで実行するのではなく、内部的に一連のより単純なマイクロ操作に分解して実行することを意味します。このマイクロコードのセットアップと実行には、以下のようなオーバーヘッドが伴います。

1. マイクロコードのロードと初期化: REP STOSが実行される際、CPUは対応するマイクロコードを内部的にロードし、必要なレジスタや内部状態を初期化します。
2. 最適化パスの選択: CPUは、データサイズ、アライメント、繰り返し回数などに基づいて、最適な実行パスを選択します。この選択プロセス自体にも時間がかかります。
3. パイプラインのフラッシュ: 複雑な命令の実行は、CPUのパイプラインを一時的に停止させたり、フラッシュさせたりすることがあり、これもパフォーマンスに影響します。

これらのオーバーヘッドは、繰り返し回数が少ない（つまり、ゼロ初期化するメモリサイズが小さい）場合には、個々のストア命令を直接実行するよりもコストが高くなることがあります。繰り返し回数が多くなればなるほど、この起動コストは償却され、REP STOSの効率性が発揮されます。

技術的詳細

このコミットは、src/cmd/6g/ggen.cとsrc/cmd/8g/ggen.c内のdefframe関数を変更しています。この関数は、Goコンパイラが関数のプロローグ（関数が呼び出された直後に実行されるコード）を生成する際に、スタックフレームのゼロ初期化を行う部分です。

変更の核心は、stkzerosize（ゼロ初期化するスタック領域のサイズ）の大きさに応じて、異なるゼロ初期化戦略を採用することです。

1. stkzerosize == 0: ゼロ初期化するサイズがない場合、何も行いません。
2. stkzerosize <= 2 * widthreg (または widthptr):
   • widthregはレジスタの幅（64-bitアーキテクチャでは8バイト、32-bitアーキテクチャでは4バイト）を指します。
   • このケースでは、スタック領域が非常に小さい（1ワードまたは2ワード）場合を扱います。
   • AMOVQ（64-bit）またはAMOVL（32-bit）命令を直接使用して、0をスタック上の各ワードにストアします。これは、REP STOSの起動コストを完全に回避する「ストレートラインコード」です。
   • 例: MOVQ $0, (SP)+offset を2回実行するようなイメージです。
3. stkzerosize <= 16 * widthreg (または widthptr):
   • スタック領域が中程度のサイズ（3ワードから16ワード）の場合を扱います。
   • まず、AXレジスタ（またはEAX）に0をロードします。
   • その後、ループを展開する形で、AMOVQ AX, (SP)+offset（またはAMOVL EAX, (SP)+offset）命令を繰り返し生成し、AXレジスタの0をスタック上の各ワードにストアします。
   • この方法もREP STOSを使用しませんが、AXレジスタを再利用することで、定数0を繰り返しロードするオーバーヘッドを削減しています。
4. stkzerosize > 16 * widthreg (または widthptr):
   • スタック領域が比較的大きい場合を扱います。
   • このケースでは、REP STOSの起動コストが償却されるため、従来のREP STOS命令を使用します。
   • AXレジスタに0をロードし、CXレジスタに繰り返し回数（stkzerosize / widthreg）を設定し、DIレジスタにストア先のスタックアドレスを設定した後、AREPプレフィックスとASTOSQ（またはASTOSL）命令を発行します。

この多段階のアプローチにより、Goコンパイラはスタックゼロ初期化のサイズに応じて最適なコードパスを選択し、全体的なパフォーマンスを向上させています。特に、頻繁に呼び出される小さな関数において、この最適化は顕著な効果を発揮すると考えられます。

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

変更は以下の2つのファイルにわたります。

• src/cmd/6g/ggen.c
• src/cmd/8g/ggen.c

それぞれのファイルのdefframe関数内で、stkzerosizeの処理ロジックが変更されています。

src/cmd/6g/ggen.c の変更点

--- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -29,12 +30,25 @@ defframe(Prog *ptxt)
 	// so that garbage collector only sees initialized values
 	// when it looks for pointers.
 	p = ptxt;
-	if(stkzerosize > 0) {
-		p = appendpp(p, movptr, D_CONST, 0, D_AX, 0);	
-		p = appendpp(p, movptr, D_CONST, stkzerosize/widthptr, D_CX, 0);	
-		p = appendpp(p, leaptr, D_SP+D_INDIR, frame-stkzerosize, D_DI, 0);	
-		p = appendpp(p, AREP, D_NONE, 0, D_NONE, 0);	
-		appendpp(p, stosptr, D_NONE, 0, D_NONE, 0);	
+	if(stkzerosize % widthreg != 0)
+		fatal("zero size not a multiple of ptr size");
+	if(stkzerosize == 0) {
+		// nothing
+	} else if(stkzerosize <= 2*widthreg) {
+		for(i = 0; i < stkzerosize; i += widthreg) {
+			p = appendpp(p, AMOVQ, D_CONST, 0, D_SP+D_INDIR, frame-stkzerosize+i);
+		}
+	} else if(stkzerosize <= 16*widthreg) {
+		p = appendpp(p, AMOVQ, D_CONST, 0, D_AX, 0);
+		for(i = 0; i < stkzerosize; i += widthreg) {
+			p = appendpp(p, AMOVQ, D_AX, 0, D_SP+D_INDIR, frame-stkzerosize+i);
+		}
+	} else {
+		p = appendpp(p, AMOVQ, D_CONST, 0, D_AX, 0);
+		p = appendpp(p, AMOVQ, D_CONST, stkzerosize/widthreg, D_CX, 0);
+		p = appendpp(p, leaptr, D_SP+D_INDIR, frame-stkzerosize, D_DI, 0);
+		p = appendpp(p, AREP, D_NONE, 0, D_NONE, 0);
+		appendpp(p, ASTOSQ, D_NONE, 0, D_NONE, 0);
 	}

src/cmd/8g/ggen.c の変更点

--- a/src/cmd/8g/ggen.c
+++ b/src/cmd/8g/ggen.c
@@ -28,7 +29,20 @@ defframe(Prog *ptxt)
 	// so that garbage collector only sees initialized values
 	// when it looks for pointers.
 	p = ptxt;
-	if(stkzerosize > 0) {
+	if(stkzerosize % widthptr != 0)
+		fatal("zero size not a multiple of ptr size");
+	if(stkzerosize == 0) {
+		// nothing
+	} else if(stkzerosize <= 2*widthptr) {
+		for(i = 0; i < stkzerosize; i += widthptr) {
+			p = appendpp(p, AMOVL, D_CONST, 0, D_SP+D_INDIR, frame-stkzerosize+i);
+		}
+	} else if(stkzerosize <= 16*widthptr) {
+		p = appendpp(p, AMOVL, D_CONST, 0, D_AX, 0);	
+		for(i = 0; i < stkzerosize; i += widthptr) {
+			p = appendpp(p, AMOVL, D_AX, 0, D_SP+D_INDIR, frame-stkzerosize+i);
+		}
+	} else {
 	p = appendpp(p, AMOVL, D_CONST, 0, D_AX, 0);	
 	p = appendpp(p, AMOVL, D_CONST, stkzerosize/widthptr, D_CX, 0);	
 	p = appendpp(p, ALEAL, D_SP+D_INDIR, frame-stkzerosize, D_DI, 0);	

コアとなるコードの解説

defframe関数は、Goコンパイラのバックエンドの一部であり、アセンブリコード生成を担当します。この関数は、Go関数のスタックフレームのセットアップと、ガベージコレクタがポインタを正しく追跡できるようにするためのスタック領域のゼロ初期化を行います。

変更されたコードブロックは、stkzerosizeという変数に基づいて、スタックのゼロ初期化方法を決定します。

• stkzerosize % widthreg != 0 (または widthptr) のチェック:

  • これは、ゼロ初期化するサイズがポインタサイズ（またはレジスタ幅）の倍数であることを確認するためのアサーションです。そうでない場合は致命的なエラー（fatal）を発生させます。

• if(stkzerosize == 0):

  • ゼロ初期化するサイズが0の場合、何もする必要がないため、このブロックはスキップされます。

• else if(stkzerosize <= 2*widthreg) (または widthptr):

  • 6g (AMD64) の場合、widthregは8バイト（64ビット）です。したがって、stkzerosizeが16バイト以下（2ワード以下）の場合にこのブロックが実行されます。
  • 8g (x86) の場合、widthptrは4バイト（32ビット）です。したがって、stkzerosizeが8バイト以下（2ワード以下）の場合にこのブロックが実行されます。
  • このブロックでは、forループを使って、AMOVQ（64ビット）またはAMOVL（32ビット）命令を直接生成し、定数0をスタック上の各ワードにストアします。これは、REP STOSの起動コストを避けるための最も直接的な方法です。

• else if(stkzerosize <= 16*widthreg) (または widthptr):

  • 6g (AMD64) の場合、stkzerosizeが16バイトより大きく、128バイト以下（16ワード以下）の場合にこのブロックが実行されます。
  • 8g (x86) の場合、stkzerosizeが8バイトより大きく、64バイト以下（16ワード以下）の場合にこのブロックが実行されます。
  • このブロックでは、まずAMOVQ D_CONST, 0, D_AX, 0（またはAMOVL D_CONST, 0, D_AX, 0）によってAXレジスタに0をロードします。
  • その後、forループを使って、AMOVQ D_AX, 0, D_SP+D_INDIR, frame-stkzerosize+i（またはAMOVL D_AX, 0, D_SP+D_INDIR, frame-stkzerosize+i）命令を生成します。これは、AXレジスタに格納された0をスタック上の各ワードにストアするものです。AXレジスタを再利用することで、定数0を繰り返し命令に埋め込むよりも効率的になります。

• else:

  • 上記の条件に当てはまらない、つまりstkzerosizeが16ワードよりも大きい場合にこのブロックが実行されます。
  • この場合、REP STOSの起動コストが償却されるため、従来のREP STOS命令が使用されます。
  • AMOVQ D_CONST, 0, D_AX, 0（またはAMOVL D_CONST, 0, D_AX, 0）でAXに0をロードします。
  • AMOVQ D_CONST, stkzerosize/widthreg, D_CX, 0（またはAMOVL D_CONST, stkzerosize/widthptr, D_CX, 0）でCXレジスタに繰り返し回数を設定します。
  • leaptr D_SP+D_INDIR, frame-stkzerosize, D_DI, 0（またはALEAL D_SP+D_INDIR, frame-stkzerosize, D_DI, 0）でDIレジスタにストア開始アドレスを設定します。
  • 最後に、AREPプレフィックスとASTOSQ（またはASTOSL）命令を生成し、REP STOSを実行します。

この変更により、Goコンパイラは生成するアセンブリコードの品質を向上させ、特に小さなスタックフレームのゼロ初期化において、より効率的な実行パスを選択できるようになりました。

関連リンク

• Go CL (Code Review) リンク: https://golang.org/cl/77920043

参考にした情報源リンク

• stackoverflow.com: x86 REP prefix high startup cost stos instruction
  • https://stackoverflow.com/questions/10400062/why-is-rep-stos-slow-for-small-sizes
  • https://stackoverflow.com/questions/10400062/why-is-rep-stos-slow-for-small-sizes
  • https://stackoverflow.com/questions/10400062/why-is-rep-stos-slow-for-small-sizes
• ycombinator.com:
  • https://news.ycombinator.com/item?id=2009999
  • https://news.ycombinator.com/item?id=2009999