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

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

このコミットは、Goランタイムにおけるメモリのコピーとゼロクリア処理のパフォーマンス改善を目的としています。特に、x86アーキテクチャのREP MOVSQおよびREP STOSQ命令が持つ起動オーバーヘッドの問題を回避するため、Duff's Device（ダフのデバイス）と呼ばれる最適化手法を導入しています。これにより、比較的小さなメモリブロックの操作において顕著な速度向上が見られます。

コミット

commit 6c7cbf086c34ebb88311ba12d3a75adcbdce8ac8
Author: Keith Randall <khr@golang.org>
Date:   Tue Apr 1 12:51:02 2014 -0700

    runtime: get rid of most uses of REP for copying/zeroing.
    
    REP MOVSQ and REP STOSQ have a really high startup overhead.
    Use a Duff's device to do the repetition instead.
    
    benchmark                 old ns/op     new ns/op     delta
    BenchmarkClearFat32       7.20          1.60          -77.78%
    BenchmarkCopyFat32        6.88          2.38          -65.41%
    BenchmarkClearFat64       7.15          3.20          -55.24%
    BenchmarkCopyFat64        6.88          3.44          -50.00%
    BenchmarkClearFat128      9.53          5.34          -43.97%
    BenchmarkCopyFat128       9.27          5.56          -40.02%
    BenchmarkClearFat256      13.8          9.53          -30.94%
    BenchmarkCopy256       13.5          10.3          -23.70%
    BenchmarkClearFat512      22.3          18.0          -19.28%
    BenchmarkCopyFat512       22.0          19.7          -10.45%
    BenchmarkCopyFat1024      36.5          38.4          +5.21%
    BenchmarkClearFat1024     35.1          35.0          -0.28%
    
    TODO: use for stack frame zeroing
    TODO: REP prefixes are still used for "reverse" copying when src/dst
    regions overlap.  Might be worth fixing.
    
    LGTM=rsc
    R=golang-codereviews, rsc
    CC=golang-codereviews, r
    https://golang.org/cl/81370046

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

https://github.com/golang/go/commit/6c7cbf086c34ebb88311ba12d3a75adcbdce8ac8

元コミット内容

このコミットの目的は、Goランタイムにおけるメモリのコピー（MOVSQ）とゼロクリア（STOSQ）処理において、x86のREPプレフィックスの使用をほとんど排除することです。REPプレフィックスは、繰り返し操作を行うための命令ですが、その起動オーバーヘッドが非常に高いため、特に小さなデータサイズでのパフォーマンスが低下していました。この問題を解決するために、Duff's Deviceという手法を用いて繰り返し処理を行うように変更されました。

ベンチマーク結果は、特に小さなデータサイズ（32バイトから512バイト）において、ゼロクリアとコピーの両方で大幅なパフォーマンス改善を示しています。例えば、BenchmarkClearFat32では77.78%の改善、BenchmarkCopyFat32では65.41%の改善が見られます。しかし、1024バイトのような大きなサイズでは、改善効果は限定的か、わずかに性能が低下するケースもあります。

コミットメッセージには、今後の改善点としてスタックフレームのゼロクリアへの適用や、ソースとデスティネーション領域がオーバーラップする場合のリバースコピーにおけるREPプレフィックスの使用の修正が挙げられています。

変更の背景

Goランタイムは、メモリの確保や解放、ガベージコレクション（GC）の過程で頻繁にメモリのゼロクリアやコピーを行います。これらの操作は、プログラム全体のパフォーマンスに大きな影響を与えます。

従来のGoランタイムでは、x86アーキテクチャにおいて、大量のメモリを効率的に操作するためにREPプレフィックス（REP MOVSQやREP STOSQなど）が使用されていました。これらの命令は、CPUのマイクロコードによって最適化されており、理論的には非常に高いスループットを発揮します。しかし、実際のCPUの挙動には、命令の起動にかかる「起動オーバーヘッド」が存在します。

