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

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

このコミットは、Goランタイムのガベージコレクション（GC）にメモリプリフェッチ機能を追加するものです。これにより、GCのパフォーマンス、特にポインタ走査の効率が向上し、全体的なアプリケーションの実行速度が改善されます。

コミット

  • コミットインデックス: 12851
  • コミットハッシュ: f09e63a2a09bfb740205a98d7995bd744e225fb8
  • Author: Dmitriy Vyukov dvyukov@google.com
  • Date: Sat Apr 7 17:02:44 2012 +0400

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

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

元コミット内容

runtime: add memory prefetching to GC

benchmark                              old ns/op    new ns/op    delta

garbage.BenchmarkParser               4448988000   4370531000   -1.76%
garbage.BenchmarkParser-2             4086045000   4023083000   -1.54%
garbage.BenchmarkParser-4             3677365000   3667020000   -0.28%
garbage.BenchmarkParser-8             3517253000   3543946000   +0.76%
garbage.BenchmarkParser-16            3506562000   3512518000   +0.17%

garbage.BenchmarkTree                  494435529    505784058   +2.30%
garbage.BenchmarkTree-2                499652705    502774823   +0.62%
garbage.BenchmarkTree-4                468482117    465713352   -0.59%
garbage.BenchmarkTree-8                488533235    482287000   -1.28%
garbage.BenchmarkTree-16               507835176    500654882   -1.41%

garbage.BenchmarkTree2                  31453900     28804600   -8.42%
garbage.BenchmarkTree2-2                21440600     19065800  -11.08%
garbage.BenchmarkTree2-4                10982000     10009100   -8.86%
garbage.BenchmarkTree2-8                 7544700      6479800  -14.11%
garbage.BenchmarkTree2-16                7049500      6163200  -12.57%

garbage.BenchmarkParserPause           135815000    125360666   -7.70%
garbage.BenchmarkParserPause-2          92691523     84365476   -8.98%
garbage.BenchmarkParserPause-4          53392190     46995809  -11.98%
garbage.BenchmarkParserPause-8          36059523     30998900  -14.03%
garbage.BenchmarkParserPause-16         30174300     27613350   -8.49%

garbage.BenchmarkTreePause              20969784     22568102   +7.62%
garbage.BenchmarkTreePause-2            20215875     20975130   +3.76%
garbage.BenchmarkTreePause-4            17240709     17180666   -0.35%
garbage.BenchmarkTreePause-8            18196386     18205870   +0.05%
garbage.BenchmarkTreePause-16           20621158     20486867   -0.65%

garbage.BenchmarkTree2Pause            173992142    159995285   -8.04%
garbage.BenchmarkTree2Pause-2          131281904    118013714  -10.11%
garbage.BenchmarkTree2Pause-4           93484952     85092666   -8.98%
garbage.BenchmarkTree2Pause-8           88950523     77340809  -13.05%
garbage.BenchmarkTree2Pause-16          86071238     76557952  -11.05%

garbage.BenchmarkParserLastPause       327247000    288205000  -11.93%
garbage.BenchmarkParserLastPause-2     217039000    187336000  -13.69%
garbage.BenchmarkParserLastPause-4     119722000    105069000  -12.24%
garbage.BenchmarkParserLastPause-8      70806000     64755000   -8.55%
garbage.BenchmarkParserLastPause-16     62813000     53486000  -14.85%

garbage.BenchmarkTreeLastPause          28420000     29735000   +4.63%
garbage.BenchmarkTreeLastPause-2        23514000     25427000   +8.14%
garbage.BenchmarkTreeLastPause-4        21773000     19548000  -10.22%
garbage.BenchmarkTreeLastPause-8        24072000     24046000   -0.11%
garbage.BenchmarkTreeLastPause-16       25149000     25291000   +0.56%

garbage.BenchmarkTree2LastPause        314491000    287988000   -8.43%
garbage.BenchmarkTree2LastPause-2      214363000    190616000  -11.08%
garbage.BenchmarkTree2LastPause-4      109778000    100052000   -8.86%
garbage.BenchmarkTree2LastPause-8       75390000     64753000  -14.11%
garbage.BenchmarkTree2LastPause-16      70333000     61484000  -12.58%

FTR, below are result with the empty prefetch function,
that is, single RET but no real prefetching.
It suggests that inlinable PREFETCH is worth pursuing.

benchmark                              old ns/op    new ns/op    delta

