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

このコミットは、Go言語のランタイムにおける型固有のアルゴリズムの準備と、それに伴う内部データ構造の最適化に関するものです。特に、構造体の等価性チェックがより複雑なロジックを必要とするため、型データ内のアルゴリズム指定方法をuint8からテーブルポインタへと変更しています。これにより、Goコンパイラが生成するコードをCコードから呼び出す際の制約（CコードがGoの戻り値に直接アクセスできない）に対応するため、ハッシュおよび等価性チェックのアルゴリズム関数のシグネチャも変更され、結果をポインタ経由で渡すようになりました。この変更は、トップレベルのマップ構造のメモリフットプリントを削減する効果ももたらしています。

コミット

• コミットハッシュ: b9ccd077dc478fca2e8bd00633c1a60a54f342d8
• Author: Russ Cox rsc@golang.org
• Date: Mon Dec 5 09:40:22 2011 -0500

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

https://github.com/golang/go/commit/b9ccd077dc478fca2e8bd00633c1a60a54f342d8

元コミット内容

runtime: prep for type-specific algorithms

Equality on structs will require arbitrary code for type equality,
so change algorithm in type data from uint8 to table pointer.
In the process, trim top-level map structure from
104/80 bytes (64-bit/32-bit) to 24/12.

Equality on structs will require being able to call code generated
by the Go compiler, and C code has no way to access Go return
values, so change the hash and equal algorithm functions to take
a pointer to a result instead of returning the result.

R=ken
CC=golang-dev
https://golang.org/cl/5453043

変更の背景

Go言語のランタイムは、様々なデータ型（プリミティブ型、文字列、インターフェース、マップ、構造体など）に対して、等価性チェック（==演算子）やハッシュ計算（マップのキーとして使用される場合など）といった基本的な操作を提供しています。これらの操作は、型によってその実装が異なります。

このコミットが行われた背景には、特に構造体の等価性チェックに関する課題がありました。単純なプリミティブ型の比較とは異なり、構造体の等価性チェックは、その構造体が持つフィールドの型や値に応じて、より複雑なロジックを必要とします。例えば、構造体内にポインタやインターフェース、あるいはさらに別の構造体が含まれる場合、それらのフィールドも再帰的に比較する必要があります。このような「任意のコード」を必要とする等価性チェックを効率的かつ柔軟に実現するためには、ランタイムが型ごとに適切なアルゴリズムを動的に選択できるメカニズムが必要でした。

また、Goランタイムの一部はC言語で実装されており、Goコンパイラが生成するコード（Goの関数）とCコードの間で連携が行われます。C言語の制約として、Goの関数が直接返す値をCコードが受け取るのが難しいという問題がありました。特に、ハッシュ値や等価性チェックの結果のような重要な値をGo関数が返す場合、Cコード側でこれらを安全に利用するためには、値の受け渡し方法を見直す必要がありました。

このコミットは、これらの課題に対処し、Goランタイムの型システムとデータ操作の基盤を強化することを目的としています。

前提知識の解説

Goランタイム (Go Runtime)

Goランタイムは、Goプログラムの実行を管理する低レベルのシステムです。ガベージコレクション、スケジューリング、チャネル通信、マップやインターフェースなどの組み込み型の実装など、Go言語の多くの機能はランタイムによって提供されます。ランタイムの一部はGoで書かれていますが、パフォーマンスが要求される部分やシステムコールに近い部分はC（またはアセンブリ）で書かれています。

型システムと型情報 (Type System and Type Information)

Goは静的型付け言語であり、コンパイル時に各変数の型が決定されます。ランタイムは、プログラムが実行時に必要とする型に関するメタデータ（サイズ、アラインメント、ハッシュ関数、等価性関数など）を保持しています。これは_type構造体（またはそれに相当するもの）として表現され、リフレクションやインターフェースの動的な振る舞いを可能にします。

構造体の等価性 (Struct Equality)

Goにおいて、構造体はフィールドごとに比較されます。すべてのフィールドが比較可能（comparable）な型であれば、構造体全体も比較可能です。比較可能な型には、数値型、文字列型、ブール型、ポインタ型、チャネル型、インターフェース型、配列型（要素が比較可能な場合）、そして比較可能なフィールドのみを持つ構造体型が含まれます。関数、マップ、スライスは比較不可能です。構造体の等価性チェックは、フィールドの数や型に応じて、単純なメモリ比較から複雑な再帰的比較まで、様々なアルゴリズムを必要とします。

