Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goランタイムのハッシュマップ（map型）の実装に関連する2つのファイルを変更しています。

  • src/pkg/runtime/hashmap.c: Goのハッシュマップの主要なロジックがC言語で実装されているファイルです。マップの作成、要素の挿入、検索、削除、そしてリサイズ（成長）といった基本的な操作が含まれます。
  • src/pkg/runtime/hashmap_fast.c: 特定のキー型（例えば、整数型）に対して最適化されたハッシュマップの操作が実装されているファイルです。パフォーマンスが重要な場面で利用されます。

これらのファイルは、Goプログラムの実行時にマップがどのように動作するかを定義する、Goランタイムの根幹をなす部分です。

コミット

runtime: don't store evacuate bit as low bit of hashtable overflow pointer.

Hash tables currently store an evacuated bit in the low bit
of the overflow pointer. That's probably not sustainable in the
long term as GC wants correctly typed & aligned pointers. It is
also a pain to move any of this code to Go in the current state.

This change moves the evacuated bit into the tophash entries.

Performance change is negligable.

R=golang-dev, bradfitz
CC=golang-dev
https://golang.org/cl/14412043

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

https://github.com/golang/go/commit/9aae6c1a8b61af33f766e9a735c04b6afa255160

元コミット内容

runtime: don't store evacuate bit as low bit of hashtable overflow pointer.

Hash tables currently store an evacuated bit in the low bit
of the overflow pointer. That's probably not sustainable in the
long term as GC wants correctly typed & aligned pointers. It is
also a pain to move any of this code to Go in the current state.

This change moves the evacuated bit into the tophash entries.

Performance change is negligable.

R=golang-dev, bradfitz
CC=golang-dev
https://golang.org/cl/14412043

変更の背景

このコミットの主な背景は、Goのハッシュテーブル（map）の実装における「evacuated bit」の格納方法が、将来的なガベージコレクション（GC）の要件や、ランタイムコードをCからGoへ移行する際の障壁となっていた点にあります。

Goのハッシュテーブルは、要素数が一定の閾値を超えると、より大きな新しいハッシュテーブルにリサイズ（成長）します。このリサイズ処理は段階的に行われ、古いテーブルのバケットから新しいテーブルのバケットへ要素が移動（evacuate）されます。この際、どのバケットが既にevacuateされたかを追跡するために「evacuated bit」が使用されていました。

以前の実装では、この「evacuated bit」がハッシュテーブルのバケット構造体内のoverflowポインタの最下位ビットに格納されていました。ポインタの最下位ビットは通常、アライメントのために0であることが多いため、そこにフラグを格納することは一般的な最適化手法です。しかし、この方法は以下の問題を引き起こしていました。

  1. GCのポインタ型・アライメント要件との衝突: Goのガベージコレクタは、メモリ上のオブジェクトを正確に識別し、ポインタを追跡する必要があります。ポインタの最下位ビットにメタデータが格納されていると、GCがポインタを「正しい型」として認識し、適切にアライメントされたアドレスとして扱う上で複雑さが増します。これはGCの正確性や効率性に影響を与える可能性がありました。GCはポインタが指す先を正確に知る必要があり、ビットが操作されていると、それが純粋なポインタ値ではないと判断されるリスクがありました。
  2. Goコードへの移行の困難さ: Goランタイムの多くの部分はC言語で書かれていますが、将来的にはGo言語自身で書かれることが目指されています。C言語ではポインタのビット操作が比較的容易ですが、Go言語ではポインタの型安全性が厳しく、このような低レベルなビット操作は推奨されませんし、実装も困難になります。overflowポインタの最下位ビットにフラグを格納する現在の設計は、このGo言語への移行を妨げる要因となっていました。

これらの問題を解決し、よりクリーンで将来性のある実装にするために、evacuated bitをoverflowポインタからtophashエントリに移動するという変更が提案されました。これにより、ポインタは純粋なポインタ値として扱われるようになり、GCの負担が軽減され、将来的なGo言語へのコード移行も容易になります。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムとハッシュテーブルに関する知識が必要です。

1. Goのハッシュテーブル（map型）の内部構造

