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

このコミットは、Go言語のランタイムにおけるチャネルとマップがインターフェース型を扱えるようにするための重要な変更を導入しています。これにより、Goの型システムと並行処理モデルの柔軟性が大幅に向上しました。

コミット

commit 3935610e35bbbfba7771b7fd1be93b3328ded4e4
Author: Russ Cox <rsc@golang.org>
Date:   Tue Dec 9 16:16:07 2008 -0800

    chans and maps of interfaces
    
    R=r
    DELTA=746  (729 added, 1 deleted, 16 changed)
    OCL=20858
    CL=20858
---
 src/runtime/chan.c    |  42 +--
 src/runtime/hashmap.c |  11 +-\
 src/runtime/runtime.c |   3 +-\
 src/runtime/runtime.h |   2 +-\
 test/chan/powser2.go  | 720 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 5 files changed, 755 insertions(+), 23 deletions(-)

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

https://github.com/golang/go/commit/3935610e35bbbfba7771b7fd1be93b3328ded4e4

変更の背景

Go言語は、静的型付け言語でありながら、インターフェースを通じて高い柔軟性とポリモーフィズムを提供します。チャネルはGoの並行処理の根幹をなす要素であり、ゴルーチン間の安全な通信手段を提供します。マップはキーと値のペアを格納するための組み込みデータ構造です。

このコミット以前は、Goのチャネルやマップは、具体的な型（プリミティブ型や構造体など）のデータしか直接扱うことができませんでした。しかし、Goの設計思想において、インターフェースは「何ができるか」という振る舞いを定義し、異なる具体的な型を統一的に扱うための強力なメカニズムです。

チャネルやマップがインターフェース型を直接サポートしない場合、開発者は異なる型のデータを送受信・格納するために、型アサーションや型スイッチを多用したり、interface{}（空インターフェース）を介してデータをやり取りする必要がありました。これはコードの複雑性を増し、型安全性を損なう可能性がありました。

このコミットの目的は、Goのランタイムレベルでチャネルとマップがインターフェース型をネイティブにサポートするように拡張することです。これにより、より柔軟で型安全な並行処理とデータ構造の利用が可能になり、Go言語の表現力と実用性が向上します。特に、interface{}型をチャネルやマップで扱う際に、内部でその具体的な型情報と値が適切に管理されるようにすることが重要でした。

test/chan/powser2.goの追加は、この変更がチャネルを介した複雑なデータストリーム（この場合は冪級数）の表現にどのように役立つかを示すテストケースとして機能しています。冪級数は、無限の係数シーケンスとして考えることができ、チャネルを介してこれらの係数をストリームとして送信することで表現できます。インターフェース型をチャネルで扱えるようになることで、rat（有理数）のようなカスタム型をitemインターフェースとして抽象化し、より汎用的な冪級数演算を実装できるようになります。

前提知識の解説

Go言語のチャネル (Channels)

Goのチャネルは、ゴルーチン（Goの軽量スレッド）間で値を安全に送受信するための通信メカニズムです。チャネルは型付けされており、特定の型の値のみを転送できます。

通信と同期: チャネルは、メモリを共有するのではなく、通信によってメモリを共有するというGoの哲学に従います。これにより、競合状態を防ぎ、ゴルーチン間の同期を容易にします。
ブロッキング操作: デフォルトでは、チャネルへの送信操作と受信操作はブロッキングされます。これにより、送信側と受信側が準備できるまで待機し、暗黙的な同期が実現されます。
バッファリング: バッファなしチャネル（容量ゼロ）とバッファ付きチャネル（非ゼロ容量）があります。バッファなしチャネルは、送信側と受信側が同時に準備ができていないとブロックします。バッファ付きチャネルは、バッファが満杯でない限り、送信側がブロックせずに値を送信できます。

Go言語のマップ (Maps)

Goのマップは、キーと値のペアを格納する組み込みのハッシュテーブル実装です。

キーの型: マップのキーは比較可能な型である必要があります（例: 整数、文字列、ポインタ、チャネル、インターフェース型）。スライス、マップ、関数などは比較可能ではないため、キーとして使用できません。
値の型: マップの値は任意の型にすることができます。
ランタイムとの連携: マップの内部実装はGoのランタイムによって管理されており、キーのハッシュ計算や値の格納・検索などが行われます。

Go言語のインターフェース (Interfaces)

Goのインターフェースは、メソッドのシグネチャの集合を定義します。Goのインターフェースは暗黙的に満たされます。