この起動オーバーヘッドは、特にコピーやゼロクリアの対象となるメモリブロックが小さい場合に顕著な問題となります。例えば、数十バイトから数百バイト程度の小さなオブジェクトの操作では、REP命令の起動オーバーヘッドが実際のデータ転送にかかる時間よりも大きくなり、結果としてパフォーマンスが低下していました。Goのプログラムでは、小さなオブジェクトの割り当てや操作が頻繁に行われるため、このオーバーヘッドが無視できない問題となっていました。

このコミットは、この「小さなサイズでのREP命令の非効率性」という具体的なパフォーマンスボトルネックを解消するために行われました。

前提知識の解説

x86のREPプレフィックスと文字列命令

x86アーキテクチャには、メモリブロックを操作するための「文字列命令（String Instructions）」と呼ばれる特殊な命令群があります。これらは、MOVS（Move String）、STOS（Store String）、CMPS（Compare String）などです。これらの命令は、通常、SI（Source Index）レジスタとDI（Destination Index）レジスタをそれぞれソースとデスティネーションのアドレスとして使用し、CX（Count）レジスタを操作回数として使用します。

REPプレフィックスは、これらの文字列命令と組み合わせて使用することで、CXレジスタがゼロになるまで命令を繰り返し実行する機能を提供します。

  • REP MOVSQ: QはQuadword（8バイト）を意味します。SIが指すアドレスからDIが指すアドレスへ8バイト単位でデータをコピーし、SIとDIをインクリメント（またはデクリメント、DFフラグによる）し、CXをデクリメントします。CXがゼロになるまで繰り返します。
  • REP STOSQ: QはQuadword（8バイト）を意味します。AL/AX/EAX/RAXレジスタの内容をDIが指すアドレスへ8バイト単位でストアし、DIをインクリメント（またはデクリメント）し、CXをデクリメントします。CXがゼロになるまで繰り返します。

パフォーマンス特性: 現代のCPUでは、これらのREP命令はマイクロコードによって実装されており、非常に最適化されています。特に大きなデータブロック（数百バイト以上）の転送においては、高いスループットを発揮し、メモリ帯域幅に近い性能を達成できます。しかし、前述の通り、命令の実行を開始するための「起動オーバーヘッド」が存在します。このオーバーヘッドは、命令のデコード、マイクロコードのロード、内部パイプラインのセットアップなどにかかる時間であり、データサイズが小さい場合には、この固定コストが相対的に大きくなり、結果として非効率になります。

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

Duff's Deviceは、1983年にトム・ダフが開発したC言語のプログラミングテクニックで、ループアンローリング（Loop Unrolling）を手動で実装する非常に巧妙な方法です。これは、switch文のフォールスルー（fall-through）特性とdo-whileループを組み合わせることで実現されます。

動作原理: 通常のループアンローリングでは、ループの本体を複数回記述することで、ループの条件判定やカウンタの更新といったオーバーヘッドを減らします。しかし、ループの反復回数がアンローリングの倍数でない場合、残りの処理をどうするかという問題が生じます。Duff's Deviceは、この「残りの処理」をswitch文のフォールスルーを利用して、メインのアンローリングされたループの途中にジャンプすることで処理します。

例えば、8回アンローリングする場合、count % 8の結果に応じてswitch文が適切なcaseラベルにジャンプします。caseラベルはdo-whileループの内部に配置されており、フォールスルーによって残りの処理が実行された後、通常のアンローリングされたループが続行されます。

アセンブリレベルでの最適化: Duff's Deviceがコンパイルされると、switch文は通常、ジャンプテーブル（jump table）に変換されます。これにより、計算されたインデックスに基づいて直接目的のコードブロックにジャンプでき、連続したif-else文よりも効率的です。ループのオーバーヘッド（条件分岐とカウンタのデクリメント）が大幅に削減されるため、CPUのパイプライン効率が向上し、より多くの命令を連続して実行できるようになります。

現代におけるDuff's Device: 現代のコンパイラは非常に高度であり、自動的にループアンローリングやその他の最適化を適用できます。多くの場合、手動でDuff's Deviceを使用するよりも、コンパイラに任せた方が良い結果が得られます。また、Duff's Deviceはコードの可読性を著しく損なうため、特殊なパフォーマンス要件がない限り、一般的には推奨されません。しかし、このコミットのように、特定の低レベルなランタイムコードやアセンブリレベルでの最適化が必要な場面では、その原理が応用されることがあります。