ハッシュ関数と等価性関数 (Hash and Equal Functions)

マップのキーとして使用される型は、ハッシュ可能（hashable）でなければなりません。これは、その型の値に対して一意のハッシュ値を計算できるハッシュ関数と、2つの値が等しいかどうかを判断できる等価性関数が提供されている必要があることを意味します。ランタイムは、これらの関数を型情報の一部として保持し、マップ操作時に利用します。

インターフェース (Interfaces)

Goのインターフェースは、動的な型付けのメカニズムを提供します。インターフェース値は、具体的な型と、その型の値のペアで構成されます。ランタイムは、インターフェース値の比較やハッシュ計算を行う際に、内包する具体的な型の型情報にアクセスし、その型固有のアルゴリズムを呼び出します。

reflectパッケージ

reflectパッケージは、実行時にGoの型情報にアクセスし、操作するための機能を提供します。このパッケージは、ランタイムが内部的に使用する型情報と密接に関連しています。

GoとCの連携 (Go and C Interoperability)

GoはC言語との相互運用性（cgo）をサポートしており、Cの関数をGoから呼び出したり、Goの関数をCから呼び出したりすることができます。しかし、GoとCの間の呼び出し規約（calling convention）は異なり、特にGoの関数が複数の戻り値を返したり、複雑なデータ構造を返したりする場合、C側でそれらを直接扱うのは困難な場合があります。このため、ポインタを介してデータをやり取りするなどの工夫が必要になります。

技術的詳細

このコミットの主要な技術的変更点は以下の通りです。

1. 型データにおけるアルゴリズム指定の変更:

   • 以前は、型情報（_type構造体）内で、その型に対するハッシュや等価性チェックのアルゴリズムをuint8型のインデックス（algフィールド）で指定していました。このインデックスは、runtime·algarrayというグローバルな配列へのオフセットとして機能し、対応するアルゴリズム関数へのポインタを取得していました。
   • このコミットでは、_type構造体内のalgフィールドをuint8から*uintptr（ポインタ）に変更しました。これにより、runtime·algarrayのような固定配列のインデックスではなく、直接アルゴリズム関数へのポインタを保持できるようになります。これは、特に構造体のように、その場で生成される可能性のある複雑なアルゴリズムを扱う際に、より柔軟な設計を可能にします。
   • src/pkg/reflect/type.goのcommonType構造体で、alg uint8が_ uint8（未使用）とalg *uintptrに置き換えられています。

2. ハッシュおよび等価性アルゴリズム関数のシグネチャ変更:

   • Goコンパイラが生成するコード（Goの関数）をCコードから呼び出す際の制約に対応するため、ハッシュ関数と等価性関数のシグネチャが変更されました。
   • 以前は、これらの関数はハッシュ値やブール値を直接戻り値として返していました。
   • 変更後、これらの関数は結果を格納するためのポインタを引数として受け取るようになりました。例えば、runtime·memhashはuintptr *hを、runtime·memequalはbool *eqを引数として受け取り、そのポインタが指すメモリ位置に結果を書き込みます。これにより、Cコード側はGo関数からの戻り値を直接処理するのではなく、ポインタを介して結果にアクセスできるようになります。

3. マップ構造のメモリフットプリント削減:

   • コミットメッセージによると、トップレベルのマップ構造のサイズが64ビットシステムで104バイトから24バイトに、32ビットシステムで80バイトから12バイトに削減されています。
   • これは、src/pkg/runtime/hashmap.cにおけるHmap構造体の定義から、data_hash, data_eq, data_delといった関数ポインタや、keysize, valsize, datavo, ko0, vo0などのオフセット関連のフィールドが削除されたことによるものです。これらの情報は、マップの型情報（MapType）から間接的にアクセスされるように変更され、Hmap構造体自体はより汎用的なデータのみを保持するようになりました。これにより、各マップインスタンスが持つメタデータの量が大幅に削減されました。