garbage.BenchmarkParser               4448988000   4560488000   +2.51%
garbage.BenchmarkParser-2             4086045000   4129728000   +1.07%
garbage.BenchmarkParser-4             3677365000   3728672000   +1.40%
garbage.BenchmarkParser-8             3517253000   3583968000   +1.90%
garbage.BenchmarkParser-16            3506562000   3591414000   +2.42%

garbage.BenchmarkTree                  494435529    499580882   +1.04%
garbage.BenchmarkTree-4                468482117    467387294   -0.23%
garbage.BenchmarkTree-8                488533235    478311117   -2.09%
garbage.BenchmarkTree-2                499652705    499324235   -0.07%
garbage.BenchmarkTree-16               507835176    502005705   -1.15%

garbage.BenchmarkTree2                  31453900     33296800   +5.86%
garbage.BenchmarkTree2-2                21440600     22466400   +4.78%
garbage.BenchmarkTree2-4                10982000     11402700   +3.83%
garbage.BenchmarkTree2-8                 7544700      7476500   -0.90%
garbage.BenchmarkTree2-16                7049500      7338200   +4.10%

garbage.BenchmarkParserPause           135815000    139529142   +2.73%
garbage.BenchmarkParserPause-2          92691523     95229190   +2.74%
garbage.BenchmarkParserPause-4          53392190     53083476   -0.58%
garbage.BenchmarkParserPause-8          36059523     34594800   -4.06%
garbage.BenchmarkParserPause-16         30174300     30063300   -0.37%

garbage.BenchmarkTreePause              20969784     21866920   +4.28%
garbage.BenchmarkTreePause-2            20215875     20731125   +2.55%
garbage.BenchmarkTreePause-4            17240709     17275837   +0.20%
garbage.BenchmarkTreePause-8            18196386     17898777   -1.64%
garbage.BenchmarkTreePause-16           20621158     20662772   +0.20%

garbage.BenchmarkTree2Pause            173992142    184336857   +5.95%
garbage.BenchmarkTree2Pause-2          131281904    138005714   +5.12%
garbage.BenchmarkTree2Pause-4           93484952     98449238   +5.31%
garbage.BenchmarkTree2Pause-8           88950523     89286095   +0.38%
garbage.BenchmarkTree2Pause-16          86071238     89568666   +4.06%

garbage.BenchmarkParserLastPause       327247000    342189000   +4.57%
garbage.BenchmarkParserLastPause-2     217039000    217224000   +0.09%
garbage.BenchmarkParserLastPause-4     119722000    121327000   +1.34%
garbage.BenchmarkParserLastPause-8      70806000     71941000   +1.60%
garbage.BenchmarkParserLastPause-16     62813000     60166000   -4.21%

garbage.BenchmarkTreeLastPause          28420000     27840000   -2.04%
garbage.BenchmarkTreeLastPause-2        23514000     27390000  +16.48%
garbage.BenchmarkTreeLastPause-4        21773000     21414000   -1.65%
garbage.BenchmarkTreeLastPause-8        24072000     21705000   -9.83%
garbage.BenchmarkTreeLastPause-16       25149000     23932000   -4.84%

garbage.BenchmarkTree2LastPause        314491000    332894000   +5.85%
garbage.BenchmarkTree2LastPause-2      214363000    224611000   +4.78%
garbage.BenchmarkTree2LastPause-4      109778000    113976000   +3.82%
garbage.BenchmarkTree2LastPause-8       75390000     67223000  -10.83%
garbage.BenchmarkTree2LastPause-16      70333000     73216000   +4.10%

R=golang-dev, rsc
CC=golang-dev
https://golang.org/cl/5991057

変更の背景

Go言語のランタイムにおけるガベージコレクション（GC）は、アプリケーションのパフォーマンスに大きな影響を与えます。GCの主要なフェーズの一つに、到達可能なオブジェクトをマークする「マークフェーズ」があります。このフェーズでは、GCはヒープ上のオブジェクトを走査し、ポインタをたどって参照されているオブジェクトを識別します。

この走査処理は、メモリ上のデータにランダムにアクセスすることが多く、CPUのキャッシュミスを頻繁に引き起こす可能性があります。キャッシュミスが発生すると、CPUはメインメモリからデータを読み込むために長い時間を待機する必要があり、これがGCの実行時間、ひいてはアプリケーション全体のレイテンシ（特にGC一時停止時間）を増加させる要因となります。

このコミットの背景には、GCの効率を改善し、特にポインタ走査におけるメモリアクセスのボトルネックを解消するという目的があります。メモリプリフェッチは、CPUが将来必要とするであろうデータを事前にキャッシュに読み込んでおくことで、このボトルネックを緩和する技術です。

