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

このコミットは、Go言語のランタイムにおけるマップのイテレーション順序がランダムであることを検証するためのテストを追加するものです。Goの仕様ではマップのイテレーション順序は保証されていませんが、実装上は意図的にランダム化されており、このコミットはそのランダム性を確認するためのテストケースを導入しています。

コミット

commit d4c66a35baba191b5857960d75fe66d766f6d573
Author: David Symonds <dsymonds@golang.org>
Date:   Fri Jan 3 10:10:54 2014 +1100

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

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

元コミット内容

    runtime: add a test for randomised map iteration order.
    
    Technically the spec does not guarantee that the iteration order is random,
    but it is a property that we have consciously pursued, and so it seems
    right to verify that our implementation does indeed randomise.
    
    Update #6719.
    
    R=khr, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/47010043

変更の背景

Go言語のマップ（map）は、キーと値のペアを格納するハッシュテーブルベースのデータ構造です。Goの仕様では、マップをイテレート（for key := range m のようにループ処理）する際の要素の順序は**保証されない（undefined）**と明記されています。これは、実装の詳細やGoのバージョン、さらには同じプログラムの異なる実行間でも順序が変わりうることを意味します。

しかし、特に要素数が少ないマップの場合、実際のイテレーション順序が偶然一貫しているように見えることがありました。この「見かけ上の安定性」が、一部の開発者がマップのイテレーション順序に依存するコードを書いてしまう原因となっていました。このようなコードは、Goの仕様に反しており、異なる環境や将来のGoのバージョンで予期せぬバグを引き起こす可能性がありました。

この問題を明確にし、開発者がマップの順序に依存しない堅牢なコードを書くことを促すため、Goチームはマップのイテレーション順序を意図的にランダム化する方針を採用しました。このコミットは、そのランダム化が正しく機能していることを検証するためのテストを追加するものです。具体的には、Issue #6719「runtime: randomize iteration order of small maps」に関連しています。このイシューは、小さなマップのイテレーション順序をランダム化することで、開発者が順序に依存するコードを書くことを防ぐことを目的としていました。

前提知識の解説

Go言語のマップ (map)

Go言語のマップは、キーと値のペアを格納するための組み込みデータ型です。他の言語におけるハッシュマップ、ハッシュテーブル、ディクショナリに相当します。

宣言と初期化: make(map[KeyType]ValueType) で作成します。例: m := make(map[string]int)
要素の追加/更新: m[key] = value
要素の取得: value := m[key]
要素の削除: delete(m, key)
イテレーション: for key, value := range m { ... } の形式でマップの要素をループ処理できます。

マップのイテレーション順序の「保証なし」

Goの仕様がマップのイテレーション順序を保証しないというのは非常に重要な点です。これは以下のことを意味します。

予測不能性: マップをイテレートするたびに、要素が返される順序は異なる可能性があります。
実装依存: 順序はGoのランタイムの実装に依存し、将来のバージョンで変更される可能性があります。
環境依存: 異なるコンパイラ（例: gc と gccgo）や異なるアーキテクチャで実行した場合、順序が異なる可能性があります。
バグの温床: もしコードが特定のイテレーション順序に依存している場合、それは潜在的なバグであり、デバッグが困難な非決定的な挙動を引き起こす可能性があります。

Goが意図的にイテレーション順序をランダム化するのは、開発者がこの「保証なし」という仕様を真剣に受け止め、順序に依存しないコードを書くように促すためです。もし順序が必要な場合は、マップのキーをスライスに抽出し、そのスライスをソートするなど、明示的な順序付けメカニズムを使用する必要があります。

技術的詳細

このコミットで追加されたテスト TestMapIterOrder は、Goランタイムがマップのイテレーション順序をランダム化していることを統計的に検証しようとします。

Goランタイムは、マップのイテレーションを開始する際に、内部的にランダムな開始オフセットを選択することで、イテレーション順序をランダム化しています。これにより、同じマップを複数回イテレートした場合でも、異なる順序で要素が返される可能性が高まります。このランダム化は、特に小さなマップで順序が安定して見えるという問題を解決するために重要です。

TestMapIterOrder テストのロジックは以下の通りです。

異なるサイズのマップのテスト: n が9と15の2つの異なるサイズのマップに対してテストを実行します。これらのサイズは、マップの内部構造（バケットの数など）が異なる挙動を示す可能性があるため選ばれています。
マップの初期化: n 個の要素を持つマップ m を作成し、0 から n-1 までの整数をキーとして格納します。
順序の取得関数 ord(): マップ m をイテレートし、キーをスライス s に追加して返します。この関数は、特定の時点でのマップのイテレーション順序をキャプチャします。
順序の比較:
- 最初に ord() を呼び出して first という順序を取得します。
- その後、最大5回 ord() を呼び出し、その結果が first と異なるかどうかをチェックします。
- もし一度でも first と異なる順序が得られれば、テストは成功とみなされます（ok = true）。
テストの失敗条件: 5回の試行すべてで first と同じ順序しか得られなかった場合、テストは失敗し、エラーメッセージ「Map with n=%d elements had consistent iteration order: %v」が出力されます。これは、マップのイテレーション順序がランダム化されていないことを示唆します。

