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

このコミットは、Go言語のコンパイラ（cmd/cc）にPREFETCHという新しい組み込み関数を追加するものです。これにより、ガベージコレクション（GC）中にメモリのアドレスを事前にフェッチ（プリフェッチ）することが可能になり、GC処理の効率が向上します。特にGC負荷の高いワークロードにおいて、最大5%の速度向上が見込まれます。

コミット

cmd/cc: PREFETCH組み込み関数を追加（SET, USEDと同様）

この変更により、ガベージコレクション中に今後アクセスされるメモリアドレスのプリフェッチをインライン化できるようになります。これにより、レジスタのフラッシュ、関数呼び出し、レジスタのリロードといったオーバーヘッドが不要になります。ガベージコレクションが頻繁に発生するワークロードにおいて、これは5%の速度向上をもたらします。

Fixes #3493.

R=dvyukov, ken, r, dave CC=golang-dev https://golang.org/cl/5990066

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

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

元コミット内容

commit d42495aa803b2efc3c58317b79f99e723c1b5195
Author: Russ Cox <rsc@golang.org>
Date:   Wed May 2 16:22:56 2012 -0400

    cmd/cc: add PREFETCH built-in (like SET, USED)
    
    This makes it possible to inline the prefetch of upcoming
    memory addresses during garbage collection, instead of
    needing to flush registers, make a function call, and
    reload registers.  On garbage collection-heavy workloads,
    this results in a 5% speedup.
    
    Fixes #3493.
    
    R=dvyukov, ken, r, dave
    CC=golang-dev
    https://golang.org/cl/5990066

変更の背景

この変更の背景には、Go言語のガベージコレクション（GC）のパフォーマンス最適化があります。GCは、不要になったメモリを自動的に解放し、再利用可能にするプロセスです。しかし、GCが実行される際には、プログラムの実行が一時的に停止したり（Stop-the-World）、メモリへのアクセスパターンが変化したりすることで、パフォーマンスのボトルネックとなることがあります。

特に、GCがメモリをスキャンする際、今後アクセスされる可能性のあるメモリアドレスを事前にCPUのキャッシュに読み込んでおく「プリフェッチ」は、メモリレイテンシを隠蔽し、全体的な処理速度を向上させる有効な手段です。しかし、従来のGoコンパイラでは、プリフェッチ命令を直接生成するための組み込み関数がありませんでした。プリフェッチを行うためには、通常、関数呼び出しを介してランタイムのヘルパー関数を呼び出す必要がありました。この関数呼び出しには、レジスタの保存（フラッシュ）と復元（リロード）といったオーバーヘッドが伴い、特にGCのように頻繁に実行される処理では、このオーバーヘッドが無視できないものとなっていました。

このコミットは、このようなオーバーヘッドを排除し、プリフェッチ命令をコンパイラが直接インラインで生成できるようにすることで、GCの効率を向上させることを目的としています。これにより、GCがメモリをスキャンする際のデータアクセスが高速化され、結果としてGC全体の実行時間が短縮され、アプリケーションの応答性が向上します。

前提知識の解説

このコミットを理解するためには、以下の技術的な概念を把握しておく必要があります。

1. CPUキャッシュとメモリ階層:

   • 現代のCPUは、メインメモリ（RAM）よりもはるかに高速な小容量のメモリであるキャッシュ（L1, L2, L3など）を持っています。
   • CPUがデータにアクセスする際、まずキャッシュを調べ、データがあれば高速に取得できます（キャッシュヒット）。
   • キャッシュにデータがない場合（キャッシュミス）、メインメモリからデータを読み込む必要があり、これはキャッシュヒットに比べて数百倍もの時間がかかります。
   • このキャッシュミスによる性能低下を「メモリレイテンシ」と呼びます。

2. プリフェッチ（Prefetching）:

   • プリフェッチとは、CPUが将来必要になると予測されるデータを、実際に必要になる前にメインメモリからキャッシュに読み込んでおく技術です。
   • これにより、データが実際に必要になった時には既にキャッシュに存在している可能性が高まり、メモリレイテンシを隠蔽し、プログラムの実行速度を向上させることができます。
   • プリフェッチは、ソフトウェア（コンパイラやプログラマによる明示的な指示）またはハードウェア（CPUの予測ロジック）によって行われます。
   • Intel x86アーキテクチャでは、PREFETCH命令（例: PREFETCHT0, PREFETCHT1, PREFETCHT2, PREFETCHNTAなど）が提供されており、プログラマが明示的にプリフェッチを指示できます。これらの命令は、指定されたメモリアドレスのデータをどのキャッシュレベルに読み込むか、またはキャッシュに影響を与えないように読み込むか（Non-Temporal Hint）などを制御します。

