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

このコミットは、Goランタイムのハッシュマップルックアップ関数におけるスタックフレームの最適化に関するものです。具体的には、src/pkg/runtime/hashmap_fast.cファイル内のHASH_LOOKUP1およびHASH_LOOKUP2関数が対象となっています。これらの関数は、Goのマップ（ハッシュマップ）の実装において、キーから値を探す際の高速なルックアップ処理を担っています。

コミット

commit a3f842a4c1aea97a79f751887555fd8497d0fed0
Author: Russ Cox <rsc@golang.org>
Date:   Fri Jun 28 13:37:07 2013 -0700

    runtime: shorten hash lookup stack frames
    
    On amd64 the frames are very close to the limit for a
    nosplit (textflag 7) function, in part because the C compiler
    does not make any attempt to reclaim space allocated for
    completely registerized variables. Avoid a few short-lived
    variables to reclaim two words.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/10758043

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

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

元コミット内容

runtime: shorten hash lookup stack frames

On amd64 the frames are very close to the limit for a
nosplit (textflag 7) function, in part because the C compiler
does not make any attempt to reclaim space allocated for
completely registerized variables. Avoid a few short-lived
variables to reclaim two words.

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/10758043

変更の背景

この変更の背景には、Goランタイムの特定の関数、特にハッシュマップのルックアップ関数が、amd64アーキテクチャ上でスタックフレームのサイズ制限に非常に近づいていたという問題があります。

Goのランタイムには、スタックの拡張を必要としない「nosplit」関数という概念があります。これらの関数は、スタックの境界チェックを行わないため、非常に高速に実行できますが、その代わりにスタックフレームのサイズに厳密な制限があります。この制限を超えると、プログラムがクラッシュする可能性があります。

コミットメッセージによると、Cコンパイラ（Goランタイムの一部はCで書かれています）が、完全にレジスタ化された変数（つまり、メモリではなくCPUレジスタに割り当てられた変数）のために確保されたスペースを再利用しようとしないことが、この問題の一因となっていました。これにより、短命な変数がスタック上に不要なスペースを占有し、スタックフレームが肥大化していました。

このコミットの目的は、これらの短命な変数を削減することで、スタックフレームのサイズを縮小し、nosplit関数のスタック制限に抵触するリスクを軽減することでした。具体的には、「2ワード」分のスペースを再利用することを目指しています。これは、パフォーマンスの最適化というよりも、ランタイムの安定性と堅牢性を向上させるための変更と言えます。

前提知識の解説

1. Goランタイム (Go Runtime)

Goランタイムは、Goプログラムの実行を管理する低レベルのシステムです。これには、ガベージコレクション、スケジューラ（ゴルーチンの管理）、メモリ割り当て、システムコールインターフェースなどが含まれます。Goランタイムの一部はGoで書かれていますが、パフォーマンスが重要な部分やOSとの直接的なやり取りが必要な部分はCやアセンブリ言語で書かれています。このコミットで変更されているhashmap_fast.cは、C言語で書かれたランタイムの一部です。

2. スタックフレーム (Stack Frame)

関数が呼び出されるたびに、その関数に必要な情報（ローカル変数、引数、戻りアドレスなど）を格納するために、メモリの「スタック」領域に新しい「スタックフレーム」が作成されます。関数が終了すると、そのスタックフレームは破棄されます。スタックフレームのサイズは、関数が使用するローカル変数の数や型、引数の数などによって決まります。

3. nosplit関数 (textflag 7)

Goランタイムには、スタックの境界チェックを行わない特別な関数があります。これらは「nosplit」関数と呼ばれ、アセンブリコードではTEXTディレクティブにNOSPLITフラグ（またはtextflag 7）を付けて定義されます。通常の関数は、呼び出し時にスタックの残りの容量をチェックし、必要であればスタックを拡張します（スタックの動的拡張）。しかし、nosplit関数はスタックチェックをスキップするため、非常に高速に実行できます。これは、頻繁に呼び出される低レベルのランタイム関数（例えば、スケジューラやガベージコレクタの一部）で特に重要です。

