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

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

このコミットは、Go言語のランタイムパッケージ内のベンチマークテストファイルである src/pkg/runtime/mapspeed_test.go に変更を加えています。このファイルは、Goのマップ（map）のパフォーマンス特性を測定するためのベンチマークテストを定義しており、特にマップのルックアップ（キー検索）操作の速度を評価することを目的としています。

コミット

commit ecdcec1df2c06754ab39fb8d8154a7977fbd11f6
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Fri Mar 29 13:50:44 2013 -0700

    runtime: additional map benchmarks for repeated lookups
    
    For the future.
    
    Update #5147
    
    R=khr, r
    CC=golang-dev
    https://golang.org/cl/8165044

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

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

元コミット内容

runtime: additional map benchmarks for repeated lookups

For the future.

Update #5147

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

変更の背景

このコミットは、Goのマップにおける「繰り返しルックアップ（repeated lookups）」のパフォーマンスを測定するための追加ベンチマークを導入しています。コミットメッセージにある Update #5147 は、GitHub Issue #5147 に関連していることを示唆しています。Web検索の結果、Issue #5147 は「runtime: consider caching previous map hash value」（ランタイム: 以前のマップハッシュ値のキャッシュを検討する）というタイトルであることが判明しました。

この背景には、Goのマップの実装において、同じキーが繰り返し検索される場合に、そのキーのハッシュ値を再計算するオーバーヘッドを削減できる可能性を探るという目的があったと考えられます。ハッシュ値をキャッシュすることで、特に頻繁にアクセスされるキーに対するマップルックアップのパフォーマンスを向上させることが期待されます。このコミットで追加されたベンチマークは、このような最適化が実際にどの程度の効果をもたらすかを評価するための基礎データを提供するために作成されました。

前提知識の解説

Goのマップ (map)

Go言語の map は、キーと値のペアを格納するための組み込みデータ構造です。他の言語ではハッシュマップ、ハッシュテーブル、連想配列、辞書などと呼ばれるものに相当します。Goのマップは内部的にハッシュテーブルとして実装されており、キーのハッシュ値を使って値を効率的に検索、挿入、削除します。

  • ハッシュ関数: キーを数値（ハッシュ値）に変換する関数です。異なるキーが同じハッシュ値になること（ハッシュ衝突）もありますが、良いハッシュ関数は衝突を最小限に抑えます。
  • バケット: ハッシュテーブルの内部構造で、ハッシュ値に基づいてキーと値のペアが格納される場所です。ハッシュ衝突が発生した場合、同じバケット内に複数のキーと値のペアが格納されることがあります。
  • ルックアップ: マップから特定のキーに対応する値を取得する操作です。この操作では、まずキーのハッシュ値を計算し、そのハッシュ値に基づいて適切なバケットを見つけ、そのバケット内でキーを検索します。

Goの testing パッケージとベンチマーク

Goの標準ライブラリには、ユニットテストとベンチマークテストをサポートする testing パッケージが含まれています。

  • ベンチマークテスト: コードのパフォーマンスを測定するために使用されます。関数名のプレフィックスは Benchmark で始まり、*testing.B 型の引数を取ります。
  • *testing.B: ベンチマークテストの実行を制御するための構造体です。
    • b.N: ベンチマーク関数が実行されるイテレーション回数を示します。testing パッケージは、ベンチマークが安定した結果を出すのに十分な回数だけ関数を実行するように b.N の値を自動的に調整します。
    • b.ResetTimer(): タイマーをリセットします。通常、ベンチマーク対象のコードのセットアップが完了した後、測定を開始する直前に呼び出されます。これにより、セットアップにかかる時間が測定結果に含まれないようにします。

ハッシュ値のキャッシュ

ハッシュテーブルのルックアップでは、キーのハッシュ値を計算するステップが常に必要です。特に文字列のような複雑なキーの場合、ハッシュ値の計算にはある程度のコストがかかります。もし同じキーが繰り返し検索される場合、その都度ハッシュ値を計算し直すのは非効率的です。

