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

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

このコミットは、Goランタイムにおけるメモリ割り当て統計（malloc stats）の収集方法を最適化し、パフォーマンスを向上させることを目的としています。具体的には、malloc（メモリ割り当て）時に行っていた統計情報のカウントを削減し、解放（free）時にのみ必要な情報をカウントするように変更することで、統計収集のオーバーヘッドを低減しています。これにより、ベンチマーク結果で示されているように、mallocの性能が改善されています。

コミット

  • コミットハッシュ: 5d637b83a90cd16ea6badbe716f5e964bd9e06db
  • 作者: Dmitriy Vyukov (dvyukov@google.com)
  • 日付: 2013年6月6日 木曜日 14:56:50 +0400
  • 概要: runtime: speedup malloc stats collection (malloc統計収集の高速化)

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

https://github.com/golang/go/commit/5d637b83a90cd16ea6badbe716f5e964bd9e06db

元コミット内容

runtime: speedup malloc stats collection
Count only number of frees, everything else is derivable
and does not need to be counted on every malloc.
benchmark                    old ns/op    new ns/op    delta
BenchmarkMalloc8                    68           66   -3.07%
BenchmarkMalloc16                   75           70   -6.48%
BenchmarkMallocTypeInfo8           102           97   -4.80%
BenchmarkMallocTypeInfo16          108          105   -2.78%

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

変更の背景

Goランタイムは、プログラムの実行中にメモリの割り当てと解放を効率的に管理し、ガベージコレクション（GC）を実行します。このメモリ管理の健全性を監視し、デバッグや最適化のために、ランタイムは様々な統計情報（メモリ割り当て回数、解放回数、ヒープサイズなど）を収集しています。

しかし、これらの統計情報を詳細に、かつ頻繁に収集することは、ランタイム自身のパフォーマンスにオーバーヘッドをもたらす可能性があります。特に、malloc（メモリ割り当て）のような頻繁に呼び出される操作のパスで多くの統計情報を更新することは、プログラム全体の実行速度に影響を与えます。

このコミットの背景には、malloc時の統計情報収集が過剰であり、その一部はfree（メモリ解放）時の情報から導出可能であるという認識がありました。つまり、すべての情報を直接カウントするのではなく、必要最小限の情報をカウントし、残りは計算によって導き出すことで、統計収集のオーバーヘッドを削減し、mallocのパフォーマンスを向上させることが目的でした。ベンチマーク結果が示すように、この変更によってmalloc関連の操作が数パーセント高速化されています。

前提知識の解説

このコミットを理解するためには、Goランタイムのメモリ管理とガベージコレクションに関する基本的な知識が必要です。

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

    • MHeap (Memory Heap): グローバルなヒープ領域を管理します。OSからメモリを要求し、それをMSpanと呼ばれる大きなチャンクに分割します。
    • MCentral (Memory Central): MHeapから取得したMSpanを、特定のサイズクラス（オブジェクトのサイズに応じたカテゴリ）に分類し、MCacheに供給します。
    • MCache (Memory Cache): 各P（Processor、Goスケジューラにおける論理プロセッサ）に紐付けられたローカルなキャッシュです。Goルーチンがメモリを割り当てる際、まずこのMCacheからメモリを取得しようとします。これにより、グローバルなロックの競合を減らし、並行性を高めます。

  2. MSpan: 連続したページ（OSのメモリ管理単位）の集合です。MHeapによって管理され、小さなオブジェクト（small objects）の場合はさらに細かく分割されてMCacheに提供されます。大きなオブジェクト（large objects）の場合は、MSpan全体が割り当てられます。

  3. サイズクラス (Size Classes): Goランタイムは、様々なサイズのオブジェクトを効率的に管理するために、あらかじめ定義されたサイズクラスを使用します。例えば、8バイト、16バイト、32バイトといったように、特定のサイズのオブジェクトを格納するためのメモリブロックのカテゴリがあります。

  4. メモリ統計 (Memory Statistics): Goランタイムは、runtime.MemStats構造体を通じて、ヒープの使用状況、割り当てられたオブジェクトの数、GCの実行回数など、様々なメモリ関連の統計情報を提供します。これらの統計は、runtime.ReadMemStats関数を通じて取得できます。

  5. mallocgcとfree:

    • runtime.mallocgc: Goプログラムがメモリを割り当てる際に内部的に呼び出される関数です。指定されたサイズのメモリブロックをヒープから取得します。
    • runtime.free: メモリブロックが不要になった際に解放される関数です。Goでは通常、ガベージコレクタが自動的にメモリを解放するため、開発者が直接この関数を呼び出すことは稀です。

  6. purgecachedstats: MCacheに一時的に蓄積されたローカルな統計情報を、グローバルなMHeapの統計情報にマージする関数です。MCacheの統計情報がオーバーフローするのを防ぐため、またはGCの際にグローバルな統計を更新するために呼び出されます。

