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

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

このコミットは、Go言語の標準ライブラリにおけるマップ（map）のテストに関する修正です。具体的には、NaN（Not a Number）をキーとして使用した場合のマップのパフォーマンス特性をテストする際に発生していた、不安定な（flaky）ビルドエラーを解消することを目的としています。テストの測定方法を改善し、より信頼性の高い結果を得られるように変更されています。

コミット

  • コミットハッシュ: 5e21cb786589d28ad6b31ec9e43f8bf73ff93a82
  • Author: Brad Fitzpatrick bradfitz@golang.org
  • Date: Sun Apr 7 11:56:15 2013 -0700

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

https://github.com/golang/go/commit/5e21cb786589d28ad6b31ec9e43f8bf73ff93a82

元コミット内容

test: fix flaky NaN-key map complexity test

Don't measure wall time in map.go. Keep it portable
and only test NaN, but not time.

Move time tests to mapnan.go and only measure user CPU time,
not wall time. It builds on Darwin and Linux, the primary
platforms where people hack on the runtime & in particular
maps. The runtime is shared, though, so we don't need it to
run on all of the platforms.

Fixes flaky build failures like:
http://build.golang.org/log/ba67eceefdeaa1142cb6c990a62fa3ffd8fd73f8

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

変更の背景

このコミットの主な背景は、Go言語のビルドシステムで発生していた不安定なテスト失敗（flaky build failures）です。具体的には、test/map.go 内の testnan 関数が、NaN（Not a Number）をマップのキーとして挿入する際のパフォーマンスを測定していましたが、このテストが「ウォールタイム（wall time）」、つまり実時間を測定していたため、実行環境の負荷や他のプロセス、スケジューリングの影響を受けやすく、結果が不安定になっていました。

Go言語のマップは、キーのハッシュ値に基づいて要素を格納します。浮動小数点数における NaN は、比較演算において NaN == NaN が false となる特殊な性質を持っています。このため、マップに複数の NaN をキーとして挿入した場合、それらが異なるエントリとして扱われる可能性があり、その際のパフォーマンスが線形（linear）であることを確認するテストが必要でした。しかし、ウォールタイムでの測定は、テストの再現性を損ない、ビルドの信頼性を低下させていました。

この不安定なテストは、Goの継続的インテグレーション（CI）システムにおいて、http://build.golang.org/log/ba67eceefdeaa1142cb6c990a62fa3ffd8fd73f8 のようなビルド失敗を引き起こしていました。開発者は、このような不安定なテストを修正し、CIの信頼性を向上させる必要がありました。

前提知識の解説

1. NaN (Not a Number)

NaN は、IEEE 754 浮動小数点数標準で定義されている特殊な数値表現です。これは、0による除算、無限大同士の減算、負の数の平方根など、数学的に未定義または表現不可能な演算の結果として生成されます。NaN の最も重要な特性は、いかなる値とも等しくないという点です。これには NaN 自身も含まれます。つまり、NaN == NaN は常に false と評価されます。

Go言語の math パッケージには math.NaN() 関数があり、NaN 値を返します。また、math.IsNaN() 関数を使って、ある値が NaN であるかどうかを判定できます。

2. Go言語のマップ (map) と NaN

Go言語のマップは、キーと値のペアを格納するハッシュテーブルの実装です。キーはハッシュ可能である必要があり、Goの組み込み型（数値、文字列、ポインタ、構造体など）の多くはハッシュ可能です。浮動小数点数もマップのキーとして使用できますが、NaN の特殊な性質が問題を引き起こす可能性があります。

通常の数値キーの場合、同じ値は同じハッシュ値を持ち、マップ内で同じエントリとして扱われます。しかし、NaN は NaN == NaN が false であるため、Goのマップの実装によっては、異なる NaN 値（たとえビットパターンが同じでも）が異なるキーとして扱われ、マップに挿入されるたびに新しいエントリが作成されてしまう可能性があります。これにより、マップのサイズが予期せず増大し、パフォーマンスが劣化する（特に線形ではなく二次曲線的に悪化する）「二次曲線的な複雑さ（quadratic complexity）」の問題が発生する可能性があります。このコミットのテストは、この問題が発生しないことを確認するためのものです。