Goのmapは、内部的にはハッシュテーブルとして実装されています。その主要な構成要素は以下の通りです。

  • Hmap構造体: マップ全体のメタデータ（要素数、バケットの数、ハッシュシードなど）を保持する構造体です。
  • Bucket構造体: ハッシュテーブルの基本的な格納単位です。各バケットは固定数のキーと値を保持できます（Go 1.18時点では8組）。
    • tophash配列: uint8型の配列で、各エントリのハッシュ値の上位8ビットを格納します。これにより、キーの比較を行う前に、ハッシュ値の上位ビットだけで高速に候補を絞り込むことができます。
    • data配列: キーと値のペアが格納される領域です。
    • overflowポインタ: バケットが満杯になった場合に、追加のキーと値を格納するための「オーバーフローバケット」を指すポインタです。これにより、ハッシュ衝突が発生しても効率的に要素を格納できます。
  • リサイズ（成長）: マップに要素が追加され、その数が一定の閾値を超えると、ハッシュテーブルはより大きなサイズに「成長」します。このプロセスは、新しいバケット配列を割り当て、古いバケットから新しいバケットへ要素を徐々に移動させることで行われます。

2. Goのガベージコレクション（GC）

Goは自動メモリ管理（ガベージコレクション）を採用しています。GCの主な役割は、プログラムがもはや参照しないメモリ領域を自動的に解放し、再利用可能にすることです。

  • ポインタの追跡: GCは、メモリ上のどの領域がポインタであり、どのオブジェクトを指しているかを正確に知る必要があります。これにより、到達可能なオブジェクトをマークし、到達不可能なオブジェクトを解放できます。
  • ポインタの型とアライメント: GCは、ポインタが指すメモリ領域の型情報（例えば、それが構造体なのか、配列なのか）や、メモリ上でのアライメント（特定のバイト境界に配置されているか）を考慮します。ポインタの最下位ビットにフラグが埋め込まれていると、GCがポインタを純粋なアドレスとして認識する上で問題が生じる可能性がありました。これは、GCがポインタをデリファレンスする際に、そのビットが邪魔になるためです。

3. ハッシュテーブルのリサイズと「Evacuation」

Goのmapのリサイズは、一括で行われるのではなく、段階的に行われます。

  • oldbuckets: リサイズが開始されると、新しいバケット配列が割り当てられ、古いバケット配列はoldbucketsとして保持されます。
  • Evacuation（要素の移動）: マップへの書き込み操作（挿入、削除）が行われるたびに、oldbucketsから少数のバケットが選択され、その中の要素が新しいバケット配列に移動されます。このプロセスが「evacuation」です。
  • evacuated bit: 各バケットがevacuateされたかどうかを示すフラグです。以前はoverflowポインタの最下位ビットに格納されていました。このビットがセットされている場合、そのバケットは既に新しいテーブルに移動済みであることを意味します。

4. tophashエントリの役割

tophashは、バケット内の各エントリ（キーと値のペア）に対応するuint8値の配列です。これは、キーの完全な比較を行う前に、ハッシュ値の上位8ビットを比較することで、目的のキーがそのバケット内に存在するかどうかを高速に判断するために使用されます。

  • tophash[i]が0の場合、そのエントリは空であることを示します。
  • このコミット以前は、tophashは純粋にハッシュ値の上位ビットを格納していましたが、この変更により、特殊な状態（evacuatedなど）を示すための予約値が導入されます。

技術的詳細

このコミットの技術的な核心は、ハッシュテーブルのバケットが「evacuated」（新しいテーブルに移動済み）であるという状態を示すビットの格納場所を変更した点にあります。

旧来の実装の問題点

以前は、Bucket構造体のoverflowポインタの最下位ビット（LSB: Least Significant Bit）をevacuatedフラグとして使用していました。

// Low-order bit of overflow field is used to mark a bucket as already evacuated
// without destroying the overflow pointer.
// Only buckets in oldbuckets will be marked as evacuated.
// Evacuated bit will be set identically on the base bucket and any overflow buckets.
#define evacuated(b) (((uintptr)(b)->overflow & 1) != 0)
#define overflowptr(b) ((Bucket*)((uintptr)(b)->overflow & ~(uintptr)1))
  • evacuated(b)マクロは、overflowポインタをuintptrにキャストし、その最下位ビットが1であるかどうかをチェックしていました。
  • overflowptr(b)マクロは、overflowポインタの最下位ビットを0にクリアしてからBucket*にキャストし直すことで、実際のポインタ値を取得していました。