暗黙的な実装: ある型がインターフェースで宣言されたすべてのメソッドを実装していれば、その型はそのインターフェースを暗黙的に満たします。implementsのようなキーワードは不要です。
ポリモーフィズム: インターフェースを使用することで、任意のインターフェースを満たす型に対して汎用的なコードを書くことができます。
内部表現: インターフェースの値は、通常、2つの要素として内部的に表現されます。1つは具体的な型（T）、もう1つはその値（V）です。これにより、インターフェース変数は異なる具体的な型の値を保持できます。

Goランタイム (Runtime)

Goランタイムは、Goプログラムの実行を管理する不可欠な部分です。コンパイルされたGoバイナリに静的にリンクされます。

ゴルーチンとスケジューリング: ゴルーチンのスケジューリング、メモリ管理（ガベージコレクションを含む）、チャネルやマップなどの組み込みデータ構造の内部実装を管理します。
型システムとの連携: ランタイムは、インターフェースが保持する動的な型情報と値を管理する上で重要な役割を果たします。

冪級数 (Power Series) とチャネル

冪級数とは、$a_0 + a_1x + a_2x^2 + \dots$ のように、無限の係数シーケンスで表される数学的な級数です。Goのチャネルは、このような無限のシーケンスをストリームとして表現するのに非常に適しています。各チャネルの値が級数における次の係数を表すことで、冪級数に対する加算、乗算、微分などの操作を、チャネルを介したデータフローとして実装できます。これは、Doug McIlroyの「Squinting at Power Series」という概念に基づいています。

技術的詳細

このコミットの主要な技術的課題は、Goのランタイムがチャネルとマップ内でインターフェース型を効率的かつ安全に扱う方法を実装することでした。インターフェース型は、その性質上、内部で異なるサイズの具体的な値を保持する可能性があるため、固定サイズのメモリ割り当てを前提とするチャネルやマップの既存のデータ構造を調整する必要がありました。

具体的には、以下の変更が行われました。

src/runtime/chan.c の変更:
- チャネルの要素（elem）のサイズを、インターフェース型が保持する可能性のある最大サイズに対応できるように調整しました。インターフェースは、ポインタと型情報の2つのワードで構成されるため、これらを格納できる十分なスペースが必要です。
- SudoG（select操作で使用されるゴルーチン情報）とLink（非同期キューのデータ要素）の構造体において、elemフィールドのサイズをsizeof(d->elem)からsizeof(*d) + c->elemsize - sizeof(d->elem)のように動的に調整するように変更されました。これは、チャネルが保持する要素の実際のサイズ（c->elemsize）に基づいてメモリを割り当てることを意味します。これにより、インターフェース型のように可変サイズのデータを効率的に扱えるようになります。
- sys·selectsend, sys·selectrecv, sys·selectdefaultなどのselect関連の関数で、Scase構造体のポインタを扱うように変更されました。以前は&sel->scase[i]のように配列の要素への直接参照でしたが、sel->scase[i]のようにポインタを介してアクセスするように変更され、必要に応じてmal（メモリ割り当て）が追加されました。これは、Scaseが可変サイズのデータを保持する可能性があるため、動的なメモリ割り当てが必要になったことを示唆しています。
src/runtime/hashmap.c の変更:
- マップのキーと値の型を扱うためのアルゴリズム選択ロジックが更新されました。具体的には、sys·newmap関数内でkeyalgとvalalgのチェックが>= 3から>= 4に変更されています。これは、新しいアルゴリズム（algarrayのインデックス3）がインターフェース型のために追加されたことを示しています。
src/runtime/runtime.c および src/runtime/runtime.h の変更:
- algarrayというグローバル配列のサイズが[3]から[4]に拡張されました。
- algarrayのインデックス3に新しいAlgエントリが追加されました。コメントには// 3 - treat interfaces as memoryとあり、これはインターフェース型をメモリとして扱うための新しいアルゴリズムが導入されたことを明確に示しています。このアルゴリズムは、インターフェースの内部表現（ポインタと型情報）を直接メモリとしてハッシュ、比較、コピー、プリントすることを目的としています。

これらの変更により、Goのランタイムは、チャネルやマップがインターフェース型を扱う際に、その内部表現（具体的な型と値）を適切に管理し、メモリを効率的に割り当て、正しいハッシュ、比較、コピー操作を実行できるようになりました。

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

`src/runtime/chan.c`