ハッシュ値のキャッシュとは、一度計算したキーのハッシュ値をメモリに保存しておき、次に同じキーが検索されたときにそのキャッシュされた値を利用することで、ハッシュ計算のオーバーヘッドを削減する最適化手法です。これにより、特にホットパス（頻繁に実行されるコードパス）でのパフォーマンス向上が期待できます。

技術的詳細

このコミットで追加されたベンチマークは、Goのマップにおける「繰り返しルックアップ」のシナリオをシミュレートし、そのパフォーマンスを測定することを目的としています。具体的には、以下の新しいベンチマーク関数が追加されています。

  1. benchmarkRepeatedLookup(b *testing.B, lookupKeySize int):

    • この関数は、実際のベンチマークロジックをカプセル化しています。
    • lookupKeySize 引数により、ルックアップに使用するキーのサイズを可変にしています。これにより、キーのサイズがハッシュ計算や比較のパフォーマンスに与える影響を評価できます。
    • マップ m には、少なくとも単一のバケットよりも多くのエントリ（64個）が事前に挿入されます。これは、マップが十分に「大きく」なり、現実的なシナリオをシミュレートするためです。
    • base 文字列は、指定された lookupKeySize に合わせてキーの長さを調整するために使用されます。
    • key1 と key2 という2つの異なるキーが定義されます。これらのキーは、ベンチマークループ内で繰り返しルックアップされます。
    • b.ResetTimer() が呼び出され、マップのセットアップにかかる時間が測定から除外されます。
    • ベンチマークループ for i := 0; i < b.N/4; i++ の中で、key1 と key2 がそれぞれ2回ずつ、合計4回のルックアップが連続して実行されます。b.N を4で割っているのは、ループ1回あたり4回のルックアップが行われるため、b.N 回のルックアップ全体で適切なイテレーション回数を確保するためです。これにより、b.N はルックアップの総回数として機能します。
    • _ = m[key] のように、ルックアップ結果を変数に代入していますが、その変数は使用していません。これは、ルックアップ操作自体にかかる時間を測定し、結果の使用による追加のオーバーヘッドを避けるためです。

  2. BenchmarkRepeatedLookupStrMapKey32(b *testing.B):

    • benchmarkRepeatedLookup を呼び出し、lookupKeySize を 32 に設定しています。これは、32バイトの文字列キーに対する繰り返しルックアップのパフォーマンスを測定します。

  3. BenchmarkRepeatedLookupStrMapKey1M(b *testing.B):

    • benchmarkRepeatedLookup を呼び出し、lookupKeySize を 1 << 20 (1メガバイト) に設定しています。これは、非常に長い文字列キー（1MB）に対する繰り返しルックアップのパフォーマンスを測定します。このような非常に長いキーは、ハッシュ計算のコストが顕著になる可能性があり、ハッシュ値のキャッシュが特に有効であるかを評価するのに役立ちます。

これらのベンチマークは、同じキーが連続してアクセスされるシナリオにおいて、Goのマップのルックアップ性能がどのように振る舞うかを詳細に分析するための重要なツールとなります。特に、キーのサイズがパフォーマンスに与える影響や、将来的なハッシュ値キャッシュ最適化の有効性を評価する上で役立ちます。

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