この方法は、ポインタが通常アライメントされているため最下位ビットが0であるという事実を利用した省スペースなテクニックです。しかし、前述の通り、GCがポインタを正確に追跡する上で複雑さを増し、Go言語へのコード移行を困難にしていました。GCはポインタが指すメモリ領域の型とアライメントを厳密に管理するため、ポインタ値がビット操作によって変更されていると、GCが誤った判断を下すリスクがありました。

新しい実装の概要

このコミットでは、evacuated bitをoverflowポインタから、各エントリのハッシュ値の上位8ビットを格納するtophash配列に移動させました。

具体的には、tophashエントリに以下の特殊な予約値が導入されました。

enum
{
	Empty = 0,		// cell is empty
	EvacuatedEmpty = 1,	// cell is empty, bucket is evacuated.
	EvacuatedX = 2,		// key/value is valid. Entry has been evacuated to first half of larger table.
	EvacuatedY = 3,		// same as above, but evacuated to second half of larger table.
	MinTopHash = 4, 	// minimum tophash for a normal filled cell.
};
  • Empty = 0: 以前から使用されていた、セルが空であることを示す値です。
  • EvacuatedEmpty = 1: セルは空だが、バケット全体がevacuateされたことを示します。
  • EvacuatedX = 2: キー/値が有効で、新しいテーブルの「前半」にevacuateされたことを示します。
  • EvacuatedY = 3: キー/値が有効で、新しいテーブルの「後半」にevacuateされたことを示します。
  • MinTopHash = 4: 実際のハッシュ値の上位8ビットが格納される場合の最小値です。これにより、0から3までの特殊な値と、実際のハッシュ値が衝突しないように区別されます。

新しいevacuated判定マクロは以下のようになります。

#define evacuated(b) ((b)->tophash[0] > Empty && (b)->tophash[0] < MinTopHash)

これは、バケットの最初のtophashエントリ（b->tophash[0]）がEmptyより大きく、かつMinTopHashより小さい場合に、そのバケットがevacuatedされたと判断します。これは、EvacuatedEmpty、EvacuatedX、EvacuatedYのいずれかの値が設定されていることを意味します。

変更による影響

  • ポインタのクリーン化: overflowポインタは純粋なポインタ値として扱われるようになり、GCがポインタを追跡する際の複雑さが解消されます。
  • Go言語への移行の容易化: 低レベルなポインタビット操作が不要になるため、将来的にハッシュマップのコードをGo言語で書き直す際の障壁が低減されます。
  • パフォーマンスへの影響は無視できるレベル: コミットメッセージにある通り、この変更によるパフォーマンスへの影響はごくわずかです。tophashのチェックは既にハッシュテーブルの操作の一部として行われており、追加のオーバーヘッドはほとんどありません。

この変更は、Goランタイムの内部実装の健全性を高め、将来的な進化のための基盤を強化するものです。

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

このコミットにおける主要なコード変更は、以下のファイルとセクションに集中しています。

  1. src/pkg/runtime/hashmap.c

    • struct Bucketのコメント変更: tophashフィールドのコメントが更新され、特殊なマークが格納される可能性が明記されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -76,7 +76,7 @@ struct Bucket
 {
 	// Note: the format of the Bucket is encoded in ../../cmd/gc/reflect.c and
 	// ../reflect/type.go. Don't change this structure without also changing that code!
-	uint8  tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (0 = empty)
+	uint8  tophash[BUCKETSIZE]; // top 8 bits of hash of each entry (or special mark below)
 	Bucket *overflow;           // overflow bucket, if any
 	byte   data[1];             // BUCKETSIZE keys followed by BUCKETSIZE values
 };
    • evacuatedマクロとoverflowptrマクロの削除、および新しいenumの定義: overflowポインタのビット操作によるevacuated判定が削除され、新しいtophashの状態を示すenumが導入されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -84,12 +84,19 @@ struct Bucket
 // code a bit more complicated than alternating key/value/key/value/... but it allows
 // us to eliminate padding which would be needed for, e.g., map[int64]int8.
 
