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

このコミットは、Goランタイムのメモリ割り当てメカニズムであるmallocgc関数において、次のメモリブロックを事前にフェッチ（プリフェッチ）する最適化を導入するものです。これにより、CPUキャッシュの効率が向上し、メモリ割り当てのパフォーマンスが改善されます。コミットメッセージには、json-1ベンチマークでCPU時間と実行時間が約1%改善され、garbage-1ベンチマークでは約2%改善されたことが示されており、この最適化が実測値で効果を発揮していることがわかります。

コミット

commit d176e3d7c5bb50685c95aaf1e0e3133bea0ea57f
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Jan 28 22:38:39 2014 +0400

    runtime: prefetch next block in mallocgc
    
    json-1
    cputime                  99600000     98600000      -1.00%
    time                    100005493     98859693      -1.15%
    
    garbage-1
    cputime                  15760000     15440000      -2.03%
    time                     15791759     15471701      -2.03%
    
    LGTM=khr
    R=golang-codereviews, gobot, khr, dave
    CC=bradfitz, golang-codereviews, iant
    https://golang.org/cl/57310043

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

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

元コミット内容

runtime: prefetch next block in mallocgc

json-1
cputime                  99600000     98600000      -1.00%
time                    100005493     98859693      -1.15%

garbage-1
cputime                  15760000     15440000      -2.03%
time                     15791759     15471701      -2.03%

LGTM=khr
R=golang-codereviews, gobot, khr, dave
CC=bradfitz, golang-codereviews, iant
https://golang.org/cl/57310043

変更の背景

Goランタイムのメモリ割り当て関数であるmallocgcは、Goプログラムがオブジェクトをヒープに割り当てる際に頻繁に呼び出されます。この関数は、利用可能なメモリブロックのリスト（フリーリスト）から適切なサイズのブロックを見つけて返します。

従来のmallocgcの実装では、次のメモリブロックが必要になったときに初めてそのブロックのアドレスを読み込み、アクセスしていました。しかし、CPUはメモリからデータを読み込む際に、メインメモリ（DRAM）から直接読み込むのではなく、より高速なキャッシュメモリ（L1, L2, L3キャッシュ）を利用します。必要なデータがキャッシュにない場合（キャッシュミス）、CPUはメインメモリにアクセスする必要があり、これは非常に時間がかかります。

このコミットの背景には、mallocgcがフリーリストを辿る際に発生するキャッシュミスを減らし、メモリ割り当てのレイテンシを削減するという目的があります。特に、小さなオブジェクトの割り当てが頻繁に行われるようなワークロードでは、このキャッシュミスの影響が顕著になります。コミットメッセージに示されているベンチマーク結果（json-1とgarbage-1）は、JSONのエンコード/デコードやガベージコレクションが頻繁に発生するようなシナリオで、メモリ割り当ての効率がボトルネックになっていたことを示唆しています。

プリフェッチ命令を導入することで、CPUが将来必要になるであろうデータを事前にキャッシュに読み込んでおくことが可能になります。これにより、実際にそのデータが必要になったときには既にキャッシュに存在している可能性が高まり、キャッシュミスによる遅延を回避または軽減できるため、全体的なパフォーマンスが向上します。

前提知識の解説

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

