[インデックス 10017] Go fmt パッケージのテスト修正：マップの反復順序への依存を除去
コミット
コミットハッシュ: e45e3244204a8c944e231a8e168e68b5b5134bea
作成者: David Symonds dsymonds@golang.org
コミット日時: 2011年10月18日 11:47:11 +1100
メッセージ: fmt: fix test relying on map iteration order.
詳細: This fixes the 386 builds.
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/e45e3244204a8c944e231a8e168e68b5b5134bea
元コミット内容
commit e45e3244204a8c944e231a8e168e68b5b5134bea
Author: David Symonds <dsymonds@golang.org>
Date: Tue Oct 18 11:47:11 2011 +1100
fmt: fix test relying on map iteration order.
This fixes the 386 builds.
R=golang-dev, adg, r
CC=golang-dev
https://golang.org/cl/5293043
src/pkg/fmt/fmt_test.go | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/src/pkg/fmt/fmt_test.go b/src/pkg/fmt/fmt_test.go
index 8786e1b451..030ad6187f 100644
--- a/src/pkg/fmt/fmt_test.go
+++ b/src/pkg/fmt/fmt_test.go
@@ -349,8 +349,8 @@ var fmttests = []struct {
{"%#v", make(chan int), "(chan int)(0xPTR)"},
{"%#v", uint64(1<<64 - 1), "0xffffffffffffffff"},
{"%#v", 1000000000, "1000000000"},
- {"%#v", map[string]int{"a": 1, "b": 2}, `map[string]int{"a":1, "b":2}`},
- {"%#v", map[string]B{"a": {1, 2}, "b": {3, 4}}, `map[string]fmt_test.B{"a":fmt_test.B{I:1, j:2}, "b":fmt_test.B{I:3, j:4}}`},
+ {"%#v", map[string]int{"a": 1}, `map[string]int{"a":1}`},
+ {"%#v", map[string]B{"a": {1, 2}}, `map[string]fmt_test.B{"a":fmt_test.B{I:1, j:2}}`},
{"%#v", []string{"a", "b"}, `[]string{"a", "b"}`},
変更の背景
このコミットは、Go 1.0リリースに向けた準備期間中の2011年10月に行われた重要な修正です。Go言語では、バージョン1.0からマップの反復順序が意図的にランダム化されました。これは、開発者がマップの特定の反復順序に依存するコードを書くことを防ぐための設計決定でした。
問題の発生経緯：
- Go 1.0の設計変更: マップの反復順序を意図的にランダム化
- アーキテクチャ固有の問題: 386アーキテクチャ（32ビットx86）で既存のテストが失敗
- テストの依存性: fmt パッケージのテストがマップの反復順序に依存していた
- ビルドの失敗: 386 ビルドが継続的に失敗する状況
David Symonds氏は、fmt パッケージのテストコードがマップの反復順序に依存していることを発見し、この問題を修正する必要がありました。これは、Go言語のクロスプラットフォーム対応とテストの信頼性を確保するための重要な修正でした。
修正の重要性：
- Go 1.0 リリースの品質保証
- アーキテクチャ間の一貫性の確保
- テストの信頼性向上
- 将来の開発者への警告的役割
前提知識の解説
Go のマップの反復順序の問題
Go言語のマップは、他の多くのプログラミング言語と同様に、内部的にハッシュテーブルを使用して実装されています。初期のGoバージョンでは、マップの反復順序は実装に依存していました。
問題の発生メカニズム:
- 開発者が小さなマップを使用してテストを書く
- たまたま一貫した反復順序で動作する
- その順序に依存するテストコードを書いてしまう
- 異なるアーキテクチャや実装で動作させると順序が変わる
- テストが原因不明で失敗する
この問題は、特に小さなマップ（8要素以下）で顕著に現れました。小さなマップでは、ハッシュテーブルの構造が単純で、反復順序が比較的予測可能だったからです。
Go 1.0でのマップ反復順序ランダム化
Go 1.0では、この問題を根本的に解決するために、意図的にマップ反復順序をランダム化しました。具体的には:
- 反復の開始位置をランダムに選択: 疑似ランダムに選択されたキーから反復を開始
- ハッシュコードの計算にランダム要素を追加: ハッシュ関数にランダムシードを使用
- 実行するたびに異なる反復順序を生成: 同じコードでも実行毎に異なる順序
これにより、反復順序に依存するコードは早期に発見され、修正されるようになりました。
fmt パッケージの %#v 動詞
%#v 動詞は、Go の fmt パッケージで提供される書式指定子の一つで、Go構文表現として値を出力します。この動詞は、デバッグやテストにおいて値の詳細な表現を確認する際に非常に有用です。
%#v の特徴:
- 値をGo言語のソースコードのような形式で出力
- 型情報も含めた完全な表現を提供
- マップの場合、
map[キー型]値型{キー:値, ...}の形式で出力 - 構造体の場合、フィールド名も含めて出力
マップでの使用例:
m := map[string]int{"a": 1, "b": 2}
fmt.Printf("%#v", m) // map[string]int{"a":1, "b":2} (順序は保証されない)
386アーキテクチャの特徴
386アーキテクチャ（32ビットx86）は、以下の特徴があります:
- レジスタサイズ: 32ビット
- メモリアドレス空間: 最大4GBの物理メモリ
- エンディアン: リトルエンディアン
- ポインタサイズ: 32ビット（4バイト）
- ハッシュ関数の動作: 64ビットアーキテクチャと異なる可能性
386アーキテクチャ固有の問題:
- メモリレイアウトの違い: 32ビットと64ビットでのメモリアライメントの違い
- ハッシュ値の計算: ポインタサイズの違いによるハッシュ値の変動
- CPU命令の違い: 32ビット特有の命令セットの影響
- コンパイラの最適化: アーキテクチャ固有の最適化の違い
これらの違いにより、マップの内部実装やハッシュ値の計算結果が64ビットアーキテクチャと異なる場合があり、反復順序の違いが顕著に現れることがありました。
技術的詳細
fmt パッケージの役割と内部動作
fmt パッケージは、Go言語の書式付き入出力を担当する標準ライブラリです。以下の機能を提供します:
Printf,Sprintf,Fprintfなどの書式付き出力関数Scan,Scanfなどの入力関数- カスタム型のフォーマット対応（
Stringer、GoStringerインターフェース） - マップの出力フォーマット処理
fmt パッケージの内部動作:
- 型判定: 渡された値の型を判定
- フォーマット処理: 指定された動詞（
%v、%#vなど）に基づいて処理 - 文字列構築: 値を文字列表現に変換
- 出力: 構築された文字列を出力
マップの出力における問題
fmt パッケージでマップを出力する際、内部的にはマップの要素を反復処理して文字列を構築します。この処理において、反復順序が出力結果に影響するため、テストでの期待値と実際の出力が一致しないという問題が発生していました。
問題の具体例:
// 同じマップでも実行毎に異なる出力
m := map[string]int{"a": 1, "b": 2}
fmt.Printf("%#v", m)
// 実行1: map[string]int{"a":1, "b":2}
// 実行2: map[string]int{"b":2, "a":1}
テストでの影響:
- テストケースで期待する文字列が固定されている
- 実行環境やアーキテクチャによって出力順序が変わる
- テストが断続的に失敗する
アーキテクチャ固有の問題
386アーキテクチャでは、以下の要因により他のアーキテクチャと異なる動作を示すことがありました:
-
ポインタサイズの違い: 32ビット vs 64ビット
- ハッシュ値の計算に影響
- メモリアドレスの表現方法の違い
-
メモリアライメント: 32ビット境界でのアライメント
- 構造体のレイアウトの違い
- キャッシュ効率の違い
-
ハッシュ関数の実装: アーキテクチャ固有の最適化
- CPU命令セットの違い
- ハッシュ値の分布の違い
-
コンパイラの動作: 異なるコード生成
- 最適化レベルの違い
- 命令の並び順の違い
マップの内部実装における影響
Go のマップは、内部的に以下の構造を持ちます：
ハッシュテーブル構造:
- バケット: キーと値のペアを格納
- オーバーフロー: 衝突時の追加ストレージ
- ハッシュ関数: キーからバケットインデックスを計算
386アーキテクチャでの特殊性:
- 32ビットハッシュ値の使用
- メモリアドレス空間の制限
- AES命令の有無による影響（後の実装で追加）
テストの不安定性の原因
マップの反復順序に依存するテストは、以下の問題を引き起こします：
- 決定論的でない動作: 同じ入力でも異なる出力
- アーキテクチャ間の非互換性: 異なるアーキテクチャで異なる結果
- 実行時の不安定性: 同じ環境でも実行によって結果が変わる
- デバッグの困難さ: 問題の再現が困難
- 継続的インテグレーションの阻害: ビルドの成功/失敗が不安定
コアとなるコードの変更箇所
変更されたファイル: src/pkg/fmt/fmt_test.go
src/pkg/fmt/fmt_test.go | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
このコミットでは、fmt パッケージのテストファイルの2行が修正されました。変更内容は比較的小さいですが、その影響は重要でした。
具体的な変更内容
変更前（問題のあるコード）:
{"%#v", map[string]int{"a": 1, "b": 2}, `map[string]int{"a":1, "b":2}`},
{"%#v", map[string]B{"a": {1, 2}, "b": {3, 4}}, `map[string]fmt_test.B{"a":fmt_test.B{I:1, j:2}, "b":fmt_test.B{I:3, j:4}}`},
変更後（修正されたコード）:
{"%#v", map[string]int{"a": 1}, `map[string]int{"a":1}`},
{"%#v", map[string]B{"a": {1, 2}}, `map[string]fmt_test.B{"a":fmt_test.B{I:1, j:2}}`},
修正の性質
- 4つの変更: 2つの削除と2つの追加
- 対象: テストコード内のマップの反復順序に依存する部分
- 手法: 複数要素のマップを単一要素のマップに変更
- 目的: アーキテクチャ非依存のテストの実現
変更の技術的意味
- 要素数の削減: 2要素のマップから1要素のマップへ
- 期待値の調整: 対応する期待値文字列も単一要素版に変更
- 順序依存の除去: 単一要素では反復順序の問題が発生しない
- テストの目的維持:
%#v動詞の動作確認という本来の目的は保持
コアとなるコードの解説
テストデータ構造の理解
変更されたコードは、fmt パッケージの fmttests という変数内のテストデータです。この変数は、以下のような構造体のスライスとして定義されています：
var fmttests = []struct {
fmt string // フォーマット文字列（例: "%#v"）
val interface{} // テスト対象の値
out string // 期待される出力
}{
// テストケース...
}
修正前の問題のあるテストケース
修正前のテストケースは、以下のような問題を抱えていました：
// 修正前の問題のあるテストケース
{"%#v", map[string]int{"a": 1, "b": 2}, `map[string]int{"a":1, "b":2}`},
問題点:
- 順序依存: 期待値が特定の順序（"a":1, "b":2）を前提としている
- アーキテクチャ依存: 386アーキテクチャでは異なる順序で出力される可能性
- 非決定的: 実行毎に異なる結果が発生する可能性
修正後の安定したテストケース
修正後のテストケースは、順序に依存しない設計になっています：
// 修正後の安定したテストケース
{"%#v", map[string]int{"a": 1}, `map[string]int{"a":1}`},
改善点:
- 順序非依存: 単一要素のため反復順序の問題が発生しない
- アーキテクチャ非依存: 全てのアーキテクチャで同じ結果
- 決定的: 常に同じ結果が保証される
修正の技術的アプローチ
このコミットでは、以下のアプローチが採用されました：
1. 単一要素マップの使用:
// 修正前: 複数要素（順序依存）
map[string]int{"a": 1, "b": 2}
// 修正後: 単一要素（順序非依存）
map[string]int{"a": 1}
2. 期待値の対応調整:
// 修正前: 複数要素の期待値
`map[string]int{"a":1, "b":2}`
// 修正後: 単一要素の期待値
`map[string]int{"a":1}`
3. テスト目的の保持:
%#v動詞の動作確認という本来の目的は維持- マップの Go 構文表現の正確性は引き続き検証
- 型情報の出力も適切に確認
他の修正アプローチとの比較
このコミットでは単一要素マップを使用しましたが、他にも以下のようなアプローチが考えられます：
1. キーのソート:
// 出力後にキーをソートして比較
keys := make([]string, 0, len(m))
for k := range m {
keys = append(keys, k)
}
sort.Strings(keys)
// ソート済みキーで期待値を構築
2. 部分的な検証:
// 期待される要素が含まれているかを個別に確認
if !strings.Contains(result, `"a":1`) ||
!strings.Contains(result, `"b":2`) {
t.Errorf("Expected elements not found")
}
3. 正規表現の使用:
// 順序に依存しないパターンマッチング
pattern := `map\[string\]int\{(?:(?:"a":1|"b":2),?\s*){2}\}`
if !regexp.MatchString(pattern, result) {
t.Errorf("Format does not match expected pattern")
}
採用されたアプローチの利点
単一要素マップのアプローチが採用された理由：
- シンプルさ: 最も単純で理解しやすい解決策
- 確実性: 確実に問題を解決できる
- 保守性: 将来の変更に対しても安定
- 効率性: 実行時のオーバーヘッドが最小
- テストの意図維持:
%#v動詞の動作確認という目的を損なわない
関連リンク
- Go 1.0 Release Notes - マップ反復順序のランダム化について
- Go 1.3 Release Notes - 小さなマップの反復順序ランダム化の再導入
- Go Map Implementation - マップの内部実装
- Go fmt Package Documentation - fmt パッケージの公式ドキュメント
- Go Language Specification - Map types - マップ型の仕様
- Go Code Review 5293043 - このコミットのコードレビュー（当時）
参考にした情報源リンク
- Why are iterations over maps random? - Stack Overflow
- Go: what determines the iteration order for map keys? - Stack Overflow
- Go's map iteration order is random | Hacker News
- runtime: randomize iteration order of small maps · Issue #6719 · golang/go
- proposal: runtime/map: fix map iteration order · Issue #54500 · golang/go
- Go Release History - Go言語のリリース履歴
- Go fmt Package - Format verbs - フォーマット動詞の詳細
- Go by Example: String Formatting - 文字列フォーマットの例