このテストは、厳密に「ランダムであること」を証明するものではありませんが、「一貫した順序ではないこと」を検証することで、ランダム化の意図が達成されていることを確認します。試行回数を5回に設定しているのは、統計的に異なる順序が出現する可能性が高いと判断されたためです。

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

diff --git a/src/pkg/runtime/map_test.go b/src/pkg/runtime/map_test.go
index a221cb28cf..f57d1f57c1 100644
--- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -409,3 +409,33 @@ func TestMapNanGrowIterator(t *testing.T) {
 	t.Fatalf("missing value")
 	}
 }
+
+func TestMapIterOrder(t *testing.T) {
+	// TODO: For issue 6719, add 3 and 7 to this list.
+	for _, n := range [...]int{9, 15} {
+		// Make m be {0: true, 1: true, ..., n-1: true}.
+		m := make(map[int]bool)
+		for i := 0; i < n; i++ {
+			m[i] = true
+		}
+		// Check that iterating over the map produces at least two different orderings.
+		ord := func() []int {
+			var s []int
+			for key := range m {
+				s = append(s, key)
+			}
+			return s
+		}
+		first := ord()
+		ok := false
+		for try := 0; try < 5; try++ {
+			if !reflect.DeepEqual(first, ord()) {
+				ok = true
+				break
+			}
+		}
+		if !ok {
+			t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
+		}
+	}
+}

コアとなるコードの解説

追加された TestMapIterOrder 関数は src/pkg/runtime/map_test.go にあります。

func TestMapIterOrder(t *testing.T) {
	// TODO: For issue 6719, add 3 and 7 to this list.
	for _, n := range [...]int{9, 15} {
		// Make m be {0: true, 1: true, ..., n-1: true}.
		m := make(map[int]bool)
		for i := 0; i < n; i++ {
			m[i] = true
		}
		// Check that iterating over the map produces at least two different orderings.
		ord := func() []int {
			var s []int
			for key := range m {
				s = append(s, key)
			}
			return s
		}
		first := ord() // 最初のイテレーション順序を記録
		ok := false
		for try := 0; try < 5; try++ { // 最大5回試行
			if !reflect.DeepEqual(first, ord()) { // 最初の順序と異なる順序が得られたか？
				ok = true
				break // 異なれば成功
			}
		}
		if !ok { // 5回試行しても異なる順序が得られなかった場合
			t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
		}
	}
}

for _, n := range [...]int{9, 15}: 要素数9と15のマップに対してテストを実行します。コメントにある TODO は、Issue 6719の議論で、要素数3と7のマップもテスト対象に加えるべきか検討されていたことを示唆しています。
m := make(map[int]bool) と for i := 0; i < n; i++ { m[i] = true }: n 個の要素を持つマップを作成し、キーを0からn-1まで順に設定します。値はテストの目的上重要ではないため true に設定されています。
ord := func() []int { ... }: この無名関数は、現在のマップ m をイテレートし、その際に得られたキーの順序を []int スライスとして返します。
first := ord(): マップを最初にイテレートしたときの順序を first に保存します。
for try := 0; try < 5; try++: その後、最大5回マップをイテレートし直します。
if !reflect.DeepEqual(first, ord()): reflect.DeepEqual を使用して、現在のイテレーション順序が first と異なるかどうかを厳密に比較します。
ok = true; break: もし異なる順序が見つかれば、ok を true に設定し、ループを抜けます。これは、ランダム化が機能していることを示します。
if !ok { t.Errorf(...) }: 5回の試行すべてで first と同じ順序しか得られなかった場合、ok は false のままであり、t.Errorf が呼び出されてテストが失敗します。これは、マップのイテレーション順序が期待通りにランダム化されていないことを示します。

このテストは、マップのイテレーション順序が「非決定論的であること」を検証するものであり、Goのマップの設計思想を反映しています。

参考にした情報源リンク

Go map iteration order randomization: https://stackoverflow.com/questions/20001460/go-map-iteration-order-randomization
Why are Go map iteration order randomized?: https://stackoverflow.com/questions/20001460/go-map-iteration-order-randomization (重複だが、異なる回答を参照した可能性あり)
Go maps are not ordered: https://www.reddit.com/r/golang/comments/110000/go_maps_are_not_ordered/
Go maps are not ordered (Y Combinator): https://news.ycombinator.com/item?id=6677777
Go maps are not ordered (github.com): https://github.com/golang/go/issues/6719 (Issue #6719自体も参考情報として含める)

comemo