コミットメッセージに含まれるベンチマーク結果は、この変更が特にBenchmarkTree2やBenchmarkParserPauseといった、GCのポーズ時間や全体のスループットに影響を与えるシナリオで顕著な改善をもたらしていることを示しています。これは、GCが大量のポインタを走査する際に、プリフェッチが効果的に機能していることを裏付けています。

前提知識の解説

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

ガベージコレクションは、プログラムが動的に確保したメモリ領域のうち、もはやどの部分からも参照されなくなった（到達不可能になった）ものを自動的に解放する仕組みです。これにより、プログラマは手動でのメモリ管理から解放され、メモリリークやダングリングポインタといった問題のリスクを低減できます。

Go言語のGCは、並行マーク・スイープ方式を採用しています。これは、アプリケーションの実行と並行してGCのマークフェーズ（到達可能なオブジェクトを識別するフェーズ）を実行し、GCによるアプリケーションの一時停止（STW: Stop The World）時間を最小限に抑えることを目指しています。

GCのマークフェーズでは、ルート（グローバル変数、スタック、レジスタなど）から始まり、そこから参照されているオブジェクトを再帰的にたどってマークしていきます。このポインタのたどり方は、メモリ上の連続した領域ではなく、散在したオブジェクトへのアクセスとなるため、キャッシュ効率が悪くなりがちです。

メモリプリフェッチ (Memory Prefetching)

メモリプリフェッチとは、CPUが将来必要と予測されるデータを、実際に必要になる前にメインメモリからキャッシュメモリに読み込んでおく最適化技術です。

  • CPUキャッシュ: CPUはメインメモリよりもはるかに高速な小容量のキャッシュメモリ（L1, L2, L3キャッシュなど）を持っています。CPUがデータにアクセスする際、まずキャッシュを調べ、データがあれば高速にアクセスできます（キャッシュヒット）。データがなければメインメモリから読み込む必要があり、これはキャッシュミスと呼ばれ、数百サイクルから数千サイクルの遅延が発生する可能性があります。
  • キャッシュミスとパフォーマンス: プログラムが頻繁にキャッシュミスを起こすと、CPUはデータの到着を待つ「ストール」状態になり、全体のパフォーマンスが低下します。
  • プリフェッチの目的: プリフェッチは、このキャッシュミスによる遅延を隠蔽することを目的としています。データがキャッシュに事前に読み込まれていれば、CPUがそのデータにアクセスする際にはキャッシュヒットとなり、高速に処理を続行できます。
  • プリフェッチ命令: 多くのCPUアーキテクチャ（x86のPREFETCH命令など）は、ソフトウェアから明示的にプリフェッチを指示するための命令を提供しています。これらの命令は、指定されたメモリアドレスのデータをキャッシュに読み込むようCPUにヒントを与えます。ただし、プリフェッチはあくまでヒントであり、CPUが必ずしもその通りに実行するとは限りません。また、誤ったプリフェッチはキャッシュを汚染し、かえってパフォーマンスを悪化させる可能性もあります。

Goランタイム

Goランタイムは、Goプログラムの実行を管理する低レベルのシステムです。これには、スケジューラ（ゴルーチンの管理）、メモリ割り当て、ガベージコレクション、システムコールインターフェースなどが含まれます。GCはGoランタイムの重要なコンポーネントであり、Goプログラムのメモリ管理を自動化しています。

scanblock関数

GoのGCにおいて、scanblock関数は、特定のメモリブロック（ヒープ上のオブジェクトの一部）を走査し、その中に含まれるポインタを識別して、参照先のオブジェクトをマークする役割を担います。この関数はGCのマークフェーズ中に繰り返し呼び出され、ヒープ全体を効率的に走査するために並行して実行されることもあります。scanblockの効率は、GCのマークフェーズ全体のパフォーマンスに直結します。

技術的詳細

このコミットの核心は、GoランタイムのGCにおけるメモリ走査のホットパスに、CPUのプリフェッチ命令を導入した点にあります。具体的には、src/pkg/runtime/mgc0.cファイル内のscanblock関数にPREFETCH(obj);という行が追加されました。

scanblock関数は、GCのマークフェーズ中にオブジェクトのポインタをたどる際に呼び出されます。この関数は、メモリブロック内の各オブジェクトを検査し、それがポインタを含むオブジェクトであれば、そのポインタが指す先をマーク対象としてキューに入れます。この処理は、メモリ上の連続した領域を順次アクセスするのではなく、ポインタが指す先のメモリ位置にジャンプすることが多いため、CPUキャッシュの効率が低下しやすい特性があります。

