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

このコミットは、Go言語のマップ（map）において、非数（NaN: Not a Number）をキーとして使用した場合の挙動、特にパフォーマンス特性に関するテストを追加するものです。具体的には、NaNをマップのキーとして繰り返し挿入する際に、処理時間が線形（linear）に増加するべきであるにもかかわらず、二次（quadratic）に増加してしまう可能性がないかを検証するためのテストが導入されています。

コミット

commit 6ebf8a6400e9637f579da52a50a0ecb94d798e46
Author: Russ Cox <rsc@golang.org>
Date:   Mon Jan 30 13:41:38 2012 -0500

    test: add test of NaN in map
    
    R=iant, r
    CC=golang-dev
    https://golang.org/cl/5576071

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

https://github.com/golang/go/commit/6ebf8a6400e9637f579da52a50a0ecb94d798e46

元コミット内容

test: add test of NaN in map

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

変更の背景

Go言語のマップはハッシュテーブルとして実装されており、キーのハッシュ値に基づいて要素を格納・検索します。浮動小数点数（float64など）をマップのキーとして使用する場合、非数（NaN）の特殊な性質が問題となることがあります。IEEE 754浮動小数点数標準において、NaNはそれ自身を含め、他のいかなる値とも等しくないと定義されています（NaN == NaNはfalse）。

この「等しくない」という特性は、マップのキーとして使用する際に問題を引き起こす可能性があります。マップはキーの等価性チェックとハッシュ値に基づいて動作するため、異なるNaN値（ビットパターンが異なるNaN）が挿入された場合、それらがすべて異なるキーとして扱われる可能性があります。もしマップの実装がNaNの特殊性を適切に扱わないと、すべてのNaNが同じハッシュバケットに衝突し、そのバケット内での線形探索が頻繁に発生することで、挿入や検索の操作がO(N)（線形時間）に近づき、結果として全体としてO(N^2)（二次時間）のパフォーマンス劣化を引き起こす可能性があります。

このコミットは、このような潜在的なパフォーマンス問題を早期に検出し、Goマップの実装がNaNをキーとして適切に処理し、パフォーマンスが二次的に劣化しないことを保証するためのテストを追加することを目的としています。

前提知識の解説

1. 非数（NaN: Not a Number）

NaNは、浮動小数点数演算の結果として定義されない、または表現できない値を表す特殊な浮動小数点値です。例えば、0/0やsqrt(-1)のような演算結果がNaNになります。IEEE 754標準では、NaNは以下の重要な特性を持ちます。

• 比較の特殊性: NaNは、それ自身を含め、他のいかなる浮動小数点値とも等しくありません。つまり、NaN == NaNはfalseと評価されます。これは、通常の数値の比較とは大きく異なる点です。
• 異なるビットパターン: 複数の異なるビットパターンを持つNaNが存在する可能性があります。これらはすべて「非数」を表しますが、内部的には異なる値として扱われることがあります。

2. Go言語のマップ（map）

Go言語のマップは、キーと値のペアを格納するハッシュテーブルです。マップの基本的な操作（挿入、検索、削除）は、平均的にはO(1)（定数時間）の計算量で実行されます。これは、キーのハッシュ値を計算し、そのハッシュ値に基づいてメモリ上の特定の位置（バケット）にアクセスすることで実現されます。

• ハッシュ関数: マップのキー型には、ハッシュ関数が定義されている必要があります。Goの組み込み型（数値、文字列、ポインタなど）は自動的にハッシュ可能です。
• 等価性チェック: 同じハッシュ値を持つ異なるキー（ハッシュ衝突）が発生した場合、マップはキーの等価性チェック（==演算子など）を使用して、目的のキーがバケット内に存在するかどうかを判断します。

3. 計算量（時間計算量）

アルゴリズムの効率性を示す指標で、入力サイズ（N）に対する処理時間の増加率を表します。

• O(1) - 定数時間: 入力サイズに関わらず、処理時間が一定。理想的な効率。
• O(N) - 線形時間: 入力サイズに比例して処理時間が増加。
• O(N^2) - 二次時間: 入力サイズの二乗に比例して処理時間が増加。入力サイズが大きくなると、処理時間が急激に増加するため、大規模なデータセットでは避けるべき非効率なアルゴリズムとされます。

4. NaNとマップの相互作用

NaNの比較特性（NaN == NaNがfalse）は、マップのキーとして使用する際に特有の課題をもたらします。Goのマップは、キーの等価性に基づいて動作するため、もし異なるNaNが異なるキーとして扱われ、かつそれらがすべて同じハッシュバケットに衝突した場合、そのバケット内での線形探索が繰り返され、結果としてマップ操作の計算量が二次的に増加する可能性があります。