1. CPUキャッシュとキャッシュミス:

   • CPUキャッシュ: CPUは、メインメモリよりもはるかに高速な小容量のメモリ（L1、L2、L3キャッシュ）を持っています。CPUがデータにアクセスする際、まずキャッシュを調べ、データがあればそこから読み込みます（キャッシュヒット）。
   • キャッシュミス: 必要なデータがキャッシュにない場合、CPUはメインメモリからデータを読み込む必要があります。このプロセスはキャッシュヒットに比べて非常に遅く、プログラムの実行速度に大きな影響を与えます。
   • 空間的局所性（Spatial Locality）: プログラムがあるメモリ位置にアクセスすると、その近くのメモリ位置にもすぐにアクセスする可能性が高いという性質。CPUはこれを利用して、アクセスされたデータだけでなく、その周辺のデータもキャッシュに読み込むことがあります。
   • 時間的局所性（Temporal Locality）: プログラムがあるメモリ位置にアクセスすると、近い将来に同じメモリ位置に再度アクセスする可能性が高いという性質。

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

   • プリフェッチとは、CPUが将来必要になるであろうデータを予測し、事前にメインメモリからキャッシュに読み込んでおく技術です。これにより、実際にデータが必要になったときにキャッシュミスを減らし、プログラムの実行を高速化できます。
   • 多くの現代のCPUは、ハードウェアによる自動プリフェッチ機能を備えていますが、プログラマが明示的にプリフェッチ命令（例: PREFETCH命令）を発行することも可能です。明示的なプリフェッチは、ハードウェアの予測が難しいアクセスパターン（例: リンクされたリストのトラバーサル）において特に有効です。

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

   • Goのランタイムは、独自のメモリ管理システムを持っています。これは、ガベージコレクション（GC）と連携して効率的なメモリ割り当てと解放を行います。
   • MHeap: Goランタイム全体のヒープメモリを管理します。
   • MSpan: 連続したメモリページ（通常は8KB）のブロックです。MSpanは、特定のサイズのオブジェクトを格納するために使用されます。
   • MCache: 各P（プロセッサ、Goスケジューラにおける論理CPU）にローカルなキャッシュです。これにより、ロックなしで高速なメモリ割り当てが可能になります。MCacheは、様々なサイズのオブジェクトに対応するフリーリスト（listフィールド）を持っています。
   • MLink: フリーリスト内のメモリブロックを連結するための構造体です。各フリーブロックの先頭には、次のフリーブロックへのポインタが格納されています。
   • mallocgc: Goランタイムの主要なメモリ割り当て関数です。オブジェクトのサイズに応じて、MCacheからメモリブロックを取得しようとします。MCacheに適切なブロックがない場合は、MHeapから取得します。
   • Tiny Objects: 16バイト以下の非常に小さなオブジェクト。これらは特別なTinySizeClassで管理され、MCacheのtinyフィールドから割り当てられます。

技術的詳細

このコミットの核心は、Goランタイムのmallocgc関数におけるフリーリストのトラバーサル中に、次のメモリブロックを事前にCPUキャッシュに読み込むためのPREFETCH命令の導入です。

mallocgc関数は、オブジェクトを割り当てる際に、まず現在のP（プロセッサ）に紐付けられたMCacheから適切なサイズのフリーブロックを探します。MCacheは、様々なサイズのオブジェクトに対応するフリーリスト（l->list）を持っています。これらのフリーリストはMLink構造体によって連結されており、各MLinkは次のフリーブロックへのポインタ（v->next）を含んでいます。

変更前のコードでは、l->list = v->next;という行で、現在のブロックvが割り当てられた後、フリーリストの先頭を次のブロックv->nextに更新していました。このとき、v->nextが指すメモリ位置は、次にmallocgcが呼び出されたときにアクセスされる可能性があります。

このコミットでは、このv->nextが指すメモリブロックを、実際に必要になる前にプリフェッチするように変更されました。具体的には、以下のステップが追加されています。

1. next = v->next;：現在のフリーブロックvの次のブロックへのポインタをnext変数に一時的に保存します。
2. if(next != nil) PREFETCH(next);：nextがnilでない場合（つまり、フリーリストの終端でない場合）、PREFETCH(next)命令を発行します。このPREFETCH命令は、nextが指すメモリブロックをCPUキャッシュに読み込むようCPUにヒントを与えます。コミットメッセージのコメント「prefetching nil leads to a DTLB miss」は、nilポインタをプリフェッチしようとすると、データ変換ルックアサイドバッファ（DTLB）ミスを引き起こす可能性があるため、nilチェックが重要であることを示しています。DTLBは仮想アドレスから物理アドレスへの変換をキャッシュするもので、無効なアドレスをプリフェッチしようとすると、この変換プロセスでミスが発生し、パフォーマンスに悪影響を与える可能性があります。
3. l->list = next;：フリーリストの先頭をnextに更新します。

この変更は、mallocgc内の2つの主要な割り当てパスに適用されています。

• Tiny Objectsの割り当てパス: TinySizeClass（16バイト以下のオブジェクト）の割り当て。
• 一般的なサイズのオブジェクトの割り当てパス: sizeclass（それ以上のサイズのオブジェクト）の割り当て。

これらのパスは、Goプログラムで非常に頻繁に実行されるため、このプリフェッチの最適化は全体的なパフォーマンスに大きな影響を与える可能性があります。特に、リンクされたリストのようなデータ構造を頻繁にトラバースする際に、次の要素を事前にキャッシュに読み込んでおくことは、キャッシュミスによるストールを大幅に削減する効果が期待できます。

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