Goランタイムのメモリ管理

Go言語は、自動ガベージコレクション（GC）を備えており、開発者が手動でメモリを管理する必要がありません。Goランタイムは、メモリの割り当て、ゼロクリア、コピー、解放を効率的に行います。

  • 自動ゼロクリア: Goでは、新しく割り当てられたメモリはデフォルトでゼロ値に初期化されます（例: 整数型は0、ポインタはnil、文字列は""、ブール型はfalse）。これは、未初期化メモリの使用によるバグやセキュリティ脆弱性を防ぐための安全機能です。
  • メモリコピーの最適化: Goランタイムは、パフォーマンスを向上させ、GCの負荷を軽減するために、不要なメモリコピーを最小限に抑えるよう努めます。例えば、スライス間のコピーには組み込みのcopy()関数が最も効率的です。また、大きな配列を値渡しするとコピーが発生するため、ポインタ渡しが推奨されることがあります。

このコミットは、Goランタイムが内部的に行うこれらのメモリ操作の効率を、アセンブリレベルでさらに高めることを目的としています。

技術的詳細

このコミットの主要な変更は、Goコンパイラ（6g、8gはそれぞれamd64と386アーキテクチャ向けのコンパイラ）とランタイムのアセンブリコードにDuff's Deviceの概念を導入し、REPプレフィックスの使用を置き換えることです。

具体的には、以下の新しいアセンブリ命令が導入されました。

  • ADUFFCOPY: メモリコピーのためのDuff's Deviceを呼び出す命令。
  • ADUFFZERO: メモリゼロクリアのためのDuff's Deviceを呼び出す命令。

これらの命令は、Goコンパイラによって生成されるコード内で、特定のサイズのメモリブロック（コミットメッセージのベンチマーク結果から、約128バイト以下の比較的小さなサイズ）のコピーやゼロクリアが必要な場合に選択的に使用されます。

src/cmd/6g/cgen.c および src/cmd/8g/cgen.c (sgen関数)

これらのファイルは、Goコンパイラのコード生成部分であり、構造体や配列などの「fat object」のコピー処理を担当するsgen関数が変更されています。 変更前は、コピーサイズqが4クアッドワード（32バイト）以上の場合にREP MOVSQ（amd64の場合）またはREP MOVSL（386の場合）を使用していました。 変更後は、qが128クアッドワード（amd64で1024バイト、386で512バイト）を超える場合にのみREP命令を使用し、qが4クアッドワード以上128クアッドワード以下の場合は、新しく導入されたADUFFCOPY命令を使用するように変更されています。

ADUFFCOPY命令は、duffcopyというランタイム関数へのジャンプ命令として生成されます。このジャンプ命令のオフセットは、コピーするバイト数qに基づいて計算されます。このオフセットがDuff's Deviceの「マジック定数」と組み合わされ、duffcopyルーチン内の適切な開始点にジャンプすることで、ループアンローリングされたコピー処理が効率的に実行されます。

src/cmd/6g/ggen.c および src/cmd/8g/ggen.c (clearfat関数)

これらのファイルは、Goコンパイラのコード生成部分であり、メモリのゼロクリア処理を担当するclearfat関数が変更されています。 変更前は、ゼロクリアサイズqが4クアッドワード（32バイト）以上の場合にREP STOSQ（amd64の場合）またはREP STOSL（386の場合）を使用していました。 変更後は、qが128クアッドワードを超える場合にのみREP命令を使用し、qが4クアッドワード以上128クアッドワード以下の場合は、新しく導入されたADUFFZERO命令を使用するように変更されています。

ADUFFZERO命令は、duffzeroというランタイム関数へのジャンプ命令として生成されます。ADUFFCOPYと同様に、ゼロクリアするバイト数qに基づいてオフセットが計算され、duffzeroルーチン内の適切な開始点にジャンプすることで、ループアンローリングされたゼロクリア処理が効率的に実行されます。

src/cmd/6l/6.out.h および src/cmd/8l/8.out.h

