[インデックス 16310] ファイルの概要
このコミットは、Goランタイムのメモリ割り当て（malloc）におけるパフォーマンス最適化を目的としています。具体的には、オブジェクトのサイズを適切なメモリクラスに変換するSizeToClass関数の呼び出しをインライン化し、さらにこの変換に使用されるルックアップテーブルのデータ型をint32からint8に変更することで、L1キャッシュの利用効率を向上させ、メモリ使用量を削減しています。これにより、BenchmarkMallocにおいて約4.68%の性能改善が報告されています。
コミット
commit 5a89b35bca720d1ba296f5d7f22376b440486faf
Author: Dmitriy Vyukov <dvyukov@google.com>
Date: Wed May 15 11:02:33 2013 +0400
runtime: inline size to class conversion in malloc()
Also change table type from int32[] to int8[] to save space in L1$.
benchmark old ns/op new ns/op delta
BenchmarkMalloc 42 40 -4.68%
R=golang-dev, bradfitz, r
CC=golang-dev
https://golang.org/cl/9199044
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/5a89b35bca720d1ba296f5d7f22376b440486faf
元コミット内容
runtime: inline size to class conversion in malloc()
Also change table type from int32[] to int8[] to save space in L1$.
benchmark old ns/op new ns/op delta
BenchmarkMalloc 42 40 -4.68%
R=golang-dev, bradfitz, r
CC=golang-dev
https://golang.org/cl/9199044
変更の背景
Goランタイムのメモリ割り当ては、プログラムのパフォーマンスに直接影響を与える重要な部分です。特に、小さなオブジェクトの割り当ては頻繁に行われるため、そのオーバーヘッドを最小限に抑えることが求められます。
このコミットの背景には、以下の2つの主要な目的があります。
SizeToClass関数の呼び出しオーバーヘッド削減:malloc関数内で、割り当て要求されたサイズに対応するメモリクラス（sizeclass）を決定するためにSizeToClass関数が呼び出されていました。関数呼び出しには一定のオーバーヘッドが伴うため、この処理がホットパス（頻繁に実行されるコードパス）にある場合、そのオーバーヘッドが全体のパフォーマンスに影響を与えます。このコミットでは、SizeToClassのロジックをmallocgc関数内に直接インライン化することで、関数呼び出しのコストを排除し、実行速度を向上させようとしています。- L1キャッシュ効率の向上とメモリ使用量の削減:
SizeToClass関数は、内部的にsize_to_class8とsize_to_class128というルックアップテーブルを使用していました。これらのテーブルは、以前はint32型の配列として宣言されていました。しかし、メモリクラスのインデックスは通常小さな値（0-255の範囲）であるため、32ビット整数（4バイト）を使用するのは過剰です。int8型（1バイト）に変更することで、各エントリが占めるメモリ量を4分の1に削減できます。これにより、テーブル全体が占めるメモリフットプリントが減少し、CPUのL1キャッシュにより多くのデータが収まるようになります。L1キャッシュヒット率の向上は、メモリアクセスレイテンシの削減に繋がり、結果としてパフォーマンスが向上します。
これらの変更は、Goプログラムが小さなオブジェクトを頻繁に割り当てる際の効率を高め、全体的な実行速度を改善することを目的としています。
前提知識の解説
このコミットを理解するためには、Goランタイムのメモリ管理、特に小さなオブジェクトの割り当てに関する以下の概念を理解しておく必要があります。
Goランタイムのメモリ管理の概要
Goランタイムは、独自のメモリマネージャ（M-Span-Pモデル）を持っています。
- M (Machine): OSスレッドを表します。
- P (Processor): Goのスケジューラが管理する論理プロセッサを表します。各Pは、Goルーチンを実行するためのコンテキストを提供します。
- Span: 連続したメモリページの集合体です。Spanは、特定のサイズのオブジェクトを割り当てるために使用されます。
mcacheとsizeclass
Goランタイムのメモリ割り当ては、主に以下の2つのレベルで行われます。
mcache(Per-P Cache): 各論理プロセッサ（P）は、mcacheと呼ばれるローカルなキャッシュを持っています。これは、小さなオブジェクト（通常32KB以下）の割り当てを高速化するためのものです。Goルーチンが小さなオブジェクトを割り当てる際、まず自身のPのmcacheからメモリを要求します。mcacheには、様々なサイズのオブジェクトに対応するフリーリスト（mspanのリスト）が保持されています。mheap(Global Heap):mcacheが枯渇した場合、または大きなオブジェクト（通常32KB以上）を割り当てる場合、mheapと呼ばれるグローバルヒープからメモリが割り当てられます。
sizeclass: Goランタイムは、メモリ割り当ての効率を高めるために、オブジェクトのサイズをいくつかの「サイズクラス」に分類します。例えば、8バイト、16バイト、32バイトといった特定のサイズに丸められます。これにより、同じサイズのオブジェクトは同じmspanから割り当てられ、メモリの断片化を減らし、再利用を促進します。SizeToClass関数は、要求されたオブジェクトサイズがどのsizeclassに属するかを決定する役割を担います。
SizeToClass関数
SizeToClass関数は、Goランタイムのメモリ割り当てにおいて非常に重要な役割を果たします。この関数は、割り当てを要求されたバイト数（size）を受け取り、それに対応するsizeclassのインデックスを返します。このインデックスは、mcache内の適切なフリーリストを選択したり、mspanからメモリを割り当てたりするために使用されます。
この関数は、内部的にルックアップテーブル（size_to_class8とsize_to_class128）を使用して、効率的にサイズクラスを決定します。
size_to_class8: 1024バイト未満の小さなサイズに対応し、8バイト単位でインデックス付けされます。size_to_class128: 1024バイト以上のサイズに対応し、128バイト単位でインデックス付けされます。
int32とint8、そしてL1キャッシュ
int32(32-bit integer): 4バイトのメモリを占有します。int8(8-bit integer): 1バイトのメモリを占有します。
CPUには、メインメモリよりも高速なキャッシュメモリが搭載されています。L1キャッシュはCPUに最も近いキャッシュであり、最も高速です。CPUがデータにアクセスする際、まずL1キャッシュを探し、データが見つかれば（キャッシュヒット）高速に処理できます。見つからなければ（キャッシュミス）、より低速なL2キャッシュ、L3キャッシュ、最終的にはメインメモリからデータを取得する必要があります。
ルックアップテーブルの要素のサイズをint32からint8に減らすことで、同じキャッシュライン（CPUが一度にキャッシュに読み込むデータのブロック）により多くのテーブルエントリを格納できるようになります。これにより、テーブルへのアクセス時にキャッシュミスが発生する可能性が減り、結果としてメモリアクセスが高速化され、全体的なパフォーマンスが向上します。
技術的詳細
このコミットは、Goランタイムのメモリ割り当てにおける2つの主要な最適化を実装しています。
-
SizeToClass関数のインライン化:- 以前は、
runtime·mallocgc関数内でruntime·SizeToClass(size)という関数呼び出しが行われていました。 - このコミットでは、
SizeToClass関数のロジック（if-elseによるサイズ範囲の判定と、対応するルックアップテーブルからの値の取得）をruntime·mallocgc関数内に直接記述（インライン化）しています。 - これにより、関数呼び出しに伴うスタックフレームの作成・破棄、レジスタの保存・復元といったオーバーヘッドがなくなります。これは、
mallocgcが頻繁に呼び出されるホットパスにあるため、特に効果的です。
- 以前は、
-
ルックアップテーブルのデータ型変更:
size_to_class8とsize_to_class128という2つのルックアップテーブルは、オブジェクトサイズからメモリクラスへのマッピングを提供します。- これらのテーブルは、
src/pkg/runtime/msize.cでstatic int32型として宣言されていました。 - このコミットでは、これらのテーブルの型を
int32からint8に変更しています。 - さらに、これらのテーブルは
msize.c内でstaticとして宣言されていたため、他のファイルからは直接アクセスできませんでした。インライン化されたSizeToClassロジックがmalloc.gocからこれらのテーブルにアクセスできるようにするため、staticキーワードを削除し、extern宣言をmalloc.hに追加することで、グローバルなシンボルとして公開しています（runtime·size_to_class8、runtime·size_to_class128）。 - この型変更により、各テーブルエントリが占めるメモリが4バイトから1バイトに削減されます。これにより、テーブル全体のサイズが小さくなり、CPUのL1キャッシュに収まる可能性が高まります。キャッシュヒット率の向上は、メモリアクセス速度の向上に直結し、ベンチマーク結果に示されるパフォーマンス改善に貢献します。
これらの変更は、Goランタイムのメモリ割り当てパスにおけるマイクロ最適化であり、全体的なアプリケーションのパフォーマンス向上に寄与します。
コアとなるコードの変更箇所
diff --git a/src/pkg/runtime/malloc.goc b/src/pkg/runtime/malloc.goc
index f1d25a793f..5326551fee 100644
--- a/src/pkg/runtime/malloc.goc
+++ b/src/pkg/runtime/malloc.goc
@@ -50,7 +50,11 @@ runtime·mallocgc(uintptr size, uint32 flag, int32 dogc, int32 zeroed)
c->local_nmalloc++;
if(size <= MaxSmallSize) {
// Allocate from mcache free lists.
- sizeclass = runtime·SizeToClass(size);
+ // Inlined version of SizeToClass().
+ if(size <= 1024-8)
+ sizeclass = runtime·size_to_class8[(size+7)>>3];
+ else
+ sizeclass = runtime·size_to_class128[(size-1024+127) >> 7];
size = runtime·class_to_size[sizeclass];
v = runtime·MCache_Alloc(c, sizeclass, size, zeroed);
if(v == nil)
diff --git a/src/pkg/runtime/malloc.h b/src/pkg/runtime/malloc.h
index 52b76d5574..7474f85258 100644
--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -275,6 +275,8 @@ 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);
diff --git a/src/pkg/runtime/msize.c b/src/pkg/runtime/msize.c
index e6cfcdb02d..a81bc11aae 100644
--- a/src/pkg/runtime/msize.c
+++ b/src/pkg/runtime/msize.c
@@ -42,17 +42,17 @@ int32 runtime·class_to_transfercount[NumSizeClasses];
// size divided by 128 (rounded up). The arrays are filled in
// by InitSizes.
-static int32 size_to_class8[1024/8 + 1];
-static int32 size_to_class128[(MaxSmallSize-1024)/128 + 1];
+int8 runtime·size_to_class8[1024/8 + 1];
+int8 runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1];
-int32
-runtime·SizeToClass(int32 size)
+static int32
+SizeToClass(int32 size)
{
if(size > MaxSmallSize)
runtime·throw(\"SizeToClass - invalid size\");
if(size > 1024-8)
-\t\treturn size_to_class128[(size-1024+127) >> 7];
-\treturn size_to_class8[(size+7)>>3];
+\t\treturn runtime·size_to_class128[(size-1024+127) >> 7];
+\treturn runtime·size_to_class8[(size+7)>>3];
}
void
@@ -111,16 +111,16 @@ runtime·InitSizes(void)
nextsize = 0;
for (sizeclass = 1; sizeclass < NumSizeClasses; sizeclass++) {
for(; nextsize < 1024 && nextsize <= runtime·class_to_size[sizeclass]; nextsize+=8)
-\t\t\tsize_to_class8[nextsize/8] = sizeclass;\n+\t\t\truntime·size_to_class8[nextsize/8] = sizeclass;
if(nextsize >= 1024)
for(; nextsize <= runtime·class_to_size[sizeclass]; nextsize += 128)
-\t\t\t\tsize_to_class128[(nextsize-1024)/128] = sizeclass;\n+\t\t\t\truntime·size_to_class128[(nextsize-1024)/128] = sizeclass;
}
// Double-check SizeToClass.
if(0) {
for(n=0; n < MaxSmallSize; n++) {
-\t\t\tsizeclass = runtime·SizeToClass(n);\n+\t\t\tsizeclass = SizeToClass(n);\n if(sizeclass < 1 || sizeclass >= NumSizeClasses || runtime·class_to_size[sizeclass] < n) {
runtime·printf(\"size=%d sizeclass=%d runtime·class_to_size=%d\\n\", n, sizeclass, runtime·class_to_size[sizeclass]);
runtime·printf(\"incorrect SizeToClass\");
@@ -157,12 +157,14 @@ dump:
runtime·printf(\" %d\", runtime·class_to_size[sizeclass]);
runtime·printf(\"\\n\\n\");
runtime·printf(\"size_to_class8:\");
-\t\tfor(i=0; i<nelem(size_to_class8); i++)\n-\t\t\truntime·printf(\" %d=>%d(%d)\\n\", i*8, size_to_class8[i], runtime·class_to_size[size_to_class8[i]]);\n+\t\tfor(i=0; i<nelem(runtime·size_to_class8); i++)\n+\t\t\truntime·printf(\" %d=>%d(%d)\\n\", i*8, runtime·size_to_class8[i],\n+\t\t\t\truntime·class_to_size[runtime·size_to_class8[i]]);
runtime·printf(\"\\n\");
runtime·printf(\"size_to_class128:\");
-\t\tfor(i=0; i<nelem(size_to_class128); i++)\n-\t\t\truntime·printf(\" %d=>%d(%d)\\n\", i*128, size_to_class128[i], runtime·class_to_size[size_to_class128[i]]);\n+\t\tfor(i=0; i<nelem(runtime·size_to_class128); i++)\n+\t\t\truntime·printf(\" %d=>%d(%d)\\n\", i*128, runtime·size_to_class128[i],\n+\t\t\t\truntime·class_to_size[runtime·size_to_class128[i]]);
runtime·printf(\"\\n\");
}\n runtime·throw(\"InitSizes failed\");
コアとなるコードの解説
src/pkg/runtime/malloc.goc
- 変更前:
sizeclass = runtime·SizeToClass(size);runtime·mallocgc関数内で、SizeToClassという外部関数を呼び出してsizeclassを取得していました。
- 変更後:
// Inlined version of SizeToClass(). if(size <= 1024-8) sizeclass = runtime·size_to_class8[(size+7)>>3]; else sizeclass = runtime·size_to_class128[(size-1024+127) >> 7];SizeToClass関数の内部ロジックがmallocgc関数内に直接展開（インライン化）されました。- これにより、関数呼び出しのオーバーヘッドが削減され、
mallocgcの実行速度が向上します。 runtime·size_to_class8とruntime·size_to_class128というグローバルな配列が直接参照されています。
src/pkg/runtime/malloc.h
- 追加:
extern int8 runtime·size_to_class8[1024/8 + 1]; extern int8 runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1];size_to_class8とsize_to_class128が、int32からint8型に変更され、かつexternキーワードが追加されました。externは、これらの配列が他のファイル（この場合はmsize.c）で定義されていることを宣言し、malloc.gocからアクセスできるようにします。
src/pkg/runtime/msize.c
- 変更前:
static int32 size_to_class8[1024/8 + 1]; static int32 size_to_class128[(MaxSmallSize-1024)/128 + 1]; int32 runtime·SizeToClass(int32 size) { // ... return size_to_class128[(size-1024+127) >> 7]; return size_to_class8[(size+7)>>3]; }size_to_class8とsize_to_class128はstatic int32として宣言されており、このファイル内でのみアクセス可能でした。runtime·SizeToClass関数は、これらのstaticな配列を参照していました。
- 変更後:
int8 runtime·size_to_class8[1024/8 + 1]; int8 runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1]; static int32 SizeToClass(int32 size) { // ... return runtime·size_to_class128[(size-1024+127) >> 7]; return runtime·size_to_class8[(size+7)>>3]; }size_to_class8とsize_to_class128のstaticキーワードが削除され、型がint32からint8に変更されました。これにより、これらの配列はグローバルなシンボルとなり、malloc.gocから直接アクセスできるようになります。- 配列名も
runtime·プレフィックスが付けられ、Goランタイムの命名規則に沿うようになりました。 - 元の
runtime·SizeToClass関数は、static int32 SizeToClass(int32 size)という形で、このファイル内でのみ使用されるヘルパー関数として残されました。これは、InitSizes関数内のSizeToClassの二重チェックロジックで引き続き使用されるためです。
これらの変更により、メモリ割り当てのホットパスにおける関数呼び出しのオーバーヘッドが排除され、ルックアップテーブルのメモリ効率が向上し、L1キャッシュの利用が最適化されることで、全体的なパフォーマンスが改善されました。
関連リンク
- Go Gerrit Change: https://golang.org/cl/9199044
参考にした情報源リンク
- Goのメモリ管理に関する公式ドキュメントやブログ記事 (一般的なGoのメモリ管理の理解のため)
- CPUキャッシュの仕組みに関する一般的な情報 (L1キャッシュの理解のため)
- C言語における
staticとexternキーワードの役割 (変数スコープの理解のため) - Goのソースコード (変更内容の確認のため)
- Goのベンチマークに関する情報 (ベンチマーク結果の解釈のため)
- Goのランタイムに関する技術記事 (Goランタイムの内部動作の理解のため)