3. ガベージコレクション（Garbage Collection, GC）:

   • Go言語は自動メモリ管理を採用しており、ガベージコレクタが不要なメモリを自動的に回収します。
   • GoのGCは、主に「マーク＆スイープ」アルゴリズムをベースにしています。このプロセスでは、まず到達可能なオブジェクトをマークし、次にマークされていない（到達不可能な）オブジェクトを解放します。
   • GCの「マーク」フェーズでは、ヒープ上のオブジェクトグラフを辿り、大量のメモリアドレスにアクセスします。このアクセスパターンは、しばしばキャッシュミスを引き起こし、GCのパフォーマンスに影響を与えます。

4. Goコンパイラ（cmd/cc）と組み込み関数:

   • Go言語のツールチェインには、Goソースコードを機械語に変換するコンパイラが含まれています。cmd/ccは、GoのCコンパイラであり、Goのランタイムや標準ライブラリの一部をコンパイルするために使用されます。
   • Goコンパイラには、特定の最適化や低レベルな操作を可能にするための「組み込み関数（built-in functions）」が存在します。これらは通常の関数呼び出しとは異なり、コンパイラによって特別な処理が施され、直接インラインで機械語命令に変換されることが多いです。
   • コミットメッセージで言及されているSETやUSEDは、Goコンパイラが内部的に使用する組み込み関数の例であり、変数の使用状況をコンパイラに伝えるなどの目的で使われます。

技術的詳細

このコミットの技術的詳細は、Goコンパイラのフロントエンド（字句解析、構文解析）とバックエンド（コード生成、最適化）の両方にわたる変更を含んでいます。

1. 字句解析器（Lexer）の変更:

   • src/cmd/cc/lex.cが変更され、新しいキーワードPREFETCHが認識されるようになりました。これにより、GoのCコンコンパイラがPREFETCHというキーワードをトークンとして扱えるようになります。

2. 構文解析器（Parser）の変更:

   • src/cmd/cc/cc.y (Yacc/Bisonの入力ファイル) が変更され、PREFETCHキーワードを伴う新しい文法規則が追加されました。具体的には、PREFETCH(zelist);という形式のステートメントが構文的に有効になります。
   • この文法規則は、OPREFETCHという新しい抽象構文木（AST）ノードを生成するように定義されています。zelistはプリフェッチ対象のアドレスを表す式です。
   • src/cmd/cc/y.tab.cとsrc/cmd/cc/y.tab.hは、cc.yの変更に伴ってBisonによって再生成されたファイルであり、LPREFETCHという新しいトークンが追加され、構文解析テーブルが更新されています。

3. ASTノードの追加:

   • src/cmd/cc/cc.hにOPREFETCHという新しいオペレーションコードが追加されました。これは、コンパイラの内部表現でプリフェッチ操作を表すために使用されます。

4. コード生成の変更:

   • src/cmd/cc/pgen.cが変更され、OPREFETCHノードが処理されるようになりました。OPREFETCHノードが検出されると、gprefetchという新しいコード生成関数が呼び出されます。
   • src/cmd/{5c,6c,8c}/txt.c (各アーキテクチャ向けコードジェネレータ) にgprefetch関数が追加されました。この関数は、OPREFETCHノードから受け取ったアドレスに対して、実際のCPUプリフェッチ命令（例: x86のPREFETCHNTA）を生成します。
     • 5c (ARM): gprefetchは現在何も生成しません（コメントアウトされているか、将来の実装を待つ状態）。これは、ARMアーキテクチャにはx86のような直接的なプリフェッチ命令がないか、または異なるアプローチが必要なためと考えられます。
     • 6c (AMD64): gprefetchはAPREFETCHNTA命令を生成します。これは、Non-Temporal Hint付きのプリフェッチ命令で、キャッシュを汚染せずにデータを読み込むことを示唆します。GCスキャンでは、一度しかアクセスしないデータが多いため、キャッシュを汚染しないこの命令が適しています。
     • 8c (x86): gprefetchはAPREFETCHNTA命令を生成します。

5. 最適化パスの変更:

   • src/cmd/{6c,8c}/peep.c (peephole optimizer) および src/cmd/{6c,8c}/reg.c (register allocator) が変更され、新しいプリフェッチ命令（APREFETCHT0, APREFETCHT1, APREFETCHT2, APREFETCHNTA）が認識されるようになりました。これにより、これらの最適化パスがプリフェッチ命令を正しく扱い、レジスタ割り当てや命令の並べ替えを行う際に、プリフェッチ命令のセマンティクスを損なわないようにします。