このコミットは、主にMCacheとMHeapにおける統計情報の管理方法、特にmallocgcとfreeパスでのカウンタの更新方法に焦点を当てています。

技術的詳細

このコミットの技術的な核心は、Goランタイムのメモリ割り当て（mallocgc）および解放（free）パスにおける統計情報収集のロジック変更です。

変更前は、MCache構造体内にlocal_nmalloc（割り当て回数）、local_objects（オブジェクト数）、local_alloc（割り当てバイト数）、local_total_alloc（総割り当てバイト数）、local_nfree（解放回数）、local_by_size（サイズクラスごとの割り当て・解放回数）など、多くのカウンタが存在し、mallocgcが呼び出されるたびにこれらのカウンタが更新されていました。

このコミットでは、以下の変更が行われました。

  1. mallocgcパスからのカウンタ更新の削除:

    • src/pkg/runtime/malloc.gocにおいて、runtime·mallocgc関数から以下のカウンタ更新が削除されました。
      • c->local_nmalloc++
      • c->local_objects++
      • c->local_alloc += size
      • c->local_total_alloc += size
      • c->local_by_size[sizeclass].nmalloc++
    • これにより、メモリ割り当て時のオーバーヘッドが大幅に削減されます。

  2. freeパスでの詳細な解放統計の追加:

    • src/pkg/runtime/malloc.gocのruntime·free関数において、大きなオブジェクト（MaxSmallSizeを超える）の解放時にc->local_nlargefree++とc->local_largefree += sizeが追加されました。
    • 小さなオブジェクトの解放時には、c->local_by_size[sizeclass].nfree++がc->local_nsmallfree[sizeclass]++に変更され、より具体的なサイズクラスごとの解放回数をカウントするようになりました。
    • c->local_nfree--とc->local_alloc -= sizeも削除されました。

  3. MCache構造体の変更:

    • src/pkg/runtime/malloc.hにおいて、MCache構造体からlocal_objects, local_alloc, local_total_alloc, local_nmalloc, local_nfree, local_by_sizeが削除されました。
    • 代わりに、local_largefree（大きなオブジェクトの解放バイト数）、local_nlargefree（大きなオブジェクトの解放回数）、local_nsmallfree（小さなオブジェクトのサイズクラスごとの解放回数）が追加されました。

  4. MHeap構造体へのグローバル解放統計の追加:

    • src/pkg/runtime/malloc.hにおいて、MHeap構造体にlargefree, nlargefree, nsmallfreeが追加されました。これらはMCacheからフラッシュされたローカルな解放統計を集約するためのグローバルカウンタです。

  5. 統計情報の導出ロジックの変更:

    • src/pkg/runtime/mgc0.cのupdatememstats関数（旧cachestats関数）が大幅に修正されました。
    • 変更前は、MCacheから直接nmallocやnfreeなどの統計をmstatsにマージしていましたが、変更後は、MCacheのローカル統計をMHeapのグローバルな解放統計にフラッシュ（runtime·purgecachedstatsとruntime·MCache_ReleaseAllを通じて）した後、ヒープ上のすべてのMSpanをスキャンして現在生きているオブジェクトの数とサイズを計算し、それに解放されたオブジェクトの数を加算することで、総割り当て数や総割り当てバイト数を導出するようになりました。
    • 具体的には、mstats.nmallocはmstats.nfree（解放回数）と現在生きているオブジェクトの数から計算され、mstats.total_allocも同様に導出されます。

