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

このコミットは、Goランタイムのメモリ管理における重要な最適化を導入しています。具体的には、MCentralからMCacheへのメモリブロック（スパン）の転送方法を変更し、より大きな単位での転送を行うように修正しています。これにより、特に小規模なオブジェクトのアロケーションにおいてパフォーマンスが向上しています。

コミット

commit 23ad56311977b4a4bfff78fb5f674616e0272445
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed May 15 18:35:05 2013 +0400

    runtime: transfer whole span from MCentral to MCache
    Finer-grained transfers were relevant with per-M caches,
    with per-P caches they are not relevant and harmful for performance.
    For few small size classes where it makes difference,
    it's fine to grab the whole span (4K).
    
    benchmark          old ns/op    new ns/op    delta
    BenchmarkMalloc           42           40   -4.45%
    
    R=golang-dev, bradfitz
    CC=golang-dev
    https://golang.org/cl/9374043

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

https://github.com/golang/go/commit/23ad56311977b4a4bfff78fb5f674616e0272445

元コミット内容

このコミットの元の内容は、Goランタイムのメモリ管理において、MCentralからMCacheへのスパン（メモリブロック）の転送方法を変更することです。以前はより細かい単位での転送が行われていましたが、per-P caches（プロセッサごとのキャッシュ）の導入により、この細かい転送が不要になり、むしろパフォーマンスに悪影響を与えるようになったため、スパン全体を転送するように変更されました。特に、いくつかの小さなサイズクラスでは、スパン全体（4KB）を取得しても問題ないという判断がなされています。

ベンチマーク結果として、BenchmarkMallocが4.45%改善されたことが示されています。

変更の背景

この変更の背景には、Goランタイムのメモリ管理モデルの進化があります。Goのガベージコレクタ（GC）は、メモリの割り当てと解放を効率的に行うために、いくつかのコンポーネントを使用します。

初期のGoランタイムでは、per-M caches（MはOSスレッドを表すM構造体）が使用されていました。このモデルでは、各OSスレッドが独自のメモリキャッシュを持っていました。この場合、MCentralからMCacheへのメモリ転送は、スレッド間の競合を減らすために、より細かい単位で行うことが理にかなっていました。

しかし、Go 1.1で導入されたper-P caches（Pは論理プロセッサを表すP構造体）への移行により、状況が変わりました。PはGoスケジューラによって管理される論理プロセッサであり、MとPは多対多の関係を持ちます。Pは、Goルーチンを実行するためのコンテキストを提供し、MはP上でGoルーチンを実行します。per-P cachesは、Pごとに独立したメモリキャッシュを持つことで、ロックの競合を減らし、並行性を向上させることを目的としていました。

per-P cachesの環境では、MCentralからMCacheへの転送は、もはやスレッド間の競合を考慮する必要が少なくなりました。Pは通常、単一のMによって排他的に利用されるため、MCacheへの転送はより大きな単位で行っても、競合によるオーバーヘッドが増加するリスクが低減されます。むしろ、細かい単位での転送は、転送回数が増えることによるオーバーヘッドや、キャッシュの局所性の低下といった問題を引き起こす可能性がありました。

このため、コミットメッセージにあるように「Finer-grained transfers were relevant with per-M caches, with per-P caches they are not relevant and harmful for performance.」という判断がなされ、スパン全体を転送する方針に転換されました。これにより、メモリ割り当ての効率が向上し、BenchmarkMallocのパフォーマンス改善に繋がったと考えられます。

前提知識の解説

このコミットを理解するためには、Goランタイムのメモリ管理の基本的な概念を理解する必要があります。

1. Goのメモリ管理の階層構造:

   • MHeap: ヒープ全体の管理を行うグローバルな構造体。大きなメモリブロック（スパン）を管理します。
   • MCentral: 特定のサイズクラス（後述）のオブジェクトを割り当てるためのスパンのリストを管理します。複数のMCacheから共有されます。
   • MCache: 各P（論理プロセッサ）に紐付けられたローカルなメモリキャッシュ。Goルーチンがオブジェクトを割り当てる際に最初に参照する場所です。ロックフリーで高速な割り当てを提供します。
   • MSpan: 連続したページ（通常4KB）のブロックを表す構造体。MCentralによって管理され、MCacheに提供されます。MSpanは、特定のサイズクラスのオブジェクトを格納するために分割されます。

2. サイズクラス (Size Classes): Goのメモリ管理では、オブジェクトのサイズに応じて異なる「サイズクラス」に分類されます。これにより、メモリの断片化を減らし、効率的な割り当てを可能にします。例えば、8バイトのオブジェクトは8バイトのサイズクラスに、16バイトのオブジェクトは16バイトのサイズクラスに属します。各サイズクラスには、そのサイズのオブジェクトを格納するために最適なMSpanのページ数と、1つのMSpanから割り当てられるオブジェクトの数が定義されています。