3. ウォールタイム (Wall Time) と ユーザーCPU時間 (User CPU Time)

  • ウォールタイム (Wall Time): 「実時間」または「経過時間」とも呼ばれ、プログラムの開始から終了までに実際に経過した時間です。これは、CPUの実行時間だけでなく、I/O待ち、他のプロセスの実行、オペレーティングシステムによるスケジューリング、ネットワーク遅延など、プログラムがブロックされている時間もすべて含みます。ウォールタイムは、システム全体の負荷や外部要因に大きく左右されるため、パフォーマンス測定の再現性が低い場合があります。

  • ユーザーCPU時間 (User CPU Time): プログラムがユーザーモードでCPUを実行した合計時間です。これは、プログラム自身のコードがCPU上で実行された純粋な時間を示します。システムコール（カーネルモードでの処理）の時間は含まれません。ユーザーCPU時間は、ウォールタイムに比べて外部要因の影響を受けにくく、プログラム自身の計算負荷をより正確に反映するため、パフォーマンスベンチマークやアルゴリズムの計算量評価に適しています。

4. syscall.Getrusage

syscall.Getrusage は、Unix系システムコールの一つで、現在のプロセスまたはその子プロセスのリソース使用状況（CPU時間、メモリ使用量、I/O操作など）を取得するために使用されます。Go言語の syscall パッケージを通じてこの関数を呼び出すことで、ユーザーCPU時間やシステムCPU時間などの詳細な情報を取得できます。

このコミットでは、syscall.Getrusage を使用してユーザーCPU時間を測定することで、ウォールタイムの不安定さを回避し、より正確で再現性の高いパフォーマンス測定を実現しています。

技術的詳細

このコミットの技術的な核心は、NaN キーを持つマップのパフォーマンス測定方法の変更と、テストコードの分離です。

  1. test/map.go から時間測定ロジックの削除:

    • 元の test/map.go の testnan 関数は、time.Now() と time.Since() を使用してウォールタイムを測定していました。
    • このコミットでは、test/map.go から time パッケージのインポートと、ウォールタイムを測定する t 関数（func(n int) time.Duration）が完全に削除されました。
    • testnan 関数は、単に n 個の NaN をマップに挿入し、マップのサイズが n であること、およびマップをイテレートした際にキーが NaN であり値が正しいことを確認する、基本的な機能テストに簡素化されました。これにより、test/map.go はプラットフォームに依存しない、純粋な機能テストとして維持されます。

  2. test/mapnan.go の新規作成とユーザーCPU時間測定への移行:

    • NaN キーを持つマップのパフォーマンス（線形性）を時間的に測定するロジックは、新しく作成された test/mapnan.go ファイルに移動されました。
    • この新しいファイルは、ビルドタグ // +build darwin,linux を持っています。これは、このテストがDarwin（macOS）とLinuxプラットフォームでのみビルドおよび実行されることを意味します。コミットメッセージにあるように、これらのプラットフォームはGoランタイム、特にマップの開発が主に行われる場所であり、すべてのプラットフォームで実行する必要はないという判断です。
    • test/mapnan.go 内の t 関数は、syscall.Getrusage を使用してユーザーCPU時間を測定するように変更されました。具体的には、マップ操作の前後で syscall.Getrusage(0, &u0) と syscall.Getrusage(0, &u1) を呼び出し、u1.Utime.Nano() - u0.Utime.Nano() によってユーザーCPU時間のナノ秒単位の差分を計算しています。
    • このテストは、n 個の NaN を挿入した場合のユーザーCPU時間 t1 と、2n 個の NaN を挿入した場合のユーザーCPU時間 t2 を比較し、t2 が 3 * t1 未満であることを確認します。これは、挿入操作の複雑さが線形（2倍のデータで2倍の時間）であることを許容範囲（最大3倍）で検証するものです。
    • テストが失敗した場合（つまり、パフォーマンスが線形ではない場合）、n の値を増やして再試行するロジックも含まれています。これは、測定の粒度が不十分な場合に、より長い実行時間で正確な測定を試みるためです。

この変更により、NaN キーを持つマップのパフォーマンステストは、ウォールタイムの変動に左右されなくなり、より安定したビルド結果をもたらすようになりました。また、プラットフォーム固有のパフォーマンス測定ロジックを分離することで、コードベース全体のポータビリティが向上しています。

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

test/map.go の変更

--- a/test/map.go
+++ b/test/map.go
@@ -5,6 +5,7 @@
 // license that can be found in the LICENSE file.
 
 // Test maps, almost exhaustively.