これらのヘッダーファイルは、Goリンカが使用する命令コードの定義を含んでいます。新しく導入されたADUFFCOPYとADUFFZERO命令が、リンカが認識できるように列挙型に追加されています。

src/liblink/asm6.c および src/liblink/asm8.c

これらのファイルは、Goのアセンブラとリンカがアセンブリ命令を処理する方法を定義しています。ADUFFCOPYとADUFFZERO命令が、リンカの命令テーブルに追加され、それらがyduffという新しいオペランドタイプ（即値32ビット）を持つZcall命令として扱われるように設定されています。特に注目すべきは、リロケーション処理において、p->to.offset（Duff's Deviceのジャンプオフセット）がr->addとしてリロケーションエントリに追加されている点です。これにより、リンカは実行時に正確なジャンプ先アドレスを解決できます。

src/pkg/runtime/asm_386.s および src/pkg/runtime/asm_amd64.s

これらのファイルは、Goランタイムの低レベルアセンブリコードを含んでいます。このコミットの核心部分であり、runtime·duffzeroとruntime·duffcopyという2つの新しいアセンブリ関数が実装されています。

runtime·duffzero (ゼロクリア用Duff's Device)

  • 386版 (asm_386.s): STOSL（Store String Longword、4バイト）命令を128回繰り返す形で記述されています。AXレジスタにはゼロが設定され、DIレジスタが指すメモリを4バイトずつゼロクリアしていきます。コンパイラは、ゼロクリアするバイト数に応じて、このルーチン内の適切なSTOSL命令の開始点にジャンプします。例えば、32バイト（8回STOSL）ゼロクリアしたい場合、STOSL命令が8回実行されるようにジャンプオフセットが計算されます。
  • amd64版 (asm_amd64.s): STOSQ（Store String Quadword、8バイト）命令を128回繰り返す形で記述されています。AXレジスタにはゼロが設定され、DIレジスタが指すメモリを8バイトずつゼロクリアしていきます。同様に、コンパイラはゼロクリアするバイト数に応じて適切な開始点にジャンプします。

runtime·duffcopy (コピー用Duff's Device)

  • 386版 (asm_386.s): MOVL (SI),CX; ADDL $4,SI; MOVL CX,(DI); ADDL $4,DI という4バイトコピーのシーケンスを128回繰り返す形で記述されています。SIレジスタがソース、DIレジスタがデスティネーションを指します。CXレジスタは一時的なデータ転送に使用されます。コンパイラは、コピーするバイト数に応じて、このルーチン内の適切なコピーシーケンスの開始点にジャンプします。
  • amd64版 (asm_amd64.s): MOVQ (SI),CX; ADDQ $8,SI; MOVQ CX,(DI); ADDQ $8,DI という8バイトコピーのシーケンスを128回繰り返す形で記述されています。SIレジスタがソース、DIレジスタがデスティネーションを指します。CXレジスタは一時的なデータ転送に使用されます。同様に、コンパイラはコピーするバイト数に応じて適切な開始点にジャンプします。

注目すべきは、amd64版のduffcopyルーチンに「NOTE: this is equivalent to a sequence of MOVSQ but for some reason that is 3.5x slower than this code. The STOSQ above seem fine, though.」というコメントがある点です。これは、MOVSQ命令の単体実行が、MOVQとADDQを組み合わせた手動のコピーシーケンスよりも遅いという、当時のCPUのマイクロアーキテクチャに起因する興味深いパフォーマンス特性を示唆しています。一方で、STOSQは問題なく機能していると述べられています。

src/pkg/runtime/memmove_test.go

このファイルには、新しいベンチマークテストが追加されています。BenchmarkClearFatXXとBenchmarkCopyFatXXという形式で、様々なサイズの「fat object」（大きな構造体や配列）のゼロクリアとコピーのパフォーマンスを測定するためのテストです。これらのテストは、コミットメッセージに記載されているベンチマーク結果を生成するために使用されました。

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

このコミットのコアとなる変更は、Goコンパイラがメモリのコピーとゼロクリアを行う際に、REPプレフィックス付きの命令を使用する条件を変更し、代わりにDuff's Deviceを呼び出す新しいアセンブリ命令（ADUFFCOPY, ADUFFZERO）を導入した点です。そして、その新しい命令の実体として、Duff's Deviceの原理に基づいたアセンブリルーチン（runtime·duffzero, runtime·duffcopy）がランタイムに追加されました。

具体的な変更箇所は以下のファイルに集中しています。

  • src/cmd/6g/cgen.c (amd64コンパイラ): sgen関数内で、コピーサイズqが4以上128以下の範囲でADUFFCOPYを使用するように変更。

    --- a/src/cmd/6g/cgen.c
+++ b/src/cmd/6g/cgen.c
@@ -1447,10 +1448,16 @@ sgen(Node *n, Node *ns, int64 w)
 	} else {
 		// normal direction
-		if(q >= 4) {
+		if(q > 128) {
 			gconreg(movptr, q, D_CX);
 			gins(AREP, N, N);	// repeat
 			gins(AMOVSQ, N, N);	// MOVQ *(SI)+,*(DI)+
+		} else if (q >= 4) {
+			p = gins(ADUFFCOPY, N, N);
+			p->to.type = D_ADDR;
+			p->to.sym = linksym(pkglookup("duffcopy", runtimepkg));
+			// 14 and 128 = magic constants: see ../../pkg/runtime/asm_amd64.s
+			p->to.offset = 14*(128-q);
 		} else
 		while(q > 0) {
 			gins(AMOVSQ, N, N);	// MOVQ *(SI)+,*(DI)+

  • src/cmd/6g/ggen.c (amd64コンパイラ): clearfat関数内で、ゼロクリアサイズqが4以上128以下の範囲でADUFFZEROを使用するように変更。

    --- a/src/cmd/6g/ggen.c
+++ b/src/cmd/6g/ggen.c
@@ -1088,10 +1088,16 @@ clearfat(Node *nl)
 	savex(D_AX, &ax, &oldax, N, types[tptr]);
 	gconreg(AMOVL, 0, D_AX);
 
-	if(q >= 4) {
+	if(q > 128) {
 		gconreg(movptr, q, D_CX);
 		gins(AREP, N, N);	// repeat
 		gins(ASTOSQ, N, N);	// STOQ AL,*(DI)+
+	} else if(q >= 4) {
+		p = gins(ADUFFZERO, N, N);
+		p->to.type = D_ADDR;
+		p->to.sym = linksym(pkglookup("duffzero", runtimepkg));
+		// 2 and 128 = magic constants: see ../../pkg/runtime/asm_amd64.s
+		p->to.offset = 2*(128-q);
 	} else
 	while(q > 0) {
 		gins(ASTOSQ, N, N);	// STOQ AL,*(DI)+

  • src/pkg/runtime/asm_386.s: runtime·duffzeroとruntime·duffcopyのアセンブリ実装を追加。

    • runtime·duffzero: 128個のSTOSL命令のシーケンス。
    • runtime·duffcopy: 128個のMOVL (SI),CX; ADDL $4,SI; MOVL CX,(DI); ADDL $4,DIシーケンス。

  • src/pkg/runtime/asm_amd64.s: runtime·duffzeroとruntime·duffcopyのアセンブリ実装を追加。

    • runtime·duffzero: 128個のSTOSQ命令のシーケンス。
    • runtime·duffcopy: 128個のMOVQ (SI),CX; ADDQ $8,SI; MOVQ CX,(DI); ADDQ $8,DIシーケンス。

（src/cmd/8g/cgen.c, src/cmd/8g/ggen.c, src/cmd/6g/prog.c, src/cmd/8g/prog.c, src/cmd/6l/6.out.h, src/cmd/8l/8.out.h, src/liblink/asm6.c, src/liblink/asm8.cも関連する変更が含まれますが、上記が主要なロジック変更点です。）

コアとなるコードの解説

コンパイラ側の変更 (cgen.c, ggen.c)

Goコンパイラは、メモリのコピーやゼロクリアが必要なGoのコード（例: 構造体の代入、配列の初期化）をアセンブリ命令に変換します。このコミットでは、その変換ロジックが変更されました。

変更前は、一定サイズ以上のメモリ操作には無条件にREPプレフィックス付きの文字列命令（MOVSQ/STOSQなど）を生成していました。しかし、このコミットにより、メモリサイズqに応じて以下の分岐ロジックが適用されます。

  1. q > 128 (クアッドワード/ロングワード): この場合、メモリサイズが十分に大きいため、REPプレフィックスの起動オーバーヘッドが相対的に小さくなります。したがって、引き続きREPプレフィックス付きのMOVSQ/STOSQ命令が使用されます。これは、REP命令が大規模なデータ転送において高いスループットを発揮するためです。

  2. 4 <= q <= 128 (クアッドワード/ロングワード): この範囲のメモリサイズは、REPプレフィックスの起動オーバーヘッドが問題となる「中程度のサイズ」に該当します。ここで、コンパイラは新しい擬似命令であるADUFFCOPYまたはADUFFZEROを生成します。

    • gins(ADUFFCOPY, N, N): ADUFFCOPY命令を生成します。
    • p->to.sym = linksym(pkglookup("duffcopy", runtimepkg)): この命令がruntimeパッケージ内のduffcopy関数（アセンブリルーチン）を指すようにシンボルを設定します。
    • p->to.offset = 14*(128-q) (amd64 cgen.c の例): ここがDuff's Deviceの核心部分です。duffcopyルーチン内のどこにジャンプするかを決定するオフセットを計算します。14や2といった定数は、アセンブリルーチン内の各命令のバイトサイズと、Duff's Deviceのアンローリング単位（この場合は128）に基づいた「マジック定数」です。128-qは、残りの処理回数に相当し、これによりduffcopyルーチン内の適切な開始点にジャンプし、必要な回数だけコピー/ゼロクリア操作が実行されます。

  3. q < 4 (クアッドワード/ロングワード): この場合、メモリサイズが非常に小さいため、ループアンローリングの恩恵も小さく、単純な単一のMOVSQ/STOSQ命令を繰り返し実行する従来のwhileループが使用されます。これは、Duff's Deviceのセットアップコストすらもオーバーヘッドとなる可能性があるためです。

ランタイムアセンブリ側の変更 (asm_386.s, asm_amd64.s)

runtime·duffzeroとruntime·duffcopyは、Duff's Deviceの原理に基づいて手動でループアンローリングされたアセンブリルーチンです。

  • runtime·duffzero: このルーチンは、STOSL（386）またはSTOSQ（amd64）命令を128回連続して記述することで、メモリのゼロクリアをアンローリングしています。コンパイラが生成したADUFFZERO命令は、このルーチン内の特定のSTOS命令に直接ジャンプします。例えば、32バイト（amd64では4クアッドワード）をゼロクリアする場合、duffzeroルーチンの末尾から4番目のSTOSQ命令にジャンプし、そこからフォールスルーで4回のSTOSQが実行され、最後にRETで戻ります。これにより、ループの条件判定やジャンプのオーバーヘッドなしに、必要な回数だけゼロクリアが実行されます。

  • runtime·duffcopy: このルーチンは、MOVとADD命令のシーケンスを128回連続して記述することで、メモリコピーをアンローリングしています。MOVSQ/MOVSL命令の代わりに、MOVQ/L (SI),CX; ADDQ/L $8/4,SI; MOVQ/L CX,(DI); ADDQ/L $8/4,DIというシーケンスを使用している点が重要です。これは、コミットメッセージのコメントにもあるように、当時のCPUではMOVSQ単体よりもこの手動シーケンスの方が高速であったためです。duffzeroと同様に、コンパイラが生成したADUFFCOPY命令は、このルーチン内の特定のコピーシーケンスに直接ジャンプし、必要な回数だけコピーが実行されます。

この変更により、特にGoランタイムが頻繁に操作する小さなオブジェクト（例: スタックフレームの初期化、小さな構造体のコピー）において、REP命令の起動オーバーヘッドを回避し、より効率的なメモリ操作を実現しています。ベンチマーク結果が示すように、この最適化は顕著なパフォーマンス向上をもたらしました。

関連リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • このコミットのChange-ID: 81370046 (GoのコードレビューシステムGerritでのID)

参考にした情報源リンク