-// Low-order bit of overflow field is used to mark a bucket as already evacuated
-// without destroying the overflow pointer.
-// Only buckets in oldbuckets will be marked as evacuated.
-// Evacuated bit will be set identically on the base bucket and any overflow buckets.
-#define evacuated(b) (((uintptr)(b)->overflow & 1) != 0)
-#define overflowptr(b) ((Bucket*)((uintptr)(b)->overflow & ~(uintptr)1))
+// tophash values. We reserve a few possibilities for special marks.
+// Each bucket (including its overflow buckets, if any) will have either all or none of its
+// entries in the Evacuated* states (except during the evacuate() method, which only happens
+// during map writes and thus no one else can observe the map during that time).
+enum
+{
+	Empty = 0,		// cell is empty
+	EvacuatedEmpty = 1,	// cell is empty, bucket is evacuated.
+	EvacuatedX = 2,		// key/value is valid. Entry has been evacuated to first half of larger table.
+	EvacuatedY = 3,		// same as above, but evacuated to second half of larger table.
+	MinTopHash = 4, 	// minimum tophash for a normal filled cell.
+};
+#define evacuated(b) ((b)->tophash[0] > Empty && (b)->tophash[0] < MinTopHash)
 
 struct Hmap
 {
    • check関数内のtophashの利用とevacuated判定の変更: マップの整合性チェックを行うcheck関数内で、tophashの値に基づいて空セルやevacuatedセルを判定するロジックが変更されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -143,16 +150,12 @@ check(MapType *t, Hmap *h)\
 
 	// check buckets
 	for(bucket = 0; bucket < (uintptr)1 << h->B; bucket++) {
-		if(h->oldbuckets != nil) {
-			oldbucket = bucket & (((uintptr)1 << (h->B - 1)) - 1);
-			b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);
-			if(!evacuated(b))
-				continue; // b is still uninitialized
-		}
 		for(b = (Bucket*)(h->buckets + bucket * h->bucketsize); b != nil; b = b->overflow) {
 			for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {
-				if(b->tophash[i] == 0)
+				if(b->tophash[i] == Empty)
 					continue;
+				if(b->tophash[i] > Empty && b->tophash[i] < MinTopHash)
+					runtime·throw("evacuated cell in buckets");
 				cnt++;
 				t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k));
 				if(!eq)
@@ -160,8 +163,8 @@ check(MapType *t, Hmap *h)\
 				hash = h->hash0;\
 				t->key->alg->hash(&hash, t->key->size, IK(h, k));\
 				top = hash >> (8*sizeof(uintptr) - 8);\
-				if(top == 0)\
-					top = 1;\
+				if(top < MinTopHash)\
+					top += MinTopHash;\
 				if(top != b->tophash[i])
 					runtime·throw("bad hash");
 			}