しかし、nosplit関数はスタックチェックを行わないため、スタックオーバーフローのリスクがあります。そのため、これらの関数が使用するスタックフレームのサイズには厳密な上限が設けられています。この上限はアーキテクチャやGoのバージョンによって異なりますが、一般的には非常に小さいです。

4. amd64アーキテクチャ

amd64は、64ビットのx86命令セットアーキテクチャのことで、IntelとAMDのプロセッサで広く使用されています。Goは様々なアーキテクチャをサポートしていますが、amd64は主要なターゲットの一つであり、多くのGoプログラムがこのアーキテクチャ上で実行されます。アーキテクチャによってレジスタの数やスタックの管理方法が異なるため、スタックフレームのサイズ制限もアーキテクチャ固有の考慮事項となります。

5. レジスタ化された変数 (Registerized Variables)

コンパイラは、プログラムの実行速度を向上させるために、頻繁にアクセスされる変数をメモリではなくCPUの高速なレジスタに割り当てることがあります。これを「レジスタ化」と呼びます。レジスタに割り当てられた変数は、メモリから読み書きするよりもはるかに高速にアクセスできます。しかし、Cコンパイラによっては、これらのレジスタ化された変数が使用するスタック上のスペースを、変数が不要になった後も適切に再利用しない場合があります。これが、スタックフレームの肥大化につながることがあります。

6. ハッシュマップ (Hash Map)

ハッシュマップ（Goではmap型）は、キーと値のペアを格納するためのデータ構造です。キーをハッシュ関数に通してハッシュ値を得て、そのハッシュ値に基づいて値を格納する場所を決定します。これにより、キーを使って高速に値を検索（ルックアップ）、挿入、削除することができます。Goのマップは、内部的に複雑なアルゴリズムとデータ構造（バケット、オーバーフローバケットなど）を使用して実装されており、そのパフォーマンスはGoアプリケーション全体の性能に大きく影響します。

技術的詳細

このコミットは、Goランタイムのハッシュマップルックアップ関数であるHASH_LOOKUP1とHASH_LOOKUP2（src/pkg/runtime/hashmap_fast.cに定義）のスタックフレームサイズを削減することを目的としています。

変更前は、これらの関数内で以下の変数が宣言されていました。

• uintptr hash;
• uintptr bucket, oldbucket;
• uintptr i;

これらの変数の中で、hashとoldbucketは、その値が計算された直後に使用され、その後はすぐに不要になる「短命な変数」でした。コミットメッセージによると、Cコンパイラがこれらの変数のために確保したスタック上のスペースを効率的に再利用していなかったため、nosplit関数のスタックフレームサイズが制限に近づいていました。

このコミットの主な変更点は、以下の通りです。

1. hash変数の削除:

   • 変更前は、ハッシュ値を計算するためにhash変数が一時的に使用されていました。
   • 変更後、ハッシュ値の計算結果は直接bucket変数に格納されるようになりました。これにより、hash変数を宣言する必要がなくなり、その分のスタックスペースが節約されます。
   • 具体的には、HASHFUNC(&hash, ...)がHASHFUNC(&bucket, ...)に変更され、ハッシュ値の計算とバケットインデックスの計算がbucket変数一つで行われるようになりました。

2. oldbucket変数の削除:

   • 変更前は、h->oldbucketsが存在する場合に古いバケットのインデックスを計算するためにoldbucket変数が使用されていました。
   • 変更後、oldbucketの計算結果は直接i変数に格納されるようになりました。これにより、oldbucket変数を宣言する必要がなくなり、その分のスタックスペースが節約されます。
   • 具体的には、oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);がi = bucket & (((uintptr)1 << (h->B - 1)) - 1);に変更されています。