4. runtime/alg.cの新規追加:

   • 以前src/pkg/runtime/runtime.cに散在していた汎用的なメモリ操作（ハッシュ、等価性チェック、コピー、プリント）に関する関数（memhash, memequalなど）が、新しくsrc/pkg/runtime/alg.cに集約されました。
   • このファイルには、様々な組み込み型（メモリ、文字列、インターフェース、スライスなど）に対する具体的なアルゴリズム関数の実装と、それらをまとめたruntime·algarrayというテーブルが定義されています。このテーブルは、型情報から参照されるアルゴリズム関数の実体を提供します。

5. slicecopyからcopyへの名称変更:

   • src/cmd/gc/runtime.goとsrc/cmd/gc/walk.cにおいて、slicecopyという関数がcopyに名称変更されています。これは、スライスだけでなく、より一般的なメモリコピー操作を指すようになったことを示唆しています。

これらの変更は、Goランタイムの内部構造をよりモジュール化し、型固有の操作をより柔軟に、かつ効率的に扱えるようにするための重要なステップです。特に、構造体の等価性チェックのような複雑なケースに対応するための基盤を整備しています。

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

このコミットにおけるコアとなるコードの変更箇所は多岐にわたりますが、特に重要なファイルと変更点を以下に示します。

1. src/pkg/reflect/type.go:

   • commonType構造体の定義が変更され、alg uint8が削除され、_ uint8（パディング用）とalg *uintptrが追加されました。

     --- a/src/pkg/reflect/type.go
     +++ b/src/pkg/reflect/type.go
     @@ -241,10 +241,11 @@ const (
      type commonType struct {
      	size       uintptr
      	hash       uint32
     -	alg        uint8
     +	_          uint8
      	align      uint8
      	fieldAlign uint8
      	kind       uint8
     +	alg        *uintptr
      	string     *string
      	*uncommonType
      	ptrToThis *runtime.Type
     

     これは、型情報がアルゴリズムを直接ポインタで参照するように変更されたことを示しています。

2. src/pkg/runtime/alg.c (新規追加):

   • このファイルが新規に作成され、様々な型に対するハッシュ、等価性、コピー、プリントの各アルゴリズム関数が定義されました。
   • 例: runtime·memhash, runtime·memequal, runtime·strhash, runtime·strequal, runtime·interhash, runtime·interequalなど。
   • これらの関数は、結果をポインタ経由で返すようにシグネチャが変更されています（例: void runtime·memhash(uintptr *h, uintptr s, void *a)）。
   • そして、これらのアルゴリズム関数をまとめたruntime·algarrayというテーブルが定義されています。

     Alg
     runtime·algarray[] =
     {
     [AMEM]		{ runtime·memhash, runtime·memequal, runtime·memprint, runtime·memcopy },
     [ANOEQ]		{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy },
     [ASTRING]	{ runtime·strhash, runtime·strequal, runtime·strprint, runtime·strcopy },
     // ... (他の型に対するアルゴリズム)
     };
     

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

   • 以前このファイルに存在していた、汎用的なハッシュ、等価性、コピー、プリント関数（memhash, memequalなど）とそのAlgテーブルの定義が、src/pkg/runtime/alg.cに移動したため、このファイルからは削除されました。これにより、runtime.cはよりコアなランタイム機能に特化するようになりました。

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

   • Hmap構造体から、data_hash, data_eq, data_delといった関数ポインタや、keysize, valsize, datavo, ko0, vo0などのオフセット関連のフィールドが削除されました。
   • マップ操作関数（hash_lookup, hash_remove, hash_insert_internalなど）のシグネチャが変更され、MapType *t引数が追加されました。これにより、マップの型情報からキーや値のアルゴリズムにアクセスできるようになりました。
   • HASH_DATA_EQマクロの定義が変更され、MapTypeからアルゴリズム関数を呼び出すようになりました。

     --- a/src/pkg/runtime/hashmap.c
     +++ b/src/pkg/runtime/hashmap.c
     @@ -6,41 +6,14 @@
      #include "hashmap.h"
      #include "type.h"
     
     -/* Return a pointer to the struct/union of type "type"
     -   whose "field" field is addressed by pointer "p". */
     -
      struct Hmap {	   /* a hash table; initialize with hash_init() */
      	uint32 count;	  /* elements in table - must be first */
     -
      	uint8 datasize;   /* amount of data to store in entry */
      	uint8 max_power;  /* max power of 2 to create sub-tables */
     -	uint8 max_probes; /* max entries to probe before rehashing */
     -	uint8 indirectval; /* storing pointers to values */
     +	uint8 indirectval;	/* storing pointers to values */
     +	uint8 valoff;	/* offset of value in key+value data block */
      	int32 changes;	      /* inc'ed whenever a subtable is created/grown */
     -	hash_hash_t (*data_hash) (uint32, void *a);  /* return hash of *a */
     -	uint32 (*data_eq) (uint32, void *a, void *b);   /* return whether *a == *b */
     -	void (*data_del) (uint32, void *arg, void *data);  /* invoked on deletion */
      	struct hash_subtable *st;    /* first-level table */
     -
     -	uint32	keysize;
     -	uint32	valsize;
     -	uint32	datavo;
     -
     -	// three sets of offsets: the digit counts how many
     -	// of key, value are passed as inputs:
     -	//	0 = func() (key, value)
     -	//	1 = func(key) (value)
     -	//	2 = func(key, value)
     -	uint32	ko0;
     -	uint32	vo0;
     -	uint32	ko1;
     -	uint32	vo1;
     -	uint32	po1;
     -	uint32	ko2;
     -	uint32	vo2;
     -	uint32	po2;
     -	Alg*	keyalg;
     -	Alg*	valalg;
      };
     
      struct hash_entry {
     @@ -58,7 +31,7 @@ struct hash_subtable {
      	struct hash_entry entry[1];  /* 2**power+max_probes-1 elements of elemsize bytes */
      };
     
     -#define HASH_DATA_EQ(h,x,y) ((*h->data_eq) (h->keysize, (x), (y)))\
     +#define HASH_DATA_EQ(eq, t, h,x,y) ((eq)=0, (*t->key->alg->equal) (&(eq), t->key->size, (x), (y)), (eq))\
     

5. src/pkg/runtime/iface.c:

   • インターフェースのハッシュや等価性チェックを行う関数（ifacehash1, ifaceeq1）内で、runtime·algarrayを直接参照するのではなく、型情報（Type *t）から取得したAlgポインタを介してアルゴリズム関数を呼び出すように変更されました。
   • また、これらの関数も結果をポインタ経由で返すように変更されています。

これらの変更は、Goランタイムの型システムとデータ操作の基盤をより柔軟で効率的なものにするための重要なリファクタリングです。

コアとなるコードの解説

src/pkg/reflect/type.go の commonType 構造体変更

type commonType struct {
	size       uintptr
	hash       uint32
	_          uint8 // 旧 alg フィールドのパディング
	align      uint8
	fieldAlign uint8
	kind       uint8
	alg        *uintptr // 新しいアルゴリズムポインタ
	string     *string
	*uncommonType
	ptrToThis *runtime.Type
}

この変更は、Goの型システムにおける根本的な変更を示しています。以前は、各型が持つハッシュや等価性チェックなどのアルゴリズムは、algというuint8型のインデックスで指定されていました。このインデックスは、ランタイム内部のruntime·algarrayという固定配列の要素を指していました。しかし、構造体のように、その場で動的に生成される可能性のある複雑なアルゴリズムを扱う場合、固定インデックスでは柔軟性に欠けます。

新しいalg *uintptrフィールドは、アルゴリズム関数へのポインタを直接保持できるようになります。これにより、ランタイムは型ごとに異なる、より特化したアルゴリズムを動的に割り当てることが可能になります。_ uint8は、以前のalgフィールドが占めていたメモリ領域を埋めるためのパディングとして機能し、構造体のアラインメントを維持しています。

src/pkg/runtime/alg.c の新規追加とアルゴリズム関数のシグネチャ変更

src/pkg/runtime/alg.cは、Goランタイムにおける型固有の操作（ハッシュ、等価性、コピー、プリント）を集中管理するための新しいファイルです。このファイルには、以下のような関数が定義されています。

void
runtime·memhash(uintptr *h, uintptr s, void *a)
{
    // ... ハッシュ計算ロジック ...
    *h ^= hash; // 結果をポインタ h が指す場所に書き込む
}

void
runtime·memequal(bool *eq, uintptr s, void *a, void *b)
{
    // ... 等価性チェックロジック ...
    *eq = 1; // または 0 をポインタ eq が指す場所に書き込む
}

// ... 他の型に対するハッシュ、等価性、コピー、プリント関数 ...

Alg
runtime·algarray[] =
{
[AMEM]		{ runtime·memhash, runtime·memequal, runtime·memprint, runtime·memcopy },
// ...
};

ここで注目すべきは、runtime·memhashやruntime·memequalといったアルゴリズム関数のシグネチャです。以前はこれらの関数は結果を直接戻り値として返していましたが、このコミットで、結果を格納するためのポインタ（uintptr *hやbool *eq）を引数として受け取るように変更されました。

この変更の理由は、コミットメッセージにもあるように「CコードがGoの戻り値にアクセスする方法がない」という制約に対応するためです。Goコンパイラが生成するGoの関数と、ランタイムのC部分との間で値をやり取りする際、Goの戻り値をC側で直接受け取るのは複雑または不可能でした。ポインタを介して結果を渡すことで、Go関数はCコードがアクセス可能なメモリ領域に結果を書き込み、Cコードはそのポインタを介して結果を読み取ることができるようになります。これにより、GoとCの間の相互運用性が向上し、ランタイムの内部実装がより堅牢になります。

runtime·algarrayは、様々な組み込み型に対するこれらのアルゴリズム関数のポインタをまとめたテーブルです。commonType構造体のalgフィールドがこのテーブル内の適切なエントリを指すことで、ランタイムは実行時に型に応じた正しいアルゴリズム関数を呼び出すことができます。

src/pkg/runtime/hashmap.c の Hmap 構造体とマップ操作関数の変更

src/pkg/runtime/hashmap.cにおけるHmap構造体の変更は、マップのメモリフットプリント削減に大きく貢献しています。

struct Hmap {
	uint32 count;
	uint8 datasize;
	uint8 max_power;
	uint8 indirectval;
	uint8 valoff;
	int32 changes;
	struct hash_subtable *st;
};

以前のHmap構造体には、キーと値のハッシュ関数や等価性関数へのポインタ（data_hash, data_eqなど）、およびキーと値のサイズやオフセットに関する情報（keysize, valsize, datavo, ko0, vo0など）が直接含まれていました。これらの情報は、マップの型（MapType）から導出できるため、各Hmapインスタンスがこれらを重複して保持する必要はありません。

このコミットでは、これらの冗長なフィールドがHmapから削除されました。代わりに、マップ操作を行う関数（例: runtime·makemap_c, runtime·mapaccess, runtime·mapassign）は、MapType *tという引数を新しく受け取るようになりました。このMapType構造体には、マップのキーと値の型情報が含まれており、そこから必要なアルゴリズム関数やサイズ、アラインメント情報を取得できるようになります。

例えば、runtime·makemap_c関数は、マップの作成時にMapTypeからキーと値のアルゴリズムを取得し、それらをHmap構造体ではなく、マップの型情報自体に依存するように変更されました。

Hmap*
runtime·makemap_c(MapType *typ, int64 hint)
{
    // ...
    // 以前はここで h->keyalg = &runtime·algarray[keyalg]; のように設定していた
    // 今は typ->key->alg から直接アルゴリズムにアクセスする
    // ...
}

これにより、各マップインスタンスのメモリ使用量が大幅に削減され、特に多数のマップが使用されるアプリケーションにおいて、メモリ効率が向上します。マップ操作関数がMapTypeを引数として受け取ることで、ランタイムはマップの型に応じた適切なアルゴリズムを動的に選択し、実行できるようになります。

これらの変更は、Goランタイムの内部設計をより洗練させ、パフォーマンスとメモリ効率を向上させるための重要な基盤を構築しています。

関連リンク

• Go言語の公式ドキュメント: https://golang.org/doc/
• Goのランタイムに関する議論（golang-devメーリングリストなど）

参考にした情報源リンク

• Goのソースコード (特にsrc/pkg/runtime/ディレクトリ): https://github.com/golang/go
• Goの型システムに関するブログ記事や解説（一般的なGoの型、インターフェース、リフレクションに関する知識）
• Cgoに関するGoの公式ドキュメント: https://golang.org/cmd/cgo/
• Goのマップの実装に関する技術記事（このコミット以前の古い情報も含む）
• Goのコミット履歴と関連するコードレビュー（CL: Change List）: https://golang.org/cl/5453043 (元のコミットメッセージに記載されているリンク)