@@ -172,14 +175,12 @@ check(MapType *t, Hmap *h)\
 	if(h->oldbuckets != nil) {
 		for(oldbucket = 0; oldbucket < (uintptr)1 << (h->B - 1); oldbucket++) {
 			b = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\
-			if(evacuated(b))
-				continue;
-			if(oldbucket < h->nevacuate)
-				runtime·throw("bucket became unevacuated");
-			for(; b != nil; b = overflowptr(b)) {
+			for(; b != nil; b = b->overflow) {
 				for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETsize; i++, k += h->keysize, v += h->valuesize) {
-					if(b->tophash[i] == 0)
+					if(b->tophash[i] < MinTopHash)
 						continue;
+					if(oldbucket < h->nevacuate)
+						runtime·throw("unevacuated entry in an evacuated bucket");
 					cnt++;
 					t->key->alg->equal(&eq, t->key->size, IK(h, k), IK(h, k));
 					if(!eq)
@@ -187,8 +188,8 @@ check(MapType *t, Hmap *h)\
 					hash = h->hash0;\
 					t->key->alg->hash(&hash, t->key->size, IK(h, k));\
 					top = hash >> (8*sizeof(uintptr) - 8);\
-					if(top == 0)\
-						top = 1;\
+					if(top < MinTopHash)\
+						top += MinTopHash;\
 					if(top != b->tophash[i])
 						runtime·throw("bad hash (old)");
 				}
    • evacuate関数内のtophashの更新ロジック: 要素を新しいバケットに移動する際に、古いバケットのtophashエントリをEvacuatedXまたはEvacuatedYに設定するようになりました。また、overflowポインタのビット操作によるevacuatedマークの削除と、GCを助けるためのoverflowポインタのnil化、データクリアが追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -273,13 +274,12 @@ hash_init(MapType *t, Hmap *h, uint32 hint)\
 }\
  \
 // Moves entries in oldbuckets[i] to buckets[i] and buckets[i+2^k].\
-// We leave the original bucket intact, except for the evacuated marks, so that\
-// iterators can still iterate through the old buckets.\
+// We leave the original bucket intact, except for marking the topbits\
+// entries as evacuated, so that iterators can still iterate through the old buckets.\
 static void\
 evacuate(MapType *t, Hmap *h, uintptr oldbucket)\
 {\
 	Bucket *b;\
-	Bucket *nextb;\
 	Bucket *x, *y;\
 	Bucket *newx, *newy;\
 	uintptr xi, yi;\
@@ -306,11 +306,15 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\
 	\tyk = y->data;\
 	\txv = xk + h->keysize * BUCKETSIZE;\
 	\tyv = yk + h->keysize * BUCKETSIZE;\
-\t\tdo {\
+\t\tfor(; b != nil; b = b->overflow) {\
 \t\t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\
 \t\t\t\ttop = b->tophash[i];\
-\t\t\t\tif(top == 0)\
+\t\t\t\tif(top == Empty) {\
+\t\t\t\t\tb->tophash[i] = EvacuatedEmpty;\
 \t\t\t\t\tcontinue;\
+\t\t\t\t}\
+\t\t\t\tif(top < MinTopHash)\
+\t\t\t\t\truntime·throw("bad state");\
  \
 \t\t\t\t// Compute hash to make our evacuation decision (whether we need\
 \t\t\t\t// to send this key/value to bucket x or bucket y).\
@@ -335,12 +339,13 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\
 \t\t\t\t\t\telse\
 \t\t\t\t\t\t\thash &= ~newbit;\
 \t\t\t\t\t\ttop = hash >> (8*sizeof(uintptr)-8);\
-\t\t\t\t\t\tif(top == 0)\
-\t\t\t\t\t\t\ttop = 1;\
+\t\t\t\t\t\tif(top < MinTopHash)\
+\t\t\t\t\t\t\ttop += MinTopHash;\
 \t\t\t\t\t}\
 \t\t\t\t}\
  \
 \t\t\t\tif((hash & newbit) == 0) {\
+\t\t\t\t\tb->tophash[i] = EvacuatedX;\
 \t\t\t\t\tif(xi == BUCKETSIZE) {\
 \t\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\
 \t\t\t\t\t\tnewx = runtime·cnew(t->bucket);\
@@ -365,6 +370,7 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\
 \t\t\t\t\txk += h->keysize;\
 \t\t\t\t\txv += h->valuesize;\
 \t\t\t\t} else {\
+\t\t\t\t\tb->tophash[i] = EvacuatedY;\
 \t\t\t\t\tif(yi == BUCKETSIZE) {\
 \t\t\t\t\t\tif(checkgc) mstats.next_gc = mstats.heap_alloc;\
 \t\t\t\t\t\tnewy = runtime·cnew(t->bucket);\
@@ -390,26 +396,21 @@ evacuate(MapType *t, Hmap *h, uintptr oldbucket)\
 \t\t\t\t\tyv += h->valuesize;\
 \t\t\t\t}\
 \t\t\t}\
+\t\t}\
  \
-\t\t\t// mark as evacuated so we don\'t do it again.\
-\t\t\t// this also tells any iterators that this data isn\'t golden anymore.\
-\t\t\tnextb = b->overflow;\
-\t\t\tb->overflow = (Bucket*)((uintptr)nextb + 1);\
-\
-\t\t\tb = nextb;\
-\t\t} while(b != nil);\
-\
-\t\t// Unlink the overflow buckets to help GC.\
-\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\
-\t\tif((h->flags & OldIterator) == 0)\
-\t\t\tb->overflow = (Bucket*)1;\
+\t\t// Unlink the overflow buckets & clear key/value to help GC.\
+\t\tif((h->flags & OldIterator) == 0) {\
+\t\t\tb = (Bucket*)(h->oldbuckets + oldbucket * h->bucketsize);\
+\t\t\tb->overflow = nil;\
+\t\t\truntime·memclr(b->data, h->bucketsize - offsetof(Bucket, data[0]));\
+\t\t}\
 	}\
  \
-\t// advance evacuation mark\
+\t// Advance evacuation mark\
 \tif(oldbucket == h->nevacuate) {\
 \t\th->nevacuate = oldbucket + 1;\
 \t\tif(oldbucket + 1 == newbit) // newbit == # of oldbuckets\
-\t\t\t// free main bucket array\
+\t\t\t// Growing is all done. Free old main bucket array.\
 \t\t\th->oldbuckets = nil;\
 \t}\
 \tif(docheck)\
    • hash_lookup, hash_insert, hash_remove関数内のtophashの調整: ハッシュ値の上位8ビットがMinTopHashより小さい場合にMinTopHashを加算して、特殊なtophash値と衝突しないようにするロジックが追加されました。 
      --- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -495,8 +495,8 @@ hash_lookup(MapType *t, Hmap *h, byte **keyp)\
 	\tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\
 \t}\
 \ttop = hash >> (sizeof(uintptr)*8 - 8);\