3. topハッシュ値の計算位置の変更:

   • 変更前は、topハッシュ値（ハッシュ値の上位8ビット）の計算が、hash変数が計算された後に行われていました。
   • 変更後、topハッシュ値の計算は、bucket変数にハッシュ値が格納された直後に行われるようになりました。これにより、hash変数を介さずに直接bucket変数からtopハッシュ値が抽出されます。

これらの変更により、hashとoldbucketという2つのuintptr型の変数が不要になり、それぞれが1ワード（uintptrはポインタサイズ、amd64では8バイト）を占めるため、合計で2ワード（16バイト）のスタックスペースが節約されます。これは、nosplit関数のスタックフレームサイズ制限が厳しい環境において、非常に重要な最適化となります。

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

src/pkg/runtime/hashmap_fast.cファイル内のHASH_LOOKUP1およびHASH_LOOKUP2関数が変更されています。

--- a/src/pkg/runtime/hashmap_fast.c
+++ b/src/pkg/runtime/hashmap_fast.c
@@ -16,10 +16,8 @@
 void
 HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value)
 {
 -	uintptr hash;
 -	uintptr bucket, oldbucket;
 +	uintptr bucket, i;
  	Bucket *b;
 -	uintptr i;
  	KEYTYPE *k;
  	byte *v;
  	uint8 top;
@@ -80,21 +78,21 @@ HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value)
  		}
  	} else {
  dohash:
 -		hash = h->hash0;
 -		HASHFUNC(&hash, sizeof(KEYTYPE), &key);
 -		bucket = hash & (((uintptr)1 << h->B) - 1);
 +		bucket = h->hash0;
 +		HASHFUNC(&bucket, sizeof(KEYTYPE), &key);
 +		top = bucket >> (sizeof(uintptr)*8 - 8);
 +		if(top == 0)
 +			top = 1;
 +		bucket &= (((uintptr)1 << h->B) - 1);
  		if(h->oldbuckets != nil) {
 -			oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);
 -			b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
 +			i = bucket & (((uintptr)1 << (h->B - 1)) - 1);
 +			b = (Bucket*)(h->oldbuckets + i * h->bucketsize);
  			if(evacuated(b)) {
  				b = (Bucket*)(h->buckets + bucket * h->bucketsize);
  			}
  		} else {
  			b = (Bucket*)(h->buckets + bucket * h->bucketsize);
  		}
 -		top = hash >> (sizeof(uintptr)*8 - 8);
 -		if(top == 0)
 -			top = 1;
  		do {
  			for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {
  				if(b->tophash[i] == top && EQFUNC(key, *k)) {
@@ -114,10 +112,8 @@ dohash:
 void
 HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res)
 {
 -	uintptr hash;
 -	uintptr bucket, oldbucket;
 +	uintptr bucket, i;
  	Bucket *b;
 -	uintptr i;
  	KEYTYPE *k;
  	byte *v;
  	uint8 top;
@@ -184,21 +180,21 @@ HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res)
  		}
  	} else {
  dohash:
 -		hash = h->hash0;
 -		HASHFUNC(&hash, sizeof(KEYTYPE), &key);
 -		bucket = hash & (((uintptr)1 << h->B) - 1);
 +		bucket = h->hash0;
 +		HASHFUNC(&bucket, sizeof(KEYTYPE), &key);
 +		top = bucket >> (sizeof(uintptr)*8 - 8);
 +		if(top == 0)
 +			top = 1;
 +		bucket &= (((uintptr)1 << h->B) - 1);
  		if(h->oldbuckets != nil) {
 -			oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);
 -			b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
 +			i = bucket & (((uintptr)1 << (h->B - 1)) - 1);
 +			b = (Bucket*)(h->oldbuckets + i * h->bucketsize);
  			if(evacuated(b)) {
  				b = (Bucket*)(h->buckets + bucket * h->bucketsize);
  			}
  		} else {
  			b = (Bucket*)(h->buckets + bucket * h->bucketsize);
  		}
 -		top = hash >> (sizeof(uintptr)*8 - 8);
 -		if(top == 0)
 -			top = 1;
  		do {
  			for(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {
  				if(b->tophash[i] == top && EQFUNC(key, *k)) {

コアとなるコードの解説

上記の差分は、HASH_LOOKUP1とHASH_LOOKUP2という2つの関数における変更を示しています。これらの関数は、Goのマップのキー検索ロジックの核心部分です。

1. 変数宣言の変更:

   • - uintptr hash; と - uintptr oldbucket; が削除され、代わりに + uintptr i; が追加されています。
   • 元々iは別の行で宣言されていましたが、bucketとまとめて宣言されるようになりました。
   • これにより、hashとoldbucketという2つのuintptr型変数がスタックから削除され、スタックフレームのサイズが削減されます。

2. ハッシュ値計算の最適化:

   • 変更前:

     hash = h->hash0;
     HASHFUNC(&hash, sizeof(KEYTYPE), &key);
     bucket = hash & (((uintptr)1 << h->B) - 1);
     // ...
     top = hash >> (sizeof(uintptr)*8 - 8);
     if(top == 0)
         top = 1;
     

     ここでは、まずhash変数に初期ハッシュ値を設定し、HASHFUNCでキーのハッシュ値を計算し、その結果をhashに格納しています。その後、hashからbucketとtopを計算しています。
   • 変更後:

     bucket = h->hash0;
     HASHFUNC(&bucket, sizeof(KEYTYPE), &key);
     top = bucket >> (sizeof(uintptr)*8 - 8);
     if(top == 0)
         top = 1;
     bucket &= (((uintptr)1 << h->B) - 1);
     

     変更後では、hash変数を介さずに、直接bucket変数に初期ハッシュ値を設定し、HASHFUNCでキーのハッシュ値を計算しています。そして、そのbucket変数から直接topハッシュ値を抽出し、最後にbucket変数自体をバケットインデックスに変換しています。これにより、hash変数が不要になり、コードの行数もわずかに削減されています。

3. oldbucketの計算と利用の統合:

   • 変更前:

     oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);
     b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
     

     oldbucketという一時変数を使って計算していました。
   • 変更後:

     i = bucket & (((uintptr)1 << (h->B - 1)) - 1);
     b = (Bucket*)(h->oldbuckets + i * h->bucketsize);
     

     oldbucket変数を削除し、その計算結果を既存のi変数に直接格納して利用しています。これにより、oldbucket変数が不要になり、スタックスペースが節約されます。

これらの変更は、Goランタイムの非常に低レベルな部分で行われており、スタックフレームのサイズを最小限に抑えるためのマイクロ最適化です。これは、Goのパフォーマンスと安定性を維持するために、ランタイム開発者がどれほど細部にまで注意を払っているかを示す良い例です。

関連リンク

• Goのマップの内部実装に関する詳細なブログ記事 (Go 1.0のマップ実装についてですが、基本的な概念は共通しています):
  • Go maps in action - The Go Programming Language
• Goのスタック管理に関する議論やドキュメント:
  • Go runtime: stack management - The Go Programming Language (Go 1.2のリリースノートですが、スタック管理の変更について触れられています)
  • Go runtime: stack growth - The Go Programming Language

参考にした情報源リンク

• GitHubのコミットページ: https://github.com/golang/go/commit/a3f842a4c1aea97a79f751887555fd8497d0fed0
• Goのコードレビューシステム (Gerrit) の変更リスト: https://golang.org/cl/10758043
• Goのドキュメントとブログ (Goのスタック管理やマップの実装に関する一般的な情報源として)
• C言語のコンパイラ最適化に関する一般的な知識 (レジスタ割り当て、スタックフレームなど)
• amd64アーキテクチャに関する一般的な知識 (レジスタ、メモリモデルなど)
• uintptr型に関するGoのドキュメント (ポインタサイズ整数型)I have generated the explanation. I will now output it to standard output.