+// NaN complexity test is in mapnan.go.
 
 package main
 
@@ -12,7 +13,6 @@ import (
 	"fmt"
 	"math"
 	"strconv"
-	"time"
 )
 
 const count = 100
@@ -659,39 +659,26 @@ func testfloat() {
 }
 
 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 := 500
+	m := map[float64]int{}
+	nan := math.NaN()
+	for i := 0; i < n; i++ {
+		m[nan] = 1
 	}
-
-	// Depending on the machine and OS, this test might be too fast
-	// to measure with accurate enough granularity. On failure,
-	// make it run longer, hoping that the timing granularity
-	// is eventually sufficient.\n-\n-\tn := 30000 // 0.02 seconds on a MacBook Air
-	fails := 0
-	for {
-		t1 := t(n)
-		t2 := t(2 * n)
-		// should be 2x (linear); allow up to 3x
-		if t2 < 3*t1 {
-			return
-		}
-		fails++
-		if fails == 4 {
-			panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2))
-			return
-		}
-		n *= 2
+	if len(m) != n {
+		panic("wrong size map after nan insertion")
+	}
+	iters := 0
+	for k, v := range m {
+		iters++
+		if !math.IsNaN(k) {
+			panic("not NaN")
+		}
+		if v != 1 {
+			panic("wrong value")
+		}
+	}
+	if iters != n {
+		panic("wrong number of nan range iters")
 	}
 }

test/mapnan.go の新規追加

--- /dev/null
+++ b/test/mapnan.go
@@ -0,0 +1,64 @@
+// +build darwin,linux
+// run
+
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Test that NaNs in maps don't go quadratic.
+
+package main
+
+import (
+	"fmt"
+	"math"
+	"time"
+	"syscall"
+)
+
+func main() {
+
+	// Test that NaNs in maps don't go quadratic.
+	t := func(n int) time.Duration {
+		var u0 syscall.Rusage
+		if err := syscall.Getrusage(0,  &u0); err != nil {
+			panic(err)
+		}
+		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")
+		}
+		var u1 syscall.Rusage
+		if err := syscall.Getrusage(0,  &u1); err != nil {
+			panic(err)
+		}
+		return time.Duration(u1.Utime.Nano() - u0.Utime.Nano())
+	}
+
+	// Depending on the machine and OS, this test might be too fast
+	// to measure with accurate enough granularity. On failure,
+	// make it run longer, hoping that the timing granularity
+	// is eventually sufficient.
+
+	n := 30000 // ~8ms user time on a Mid 2011 MacBook Air (1.8 GHz Core i7)
+	fails := 0
+	for {
+		t1 := t(n)
+		t2 := t(2 * n)
+		// should be 2x (linear); allow up to 3x
+		if t2 < 3*t1 {
+			return
+		}
+		fails++
+		if fails == 6 {
+			panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2))
+		}
+		if fails < 4 {
+			n *= 2
+		}
+	}
+}

コアとなるコードの解説

test/map.go の testnan 関数

変更後の testnan 関数は、時間測定のロジックが削除され、NaN をキーとしてマップに挿入した際の基本的な動作確認に特化しています。

  1. n := 500: テストに使用する NaN の挿入回数を 500 に設定しています。
  2. m := map[float64]int{}: float64 をキー、int を値とするマップを初期化します。
  3. nan := math.NaN(): NaN 値を生成します。
  4. for i := 0; i < n; i++ { m[nan] = 1 }: n 回ループし、毎回同じ NaN 値をキーとしてマップに挿入します。Goのマップは、NaN をキーとして使用した場合でも、それらが同じエントリとして扱われるように設計されているため、このループの終了後もマップの len(m) は 1 になるはずです（ただし、このテストでは n 個の NaN が挿入された後に len(m) が n になることを期待しているように見えます。これは、Goのマップが NaN をキーとして扱う際の特殊な挙動、つまり異なる NaN は異なるキーとして扱われるという性質をテストしているためです。実際には、Goのマップは NaN をキーとして使用すると、NaN のビットパターンが同じでも、異なる NaN は異なるキーとして扱われる可能性があります。このテストは、その際にパフォーマンスが劣化しないことを確認しています）。
  5. if len(m) != n { panic("wrong size map after nan insertion") }: マップの要素数が n と等しいことを確認します。これは、n 個の異なる NaN がマップに挿入されたことを期待していることを示唆しています。
  6. for k, v := range m { ... }: マップをイテレートし、各キー k が NaN であること、および値 v が 1 であることを確認します。これにより、挿入されたデータが正しく保持されていることを検証します。
  7. if iters != n { panic("wrong number of nan range iters") }: イテレーション回数が n と等しいことを確認します。

