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

このコミットは、GoランタイムにおけるゴルーチンIDの割り当てメカニズムを改善し、ID生成時の競合を削減することを目的としています。具体的には、各P（プロセッサ）がゴルーチンIDをバッチで取得するように変更することで、グローバルなゴルーチンIDジェネレータ (runtime.sched.goidgen) へのアクセス頻度を減らし、並行処理のパフォーマンスを向上させています。

コミット

commit 98b50b89a8002e1a40f28d1851d0223d424825f6
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed Jan 22 10:34:36 2014 +0400

    runtime: allocate goroutine ids in batches
    Helps reduce contention on sched.goidgen.
    
    benchmark                               old ns/op    new ns/op    delta
    BenchmarkCreateGoroutines-16                  259          237   -8.49%
    BenchmarkCreateGoroutinesParallel-16          127           43  -66.06%
    
    R=golang-codereviews, dave, bradfitz, khr
    CC=golang-codereviews, rsc
    https://golang.org/cl/46970043
---
 src/pkg/runtime/proc.c    | 25 +++++++++++++++++++------
 src/pkg/runtime/runtime.h |  4 ++++
 2 files changed, 23 insertions(+), 6 deletions(-)

diff --git a/src/pkg/runtime/proc.c b/src/pkg/runtime/proc.c
index 92d6f27da3..9eb4ad9f95 100644
--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -58,9 +58,16 @@ struct Sched {\n 	int32	profilehz;\t// cpu profiling rate\n };\n \n-// The max value of GOMAXPROCS.\n-// There are no fundamental restrictions on the value.\n-enum { MaxGomaxprocs = 1<<8 };\n+enum\n+{\n+\t// The max value of GOMAXPROCS.\n+\t// There are no fundamental restrictions on the value.\n+\tMaxGomaxprocs = 1<<8,\n+\n+\t// Number of goroutine ids to grab from runtime·sched.goidgen to local per-P cache at once.\n+\t// 16 seems to provide enough amortization, but other than that it's mostly arbitrary number.\n+\tGoidCacheBatch = 16,\n+};\n \n Sched	runtime·sched;\n int32	runtime·gomaxprocs;\n@@ -1752,6 +1759,7 @@ runtime·newproc1(FuncVal *fn, byte *argp, int32 narg, int32 nret, void *callerp\n {\n 	byte *sp;\n 	G *newg;\n+\tP *p;\n 	int32 siz;\n \n //runtime·printf(\"newproc1 %p %p narg=%d nret=%d\\n\", fn->fn, argp, narg, nret);\n@@ -1766,7 +1774,8 @@ runtime·newproc1(FuncVal *fn, byte *argp, int32 narg, int32 nret, void *callerp\n \tif(siz > StackMin - 1024)\n \t\truntime·throw(\"runtime.newproc: function arguments too large for new goroutine\");\n \n-\tif((newg = gfget(m->p)) != nil) {\n+\tp = m->p;\n+\tif((newg = gfget(p)) != nil) {\n \t\tif(newg->stackguard - StackGuard != newg->stack0)\n \t\t\truntime·throw(\"invalid stack in newg\");\n \t} else {\n@@ -1790,11 +1799,15 @@ runtime·newproc1(FuncVal *fn, byte *argp, int32 narg, int32 nret, void *callerp\n \truntime·gostartcallfn(&newg->sched, fn);\n \tnewg->gopc = (uintptr)callerpc;\n \tnewg->status = Grunnable;\n-\tnewg->goid = runtime·xadd64(&runtime·sched.goidgen, 1);\n+\tif(p->goidcache == p->goidcacheend) {\n+\t\tp->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);\n+\t\tp->goidcacheend = p->goidcache + GoidCacheBatch;\n+\t}\n+\tnewg->goid = p->goidcache++;\n \tnewg->panicwrap = 0;\n \tif(raceenabled)\n \t\tnewg->racectx = runtime·racegostart((void*)callerpc);\n-\trunqput(m->p, newg);\n+\trunqput(p, newg);\n \n \tif(runtime·atomicload(&runtime·sched.npidle) != 0 && runtime·atomicload(&runtime·sched.nmspinning) == 0 && fn->fn != runtime·main)  // TODO: fast atomic\n \t\twakep();\ndiff --git a/src/pkg/runtime/runtime.h b/src/pkg/runtime/runtime.h
index 119b9e3b7d..5e3c0c497f 100644
--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -385,6 +385,10 @@ struct P
 	MCache*	mcache;\n 	Defer*	deferpool[5];	// pool of available Defer structs of different sizes (see panic.c)\n \n+\t// Cache of goroutine ids, amortizes accesses to runtime·sched.goidgen.\n+\tuint64\tgoidcache;\n+\tuint64\tgoidcacheend;\n+\n \t// Queue of runnable goroutines.\n \tuint32\trunqhead;\n \tuint32\trunqtail;\n```

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

[https://github.com/golang/go/commit/98b50b89a8002e1a40f28d1851d0223d424825f6](https://github.com/golang/go/commit/98b50b89a8002e1a40f28d1851d0223d424825f6)

## 元コミット内容

このコミットは、GoランタイムがゴルーチンIDを割り当てる方法を変更し、ID生成時の競合を軽減することを目的としています。具体的には、ゴルーチンIDを一度に1つずつ取得するのではなく、バッチで取得するように変更しています。これにより、グローバルなゴルーチンIDジェネレータ (`runtime.sched.goidgen`) へのアトミックなアクセス回数が減少し、特に多数のゴルーチンが並行して生成されるシナリオでのパフォーマンスが向上します。

ベンチマーク結果は以下の通りです。
*   `BenchmarkCreateGoroutines-16`: 259 ns/op から 237 ns/op へと 8.49% 改善。
*   `BenchmarkCreateGoroutinesParallel-16`: 127 ns/op から 43 ns/op へと 66.06% 改善。

特に並行してゴルーチンが生成されるケースで顕著な改善が見られます。

## 変更の背景

Goランタイムは、新しいゴルーチンが作成されるたびに一意のID（`goid`）を割り当てます。このIDは、`runtime.sched.goidgen`というグローバルなカウンタから取得されます。複数のP（プロセッサ、Goスケジューラにおける論理的なCPU）が同時にゴルーチンを生成しようとすると、この`goidgen`カウンタへのアクセスが競合（コンテンション）を引き起こします。

競合とは、複数の並行プロセスやスレッドが共有リソース（この場合は`goidgen`カウンタ）に同時にアクセスしようとするときに発生する状況です。共有リソースへのアクセスは通常、アトミック操作やロックによって保護されるため、競合が発生すると、他のプロセスはリソースが解放されるまで待機しなければなりません。これにより、並行処理の効率が低下し、スループットが制限されます。

このコミット以前は、新しいゴルーチンが作成されるたびに、`runtime.xadd64(&runtime.sched.goidgen, 1)`というアトミックな加算操作によって`goidgen`から1つずつIDが取得されていました。ゴルーチン生成が頻繁に行われるアプリケーションでは、この単一のグローバルカウンタがボトルネックとなり、パフォーマンスの低下を招いていました。この変更の背景には、このボトルネックを解消し、ゴルーチン生成の並行性を高めるという明確な目的があります。

## 前提知識の解説

このコミットを理解するためには、以下のGoランタイムの概念と並行処理の基本的な知識が必要です。

### Goスケジューラ (M, P, G)

Goランタイムは、独自のスケジューラを持っており、OSのスレッド（M: Machine）上でゴルーチン（G: Goroutine）を実行します。P（Processor）は、MとGの間のコンテキストとして機能し、実行可能なゴルーチンのローカルキューを管理します。

*   **G (Goroutine)**: Goにおける軽量な実行単位です。OSスレッドよりもはるかに軽量で、数百万のゴルーチンを同時に実行できます。各ゴルーチンには一意のID (`goid`) が割り当てられます。
*   **M (Machine)**: OSのスレッドに相当します。Goランタイムは、M上でPとGを実行します。
*   **P (Processor)**: 論理的なプロセッサであり、Mにアタッチされます。Pは実行可能なゴルーチンのローカルキュー (`runq`) を持ち、ゴルーチンをMにディスパッチします。`GOMAXPROCS`環境変数によって設定されるPの数は、同時に実行できるOSスレッドの最大数を決定します。

### ゴルーチンID (`goid`)

各ゴルーチンには、そのゴルーチンを一意に識別するための整数IDが割り当てられます。このIDはデバッグやプロファイリングの際に役立ちます。以前は、このIDはグローバルなカウンタ`runtime.sched.goidgen`から順次割り当てられていました。

### `runtime.sched.goidgen`

これは、Goランタイム全体でゴルーチンIDを生成するためのグローバルな64ビットカウンタです。新しいゴルーチンが作成されるたびに、このカウンタがインクリメントされ、その値が新しいゴルーチンのIDとして使用されます。

### `runtime.xadd64`

これは、Goランタイム内部で使用されるアトミックな加算操作です。`runtime.xadd64(ptr, delta)`は、`ptr`が指す64ビット整数に`delta`を加算し、その結果を`ptr`に格納し、加算前の元の値を返します。この操作は、複数のスレッドから同時に実行されても、データの一貫性を保証します。`goidgen`のような共有カウンタを安全にインクリメントするために使用されます。

### 競合 (Contention)

並行プログラミングにおいて、複数のスレッドやゴルーチンが同時に同じ共有リソース（メモリ、ファイル、カウンタなど）にアクセスしようとするときに発生する状況です。共有リソースへのアクセスがアトミック操作やロックによって保護されている場合、競合が発生すると、他のアクセスは待機状態になり、プログラムの全体的なスループットが低下します。

### キャッシュとバッチ処理

パフォーマンス最適化の一般的な手法として、キャッシュとバッチ処理があります。
*   **キャッシュ**: 頻繁にアクセスされるデータを一時的に高速なメモリに保存することで、低速なストレージへのアクセス回数を減らします。
*   **バッチ処理**: 個々の操作をまとめて一度に処理することで、オーバーヘッドを削減します。このコミットでは、ゴルーチンIDの取得をバッチ化することで、`goidgen`へのアトミックなアクセスという高コストな操作の回数を減らしています。

## 技術的詳細

このコミットの核心は、ゴルーチンIDの割り当てをグローバルな`runtime.sched.goidgen`から、各P（プロセッサ）のローカルキャッシュに移行した点にあります。

### 変更前

変更前は、`runtime.newproc1`関数（新しいゴルーチンを作成する内部関数）内で、新しいゴルーチンが作成されるたびに以下の行が実行されていました。

```c
newg->goid = runtime·xadd64(&runtime·sched.goidgen, 1);

これは、runtime.sched.goidgenというグローバルなカウンタをアトミックに1つインクリメントし、その結果を新しいゴルーチンのIDとして割り当てる操作です。runtime.xadd64はアトミック操作であるため、複数のPが同時にゴルーチンを作成しようとすると、この操作がボトルネックとなり、競合が発生していました。

変更後

変更後は、各Pにgoidcacheとgoidcacheendという2つの新しいフィールドが追加されました。

goidcache: Pが現在利用可能なゴルーチンIDの範囲の開始点。
goidcacheend: Pが現在利用可能なゴルーチンIDの範囲の終了点（排他的）。

新しいゴルーチンが作成される際、runtime.newproc1はまず、現在のPのローカルキャッシュ (p->goidcache) からIDを取得しようとします。

if(p->goidcache == p->goidcacheend) {
    p->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);
    p->goidcacheend = p->goidcache + GoidCacheBatch;
}
newg->goid = p->goidcache++;

このコードブロックの動作は以下の通りです。

if(p->goidcache == p->goidcacheend): Pのローカルキャッシュが空になったかどうかをチェックします。つまり、Pが以前に取得したバッチ内のすべてのIDを使い果たしたかどうかを確認します。
キャッシュが空の場合:
- p->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);: グローバルなruntime.sched.goidgenからGoidCacheBatch（このコミットでは16に設定）個のIDをアトミックに取得します。runtime.xadd64は加算前の値を返すため、これが新しいバッチの開始IDとなります。
- p->goidcacheend = p->goidcache + GoidCacheBatch;: 新しいバッチの終了IDを設定します。
newg->goid = p->goidcache++;: Pのローカルキャッシュから次のIDを取得し、p->goidcacheをインクリメントして次のゴルーチンに備えます。

このメカニズムにより、runtime.sched.goidgenへのアトミックなアクセスは、GoidCacheBatch個のゴルーチンIDを使い切ったときにのみ発生します。これにより、グローバルカウンタへのアクセス頻度が大幅に減少し、結果として競合が緩和されます。

コミットメッセージには「16 seems to provide enough amortization, but other than that it's mostly arbitrary number.」とあります。これは、GoidCacheBatchの値16が、アトミック操作の償却（amortization）に十分な効果をもたらす一方で、厳密な最適値というよりは経験的な選択であることを示唆しています。バッチサイズが大きすぎると、PがIDを使い切る前にシャットダウンした場合にIDが無駄になる可能性がありますが、小さすぎると競合削減の効果が薄れます。16という値は、当時のGoランタイムのワークロードとパフォーマンス特性に基づいてバランスの取れた選択と判断されたと考えられます。

パフォーマンスへの影響

ベンチマーク結果は、この変更がゴルーチン生成のパフォーマンスに大きな影響を与えたことを明確に示しています。

BenchmarkCreateGoroutines-16: これは単一のPでゴルーチンを連続して作成するシナリオを示唆しています。この場合でも、バッチ処理によってxadd64のオーバーヘッドが償却されるため、わずかながら改善が見られます（-8.49%）。
BenchmarkCreateGoroutinesParallel-16: これは複数のPが並行してゴルーチンを作成するシナリオを示唆しており、このコミットが解決しようとしている競合の問題が顕著に現れるケースです。このベンチマークでは、パフォーマンスが66.06%も改善されており、バッチ割り当てがグローバルカウンタの競合を劇的に削減したことを裏付けています。

この改善は、特に高並行性のGoアプリケーションにおいて、ゴルーチン生成のオーバーヘッドを削減し、全体的なスループットを向上させる上で非常に重要です。

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

このコミットによる主要なコード変更は、以下の2つのファイルに集中しています。

src/pkg/runtime/proc.c: ゴルーチンIDの割り当てロジックが変更されたファイル。
src/pkg/runtime/runtime.h: P構造体に新しいフィールドが追加されたファイル。

`src/pkg/runtime/proc.c` の変更

GoidCacheBatch 定数の追加:

enum
{
	// The max value of GOMAXPROCS.
	// There are no fundamental restrictions on the value.
	MaxGomaxprocs = 1<<8,

	// Number of goroutine ids to grab from runtime·sched.goidgen to local per-P cache at once.
	// 16 seems to provide enough amortization, but other than that it's mostly arbitrary number.
	GoidCacheBatch = 16,
};

MaxGomaxprocsの定義に加えて、GoidCacheBatchという新しい定数が追加されました。この値（16）は、runtime.sched.goidgenから一度に取得するゴルーチンIDの数を定義します。

runtime·newproc1 関数の変更: 新しいゴルーチンを作成する際にIDを割り当てる部分が変更されました。
```
// 変更前
// newg->goid = runtime·xadd64(&runtime·sched.goidgen, 1);

// 変更後
p = m->p; // 現在のMにアタッチされているPを取得
if(p->goidcache == p->goidcacheend) {
	p->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);
	p->goidcacheend = p->goidcache + GoidCacheBatch;
}
newg->goid = p->goidcache++;
```
この変更により、ゴルーチンIDはまずPのローカルキャッシュから取得され、キャッシュが空の場合にのみグローバルなgoidgenからバッチで取得されるようになりました。
m->p から p への変更: gfgetとrunqputの呼び出しで、m->pを直接使用する代わりに、ローカル変数pを導入しています。これは機能的な変更というよりは、コードの可読性と一貫性を向上させるためのリファクタリングです。

`src/pkg/runtime/runtime.h` の変更

P 構造体へのフィールド追加: P構造体に、ゴルーチンIDのローカルキャッシュを管理するための2つの新しいフィールドが追加されました。
```
struct P
{
	// ... 既存のフィールド ...

	// Cache of goroutine ids, amortizes accesses to runtime·sched.goidgen.
	uint64	goidcache;
	uint64	goidcacheend;

	// ... 既存のフィールド ...
};
```
goidcacheは現在Pが保持しているIDの範囲の開始点、goidcacheendはその終了点を示します。これにより、各Pが独立してゴルーチンIDのバッチを管理できるようになります。

コアとなるコードの解説

このコミットのコアとなるコードは、src/pkg/runtime/proc.c 内の runtime·newproc1 関数におけるゴルーチンIDの割り当てロジックの変更と、src/pkg/runtime/runtime.h 内の P 構造体へのキャッシュフィールドの追加です。

`P` 構造体へのキャッシュフィールド追加 (`runtime.h`)

	// Cache of goroutine ids, amortizes accesses to runtime·sched.goidgen.
	uint64	goidcache;
	uint64	goidcacheend;

この変更は、各PがゴルーチンIDのローカルキャッシュを持つための基盤を確立します。

goidcache: Pが次に割り当てるゴルーチンIDの現在値。
goidcacheend: Pが現在保持しているIDのバッチの終端（この値は含まれない）。これらのフィールドは、runtime.sched.goidgenへのグローバルなアトミック操作のコストを償却（amortize）するために使用されます。つまり、一度のグローバルなアトミック操作で複数のIDを取得し、それらをローカルで消費することで、グローバルな競合を減らすという意図がコメントに明記されています。

`runtime·newproc1` 関数内のID割り当てロジック (`proc.c`)

	p = m->p; // 現在のMにアタッチされているPを取得
	if((newg = gfget(p)) != nil) {
		// ... 既存のコード ...
	} else {
		// ... 既存のコード ...
	}
	// ... 既存のコード ...
	newg->status = Grunnable;
	// 変更されたID割り当てロジック
	if(p->goidcache == p->goidcacheend) {
		// ローカルキャッシュが空の場合、グローバルカウンタから新しいバッチを取得
		p->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);
		p->goidcacheend = p->goidcache + GoidCacheBatch;
	}
	newg->goid = p->goidcache++; // ローカルキャッシュからIDを割り当て、次のIDに進む
	newg->panicwrap = 0;
	// ... 既存のコード ...
	if(raceenabled)
		newg->racectx = runtime·racegostart((void*)callerpc);
	runqput(p, newg); // 変更: m->p から p へ

このコードブロックは、新しいゴルーチンが作成されるたびに実行されます。

p = m->p;: 現在のM（OSスレッド）が実行しているP（論理プロセッサ）へのポインタを取得します。これにより、Pのローカルキャッシュにアクセスできるようになります。
if(p->goidcache == p->goidcacheend): この条件は、現在のPが保持しているゴルーチンIDのローカルキャッシュが使い果たされたかどうかをチェックします。
- 初回またはキャッシュが空の場合、p->goidcacheとp->goidcacheendは等しくなります。
キャッシュが空の場合の処理:
- p->goidcache = runtime·xadd64(&runtime·sched.goidgen, GoidCacheBatch);: ここが最も重要な変更点です。runtime.sched.goidgenというグローバルなカウンタに対して、GoidCacheBatch（16）個のIDをアトミックに加算します。runtime.xadd64は加算前の値を返すため、この操作によってPはGoidCacheBatch個の連続したIDのブロックの開始IDを取得し、それをp->goidcacheに設定します。
- p->goidcacheend = p->goidcache + GoidCacheBatch;: 取得したバッチの終了IDを設定します。これで、Pは次の16個のゴルーチンIDをグローバルカウンタにアクセスすることなく、ローカルで割り当てられるようになります。
newg->goid = p->goidcache++;: Pのローカルキャッシュから次の利用可能なIDを新しいゴルーチンに割り当てます。その後、p->goidcacheをインクリメントして、次のゴルーチンに割り当てるIDを準備します。

このバッチ割り当て戦略により、runtime.sched.goidgenへのアトミックなアクセスは、GoidCacheBatch個のゴルーチンが作成されるごとに1回に削減されます。これにより、グローバルなロックやアトミック操作による競合が大幅に減少し、特に多数のゴルーチンが並行して生成される高負荷なシナリオでのパフォーマンスが劇的に向上します。

runqput(p, newg); の変更は、m->p を直接参照する代わりに、既に取得したローカル変数 p を使用するように統一したもので、コードの整合性を高めています。

参考にした情報源リンク

Go言語のソースコード (特に src/runtime/proc.go および src/runtime/runtime.h の関連部分)
Go言語の公式ブログ
Go言語のスケジューラに関する技術ブログや記事 (例: Medium, Go Conferenceの発表資料など)
コミットメッセージに記載されているベンチマーク結果
https://golang.org/cl/46970043 (このコミットのGo Code Review)I have generated the detailed technical explanation in Markdown format, following all the specified instructions and chapter structure. The output is provided directly to standard output as requested.

comemo