このアプローチの利点は、mallocのようなホットパスから統計更新のオーバーヘッドを取り除くことで、割り当て性能を向上させる点にあります。統計情報は、GCの実行時など、より頻度の低いタイミングで、解放情報とヒープのスキャン結果から正確に再構築されるため、統計の正確性を損なうことなくパフォーマンスが改善されます。

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

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

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

    • runtime·mallocgc関数から、local_nmalloc, local_objects, local_alloc, local_total_alloc, local_by_size[sizeclass].nmallocの更新が削除されました。
    • runtime·free関数で、大きなオブジェクトの解放時にlocal_nlargefreeとlocal_largefreeの更新が追加され、小さなオブジェクトの解放時にlocal_nsmallfreeの更新が追加されました。

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

    • MCache構造体から、local_objects, local_alloc, local_total_alloc, local_nmalloc, local_nfree, local_by_sizeが削除され、local_largefree, local_nlargefree, local_nsmallfreeが追加されました。
    • MHeap構造体に、largefree, nlargefree, nsmallfreeが追加されました。

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

    • sweepspan関数（GCのスイープフェーズでメモリを解放する）において、解放統計の更新がlocal_nlargefree, local_largefree, local_nsmallfreeを使用するように変更されました。
    • cachestats関数がupdatememstatsに改名され、そのロジックが大幅に修正されました。特に、MCacheのローカル統計をMHeapにフラッシュした後、MSpanをスキャンして生きているオブジェクトの数を計算し、それに基づいてmstatsのnmallocやtotal_allocなどの統計を導出するようになりました。

コアとなるコードの解説

runtime·mallocgc (src/pkg/runtime/malloc.goc)

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -48,7 +48,6 @@ runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
 		size += sizeof(uintptr);
 
 	c = m->mcache;
-	c->local_nmalloc++;
 	if(size <= MaxSmallSize) {
 		// Allocate from mcache free lists.
 		// Inlined version of SizeToClass().
@@ -70,10 +69,6 @@ runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
 			runtime·memclr((byte*)v, size);
 		}
 		c->local_cachealloc += size;
-		c->local_objects++;
-		c->local_alloc += size;
-		c->local_total_alloc += size;
-		c->local_by_size[sizeclass].nmalloc++;
 	} else {
 		// TODO(rsc): Report tracebacks for very large allocations.
 
@@ -86,21 +81,12 @@ runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
 			runtime·throw("out of memory");
 		s->limit = (byte*)(s->start<<PageShift) + size;
 		size = npages<<PageShift;
-		c->local_alloc += size;
-		c->local_total_alloc += size;
 		v = (void*)(s->start << PageShift);
 
 		// setup for mark sweep
 		runtime·markspan(v, 0, 0, true);
 	}
 
-	if (sizeof(void*) == 4 && c->local_total_alloc >= (1<<30)) {
-		// purge cache stats to prevent overflow
-		runtime·lock(&runtime·mheap);
-		runtime·purgecachedstats(c);
-		runtime·unlock(&runtime·mheap);
-	}
-
 	if(!(flag & FlagNoGC))
 		runtime·markallocated(v, size, (flag&FlagNoPointers) != 0);

解説: この変更は、メモリ割り当てのホットパスから統計情報の更新を削除することで、mallocgcの実行速度を向上させます。以前は、割り当てが行われるたびにMCacheの様々なカウンタ（割り当て回数、オブジェクト数、割り当てバイト数など）がインクリメントされていました。これらの操作は、たとえアトミック操作でなくても、キャッシュラインのダーティ化やCPUパイプラインのストールを引き起こす可能性があり、高頻度で実行されるとパフォーマンスに影響を与えます。これらのカウンタを削除することで、mallocgcの実行パスが短縮され、より高速になります。local_total_allocのオーバーフローを防ぐためのpurgecachedstatsの呼び出しも不要になりました。

runtime·free (src/pkg/runtime/malloc.goc)

--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -183,6 +169,8 @@ runtime·free(void *v)
 		runtime·markfreed(v, size);
 		runtime·unmarkspan(v, 1<<PageShift);
 		runtime·MHeap_Free(&runtime·mheap, s, 1);
+		c->local_nlargefree++;
+		c->local_largefree += size;
 	} else {
 		// Small object.
 		size = runtime·class_to_size[sizeclass];
@@ -192,11 +180,9 @@ runtime·free(void *v)
 		// it might coalesce v and other blocks into a bigger span
 		// and change the bitmap further.
 		runtime·markfreed(v, size);
-		c->local_by_size[sizeclass].nfree++;
+		c->local_nsmallfree[sizeclass]++;
 		runtime·MCache_Free(c, v, sizeclass, size);
 	}
-	c->local_nfree++;
-	c->local_alloc -= size;
 	if(prof)
 		runtime·MProf_Free(v, size);
 	m->mallocing = 0;