この簡素化された testnan 関数は、NaN の基本的なマップ動作を検証し、時間測定の複雑さを排除することで、よりポータブルで安定したテストを実現しています。

test/mapnan.go の main 関数

新しく追加された test/mapnan.go は、NaN キーを持つマップのパフォーマンス特性を、より厳密に時間測定する役割を担います。

  1. // +build darwin,linux: この行はビルドタグです。Goのビルドシステムは、このタグがあるファイルが darwin または linux 環境でのみコンパイルされるようにします。これにより、syscall.Getrusage のようなプラットフォーム固有のAPIを使用するコードが、サポートされていない環境でコンパイルエラーになるのを防ぎます。
  2. t := func(n int) time.Duration { ... }: この匿名関数 t は、n 個の NaN をマップに挿入する操作にかかるユーザーCPU時間を測定します。
    • var u0 syscall.Rusage: syscall.Rusage 構造体を宣言し、操作前のリソース使用状況を格納します。
    • syscall.Getrusage(0, &u0): 現在のプロセスのリソース使用状況を取得します。
    • マップへの NaN 挿入ロジックは test/map.go と同様です。
    • var u1 syscall.Rusage: 操作後のリソース使用状況を格納します。
    • syscall.Getrusage(0, &u1): 操作後のリソース使用状況を再度取得します。
    • return time.Duration(u1.Utime.Nano() - u0.Utime.Nano()): u1.Utime と u0.Utime は syscall.Timeval 型で、秒とマイクロ秒のフィールドを持ちます。.Nano() メソッドはこれをナノ秒に変換します。この差分がユーザーCPU時間です。
  3. n := 30000: 初期挿入回数を 30000 に設定しています。これは、測定の粒度を確保するために十分な時間かかるように調整された値です。
  4. for { ... }: 無限ループでテストを繰り返します。
    • t1 := t(n): n 個の挿入にかかるユーザーCPU時間を測定します。
    • t2 := t(2 * n): 2n 個の挿入にかかるユーザーCPU時間を測定します。
    • if t2 < 3*t1 { return }: パフォーマンスが線形であることを検証します。2n 個の挿入にかかる時間が n 個の挿入にかかる時間の3倍未満であれば、テストは成功とみなされ、関数を終了します。これは、厳密な2倍ではなく、ある程度の許容範囲を持たせています。
    • fails++: 失敗回数をカウントします。
    • if fails == 6 { panic(...) }: 失敗回数が6回に達した場合、テストは「遅すぎる」と判断し、パニック（エラー）を発生させます。
    • if fails < 4 { n *= 2 }: 失敗回数が4回未満の場合、n の値を2倍にして、より長い実行時間で再試行します。これは、測定の粒度が不十分で、正確な時間差を捉えられない場合に、テストをより長く実行させることで解決を試みるためのロジックです。

この mapnan.go のテストは、NaN キーを持つマップのパフォーマンスが、挿入される要素数に対して線形であることを、ユーザーCPU時間という安定した指標を用いて厳密に検証しています。これにより、Goのマップ実装が NaN を効率的に処理していることを保証し、CIの不安定性を解消しています。

関連リンク

参考にした情報源リンク

このコミット解説は、Go言語のマップにおける NaN キーの挙動と、テストの安定性に関する重要な側面を深く掘り下げています。

Go言語のマップと NaN キーの挙動について補足:

検索結果で「In Go, NaN (Not a Number) values cannot be used as map keys. This is because map keys must be comparable, and NaN values are not comparable to themselves (i.e., NaN == NaN evaluates to false). Attempting to use a NaN value as a key in a Go map will result in a runtime panic.」とありますが、これはGoのバージョンが古いか、あるいは一般的な誤解に基づいている可能性があります。