--- a/src/runtime/chan.c
+++ b/src/runtime/chan.c
@@ -17,10 +17,10 @@ typedef	struct	Scase	Scase;
 struct	SudoG
 {
 	G*	g;		// g and selgen constitute
-	byte	elem[8];	// synch data element
+	byte	elem[8];	// synch data element (+ more)
 	int16	offset;		// offset of case number
 	int32	selgen;		// a weak pointer to g
 	SudoG*	link;
 };
 
 struct	WaitQ
@@ -45,7 +45,7 @@ struct	Hchan
 struct	Link
 {
 	Link*	link;			// asynch queue circular linked list
-	byte	elem[8];		// asynch queue data element
+	byte	elem[8];		// asynch queue data element (+ more)
 };
 
 struct	Scase
@@ -65,7 +65,7 @@ struct	Select
 	uint16	tcase;			// total count of scase[]
 	uint16	ncase;			// currently filled scase[]
 	Select*	link;			// for freelist
-	Scase	scase[1];		// one per case
+	Scase*	scase[1];		// one per case
 };
 
 static	Select*	selfree[20];
@@ -108,7 +108,7 @@ sys·newchan(uint32 elemsize, uint32 elemalg, uint32 hint,
 		tb = nil;
 		te = nil;
 		for(i=0; i<hint; i++) {
-			d = mal(sizeof(*d));
+			d = mal(sizeof(*d) + c->elemsize - sizeof(d->elem));
 			if(e == nil)
 				e = d;
 			d->link = b;
@@ -430,7 +430,11 @@ sys·selectsend(Select *sel, Hchan *c, ...)
 	if(i >= sel->tcase)
 		throw("selectsend: too many cases");
 	sel->ncase = i+1;
-	cas = &sel->scase[i];
+	cas = sel->scase[i];
+	if(cas == nil) {
+		cas = mal(sizeof *cas + c->elemsize - sizeof(cas->u.elem));
+		sel->scase[i] = cas;
+	}
 
 	cas->pc = sys·getcallerpc(&sel);\n 	cas->chan = c;
@@ -473,8 +477,11 @@ sys·selectrecv(Select *sel, Hchan *c, ...)
 	if(i >= sel->tcase)
 		throw("selectrecv: too many cases");
 	sel->ncase = i+1;
-	cas = &sel->scase[i];
-
+	cas = sel->scase[i];
+	if(cas == nil) {
+		cas = mal(sizeof *cas);
+		sel->scase[i] = cas;
+	}
 	cas->pc = sys·getcallerpc(&sel);
 	cas->chan = c;
 
@@ -506,13 +513,16 @@ sys·selectdefault(Select *sel, ...)
 {
 	int32 i;
 	Scase *cas;
-	
+
 	i = sel->ncase;
 	if(i >= sel->tcase)
 		throw("selectdefault: too many cases");
 	sel->ncase = i+1;
-	cas = &sel->scase[i];
-
+	cas = sel->scase[i];
+	if(cas == nil) {
+		cas = mal(sizeof *cas);
+		sel->scase[i] = cas;
+	}
 	cas->pc = sys·getcallerpc(&sel);
 	cas->chan = nil;
 
@@ -579,7 +589,7 @@ sys·selectgo(Select *sel)
 	// pass 1 - look for something already waiting
 	dfl = nil;
 	for(i=0; i<sel->ncase; i++) {
-		cas = &sel->scase[o];
+		cas = sel->scase[o];
 
 		if(cas->send == 2) {	// default
 			dfl = cas;
@@ -613,16 +623,16 @@ sys·selectgo(Select *sel)
 		if(o >= sel->ncase)
 			o -= sel->ncase;
 	}
-	
+
 	if(dfl != nil) {
 		cas = dfl;
 		goto retc;
 	}
-		
+
 
 	// pass 2 - enqueue on all chans
 	for(i=0; i<sel->ncase; i++) {
-		cas = &sel->scase[o];
+		cas = sel->scase[o];
 		c = cas->chan;
 
 		if(c->dataqsiz > 0) {
@@ -682,7 +692,7 @@ sys·selectgo(Select *sel)
 	lock(&chanlock);
 	sg = g->param;
 	o = sg->offset;
-	cas = &sel->scase[o];
+	cas = sel->scase[o];
 	c = cas->chan;
 
 	if(xxx) {
@@ -832,7 +842,7 @@ allocsg(Hchan *c)
 	if(sg != nil) {
 		c->free = sg->link;
 	} else
-		sg = mal(sizeof(*sg));
+		sg = mal(sizeof(*sg) + c->elemsize - sizeof(sg->elem));
 	sg->selgen = g->selgen;
 	sg->g = g;
 	sg->offset = 0;

`src/runtime/hashmap.c`

--- a/src/runtime/hashmap.c
+++ b/src/runtime/hashmap.c
@@ -662,8 +663,8 @@ sys·newmap(uint32 keysize, uint32 valsize,
 {
 	Hmap *h;
 
-\tif(keyalg >= 3 ||
-\t   valalg >= 3) {
+\tif(keyalg >= 4 ||
+\t   valalg >= 4) {
 		prints("0<=");
 		sys·printint(keyalg);
 		prints("<");

`src/runtime/runtime.c`

--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -644,11 +644,12 @@ pointercopy(uint32 s, void **a, void **b)
 }
 
 Alg
-algarray[3] =
+algarray[4] =
 {
 	{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 0
 	{\tstringhash,\tstringequal,\tstringprint,\tstringcopy\t},  // 1
 //\t{\tpointerhash,\tpointerequal,\tpointerprint,\tpointercopy\t},  // 2
 	{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 2 - treat pointers as ints
+\t{\tmemhash,\tmemequal,\tmemprint,\tmemcopy\t},  // 3 - treat interfaces as memory
 };

`src/runtime/runtime.h`

--- a/src/runtime/runtime.h
+++ b/src/runtime/runtime.h
@@ -220,7 +220,7 @@ struct	Func
 /*
  * external data
  */
-extern	Alg	algarray[3];
+extern	Alg	algarray[4];
 extern	string	emptystring;
 G*	allg;
 int32	goidgen;

`test/chan/powser2.go`

このファイルは新規追加されており、チャネルを介して冪級数を表現し、インターフェース型（item）を使用することで、その柔軟性を示すテストケースとなっています。

コアとなるコードの解説

`src/runtime/chan.c` の変更点

可変長要素のサポート: SudoG、Link、Scase構造体内のelemフィールドのコメントに「(+ more)」が追加され、これらの構造体がチャネル要素の実際のサイズに応じてより多くのメモリを保持できるようになったことを示唆しています。特に、sys·newchan、sys·selectsend、sys·selectrecv、sys·selectdefault、allocsg関数におけるmal（メモリ割り当て）の呼び出しが変更され、sizeof(*d) + c->elemsize - sizeof(d->elem)のように、チャネルの要素サイズ（c->elemsize）に基づいて動的にメモリを割り当てるようになりました。これは、インターフェース型のようにサイズが可変である可能性のあるデータをチャネルが効率的に格納できるようにするために不可欠です。
Scaseのポインタ化: Select構造体内のscaseフィールドがScase scase[1]からScase* scase[1]に変更されました。これにより、select文の各ケースがScase構造体へのポインタを保持するようになり、必要に応じて動的にScase構造体を割り当てることが可能になります。これは、インターフェース型を扱う際に、その具体的な型に応じてScaseの内部構造が変化する可能性があるため、柔軟なメモリ管理が必要になったためと考えられます。

`src/runtime/hashmap.c` の変更点

新しいアルゴリズムの利用: sys·newmap関数で、キーと値のアルゴリズム選択の条件がkeyalg >= 3 || valalg >= 3からkeyalg >= 4 || valalg >= 4に変更されました。これは、マップがインターフェース型を扱うために、algarrayに新しく追加されたアルゴリズム（インデックス3）を利用するように指示しています。

`src/runtime/runtime.c` および `src/runtime/runtime.h` の変更点

algarrayの拡張とインターフェース用アルゴリズムの追加: Alg構造体の配列であるalgarrayのサイズが3から4に拡張されました。そして、algarrayのインデックス3に新しいエントリが追加され、コメントに// 3 - treat interfaces as memoryと明記されています。これは、インターフェース型をハッシュ、比較、プリント、コピーするための新しいアルゴリズムが導入されたことを意味します。インターフェースは内部的にポインタと型情報のペアとして表現されるため、これらの操作はインターフェースの内部メモリ表現を直接扱うように設計されています。これにより、マップがインターフェース型をキーや値として使用する際に、正しい動作が保証されます。

これらの変更は、Goのランタイムがインターフェースの動的な性質（異なる具体的な型と値を持つことができる）を考慮し、チャネルとマップがこれらの型を効率的かつ安全に処理できるようにするための基盤を構築しています。

comemo