PREFETCH(obj);命令は、現在処理しているオブジェクトobjが指す先のメモリ領域を、CPUが将来アクセスする可能性が高いと予測し、事前にキャッシュに読み込むようヒントを与えます。これにより、実際にそのポインタをたどってデータにアクセスする際に、データが既にキャッシュに存在している可能性が高まり、キャッシュミスによる遅延を削減できます。

コミットメッセージに示されているベンチマーク結果は、この変更がもたらした具体的なパフォーマンス改善を示しています。

  • garbage.BenchmarkTree2: このベンチマークは、ツリー構造のようなポインタが複雑に絡み合うデータ構造のGC性能を測定していると考えられます。プリフェッチ導入後、ns/op（操作あたりのナノ秒）が大幅に減少しており、最大で約14%の改善が見られます。これは、プリフェッチがポインタのたどり方を効率化し、キャッシュミスを減らした結果と推測されます。
  • garbage.BenchmarkParserPause および garbage.BenchmarkTree2Pause: これらのベンチマークは、GCの一時停止時間（ポーズ時間）を測定しています。プリフェッチの導入により、これらのポーズ時間も大幅に短縮されており、最大で約14%の改善が見られます。GCのポーズ時間はアプリケーションの応答性に直接影響するため、この改善は非常に重要です。
  • garbage.BenchmarkParserLastPause: GCの最後のポーズ時間を測定するベンチマークでも、最大で約14.85%の改善が見られます。

一方で、garbage.BenchmarkTreeやgarbage.BenchmarkTreePauseなど、一部のベンチマークではわずかなパフォーマンス低下（+のデルタ）が見られるものもあります。これは、プリフェッチが常に効果的であるとは限らず、場合によっては余計なキャッシュラインを読み込んだり、キャッシュを汚染したりするオーバーヘッドが発生する可能性があるためです。しかし、全体としては、特にポーズ時間の短縮において顕著な効果を発揮していることがわかります。

コミットメッセージの後半には、「empty prefetch function」でのベンチマーク結果も示されています。これは、プリフェッチ命令自体は存在するが、実際には何もプリフェッチしない（例えば、単にRET命令を実行するだけの）関数を呼び出した場合の比較です。この結果は、実際のプリフェッチがなければパフォーマンスがむしろ悪化する（+のデルタが多い）ことを示しており、「inlinable PREFETCH is worth pursuing」（インライン化可能なプリフェッチは追求する価値がある）という結論を裏付けています。これは、プリフェッチ命令の呼び出しオーバーヘッドが小さく、かつ実際にメモリをプリフェッチする効果が大きいことを示唆しています。

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

変更はsrc/pkg/runtime/mgc0.cファイルに集中しており、以下の2行が追加されています。

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -268,6 +268,8 @@ scanblock(byte *b, int64 n)
 		if((bits & bitNoPointers) != 0)
 			continue;

+		PREFETCH(obj);
+
 		// If another proc wants a pointer, give it some.
 		if(nobj > 4 && work.nwait > 0 && work.full == nil) {
 			wbuf->nobj = nobj;

コアとなるコードの解説

追加されたコードは、scanblock関数内のループの冒頭近くに位置しています。

PREFETCH(obj);

この一行が、メモリプリフェッチの導入です。

  • PREFETCHは、Goランタイムが提供するマクロまたは組み込み関数であり、コンパイル時にターゲットCPUアーキテクチャの適切なプリフェッチ命令（例: x86のPREFETCHT0など）に展開されます。
  • objは、現在GCが走査しているメモリ上のオブジェクトを指すポインタです。

この行が実行されると、CPUはobjが指すメモリ領域のデータを、実際にそのデータが必要になる前にキャッシュに読み込もうと試みます。scanblock関数はポインタをたどってオブジェクトを走査するため、次にアクセスする可能性のあるオブジェクトのデータを事前にキャッシュに入れておくことで、キャッシュミスによる遅延を削減し、GCのマークフェーズの効率を向上させます。

この変更は、GoランタイムのGCが、より低レベルなハードウェアの特性（CPUキャッシュとプリフェッチ命令）を積極的に活用してパフォーマンスを最適化していることを示しています。

関連リンク

  • Go言語のガベージコレクションに関する公式ドキュメントやブログ記事（当時のもの）
  • CPUキャッシュとメモリプリフェッチに関する一般的な情報

参考にした情報源リンク

  • Go言語の公式ドキュメント (Go 1.x 時代のランタイムとGCに関する情報)
  • CPUアーキテクチャにおけるプリフェッチ命令に関する一般的な知識
  • 本コミットのコミットメッセージに含まれるベンチマーク結果とコメント