Go 1.0以降、float64 や float32 はマップのキーとして使用できます。そして、NaN もキーとして使用できます。 重要なのは、Goのマップが NaN をキーとして扱う際の挙動です。

  • NaN == NaN は false ですが、マップのキーとしての比較は異なります。 Goのマップは、キーの等価性を判断するために、== 演算子ではなく、内部的なハッシュ関数と等価性チェックを使用します。
  • Goのマップでは、すべての NaN は同じハッシュ値を持つように設計されています。 しかし、NaN は == で比較すると常に false になるため、マップに複数の NaN をキーとして挿入した場合、それらは異なるエントリとして扱われます。つまり、m[math.NaN()] = 1 を複数回実行すると、マップのサイズは挿入回数分だけ増えます。
  • このコミットのテスト testnan が if len(m) != n { panic("wrong size map after nan insertion") } としているのは、まさにこの挙動（n 回挿入すれば n 個のエントリができる）を期待しているためです。そして、この n 個の異なる NaN エントリを効率的に処理できるか（二次曲線的な複雑さにならないか）を mapnan.go で時間測定しているわけです。

したがって、検索結果の「Attempting to use a NaN value as a key in a Go map will result in a runtime panic」という記述は、現在のGoの挙動とは異なります。Goのマップは NaN をキーとして受け入れますが、その比較特性により、複数の NaN は異なるキーとして扱われるという特殊な挙動を示します。このコミットは、その特殊な挙動下でのパフォーマンスが線形であることを保証するためのものです。

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

このコミットは、Go言語の標準ライブラリにおけるマップ（map）のテストに関する修正です。具体的には、NaN（Not a Number）をキーとして使用した場合のマップのパフォーマンス特性をテストする際に発生していた、不安定な（flaky）ビルドエラーを解消することを目的としています。テストの測定方法を改善し、より信頼性の高い結果を得られるように変更されています。

コミット

  • コミットハッシュ: 5e21cb786589d28ad6b31ec9e43f8bf73ff93a82
  • Author: Brad Fitzpatrick bradfitz@golang.org
  • Date: Sun Apr 7 11:56:15 2013 -0700

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

https://github.com/golang/go/commit/5e21cb786589d28ad6b31ec9e43f8bf73ff93a82

元コミット内容

test: fix flaky NaN-key map complexity test

Don't measure wall time in map.go. Keep it portable
and only test NaN, but not time.

Move time tests to mapnan.go and only measure user CPU time,
not wall time. It builds on Darwin and Linux, the primary
platforms where people hack on the runtime & in particular
maps. The runtime is shared, though, so we don't need it to
run on all of the platforms.

Fixes flaky build failures like:
http://build.golang.org/log/ba67eceefdeaa1142cb6c990a62fa3ffd8fd73f8

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

変更の背景

このコミットの主な背景は、Go言語のビルドシステムで発生していた不安定なテスト失敗（flaky build failures）です。具体的には、test/map.go 内の testnan 関数が、NaN（Not a Number）をマップのキーとして挿入する際のパフォーマンスを測定していましたが、このテストが「ウォールタイム（wall time）」、つまり実時間を測定していたため、実行環境の負荷や他のプロセス、スケジューリングの影響を受けやすく、結果が不安定になっていました。

Go言語のマップは、キーのハッシュ値に基づいて要素を格納します。浮動小数点数における NaN は、比較演算において NaN == NaN が false となる特殊な性質を持っています。このため、マップに複数の NaN をキーとして挿入した場合、それらが異なるエントリとして扱われる可能性があり、その際のパフォーマンスが線形（linear）であることを確認するテストが必要でした。しかし、ウォールタイムでの測定は、テストの再現性を損ない、ビルドの信頼性を低下させていました。

この不安定なテストは、Goの継続的インテグレーション（CI）システムにおいて、http://build.golang.org/log/ba67eceefdeaa1142cb6c990a62fa3ffd8fd73f8 のようなビルド失敗を引き起こしていました。開発者は、このような不安定なテストを修正し、CIの信頼性を向上させる必要がありました。

前提知識の解説

1. NaN (Not a Number)

NaN は、IEEE 754 浮動小数点数標準で定義されている特殊な数値表現です。これは、0による除算、無限大同士の減算、負の数の平方根など、数学的に未定義または表現不可能な演算の結果として生成されます。NaN の最も重要な特性は、いかなる値とも等しくないという点です。これには NaN 自身も含まれます。つまり、NaN == NaN は常に false と評価されます。

Go言語の math パッケージには math.NaN() 関数があり、NaN 値を返します。また、math.IsNaN() 関数を使って、ある値が NaN であるかどうかを判定できます。

2. Go言語のマップ (map) と NaN