変更はsrc/pkg/runtime/malloc.gocファイルに集中しています。

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -40,7 +40,7 @@ runtime·mallocgc(uintptr size, uintptr typ, uint32 flag)
  	intgo rate;
  	MCache *c;
  	MCacheList *l;
-	MLink *v;
+	MLink *v, *next;
  	byte *tiny;
  
  	if(size == 0) {
@@ -120,7 +120,10 @@ runtime·mallocgc(uintptr size, uintptr typ, uint32 flag)
  		if(l->list == nil)
  			runtime·MCache_Refill(c, TinySizeClass);
  		v = l->list;
-		l->list = v->next;
+		next = v->next;
+		if(next != nil)  // prefetching nil leads to a DTLB miss
+			PREFETCH(next);
+		l->list = next;
  		l->nlist--;
  		((uint64*)v)[0] = 0;
  		((uint64*)v)[1] = 0;
@@ -144,7 +147,10 @@ runtime·mallocgc(uintptr size, uintptr typ, uint32 flag)
  		if(l->list == nil)
  			runtime·MCache_Refill(c, sizeclass);
  		v = l->list;
-		l->list = v->next;
+		next = v->next;
+		if(next != nil)  // prefetching nil leads to a DTLB miss
+			PREFETCH(next);
+		l->list = next;
  		l->nlist--;
  		if(!(flag & FlagNoZero)) {
  			v->next = nil;

コアとなるコードの解説

変更は主に2つの部分に分けられます。

1. 変数の追加:

   -	MLink *v;
   +	MLink *v, *next;
   

   MLink型のポインタ変数nextが追加されました。これは、フリーリストの次の要素へのポインタを一時的に保持するために使用されます。

2. プリフェッチロジックの追加: runtime·mallocgc関数内の、TinySizeClassとsizeclassの割り当てパスの両方で、以下のパターンが導入されました。

   変更前:

   v = l->list;
   l->list = v->next; // 次の要素を直接リストの先頭に設定
   

   変更後:

   v = l->list;
   next = v->next; // 次の要素へのポインタを一時変数nextに保存
   if(next != nil)  // nextがnilでない場合のみプリフェッチ
       PREFETCH(next); // nextが指すメモリブロックをプリフェッチ
   l->list = next; // リストの先頭をnextに更新
   

   この変更により、vが指すメモリブロックが割り当てられ、その次のブロックv->nextがフリーリストの新しい先頭になる直前に、PREFETCH命令が発行されます。これにより、次にmallocgcが呼び出され、このフリーリストからメモリブロックを取得しようとしたときに、nextが指すメモリブロックが既にCPUキャッシュに存在している可能性が高まります。

   PREFETCHは、通常、コンパイラ組み込み関数やアセンブリ命令として提供されるCPU命令です。これはCPUに対して、指定されたアドレスのデータをキャッシュに読み込むよう「ヒント」を与えるものであり、必ずしも即座にデータが読み込まれることを保証するものではありませんが、多くの場合、パフォーマンス向上に寄与します。

   if(next != nil)のチェックは重要です。nilポインタをプリフェッチしようとすると、無効なメモリアドレスへのアクセスとなり、データ変換ルックアサイドバッファ（DTLB）ミスなどの不要なオーバーヘッドを引き起こす可能性があるためです。

関連リンク

• Go CL (Code Review) 57310043: https://golang.org/cl/57310043

参考にした情報源リンク

• Goのメモリ管理に関する一般的な情報:
  • The Go Programming Language Specification - Memory Model: https://go.dev/ref/mem
  • Go's Memory Allocator: https://go.dev/src/runtime/malloc.go (このコミットの対象ファイルはmalloc.gocですが、Goのメモリ管理の全体像を理解するのに役立ちます)
• CPUキャッシュとプリフェッチに関する一般的な情報:
  • CPU cache - Wikipedia: https://en.wikipedia.org/wiki/CPU_cache
  • Cache prefetching - Wikipedia: https://en.wikipedia.org/wiki/Cache_prefetching
  • Intel 64 and IA-32 Architectures Software Developer's Manuals (PREFETCH instructions): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html (具体的なPREFETCH命令の詳細については、CPUアーキテクチャのドキュメントを参照する必要があります)
• DTLB (Data Translation Lookaside Buffer) について:
  • Translation lookaside buffer - Wikipedia: https://en.wikipedia.org/wiki/Translation_lookaside_buffer