6. ランタイムの変更（削除）:

   • src/pkg/runtime/arch_386.h, src/pkg/runtime/arch_amd64.h, src/pkg/runtime/arch_arm.h および src/pkg/runtime/asm_386.s, src/pkg/runtime/asm_amd64.s から、既存のプリフェッチ関連の定義やアセンブリコードが削除されています。これは、新しい組み込み関数によるインライン化が可能になったため、ランタイム側のヘルパー関数が不要になったことを示唆しています。

この一連の変更により、GoのCコンパイラは、PREFETCH(addr)という構文を認識し、それを直接対応するCPUのプリフェッチ命令に変換できるようになります。これにより、GCがメモリをスキャンする際に、Goランタイムが明示的にプリフェッチ命令を挿入できるようになり、関数呼び出しのオーバーヘッドなしにキャッシュ効率を向上させることができます。

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

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

1. src/cmd/cc/cc.y:

   • GoのCコンパイラの構文定義ファイル。
   • LPREFETCHトークンが追加され、PREFETCH ( zelist ) ;という新しい文法規則が定義されています。
   • この規則がマッチすると、new(OPREFETCH, $3, Z)というASTノードが生成されます。これは、OPREFETCHという操作コードを持つ新しいノードを作成し、その子ノードとしてzelist（プリフェッチ対象のアドレスを表す式）を設定することを意味します。

   --- a/src/cmd/cc/cc.y
   +++ b/src/cmd/cc/cc.y
   @@ -93,7 +93,7 @@
    %token	<sval>	LSTRING LLSTRING
    %token		LAUTO LBREAK LCASE LCHAR LCONTINUE LDEFAULT LDO
    %token		LDOUBLE LELSE LEXTERN LFLOAT LFOR LGOTO
   -%token	LIF LINT LLONG LREGISTER LRETURN LSHORT LSIZEOF LUSED
   +%token	LIF LINT LLONG LPREFETCH LREGISTER LRETURN LSHORT LSIZEOF LUSED
    %token	LSTATIC LSTRUCT LSWITCH LTYPEDEF LTYPESTR LUNION LUNSIGNED
    %token	LWHILE LVOID LENUM LSIGNED LCONSTNT LVOLATILE LSET LSIGNOF
    %token	LRESTRICT LINLINE
   @@ -535,6 +535,10 @@ ulstmnt:
    	{
    		$$ = new(OUSED, $3, Z);
    	}
   +|\tLPREFETCH '(' zelist ')' ';'
   +\t{
   +\t\t$$ = new(OPREFETCH, $3, Z);
   +\t}\
    |\tLSET '(' zelist ')' ';'
    	{
    		$$ = new(OSET, $3, Z);
   

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

   • ASTノードから中間コードを生成する部分。
   • OPREFETCHノードが処理される際に、gprefetch(n)関数が呼び出されるように変更されています。

   --- a/src/cmd/cc/pgen.c
   +++ b/src/cmd/cc/pgen.c
   @@ -528,6 +528,7 @@ loop:
    
    	case OSET:
    	case OUSED:
   +	case OPREFETCH:
    	\tusedset(n->left, o);
    	\tbreak;
    	}
   @@ -542,6 +543,10 @@ usedset(Node *n, int o)\n     	\treturn;\n     	}\n     	complex(n);\n    +\tif(o == OPREFETCH) {\n    +\t\tgprefetch(n);\n    +\t\treturn;\n    +\t}\
    	switch(n->op) {\
    	case OADDR:\t/* volatile */\
    	\tgins(ANOP, n, Z);\
   

3. src/cmd/{6c,8c}/txt.c:

   • AMD64 (6c) および x86 (8c) アーキテクチャ向けのコードジェネレータ。
   • gprefetch関数が追加され、プリフェッチ対象のアドレスからNodeを受け取り、APREFETCHNTA命令を生成しています。regallocとregfreeはレジスタの割り当てと解放を行っています。

   --- a/src/cmd/6c/txt.c
   +++ b/src/cmd/6c/txt.c
   @@ -1502,6 +1502,18 @@ gpseudo(int a, Sym *s, Node *n)\
    	\tpc--;
    }\
    \
   +void\
   +gprefetch(Node *n)\
   +{\
   +\tNode n1;\
   +\t\
   +\tregalloc(&n1, n, Z);\
   +\tgmove(n, &n1);\
   +\tn1.op = OINDREG;\
   +\tgins(APREFETCHNTA, &n1, Z);\
   +\tregfree(&n1);\
   +}\
   +\
    int\
    sconst(Node *n)\
    {\
   

   （src/cmd/8c/txt.cも同様の変更）

コアとなるコードの解説

上記の変更は、GoコンパイラがPREFETCHという新しい組み込み関数をどのように処理するかを示しています。

• src/cmd/cc/cc.yの変更:

  • これは、GoのCコンパイラがPREFETCHキーワードを認識し、それを構文木の一部として表現できるようにするための第一歩です。LPREFETCHは字句解析器によって生成されるトークンであり、zelistはプリフェッチしたいメモリアドレスを表す式です。
  • new(OPREFETCH, $3, Z)は、コンパイラの内部表現である抽象構文木（AST）に、OPREFETCHという新しい種類の操作ノードを作成します。$3はzelistに対応し、プリフェッチ対象のアドレス情報がこのノードに格納されます。Zはnullを表し、このノードには右の子ノードがないことを示します。

• src/cmd/cc/pgen.cの変更:

  • pgen.cは、構文解析器が生成したASTを巡回し、各ノードに対応する中間コードを生成する役割を担っています。
  • case OPREFETCH:の追加により、コンパイラはOPREFETCHノードを見つけると、特別な処理を行うようになります。
  • usedset(n->left, o);は、プリフェッチ対象のアドレス式が使用されていることをコンパイラに通知し、不要なコード削除を防ぐためのものです。
  • if(o == OPREFETCH) { gprefetch(n); return; }の部分が重要です。これは、OPREFETCHノードの場合に、gprefetchという関数を呼び出して、実際のプリフェッチ命令を生成するように指示しています。これにより、プリフェッチ操作がコンパイラのバックエンドに引き渡されます。

• src/cmd/{6c,8c}/txt.cのgprefetch関数:

  • この関数は、特定のCPUアーキテクチャ（AMD64とx86）向けに、実際の機械語命令を生成する部分です。
  • regalloc(&n1, n, Z);は、プリフェッチ対象のアドレスを保持するための一時的なレジスタを割り当てます。
  • gmove(n, &n1);は、プリフェッチ対象のアドレスをそのレジスタに移動します。
  • n1.op = OINDREG;は、レジスタの内容が指すメモリアドレスを操作対象とすることを示します。
  • gins(APREFETCHNTA, &n1, Z);が最も重要な部分です。これは、APREFETCHNTAというアセンブリ命令を生成するようコンパイラに指示します。APREFETCHNTAは、Intel/AMDプロセッサで利用可能なプリフェッチ命令の一つで、指定されたアドレスのデータをキャッシュに読み込みますが、キャッシュの他のデータを追い出す可能性を最小限に抑える（Non-Temporal Hint）ように動作します。これは、GCスキャンで一度しかアクセスしない可能性のあるデータに対して特に有効です。
  • regfree(&n1);は、使用した一時レジスタを解放します。

これらの変更により、GoのCコンパイラは、ソースコード中のPREFETCH(addr)という記述を、対応するCPUのプリフェッチ命令に直接変換できるようになります。これにより、GCがメモリをスキャンする際に、関数呼び出しのオーバーヘッドなしに、効率的にデータをキャッシュに読み込むことが可能になり、GCのパフォーマンスが向上します。

関連リンク

• Go Issue #3493: cmd/cc: add PREFETCH built-in (like SET, USED) - このコミットが解決したGoのIssueトラッカーのエントリ。
• Go Code Review 5990066: cmd/cc: add PREFETCH built-in (like SET, USED) - この変更のコードレビューページ。

参考にした情報源リンク

• CPU Prefetching:
  • Intel 64 and IA-32 Architectures Software Developer's Manuals (特にVolume 2A: Instruction Set Reference, A-M の PREFETCHh 命令に関する記述)
  • AMD64 Architecture Programmer's Manual Volume 3: General-Purpose and System Instructions (特にPREFETCH命令に関する記述)
• Go Garbage Collection:
  • Go's Garbage Collector: A Comprehensive Guide (Go 1.5以降のGCに関する公式ブログ記事)
  • The Go Programming Language Specification - Built-in functions (Go言語の組み込み関数に関する公式仕様)
• Compiler Design (Lexing, Parsing, Code Generation):
  • Compilers: Principles, Techniques, and Tools (Dragon Book) (コンパイラ設計の古典的な教科書)
  • Bison Manual (Yacc/Bisonの構文定義に関する情報)