Go言語のマップは、キーと値のペアを格納するハッシュテーブルの実装です。キーはハッシュ可能である必要があり、Goの組み込み型（数値、文字列、ポインタ、構造体など）の多くはハッシュ可能です。float64 や float32 もマップのキーとして使用できます。

NaN をマップのキーとして使用した場合、Goのマップは以下のような挙動を示します。

  • NaN はマップのキーとして有効です。 Goのマップは、NaN をキーとして受け入れます。
  • 複数の NaN は異なるキーとして扱われます。 NaN == NaN が false であるという特性のため、Goのマップに math.NaN() をキーとして複数回挿入すると、たとえ同じ math.NaN() の呼び出しであっても、それらは異なるエントリとして扱われ、マップのサイズは挿入回数分だけ増大します。これは、マップがキーの等価性を判断する際に、== 演算子とは異なる内部的なメカニズムを使用しているためです。
  • この挙動により、マップに大量の NaN をキーとして挿入した場合に、マップの内部構造が肥大化し、検索や挿入のパフォーマンスが線形ではなく二次曲線的に悪化する「二次曲線的な複雑さ（quadratic complexity）」の問題が発生する可能性があります。このコミットのテストは、この問題が発生しないことを確認するためのものです。

3. ウォールタイム (Wall Time) と ユーザーCPU時間 (User CPU Time)

  • ウォールタイム (Wall Time): 「実時間」または「経過時間」とも呼ばれ、プログラムの開始から終了までに実際に経過した時間です。これは、CPUの実行時間だけでなく、I/O待ち、他のプロセスの実行、オペレーティングシステムによるスケジューリング、ネットワーク遅延など、プログラムがブロックされている時間もすべて含みます。ウォールタイムは、システム全体の負荷や外部要因に大きく左右されるため、パフォーマンス測定の再現性が低い場合があります。

  • ユーザーCPU時間 (User CPU Time): プログラムがユーザーモードでCPUを実行した合計時間です。これは、プログラム自身のコードがCPU上で実行された純粋な時間を示します。システムコール（カーネルモードでの処理）の時間は含まれません。ユーザーCPU時間は、ウォールタイムに比べて外部要因の影響を受けにくく、プログラム自身の計算負荷をより正確に反映するため、パフォーマンスベンチマークやアルゴリズムの計算量評価に適しています。

4. syscall.Getrusage

syscall.Getrusage は、Unix系システムコールの一つで、現在のプロセスまたはその子プロセスのリソース使用状況（CPU時間、メモリ使用量、I/O操作など）を取得するために使用されます。Go言語の syscall パッケージを通じてこの関数を呼び出すことで、ユーザーCPU時間やシステムCPU時間などの詳細な情報を取得できます。

このコミットでは、syscall.Getrusage を使用してユーザーCPU時間を測定することで、ウォールタイムの不安定さを回避し、より正確で再現性の高いパフォーマンス測定を実現しています。

技術的詳細

このコミットの技術的な核心は、NaN キーを持つマップのパフォーマンス測定方法の変更と、テストコードの分離です。

  1. test/map.go から時間測定ロジックの削除:

    • 元の test/map.go の testnan 関数は、time.Now() と time.Since() を使用してウォールタイムを測定していました。
    • このコミットでは、test/map.go から time パッケージのインポートと、ウォールタイムを測定する t 関数（func(n int) time.Duration）が完全に削除されました。
    • testnan 関数は、単に n 個の NaN をマップに挿入し、マップのサイズが n であること、およびマップをイテレートした際にキーが NaN であり値が正しいことを確認する、基本的な機能テストに簡素化されました。これにより、test/map.go はプラットフォームに依存しない、純粋な機能テストとして維持されます。

  2. test/mapnan.go の新規作成とユーザーCPU時間測定への移行:

    • NaN キーを持つマップのパフォーマンス（線形性）を時間的に測定するロジックは、新しく作成された test/mapnan.go ファイルに移動されました。
    • この新しいファイルは、ビルドタグ // +build darwin,linux を持っています。これは、このテストがDarwin（macOS）とLinuxプラットフォームでのみビルドおよび実行されることを意味します。コミットメッセージにあるように、これらのプラットフォームはGoランタイム、特にマップの開発が主に行われる場所であり、すべてのプラットフォームで実行する必要はないという判断です。
    • test/mapnan.go 内の t 関数は、syscall.Getrusage を使用してユーザーCPU時間を測定するように変更されました。具体的には、マップ操作の前後で syscall.Getrusage(0, &u0) と syscall.Getrusage(0, &u1) を呼び出し、u1.Utime.Nano() - u0.Utime.Nano() によってユーザーCPU時間のナノ秒単位の差分を計算しています。
    • このテストは、n 個の NaN を挿入した場合のユーザーCPU時間 t1 と、2n 個の NaN を挿入した場合のユーザーCPU時間 t2 を比較し、t2 が 3 * t1 未満であることを確認します。これは、挿入操作の複雑さが線形（2倍のデータで2倍の時間）であることを許容範囲（最大3倍）で検証するものです。
    • テストが失敗した場合（つまり、パフォーマンスが線形ではない場合）、n の値を増やして再試行するロジックも含まれています。これは、測定の粒度が不十分な場合に、より長い実行時間で正確な測定を試みるためです。

