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

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

このコミットは、Go言語のテストスイート内にあるmapのパフォーマンス測定に関するテストの堅牢性を向上させるものです。特に、実行環境（マシンやOS）のタイミング粒度によってテストが不安定になる問題を解決するために、テストの実行ロジックが改善されました。

コミット

commit 69a5b23dc58a589f491e5524d3e32019a5de69b5
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Feb 2 11:49:28 2012 -0800

    test: make map nan timing test more robust

    take 2

    R=rsc
    CC=golang-dev
    https://golang.org/cl/5617045

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

https://github.com/golang/go/commit/69a5b23dc58a589f491e5524d3e32019a5de69b5

元コミット内容

test: make map nan timing test more robust

take 2

R=rsc
CC=golang-dev
https://golang.org/cl/5617045

変更の背景

この変更の背景には、Go言語のmap（ハッシュマップ）のパフォーマンスを測定するテストが、特定の環境下で不安定（flaky）になるという問題がありました。特に、テストが実行されるマシンやOSのタイマーの精度（タイミング粒度）が十分でない場合、短い時間で完了する操作の測定結果が不正確になり、テストが誤って失敗する可能性がありました。

元のテストでは、n個の要素をmapに挿入する時間t1と、2*n個の要素を挿入する時間t2を比較し、t2がt1の約2倍（線形性）であることを期待していました。しかし、測定時間が非常に短い場合、システムが提供する最小の時間単位（例えばミリ秒やマイクロ秒）よりも短い時間で処理が完了してしまうと、正確な比率を測定できず、テストが失敗することがありました。

このコミットは、このようなタイミングの不正確さに起因するテストの不安定性を解消し、より堅牢で信頼性の高いパフォーマンス測定を可能にすることを目的としています。コミットメッセージにある「take 2」は、この問題に対する以前の試みがあったことを示唆しており、今回の変更がその改善版であることを意味します。

前提知識の解説

Go言語のmap

Go言語のmapは、キーと値のペアを格納するための組み込みのデータ構造です。他の言語のハッシュマップ、ディクショナリ、連想配列に相当します。mapは内部的にハッシュテーブルとして実装されており、キーのハッシュ値に基づいて値を効率的に検索、挿入、削除できます。そのパフォーマンスは、ハッシュ関数の品質、衝突解決戦略、およびメモリ割り当ての効率に大きく依存します。

time.Sinceとパフォーマンス測定

Go言語では、timeパッケージを使用して時間の測定を行います。time.Since(t)関数は、指定された時刻tから現在までの経過時間をtime.Duration型で返します。パフォーマンス測定では、操作の開始時刻を記録し、操作完了後にtime.Sinceを使って経過時間を計算するのが一般的です。

しかし、コンピュータシステムにおける時間の測定には、いくつかの課題があります。

  • タイミング粒度（Granularity）: OSやハードウェアが提供するタイマーの最小分解能です。例えば、タイマーがミリ秒単位でしか更新されない場合、ミリ秒未満の操作は正確に測定できません。
  • システム負荷: バックグラウンドで実行されている他のプロセスやOSのスケジューリングによって、測定対象の操作の実行時間が変動することがあります。
  • JITコンパイル/最適化: 実行時にコードが最適化される（JITコンパイルなど）場合、初回実行と2回目以降の実行でパフォーマンスが大きく異なることがあります。
  • キャッシュ: CPUキャッシュやメモリキャッシュの状態によって、アクセス速度が変動します。

これらの要因により、特に非常に短い時間の操作を測定する場合、結果が不安定になり「flaky test」（不安定なテスト）となることがあります。

堅牢なテストの設計

パフォーマンス測定を含むテストを堅牢にするためには、以下のようなアプローチが考えられます。

  • 十分な繰り返し回数: 測定対象の操作を何度も繰り返し実行し、平均値や中央値を取ることで、一時的なノイズの影響を軽減します。
  • ウォームアップ期間: JITコンパイルやキャッシュのウォームアップのために、測定前に数回操作を実行します。
  • 統計的分析: 測定結果のばらつきを許容範囲内に収めるために、統計的な手法（標準偏差など）を用いて分析します。
  • 動的な調整: 実行環境の特性に合わせて、テストのパラメータ（繰り返し回数など）を動的に調整する。今回のコミットはこのアプローチに該当します。

技術的詳細