3. per-M caches と per-P caches:

   • per-M caches (旧モデル): 各OSスレッド（M）が独自のMCacheを持つモデル。スレッド間の競合を避けるために、MCentralからMCacheへの転送は、必要なオブジェクト数だけを転送する「細かい単位」で行われていました。
   • per-P caches (現行モデル): 各論理プロセッサ（P）が独自のMCacheを持つモデル。Pは通常、単一のMによって排他的に利用されるため、MCacheへの転送はより大きな単位で行っても、競合によるオーバーヘッドが少ないという利点があります。このモデルでは、MCentralからMCacheへの転送は、スパン全体を転送する方が効率的になります。

4. runtime·class_to_transfercount: このコミットで削除されるruntime·class_to_transfercountは、以前のper-M cachesモデルにおいて、MCentralからMCacheへ一度に転送するオブジェクトの数を定義していた配列です。オブジェクトのサイズクラスごとに、転送するオブジェクトの数が決められていました。この値は、キャッシュの効率と競合のバランスを取るために調整されていました。

技術的詳細

このコミットの技術的な変更点は、主に以下の3つのファイルにわたっています。

1. src/pkg/runtime/malloc.h:

   • runtime·class_to_transfercountというグローバル変数の宣言が削除されました。これは、MCentralからMCacheへの転送単位を決定するために使用されていた配列であり、今回の変更で不要になったためです。
   • runtime·MCentral_AllocList関数のシグネチャが変更されました。以前はint32 nという引数（転送するオブジェクトの数）を受け取っていましたが、これが削除され、MLink **firstのみを受け取るようになりました。これは、スパン全体を転送するようになったため、転送数を明示的に指定する必要がなくなったことを意味します。

2. src/pkg/runtime/mcache.c:

   • runtime·MCache_Alloc関数内で、MCentralからMCacheへメモリを補充する際に、runtime·MCentral_AllocListの呼び出しからruntime·class_to_transfercount[sizeclass]引数が削除されました。これにより、MCentral_AllocListはスパン全体を転送するようになります。
   • runtime·MCache_Free関数内で、MaxMCacheListLenを超えた場合にMCacheからMCentralへメモリを解放するReleaseN関数の呼び出しにおいて、解放するオブジェクトの数がruntime·class_to_transfercount[sizeclass]からl->nlist/2に変更されました。これは、MCacheが保持しているリストの半分を解放するという、より動的なアプローチに変わったことを示しています。

3. src/pkg/runtime/mcentral.c:

   • runtime·MCentral_AllocList関数の実装が大幅に変更されました。
     • 関数のシグネチャからint32 n引数が削除されました。
     • 以前はn個のオブジェクトをリストから取り出し、それらをリンクして返すロジック（for(i=1; i<n; i++) { last = last->next; }など）が存在しましたが、これが完全に削除されました。
     • 新しい実装では、s->freelist（スパンのフリーリストの先頭）を直接*pfirstに代入し、s->freelist自体をnilに設定しています。これは、スパンのフリーリスト全体をMCacheに転送することを意味します。
     • s->ref（スパンから割り当てられたオブジェクトの数）は、スパンの容量全体（cap）からs->refを引いた値（つまり、スパンに残っているすべてのオブジェクト）に設定されます。
     • スパンが完全に空になった場合（n == avail）のチェックと、MCentralのemptyリストへのスパンの移動ロジックが簡素化されました。以前はs->freelist != nil || s->ref != capという複雑なチェックがありましたが、新しいロジックではスパン全体が転送されるため、より直接的にemptyリストに移動されます。

4. src/pkg/runtime/msize.c:

   • runtime·class_to_transfercountというグローバル変数の定義が削除されました。
   • runtime·InitSizes関数内で、runtime·class_to_transfercountを初期化していたループが完全に削除されました。これは、この配列がもはや使用されないためです。

これらの変更により、MCentralからMCacheへのメモリ転送は、特定のオブジェクト数ではなく、MSpanが持つフリーリスト全体（つまり、スパン全体）を転送するようになりました。これにより、転送ごとのオーバーヘッドが削減され、特に小さなオブジェクトの割り当てにおいてパフォーマンスが向上します。

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

src/pkg/runtime/malloc.h

--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -267,14 +267,10 @@ extern MStats mstats;
 // class_to_size[i] = largest size in class i
 // class_to_allocnpages[i] = number of pages to allocate when
 //	making new objects in class i