この変更により、NaN キーを持つマップのパフォーマンステストは、ウォールタイムの変動に左右されなくなり、より安定したビルド結果をもたらすようになりました。また、プラットフォーム固有のパフォーマンス測定ロジックを分離することで、コードベース全体のポータビリティが向上しています。

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

test/map.go の変更

--- a/test/map.go
+++ b/test/map.go
@@ -5,6 +5,7 @@
 // license that can be found in the LICENSE file.
 
 // Test maps, almost exhaustively.
+// NaN complexity test is in mapnan.go.
 
 package main
 
@@ -12,7 +13,6 @@ import (
 	"fmt"
 	"math"
 	"strconv"
-	"time"
 )
 
 const count = 100
@@ -659,39 +659,26 @@ func testfloat() {
 }
 
 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 := 500
+	m := map[float64]int{}
+	nan := math.NaN()
+	for i := 0; i < n; i++ {
+		m[nan] = 1
 	}
-
-	// Depending on the machine and OS, this test might be too fast
-	// to measure with accurate enough granularity. On failure,
-	// make it run longer, hoping that the timing granularity
-	// is eventually sufficient.\n-\n-\tn := 30000 // 0.02 seconds on a MacBook Air
-	fails := 0
-	for {
-		t1 := t(n)
-		t2 := t(2 * n)
-		// should be 2x (linear); allow up to 3x
-		if t2 < 3*t1 {
-			return
-		}
-		fails++
-		if fails == 4 {
-			panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2))
-			return
-		}
-		n *= 2
+	if len(m) != n {
+		panic("wrong size map after nan insertion")
+	}
+	iters := 0
+	for k, v := range m {
+		iters++
+		if !math.IsNaN(k) {
+			panic("not NaN")
+		}
+		if v != 1 {
+			panic("wrong value")
+		}
+	}
+	if iters != n {
+		panic("wrong number of nan range iters")
 	}
 }

test/mapnan.go の新規追加

--- /dev/null
+++ b/test/mapnan.go
@@ -0,0 +1,64 @@
+// +build darwin,linux
+// run
+
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Test that NaNs in maps don't go quadratic.
+
+package main
+
+import (
+	"fmt"
+	"math"
+	"time"
+	"syscall"
+)
+
+func main() {
+
+	// Test that NaNs in maps don't go quadratic.
+	t := func(n int) time.Duration {
+		var u0 syscall.Rusage
+		if err := syscall.Getrusage(0,  &u0); err != nil {
+			panic(err)
+		}
+		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")
+		}
+		var u1 syscall.Rusage
+		if err := syscall.Getrusage(0,  &u1); err != nil {
+			panic(err)
+		}
+		return time.Duration(u1.Utime.Nano() - u0.Utime.Nano())
+	}
+
+	// Depending on the machine and OS, this test might be too fast
+	// to measure with accurate enough granularity. On failure,
+	// make it run longer, hoping that the timing granularity
+	// is eventually sufficient.
+
+	n := 30000 // ~8ms user time on a Mid 2011 MacBook Air (1.8 GHz Core i7)
+	fails := 0
+	for {
+		t1 := t(n)
+		t2 := t(2 * n)
+		// should be 2x (linear); allow up to 3x
+		if t2 < 3*t1 {
+			return
+		}
+		fails++
+		if fails == 6 {
+			panic(fmt.Sprintf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2))
+		}
+		if fails < 4 {
+			n *= 2
+		}
+	}
+}

コアとなるコードの解説