解説: malloc時のカウンタ更新を削除した代わりに、メモリ解放時（free）に、より詳細な解放統計をMCacheのローカルカウンタに記録するようになりました。大きなオブジェクトの解放時にはlocal_nlargefree（解放回数）とlocal_largefree（解放バイト数）を、小さなオブジェクトの解放時にはlocal_nsmallfree（サイズクラスごとの解放回数）を更新します。これにより、解放されたメモリに関する正確な情報が保持され、後で全体の統計を導出する際に利用されます。

MCache構造体 (src/pkg/runtime/malloc.h)

--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -286,22 +286,15 @@ struct MCache
 {
 	// The following members are accessed on every malloc,
 	// so they are grouped here for better caching.
-	int32 next_sample;	// trigger heap sample after allocating this many bytes
+	int32 next_sample;		// trigger heap sample after allocating this many bytes
 	intptr local_cachealloc;	// bytes allocated (or freed) from cache since last lock of heap
 	// The rest is not accessed on every malloc.
 	MCacheList list[NumSizeClasses];
-	intptr local_objects;	// objects allocated (or freed) from cache since last lock of heap
-	intptr local_alloc;	// bytes allocated (or freed) since last lock of heap
-	uintptr local_total_alloc;	// bytes allocated (even if freed) since last lock of heap
-	uintptr local_nmalloc;	// number of mallocs since last lock of heap
-	uintptr uintptr local_nfree;	// number of frees since last lock of heap
 	uintptr local_nlookup;	// number of pointer lookups since last lock of heap
-	// Statistics about allocation size classes since last lock of heap
-	struct {
-		uintptr nmalloc;
-		uintptr nfree;
-	} local_by_size[NumSizeClasses];
-
+	// Local allocator stats, flushed during GC.
+	uintptr local_nlookup;		// number of pointer lookups
+	uintptr local_largefree;	// bytes freed for large objects (>MaxSmallSize)
+	uintptr local_nlargefree;	// number of frees for large objects (>MaxSmallSize)
+	uintptr local_nsmallfree[NumSizeClasses];	// number of frees for small objects (<=MaxSmallSize)
 };

解説: MCache構造体は、各P（論理プロセッサ）がローカルに持つメモリキャッシュの統計情報を保持します。malloc時に更新されていた多くのカウンタが削除され、代わりにfree時に更新されるlocal_largefree, local_nlargefree, local_nsmallfreeが追加されました。これにより、MCacheの構造が簡素化され、mallocパスでのキャッシュ効率が向上する可能性があります。

MHeap構造体 (src/pkg/runtime/malloc.h)

--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -431,6 +424,11 @@ struct MHeap
 
 	FixAlloc spanalloc;	// allocator for Span*
 	FixAlloc cachealloc;	// allocator for MCache*
+
+	// Malloc stats.
+	uint64 largefree;	// bytes freed for large objects (>MaxSmallSize)
+	uint64 nlargefree;	// number of frees for large objects (>MaxSmallSize)
+	uint64 nsmallfree[NumSizeClasses];	// number of frees for small objects (<=MaxSmallSize)
 };
 extern MHeap runtime·mheap;

解説: MHeapはグローバルなヒープを管理する構造体です。MCacheからフラッシュされたローカルな解放統計を集約するために、largefree, nlargefree, nsmallfreeというグローバルカウンタが追加されました。これにより、全体の解放統計がMHeapレベルで正確に追跡できるようになります。

updatememstats (src/pkg/runtime/mgc0.c)

--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -1855,13 +1852,28 @@ runtime·gchelper(void)
 static int32 gcpercent = GcpercentUnknown;
 
 static void
-cachestats(GCStats *stats)
+cachestats(void)
+{
+	MCache *c;
+	P *p, **pp;
+
+	for(pp=runtime·allp; p=*pp; pp++) {
+		c = p->mcache;
+		if(c==nil)
+			continue;
+		runtime·purgecachedstats(c);
+	}
+}
+
+static void
+updatememstats(GCStats *stats)
 {
 	M *mp;
+	MSpan *s;
 	MCache *c;
 	P *p, **pp;
 	int32 i;
-	uint64 stacks_inuse;
+	uint64 stacks_inuse, smallfree;
 	uint64 *src, *dst;
 
 	if(stats)
@@ -1877,13 +1889,65 @@ cachestats(GCStats *stats)
 		runtime·memclr((byte*)&mp->gcstats, sizeof(mp->gcstats));
 	}