diff --git a/src/pkg/runtime/mapspeed_test.go b/src/pkg/runtime/mapspeed_test.go
index a379740606..4d77347b24 100644
--- a/src/pkg/runtime/mapspeed_test.go
+++ b/src/pkg/runtime/mapspeed_test.go
@@ -138,6 +138,7 @@ func BenchmarkSmallStrMap(b *testing.B) {
 		_, _ = m[key]
 	}\n
 }\n+\n
 func BenchmarkIntMap(b *testing.B) {
 	m := make(map[int]bool)
 	for i := 0; i < 8; i++ {
@@ -148,3 +149,25 @@ func BenchmarkIntMap(b *testing.B) {
 		_, _ = m[7]
 	}\n
 }\n+\n+// Accessing the same keys in a row.\n+func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {\n+\tm := make(map[string]bool)\n+\t// At least bigger than a single bucket:\n+\tfor i := 0; i < 64; i++ {\n+\t\tm[fmt.Sprintf(\"some key %d\", i)] = true\n+\t}\n+\tbase := strings.Repeat(\"x\", lookupKeySize-1)\n+\tkey1 := base + \"1\"\n+\tkey2 := base + \"2\"\n+\tb.ResetTimer()\n+\tfor i := 0; i < b.N/4; i++ {\n+\t\t_ = m[key1]\n+\t\t_ = m[key1]\n+\t\t_ = m[key2]\n+\t\t_ = m[key2]\n+\t}\n+}\n+\n+func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }\n+func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }\n```

## コアとなるコードの解説

追加されたコードは、`mapspeed_test.go` ファイルの既存のベンチマーク関数の後に追加されています。

### `benchmarkRepeatedLookup` 関数

```go
// Accessing the same keys in a row.
func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
	m := make(map[string]bool)
	// At least bigger than a single bucket:
	for i := 0; i < 64; i++ {
		m[fmt.Sprintf("some key %d", i)] = true
	}
	base := strings.Repeat("x", lookupKeySize-1)
	key1 := base + "1"
	key2 := base + "2"
	b.ResetTimer()
	for i := 0; i < b.N/4; i++ {
		_ = m[key1]
		_ = m[key1]
		_ = m[key2]
		_ = m[key2]
	}
}
  • // Accessing the same keys in a row.: このコメントは、このベンチマークの目的が「同じキーを連続してアクセスする」シナリオを測定することであることを明確に示しています。
  • m := make(map[string]bool): 文字列をキー、ブール値を値とするマップを作成します。
  • for i := 0; i < 64; i++ { m[fmt.Sprintf("some key %d", i)] = true }: マップに64個の異なるエントリを挿入します。これは、マップが単一のバケットに収まらないようにし、より現実的なハッシュテーブルの動作をシミュレートするためです。
  • base := strings.Repeat("x", lookupKeySize-1): lookupKeySize で指定された長さのキーを作成するためのベース文字列を生成します。例えば lookupKeySize が32なら、base は31個の 'x' からなる文字列になります。
  • key1 := base + "1" と key2 := base + "2": base 文字列に "1" または "2" を追加することで、指定された長さの2つの異なるキー key1 と key2 を作成します。これらのキーは、ベンチマークループ内で繰り返しルックアップされます。
  • b.ResetTimer(): ここでタイマーをリセットし、マップの初期化とキーの生成にかかる時間をベンチマークの測定から除外します。
  • for i := 0; i < b.N/4; i++ { ... }: ベンチマークのメインループです。b.N は testing パッケージによって自動的に調整されるイテレーション回数です。ループ内で key1 を2回、key2 を2回、合計4回のマップルックアップを実行するため、b.N を4で割ることで、b.N 回のルックアップ全体で適切なループ回数を確保しています。
  • _ = m[key1]: マップからキーをルックアップする操作です。結果を変数に代入していますが、その変数は使用していません。これは、ルックアップ操作自体のパフォーマンスのみを測定し、結果の利用による副作用を排除するためです。

BenchmarkRepeatedLookupStrMapKey32 と BenchmarkRepeatedLookupStrMapKey1M 関数

func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }

これらの関数は、benchmarkRepeatedLookup ヘルパー関数を呼び出すことで、特定のキーサイズでの繰り返しルックアップベンチマークを実行します。

  • BenchmarkRepeatedLookupStrMapKey32: キーサイズを32バイトに設定してベンチマークを実行します。
  • BenchmarkRepeatedLookupStrMapKey1M: キーサイズを1メガバイト（1 << 20）に設定してベンチマークを実行します。これにより、非常に長い文字列キーに対するマップルックアップのパフォーマンスを評価できます。

これらのベンチマークは、Goのマップの内部実装、特にハッシュ計算とキー比較の効率性に関する洞察を提供し、将来的なパフォーマンス最適化の方向性を決定するのに役立ちます。

関連リンク

  • GitHub Issue #5147: https://github.com/golang/go/issues/5147 (Web検索結果より、このIssueは「runtime: consider caching previous map hash value」に関するものであることが示唆されていますが、直接的なリンクは提供されていませんでした。しかし、コミットメッセージの Update #5147 から関連性が推測されます。)
  • Go Change List 8165044: https://golang.org/cl/8165044

参考にした情報源リンク