このコミットは、test/map.go内のtestnan()関数におけるmapの挿入タイミングテストを改善しています。元のコードでは、固定のn値（60000）で2回の測定を行い、その比率をチェックしていました。しかし、この固定値では、タイミング粒度が粗い環境でテストが不安定になる問題がありました。

新しい実装では、この問題を解決するために、テストの実行回数を動的に調整するループが導入されています。

  1. 初期のn値: nの初期値が60000から30000に減らされています。これは、テストが速すぎる場合に、より短い時間から開始して徐々にnを増やしていく戦略のためです。
  2. リトライメカニズム: forループが導入され、テストが期待する線形性（t2 < 3*t1）を満たさない場合にリトライするようになりました。
  3. failsカウンター: failsという変数が導入され、テストが期待する条件を満たさなかった回数をカウントします。
  4. nの倍増: テストが失敗するたびに、nの値が2倍になります（n *= 2）。これにより、mapへの挿入回数が増え、測定される時間も長くなります。測定時間が長くなることで、タイミング粒度の影響を受けにくくなり、より正確な測定が可能になります。
  5. 最大リトライ回数: failsが4に達すると、テストは最終的に失敗と判断され、エラーメッセージを出力して終了します。これは、無限ループを防ぎ、テストがいつまでも終わらない状況を避けるための安全策です。

この変更により、テストは「もし測定が速すぎて精度が足りないなら、もっと長い時間測定するように試行回数を増やそう」というロジックを持つことになります。これにより、様々な実行環境において、より安定してmapのパフォーマンス特性を検証できるようになりました。

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

--- a/test/map.go
+++ b/test/map.go
@@ -667,10 +667,25 @@ func testnan() {
 		return time.Since(t0)
 	}

-	n := 60000 // 0.04 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)
+	// 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 // 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 {
+			fmt.Printf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2)
+			return
+		}
+		n *= 2
 	}
 }

コアとなるコードの解説

変更されたtestnan()関数内の主要なロジックは以下の通りです。

	// 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 // 0.02 seconds on a MacBook Air
	fails := 0

nはmapに挿入する要素の初期数です。以前の60000から30000に減らされています。failsは、テストが期待する条件を満たさなかった回数を記録するためのカウンターです。

	for {

無限ループを開始します。このループは、テストが成功するか、最大リトライ回数に達するまで繰り返されます。

		t1 := t(n)
		t2 := t(2 * n)

t(n)関数を呼び出して、n個の要素をmapに挿入するのにかかる時間t1と、2*n個の要素を挿入するのにかかる時間t2を測定します。t(n)関数は、内部でmake(map[int]int, n)でmapを作成し、n回ループしてmap[i] = iのように要素を挿入し、その経過時間を返します。

		// should be 2x (linear); allow up to 3x
		if t2 < 3*t1 {
			return
		}

これがテストの主要なアサーションです。2*n個の挿入にかかる時間t2が、n個の挿入にかかる時間t1の3倍未満であれば、テストは成功とみなされ、関数を終了します。mapの挿入操作は要素数に対してほぼ線形に増加するため、t2はt1の約2倍になることが期待されます。3*t1という許容範囲は、ある程度のばらつきを許容するためのものです。

		fails++
		if fails == 4 {
			fmt.Printf("too slow: %d inserts: %v; %d inserts: %v\n", n, t1, 2*n, t2)
			return
		}

もしt2 < 3*t1の条件が満たされなかった場合（つまり、テストが期待通りに線形性を示さなかった場合）、failsカウンターをインクリメントします。failsが4に達した場合、それはテストが複数回リトライしても成功しなかったことを意味するため、エラーメッセージを出力して関数を終了します。これは、テストが無限にリトライし続けるのを防ぐためのものです。

		n *= 2

テストが失敗した場合、nの値を2倍にします。これにより、次のループではより多くの要素が挿入され、測定時間が長くなります。測定時間が長くなることで、システムタイマーの粒度の影響を受けにくくなり、より正確な比率を測定できる可能性が高まります。

このロジックにより、testnan()関数は、実行環境のタイミング精度に依存せず、mapのパフォーマンス特性をより堅牢に検証できるようになりました。

関連リンク

参考にした情報源リンク

  • Go言語のmapに関する公式ドキュメントやブログ記事
  • Go言語のベンチマークテストに関する一般的なプラクティスや課題についての記事
  • システムにおけるタイミング測定の精度に関する一般的な情報