+	mstats.stacks_inuse = stacks_inuse;
+
+	// Calculate memory allocator stats.
+	// During program execution we only count number of frees and amount of freed memory.
+	// Current number of alive object in the heap and amount of alive heap memory
+	// are calculated by scanning all spans.
+	// Total number of mallocs is calculated as number of frees plus number of alive objects.
+	// Similarly, total amount of allocated memory is calculated as amount of freed memory
+	// plus amount of alive heap memory.
+	mstats.alloc = 0;
+	mstats.total_alloc = 0;
+	mstats.nmalloc = 0;
+	mstats.nfree = 0;
+	for(i = 0; i < nelem(mstats.by_size); i++) {
+		mstats.by_size[i].nmalloc = 0;
+		mstats.by_size[i].nfree = 0;
+	}
+
+	// Flush MCache's to MCentral.
 	for(pp=runtime·allp; p=*pp; pp++) {
 		c = p->mcache;
 		if(c==nil)
 			continue;
-		runtime·purgecachedstats(c);
+		runtime·MCache_ReleaseAll(c);
 	}
-	mstats.stacks_inuse = stacks_inuse;
+
+	// Aggregate local stats.
+	cachestats(); // This now calls purgecachedstats for all MCaches
+
+	// Scan all spans and count number of alive objects.
+	for(i = 0; i < runtime·mheap.nspan; i++) {
+		s = runtime·mheap.allspans[i];
+		if(s->state != MSpanInUse)
+			continue;
+		if(s->sizeclass == 0) { // large object
+			mstats.nmalloc++;
+			mstats.alloc += s->elemsize;
+		} else { // small object
+			mstats.nmalloc += s->ref; // s->ref is number of alive objects in span
+			mstats.by_size[s->sizeclass].nmalloc += s->ref;
+			mstats.alloc += s->ref*s->elemsize;
+		}
+	}
+
+	// Aggregate by size class.
+	smallfree = 0;
+	mstats.nfree = runtime·mheap.nlargefree;
+	for(i = 0; i < nelem(mstats.by_size); i++) {
+		mstats.nfree += runtime·mheap.nsmallfree[i];
+		mstats.by_size[i].nfree = runtime·mheap.nsmallfree[i];
+		mstats.by_size[i].nmalloc += runtime·mheap.nsmallfree[i]; // Add freed objects to total malloc count
+		smallfree += runtime·mheap.nsmallfree[i] * runtime·class_to_size[i];
+	}
+	mstats.nmalloc += mstats.nfree; // Total mallocs = alive objects + freed objects
+
+	// Calculate derived stats.
+	mstats.total_alloc = mstats.alloc + runtime·mheap.largefree + smallfree;
+	mstats.heap_alloc = mstats.alloc;
+	mstats.heap_objects = mstats.nmalloc - mstats.nfree;
 }

解説: この関数は、Goランタイムのグローバルなメモリ統計（mstats）を更新する役割を担います。最も重要な変更点は、統計情報の「導出」ロジックです。

  1. まず、すべてのMCacheのローカル統計をMHeapのグローバルな解放統計にフラッシュします（runtime·MCache_ReleaseAllとcachestats関数を通じてpurgecachedstatsが呼び出される）。
  2. 次に、ヒープ上のすべてのMSpanをスキャンし、現在使用中の（生きている）オブジェクトの数と、それらが占めるメモリ量を正確にカウントします。これにより、mstats.alloc（現在割り当てられているヒープメモリ量）と、生きているオブジェクトのmstats.nmalloc（割り当て回数）が計算されます。
  3. 最後に、MHeapに集約された解放統計（nlargefree, nsmallfree）と、スキャンによって得られた生きているオブジェクトの数から、mstats.nmalloc（総割り当て回数）とmstats.total_alloc（総割り当てバイト数）を導出します。mstats.nmallocは「生きているオブジェクトの数 + 解放されたオブジェクトの数」として計算され、mstats.total_allocも同様に「生きているメモリ量 + 解放されたメモリ量」として計算されます。

この新しいアプローチにより、malloc時の統計更新のオーバーヘッドが排除され、統計情報の正確性はGC時などの定期的なスキャンと解放情報から保証されるようになりました。

関連リンク

参考にした情報源リンク

  • Goのメモリ管理に関する公式ドキュメントやブログ記事 (一般的なGoランタイムのメモリ管理の理解のため)
  • Goのガベージコレクションに関する資料 (GCの仕組みと統計収集の関連性を理解するため)
  • Goのソースコード (src/pkg/runtime/) (変更箇所の詳細な分析のため)