例えば、map[float64]intに複数のNaNを挿入する場合、Goのマップは内部的にこれらのNaNを異なるキーとして認識し、それぞれを異なるエントリとして格納しようとします。しかし、もしハッシュ関数がすべてのNaNに対して同じハッシュ値を返す場合、それらはすべて同じハッシュバケットに格納されます。このバケットが非常に大きくなると、新しいNaNを挿入するたびに、そのバケット内の既存のすべての要素と比較する必要が生じ、これが二次的なパフォーマンス劣化の原因となります。

技術的詳細

このコミットで追加されたテスト testnan() は、Go言語のマップがNaNをキーとして使用した場合に、パフォーマンスが二次的に劣化しないことを検証するために設計されています。

テストの核心は以下の点にあります。

1. NaNの繰り返し挿入: math.NaN()によって生成されたNaN値を、大量（n回、最初は30000回）マップのキーとして繰り返し挿入します。Goのマップは、NaNをキーとして使用した場合、異なるNaN値（たとえビットパターンが同じでも）を異なるキーとして扱います。したがって、m[nan] = 1という操作をn回繰り返すと、マップのサイズはnになるはずです。
2. 時間計測: time.Now()とtime.Since()を使用して、n回の挿入にかかる時間（t1）と、2*n回の挿入にかかる時間（t2）を計測します。
3. パフォーマンスの検証:
   • もしマップの操作が線形時間（O(N)）であれば、2*n回の挿入にかかる時間t2は、n回の挿入にかかる時間t1の約2倍になるはずです。
   • もしマップの操作が二次時間（O(N^2)）であれば、2*n回の挿入にかかる時間t2は、n回の挿入にかかる時間t1の約4倍になるはずです。
   • テストでは、t2 > 3*t1という条件でパフォーマンスの劣化をチェックしています。これは、線形時間（2倍）に多少の余裕（3倍まで許容）を持たせつつ、二次時間（4倍以上）への移行を検出するための閾値です。もしこの条件が真であれば、パフォーマンスが期待通りに線形ではなく、二次的に劣化している可能性が高いと判断し、エラーメッセージを出力します。

このテストは、Goのマップ実装がNaNの特殊性を適切に処理し、ハッシュ衝突の解決やバケット管理において効率的なアルゴリズムを維持していることを保証するための重要なチェックとなります。具体的には、GoのマップはNaNをキーとして扱う際に、すべてのNaNが同じハッシュ値を持つように設計されており、内部的にはそれらを異なるキーとして認識しつつも、効率的な衝突解決メカニズム（例えば、オープンアドレス法やチェイニング）によってパフォーマンス劣化を防いでいると考えられます。

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

test/map.go ファイルに以下の変更が加えられています。

1. import 文に "time" パッケージが追加されました。
2. main 関数内で、既存の testbasic() と testfloat() の呼び出しに加えて、新しく追加された testnan() 関数が呼び出されるようになりました。
3. testfloat() 関数の呼び出しが main 関数から削除され、main 関数内で直接呼び出されるようになりました。
4. testnan() という新しい関数が追加されました。

--- a/test/map.go
+++ b/test/map.go
@@ -10,6 +10,7 @@ import (
  	"fmt"
  	"math"
  	"strconv"
+	"time"
  )
  
  const count = 100