test/map.go の testnan 関数

変更後の testnan 関数は、時間測定のロジックが削除され、NaN をキーとしてマップに挿入した際の基本的な動作確認に特化しています。

  1. n := 500: テストに使用する NaN の挿入回数を 500 に設定しています。
  2. m := map[float64]int{}: float64 をキー、int を値とするマップを初期化します。
  3. nan := math.NaN(): NaN 値を生成します。
  4. for i := 0; i < n; i++ { m[nan] = 1 }: n 回ループし、毎回同じ NaN 値をキーとしてマップに挿入します。Goのマップは、NaN をキーとして使用した場合でも、それらが異なるエントリとして扱われるため、このループの終了後、マップの len(m) は n になります。
  5. if len(m) != n { panic("wrong size map after nan insertion") }: マップの要素数が n と等しいことを確認します。これは、n 個の異なる NaN がマップに挿入されたことを期待していることを示唆しています。
  6. for k, v := range m { ... }: マップをイテレートし、各キー k が NaN であること、および値 v が 1 であることを確認します。これにより、挿入されたデータが正しく保持されていることを検証します。
  7. if iters != n { panic("wrong number of nan range iters") }: イテレーション回数が n と等しいことを確認します。

この簡素化された testnan 関数は、NaN の基本的なマップ動作を検証し、時間測定の複雑さを排除することで、よりポータブルで安定したテストを実現しています。

test/mapnan.go の main 関数

新しく追加された test/mapnan.go は、NaN キーを持つマップのパフォーマンス特性を、より厳密に時間測定する役割を担います。

  1. // +build darwin,linux: この行はビルドタグです。Goのビルドシステムは、このタグがあるファイルが darwin または linux 環境でのみコンパイルされるようにします。これにより、syscall.Getrusage のようなプラットフォーム固有のAPIを使用するコードが、サポートされていない環境でコンパイルエラーになるのを防ぎます。
  2. t := func(n int) time.Duration { ... }: この匿名関数 t は、n 個の NaN をマップに挿入する操作にかかるユーザーCPU時間を測定します。
    • var u0 syscall.Rusage: syscall.Rusage 構造体を宣言し、操作前のリソース使用状況を格納します。
    • syscall.Getrusage(0, &u0): 現在のプロセスのリソース使用状況を取得します。
    • マップへの NaN 挿入ロジックは test/map.go と同様です。
    • var u1 syscall.Rusage: 操作後のリソース使用状況を格納します。
    • syscall.Getrusage(0, &u1): 操作後のリソース使用状況を再度取得します。
    • return time.Duration(u1.Utime.Nano() - u0.Utime.Nano()): u1.Utime と u0.Utime は syscall.Timeval 型で、秒とマイクロ秒のフィールドを持ちます。.Nano() メソッドはこれをナノ秒に変換します。この差分がユーザーCPU時間です。
  3. n := 30000: 初期挿入回数を 30000 に設定しています。これは、測定の粒度を確保するために十分な時間かかるように調整された値です。
  4. for { ... }: 無限ループでテストを繰り返します。
    • t1 := t(n): n 個の挿入にかかるユーザーCPU時間を測定します。
    • t2 := t(2 * n): 2n 個の挿入にかかるユーザーCPU時間を測定します。
    • if t2 < 3*t1 { return }: パフォーマンスが線形であることを検証します。2n 個の挿入にかかる時間が n 個の挿入にかかる時間の3倍未満であれば、テストは成功とみなされ、関数を終了します。これは、厳密な2倍ではなく、ある程度の許容範囲を持たせています。
    • fails++: 失敗回数をカウントします。
    • if fails == 6 { panic(...) }: 失敗回数が6回に達した場合、テストは「遅すぎる」と判断し、パニック（エラー）を発生させます。
    • if fails < 4 { n *= 2 }: 失敗回数が4回未満の場合、n の値を2倍にして、より長い実行時間で再試行します。これは、測定の粒度が不十分で、正確な時間差を捉えられない場合に、テストをより長く実行させることで解決を試みるためのロジックです。

この mapnan.go のテストは、NaN キーを持つマップのパフォーマンスが、挿入される要素数に対して線形であることを、ユーザーCPU時間という安定した指標を用いて厳密に検証しています。これにより、Goのマップ実装が NaN を効率的に処理していることを保証し、CIの不安定性を解消しています。

関連リンク

参考にした情報源リンク