-// class_to_transfercount[i] = number of objects to move when
-//	taking a bunch of objects out of the central lists
-//	and putting them in the thread free list.
- 
 int32	runtime·SizeToClass(int32);
 extern	int32	runtime·class_to_size[NumSizeClasses];
 extern	int32	runtime·class_to_allocnpages[NumSizeClasses];
-extern	int32	runtime·class_to_transfercount[NumSizeClasses];
 extern	int8	runtime·size_to_class8[1024/8 + 1];
 extern	int8	runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1];
 extern	void	runtime·InitSizes(void);
@@ -399,7 +395,7 @@ struct MCentral
 };
 
 void	runtime·MCentral_Init(MCentral *c, int32 sizeclass);
-int32	runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **first);
+int32	runtime·MCentral_AllocList(MCentral *c, MLink **first);
 void	runtime·MCentral_FreeList(MCentral *c, int32 n, MLink *first);
 void	runtime·MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, MLink *end);

src/pkg/runtime/mcache.c

--- a/src/pkg/runtime/mcache.c
+++ b/src/pkg/runtime/mcache.c
@@ -21,8 +21,7 @@ runtime·MCache_Alloc(MCache *c, int32 sizeclass, uintptr size, int32 zeroed)
 	l = &c->list[sizeclass];
 	if(l->list == nil) {
 		// Replenish using central lists.
-		n = runtime·MCentral_AllocList(&runtime·mheap->central[sizeclass],
-			runtime·class_to_transfercount[sizeclass], &first);
+		n = runtime·MCentral_AllocList(&runtime·mheap->central[sizeclass], &first);
 		if(n == 0)
 			runtime·throw("out of memory");
 		l->list = first;
@@ -91,7 +90,7 @@ runtime·MCache_Free(MCache *c, void *v, int32 sizeclass, uintptr size)
 
 	if(l->nlist >= MaxMCacheListLen) {
 		// Release a chunk back.
-		ReleaseN(c, l, runtime·class_to_transfercount[sizeclass], sizeclass);
+		ReleaseN(c, l, l->nlist/2, sizeclass);
 	}
 
 	if(c->size >= MaxMCacheSize) {

src/pkg/runtime/mcentral.c

--- a/src/pkg/runtime/mcentral.c
+++ b/src/pkg/runtime/mcentral.c
@@ -30,16 +30,15 @@ runtime·MCentral_Init(MCentral *c, int32 sizeclass)
 	runtime·MSpanList_Init(&c->empty);
 }
 
-// Allocate up to n objects from the central free list.
+// Allocate a list of objects from the central free list.
 // Return the number of objects allocated.
 // The objects are linked together by their first words.
 // On return, *pstart points at the first object.
 int32
-runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
+runtime·MCentral_AllocList(MCentral *c, MLink **pfirst)
 {
 	MSpan *s;
-\tMLink *first, *last;
-\tint32 cap, avail, i;
+\tint32 cap, n;
 
 	runtime·lock(c);
 	// Replenish central list if empty.
@@ -52,31 +51,14 @@ runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
 	}
 	s = c->nonempty.next;
 	cap = (s->npages << PageShift) / s->elemsize;
-\tavail = cap - s->ref;
-\tif(avail < n)
-\t\tn = avail;
-\n-\t// First one is guaranteed to work, because we just grew the list.
-\tfirst = s->freelist;
-\tlast = first;
-\tfor(i=1; i<n; i++) {
-\t\tlast = last->next;\n-\t}\n-\ts->freelist = last->next;
-\tlast->next = nil;
+\tn = cap - s->ref;
+\t*pfirst = s->freelist;
+\ts->freelist = nil;
 	s->ref += n;
 	c->nfree -= n;
-\n-\tif(n == avail) {
-\t\tif(s->freelist != nil || s->ref != cap) {
-\t\t\truntime·throw("invalid freelist");
-\t\t}\n-\t\truntime·MSpanList_Remove(s);
-\t\truntime·MSpanList_Insert(&c->empty, s);
-\t}\n-\n+\truntime·MSpanList_Remove(s);
+\truntime·MSpanList_Insert(&c->empty, s);
 	runtime·unlock(c);
-\t*pfirst = first;
 	return n;
 }

src/pkg/runtime/msize.c

--- a/src/pkg/runtime/msize.c
+++ b/src/pkg/runtime/msize.c
@@ -31,7 +31,6 @@
 
 int32 runtime·class_to_size[NumSizeClasses];
 int32 runtime·class_to_allocnpages[NumSizeClasses];