-\tif(top == 0)\
-\t\ttop = 1;\
+\tif(top < MinTopHash)\
+\t\ttop += MinTopHash;\
 \tdo {\
 \t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\
 \t\t\tif(b->tophash[i] == top) {\
@@ -608,15 +608,15 @@ hash_insert(MapType *t, Hmap *h, void *key, void *value)\
 \t\tgrow_work(t, h, bucket);\
 \tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\
 \ttop = hash >> (sizeof(uintptr)*8 - 8);\
-\tif(top == 0)\
-\t\ttop = 1;\
+\tif(top < MinTopHash)\
+\t\ttop += MinTopHash;\
 \tinserti = nil;\
 \tinsertk = nil;\
 \tinsertv = nil;\
 \twhile(true) {\
 \t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\
 \t\t\tif(b->tophash[i] != top) {\
-\t\t\t\tif(b->tophash[i] == 0 && inserti == nil) {\
+\t\t\t\tif(b->tophash[i] == Empty && inserti == nil) {\
 \t\t\t\t\tinserti = &b->tophash[i];\
 \t\t\t\t\tinsertk = k;\
 \t\t\t\t\tinsertv = v;\
@@ -697,8 +697,8 @@ hash_remove(MapType *t, Hmap *h, void *key)\
 \t\tgrow_work(t, h, bucket);\
 \tb = (Bucket*)(h->buckets + bucket * h->bucketsize);\
 \ttop = hash >> (sizeof(uintptr)*8 - 8);\
-\tif(top == 0)\
-\t\ttop = 1;\
+\tif(top < MinTopHash)\
+\t\ttop += MinTopHash;\
 \tdo {\
 \t\tfor(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\
 \t\t\tif(b->tophash[i] != top)\
@@ -718,7 +718,7 @@ hash_remove(MapType *t, Hmap *h, void *key)\
 \t\t\t\tt->elem->alg->copy(t->elem->size, v, nil);\
 \t\t\t}\
  \
-\t\t\tb->tophash[i] = 0;\
+\t\t\tb->tophash[i] = Empty;\
 \t\t\th->count--;\
 \t\t\t\
  \
@@ -857,11 +857,12 @@ next:\
 \tk = b->data + h->keysize * i;\
 \tv = b->data + h->keysize * BUCKETSIZE + h->valuesize * i;\
 \tfor(; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {\
-\t\tif(b->tophash[i] != 0) {\
+\t\tif(b->tophash[i] != Empty && b->tophash[i] != EvacuatedEmpty) {\
 \t\t\tif(check_bucket >= 0) {\
 \t\t\t\t// Special case: iterator was started during a grow and the\
 \t\t\t\t// grow is not done yet. We're working on a bucket whose\
-\t\t\t\t// oldbucket has not been evacuated yet. So we're iterating\
+\t\t\t\t// oldbucket has not been evacuated yet. Or at least, it wasn't\
+\t\t\t\t// evacuated when we started the bucket. So we're iterating\
 \t\t\t\t// through the oldbucket, skipping any keys that will go\
 \t\t\t\t// to the other new bucket (each oldbucket expands to two\
 \t\t\t\t// buckets during a grow).\
@@ -879,12 +880,15 @@ next:\
 \t\t\t\t\t// repeatable and randomish choice of which direction\
 \t\t\t\t\t// to send NaNs during evacuation. We'll use the low\
 \t\t\t\t\t// bit of tophash to decide which way NaNs go.\
+\t\t\t\t\t// NOTE: this case is why we need two evacuate tophash\
+\t\t\t\t\t// values, evacuatedX and evacuatedY, that differ in\
+\t\t\t\t\t// their low bit.\
 \t\t\t\t\tif(check_bucket >> (it->B - 1) != (b->tophash[i] & 1)) {\
 \t\t\t\t\t\tcontinue;\
 \t\t\t\t\t}\
 \t\t\t\t}\
 \t\t\t}\
-\t\t\tif(!evacuated(b)) {\
+\t\t\tif(b->tophash[i] != EvacuatedX && b->tophash[i] != EvacuatedY) {\
 \t\t\t\t// this is the golden data, we can return it.\
 \t\t\t\tit->key = IK(h, k);\
 \t\t\t\tit->value = IV(h, v);\
@@ -920,7 +924,7 @@ next:\
 \t\t\treturn;\
 \t\t}\
 \t}\
-\tb = overflowptr(b);\
+\tb = b->overflow;\
 \ti = 0;\
 \tgoto next;\
 }\

  2. src/pkg/runtime/hashmap_fast.c

    • HASH_LOOKUP1およびHASH_LOOKUP2マクロ内のtophashの利用: tophashがEmptyであるかどうかのチェックが追加されました。 
      --- a/src/pkg/runtime/hashmap_fast.c
+++ b/src/pkg/runtime/hashmap_fast.c
@@ -40,7 +40,7 @@ HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value)\
 	\tb = (Bucket*)h->buckets;\
 	\tif(FASTKEY(key)) {\
 	\t\tfor(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {\
-\t\t\t\tif(b->tophash[i] == 0)\
+\t\t\t\tif(b->tophash[i] == Empty)\
 \t\t\t\t\tcontinue;\
 \t\t\t\tif(QUICK_NE(key, *k))\
 \t\t\t\t\tcontinue;\
@@ -53,7 +53,7 @@ HASH_LOOKUP1(MapType *t, Hmap *h, KEYTYPE key, byte *value)\
 	\t} else {\
 	\t\tkeymaybe = -1;\
 	\t\tfor(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {\
-\t\t\t\tif(b->tophash[i] == 0)\
+\t\t\t\tif(b->tophash[i] == Empty)\
 \t\t\t\t\tcontinue;\
 \t\t\t\tif(QUICK_NE(key, *k))\
 \t\t\t\t\tcontinue;\
@@ -88,8 +88,8 @@ dohash:\
 \t\tbucket = h->hash0;\
 \t\tHASHFUNC(&bucket, sizeof(KEYTYPE), &key);\
 \t\ttop = bucket >> (sizeof(uintptr)*8 - 8);\
-\t\tif(top == 0)\
-\t\t\ttop = 1;\
+\t\tif(top < MinTopHash)\
+\t\t\ttop += MinTopHash;\
 \t\tbucket &= (((uintptr)1 << h->B) - 1);\
 \t\tif(h->oldbuckets != nil) {\
 \t\t\ti = bucket & (((uintptr)1 << (h->B - 1)) - 1);\
@@ -154,7 +154,7 @@ HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res)\
 	\tb = (Bucket*)h->buckets;\
 	\tif(FASTKEY(key)) {\
 	\t\tfor(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {\
-\t\t\t\tif(b->tophash[i] == 0)\
+\t\t\t\tif(b->tophash[i] == Empty)\
 \t\t\t\t\tcontinue;\
 \t\t\t\tif(QUICK_NE(key, *k))\
 \t\t\t\t\tcontinue;\
@@ -169,7 +169,7 @@ HASH_LOOKUP2(MapType *t, Hmap *h, KEYTYPE key, byte *value, bool res)\
 	\t} else {\
 	\t\tkeymaybe = -1;\
 	\t\tfor(i = 0, k = (KEYTYPE*)b->data, v = (byte*)(k + BUCKETSIZE); i < BUCKETSIZE; i++, k++, v += h->valuesize) {\
-\t\t\t\tif(b->tophash[i] == 0)\
+\t\t\t\tif(b->tophash[i] == Empty)\
 \t\t\t\t\tcontinue;\
 \t\t\t\tif(QUICK_NE(key, *k))\
 \t\t\t\t\tcontinue;\
@@ -208,8 +208,8 @@ dohash:\
 \t\tbucket = h->hash0;\
 \t\tHASHFUNC(&bucket, sizeof(KEYTYPE), &key);\
 \t\ttop = bucket >> (sizeof(uintptr)*8 - 8);\
-\t\tif(top == 0)\
-\t\t\ttop = 1;\
+\t\tif(top < MinTopHash)\
+\t\t\ttop += MinTopHash;\
 \t\tbucket &= (((uintptr)1 << h->B) - 1);\
 \t\tif(h->oldbuckets != nil) {\
 \t\t\ti = bucket & (((uintptr)1 << (h->B - 1)) - 1);\

コアとなるコードの解説

このコミットの核となる変更は、evacuated状態の管理方法をoverflowポインタのビット操作からtophashエントリの値に変更したことです。

  1. evacuatedマクロの変更:

    • 旧: ((uintptr)(b)->overflow & 1) != 0
    • 新: ((b)->tophash[0] > Empty && (b)->tophash[0] < MinTopHash) この変更により、overflowポインタは純粋なポインタとして扱われるようになり、GCがポインタを追跡する際の複雑さが解消されました。evacuatedの判定は、バケットの最初のtophashエントリがEmpty (0) より大きく、かつMinTopHash (4) より小さい値（つまり、EvacuatedEmpty、EvacuatedX、EvacuatedYのいずれか）であるかどうかで判断されるようになりました。

  2. enumによるtophash特殊値の導入: Empty (0) に加えて、EvacuatedEmpty (1)、EvacuatedX (2)、EvacuatedY (3) といった新しいtophash値が導入されました。これらは、バケット内のセルがevacuateされた状態を示すために使用されます。

    • EvacuatedEmpty: セル自体は空だが、そのバケットがevacuate済みであることを示します。
    • EvacuatedX / EvacuatedY: セルに有効なキー/値ペアが含まれており、それが新しいテーブルのどちらの半分にevacuateされたかを示します。これは、リサイズ中に古いバケットをイテレートする際に、要素が既に新しいテーブルのどこかに移動したことを示すために重要です。
    • MinTopHash (4): 実際のハッシュ値の上位8ビットが格納される場合の最小値として定義されました。これにより、0から3までの特殊な値と、実際のハッシュ値が衝突しないように区別されます。

  3. evacuate関数内のtophash更新: evacuate関数は、古いバケットから新しいバケットへ要素を移動する際に呼び出されます。この関数内で、移動された要素に対応する古いバケットのtophashエントリが、EvacuatedXまたはEvacuatedYに設定されるようになりました。これにより、古いバケットをイテレートする際に、どの要素が既に移動済みであるかをtophashの値から直接判断できるようになります。 また、overflowポインタのビット操作によるevacuatedマークの削除（b->overflow = (Bucket*)((uintptr)nextb + 1);のような行が削除された）と、GCを助けるためにoverflowポインタをnilにし、バケットのデータ領域をクリアする処理が追加されました。これは、古いバケットがGCによって解放される際に、不要な参照が残らないようにするためです。

  4. ハッシュ値の調整 (top = 0からtop = 1への変更、そしてtop < MinTopHashの場合の調整): 以前は、ハッシュ値の上位8ビットが0になる場合、それを1に調整していました。これは、tophashが0を「空」として予約していたためです。 このコミットでは、MinTopHashが導入されたため、ハッシュ値の上位8ビットがMinTopHash (4) より小さい場合（つまり、0, 1, 2, 3のいずれかになる場合）に、MinTopHashを加算して実際のハッシュ値が特殊なtophash値と衝突しないように調整するようになりました。

    • 旧: if(top == 0) top = 1;
    • 新: if(top < MinTopHash) top += MinTopHash; これにより、tophashエントリは、実際のハッシュ値の上位8ビットか、あるいはEmpty、EvacuatedEmpty、EvacuatedX、EvacuatedYのいずれかの特殊な値を持つことになります。

これらの変更により、Goのハッシュテーブルの実装は、GCの要件により適合し、将来的なGo言語へのコード移行が容易になるように改善されました。

関連リンク

参考にした情報源リンク

  • コミットメッセージと差分（diff）の内容
  • Go言語のmapの内部実装に関する一般的な知識
  • ガベージコレクションに関する一般的な知識