@@ -27,6 +28,12 @@ func P(a []string) string {
  }
  
  func main() {
+	testbasic()
+	testfloat()
+	testnan()
+}
+
+func testbasic() {
  	// Test a map literal.
  	mlit := map[string]int{"0": 0, "1": 1, "2": 2, "3": 3, "4": 4}
  	for i := 0; i < len(mlit); i++ {
@@ -489,8 +496,6 @@ func main() {
  	for _, _ = range mnil {
  		panic("range mnil")
  	}
-
-	testfloat()
  }
  
  func testfloat() {
@@ -646,3 +651,26 @@ func testfloat() {
  		}
  	}\n
 }\n
+\n
+func testnan() {
+\t// Test that NaNs in maps don't go quadratic.
+\tt := func(n int) time.Duration {
+\t\tt0 := time.Now()
+\t\tm := map[float64]int{}\n
+\t\tnan := math.NaN()\n
+\t\tfor i := 0; i < n; i++ {
+\t\t\tm[nan] = 1
+\t\t}\n
+\t\tif len(m) != n {
+\t\t\tpanic("wrong size map after nan insertion")
+\t\t}\n
+\t\treturn time.Since(t0)\n
+\t}\n
+\n
+\tn := 30000 // 0.02 seconds on a MacBook Air
+\tt1 := t(n)\n
+\tt2 := t(2 * n)\n
+\tif t2 > 3*t1 { // should be 2x (linear); allow up to 3x
+\t\tfmt.Printf("too slow: %d inserts: %v; %d inserts: %v\\n", n, t1, 2*n, t2)\n
+\t}\n
+}\n

コアとなるコードの解説

追加された testnan() 関数は以下のロジックで構成されています。

func testnan() {
	// Test that NaNs in maps don't go quadratic.
	t := func(n int) time.Duration {
		t0 := time.Now()
		m := map[float64]int{}
		nan := math.NaN()
		for i := 0; i < n; i++ {
			m[nan] = 1
		}
		if len(m) != n {
			panic("wrong size map after nan insertion")
		}
		return time.Since(t0)
	}

	n := 30000 // 0.02 seconds on a MacBook Air
	t1 := t(n)
	t2 := t(2 * n)
	if t2 > 3*t1 { // should be 2x (linear); allow up to 3x
		fmt.Printf("too slow: %d inserts: %v; %d inserts: %v\\n", n, t1, 2*n, t2)
	}
}

1. t := func(n int) time.Duration { ... }:

   • これは、指定された回数 n だけNaNをマップに挿入し、その操作にかかる時間を計測する匿名関数です。
   • t0 := time.Now(): 処理開始時刻を記録します。
   • m := map[float64]int{}: float64をキーとする新しいマップを作成します。
   • nan := math.NaN(): 非数（NaN）を生成します。Go言語では、math.NaN()は常に同じビットパターンを持つNaNを返しますが、IEEE 754の定義により、nan == nanはfalseとなります。
   • for i := 0; i < n; i++ { m[nan] = 1 }: n回ループし、毎回同じnan変数をキーとしてマップに値を挿入します。GoのマップはNaNをキーとして使用した場合、異なるNaN値（たとえビットパターンが同じでも）を異なるキーとして扱います。したがって、このループが完了すると、マップmにはn個の異なるエントリが格納されているはずです。
   • if len(m) != n { panic("wrong size map after nan insertion") }: マップのサイズが期待通りnになっているかを確認します。もしn個のNaNが異なるキーとして正しく挿入されていない場合（例えば、NaNが重複して扱われたり、挿入が失敗したりした場合）、パニックを発生させます。
   • return time.Since(t0): 処理にかかった時間をtime.Duration型で返します。

2. n := 30000:

   • 最初の挿入回数を30000回に設定しています。コメントには「MacBook Airで0.02秒」とあり、これはこのテストが比較的短時間で実行されることを示唆しています。

3. t1 := t(n):

   • n回（30000回）のNaN挿入にかかる時間を計測し、t1に格納します。

4. t2 := t(2 * n):

   • 2 * n回（60000回）のNaN挿入にかかる時間を計測し、t2に格納します。

5. if t2 > 3*t1 { ... }:

   • この条件がテストの核心です。
   • もしマップの操作が**線形時間（O(N)）**であれば、2*n回の操作はn回の操作の約2倍の時間がかかるはずです（t2 ≈ 2 * t1）。
   • もしマップの操作が**二次時間（O(N^2)）**であれば、2*n回の操作はn回の操作の約4倍の時間がかかるはずです（t2 ≈ 4 * t1）。
   • 3*t1という閾値は、線形時間（2倍）に多少の余裕を持たせつつ、二次時間（4倍以上）への移行を検出するためのものです。もしt2がt1の3倍を超えた場合、それはパフォーマンスが期待される線形性を逸脱し、二次的な劣化の兆候があると判断され、エラーメッセージが出力されます。

このテストは、GoのマップがNaNをキーとして扱う際のパフォーマンス特性を厳密に検証し、大規模なデータセットでも効率的な動作を保証するための重要なセーフティネットとして機能します。

関連リンク

• Go言語のマップの内部実装 (Go's map implementation) - Go言語のマップの基本的な動作と内部構造について解説されています。
• IEEE 754 浮動小数点数標準 - NaNの定義と特性に関する詳細な情報。
• Go言語の浮動小数点数とNaNの比較に関する議論 (Go issue tracker discussions on NaN comparison) - Go言語におけるNaNの比較やマップでの挙動に関する過去の議論が見つかる可能性があります。

参考にした情報源リンク

• コミット情報: /home/orange/Project/comemo/commit_data/11475.txt
• GitHubコミットページ: https://github.com/golang/go/commit/6ebf8a6400e9637f579da52a50a0ecb94d798e46
• Go言語のドキュメント（mathパッケージ、timeパッケージ、mapの言語仕様など）
• IEEE 754浮動小数点数標準に関する一般的な知識
• 計算量に関する一般的な知識