-int32 runtime·class_to_transfercount[NumSizeClasses];
 
 // The SizeToClass lookup is implemented using two arrays,
 // one mapping sizes <= 1024 to their class and one mapping
@@ -137,16 +136,6 @@ runtime·InitSizes(void)\n 	// Copy out for statistics table.\n 	for(i=0; i<nelem(runtime·class_to_size); i++)\n 		mstats.by_size[i].size = runtime·class_to_size[i];
-\n-\t// Initialize the runtime·class_to_transfercount table.\n-\tfor(sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) {\n-\t\tn = 64*1024 / runtime·class_to_size[sizeclass];\n-\t\tif(n < 2)\n-\t\t\tn = 2;\n-\t\tif(n > 32)\n-\t\t\tn = 32;\n-\t\truntime·class_to_transfercount[sizeclass] = n;\n-\t}\n 	return;
-\n dump:

コアとなるコードの解説

このコミットの核心は、runtime·MCentral_AllocList関数の動作変更にあります。

変更前: runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst) は、MCentralからn個のオブジェクトをMCacheに転送することを意図していました。このnの値は、runtime·class_to_transfercount配列から取得され、サイズクラスごとに異なる値が設定されていました。関数内部では、スパンのフリーリストからn個のオブジェクトを抽出し、それらをリンクしてMCacheに渡していました。

変更後: runtime·MCentral_AllocList(MCentral *c, MLink **pfirst) は、n引数が削除されました。関数内部では、スパンのフリーリストの先頭（s->freelist）を直接*pfirstに代入し、s->freelist自体をnilに設定しています。これは、スパンが持つフリーリスト全体（つまり、スパンに残っているすべての利用可能なオブジェクト）をMCacheに転送することを意味します。

この変更により、MCentralとMCache間の転送がより粗い粒度で行われるようになります。

• 利点:

  • 転送ごとのオーバーヘッドが削減されます。以前はn個のオブジェクトを抽出するためにループ処理が必要でしたが、これが不要になります。
  • キャッシュの局所性が向上する可能性があります。一度に多くのオブジェクトをMCacheに転送することで、Goルーチンが連続してメモリを割り当てる際に、MCache内で必要なオブジェクトが見つかる可能性が高まります。
  • per-P cachesの設計とより整合性が取れます。Pは通常、単一のMによって排他的に利用されるため、MCacheへの転送はより大きな単位で行っても、競合によるオーバーヘッドが少ないという利点があります。

• 考慮事項:

  • MCacheが一度に多くのメモリを保持することになるため、メモリ使用量が増加する可能性があります。しかし、コミットメッセージにあるように「For few small size classes where it makes difference, it's fine to grab the whole span (4K).」とあり、特に小さなオブジェクトのサイズクラスでは、スパン全体（通常4KB）を転送しても問題ないという判断がなされています。これは、小さなオブジェクトは頻繁に割り当てられ、すぐに解放される傾向があるため、MCacheに多くのオブジェクトがあってもすぐに消費されるか、MCentralに返却されるためと考えられます。

また、runtime·MCache_Free関数におけるReleaseNの呼び出しも変更されています。以前はruntime·class_to_transfercount[sizeclass]個のオブジェクトをMCentralに返却していましたが、新しいコードではl->nlist/2、つまりMCacheのリストの半分を返却するようになりました。これは、MCacheが過剰なメモリを保持しないように、より動的に調整するメカニズムです。

全体として、このコミットはGoランタイムのメモリ管理を、per-P cachesのアーキテクチャに合わせて最適化し、メモリ割り当てのパフォーマンスを向上させることを目的としています。

関連リンク

• Goのメモリ管理に関する公式ドキュメントやブログ記事
• Goのガベージコレクタの進化に関する情報
• GoのM、P、Gスケジューラモデルに関する解説

参考にした情報源リンク

• https://golang.org/cl/9374043 (Goの変更リスト)
• Goの公式ドキュメント (Goのメモリ管理、スケジューラに関するセクション)
• Goのランタイムソースコード (特にsrc/runtimeディレクトリ)
• Goのメモリ管理に関する技術ブログや論文 (例: "Go's Memory Allocator" by Rick Hudson, "The Go scheduler" by Dmitry Vyukov)
• Goのメモリ管理の仕組みを理解する - Qiita (一般的なGoのメモリ管理の解説)
• GoのGCの仕組み - Qiita (GoのGCに関する解説)
• Goのスケジューラについて - Qiita (Goのスケジューラに関する解説)

（注：上記のQiitaリンクは一般的なGoのメモリ管理、GC、スケジューラに関する情報源の例であり、この特定のコミットに直接言及しているわけではありません。しかし、前提知識を補完するために役立つ情報源です。）