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

このコミットは、Go言語のランタイムにおけるマップ（map型）のテストとベンチマークを強化するものです。具体的には、文字列キーを持つマップの挙動、特にハッシュ衝突が発生しやすい「シングルバケット」のシナリオや、キーの長さがパフォーマンスに与える影響を検証するための新しいテストケースとベンチマークが追加されています。また、既存のベンチマーク関数が適切なベンチマークファイルに移動され、テストとベンチマークの役割分担が明確化されています。

コミット

• コミットハッシュ: 3b09ac57ac473657e9f827d49689a20958bf6015
• 作者: Brad Fitzpatrick bradfitz@golang.org
• コミット日時: 2013年4月2日 火曜日 17:55:49 -0700

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

https://github.com/golang/go/commit/3b09ac57ac473657e9f827d49689a20958bf6015

元コミット内容

runtime: new map tests and benchmarks

Also, move an existing benchmark from map_test.go to
mapspeed_test.go.

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

変更の背景

Go言語のマップは、その内部実装がパフォーマンスに大きく影響するため、継続的な最適化と堅牢性の確保が重要です。このコミットは、特に文字列キーを持つマップの挙動、中でもハッシュ衝突が発生しやすい特定のシナリオ（「シングルバケット」）や、キーの長さがパフォーマンスに与える影響について、より詳細なテストとベンチマークを行うことを目的としています。

Goのマップはハッシュテーブルとして実装されており、キーのハッシュ値に基づいて要素が格納されます。ハッシュ衝突は避けられない現象であり、Goのランタイムはこれを効率的に処理する必要があります。特に、異なるキーが同じハッシュ値を持つ、あるいは同じバケットに割り当てられるようなケース（シングルバケット）は、マップの性能劣化を引き起こす可能性があります。このコミットは、このようなエッジケースにおけるマップの正確性とパフォーマンスを検証するためのものです。

また、既存のベンチマーク関数がmap_test.goからmapspeed_test.goへ移動されたのは、テストとベンチマークの目的を明確に分離するためです。_test.goファイルは通常、機能的な正しさを検証するテストを含み、_speed_test.goや_bench_test.goのようなファイルはパフォーマンス測定のためのベンチマークを含むという慣習があります。これにより、コードベースの整理と可読性が向上します。

前提知識の解説

Go言語のmap型

Go言語のmapは、キーと値のペアを格納する組み込みのデータ構造であり、他の言語におけるハッシュマップ、ハッシュテーブル、辞書に相当します。mapは内部的にハッシュテーブルとして実装されており、キーのハッシュ値に基づいて値が格納・検索されます。これにより、平均的にはO(1)の高速なアクセスが可能です。

Goのtestingパッケージ

Goの標準ライブラリには、テストとベンチマークを記述するためのtestingパッケージが用意されています。

• テスト関数: func TestXxx(*testing.T)という形式で記述され、コードの機能的な正しさを検証します。*testing.T型の引数を通じて、テストの失敗を報告したり、ログを出力したりできます。
• ベンチマーク関数: func BenchmarkXxx(*testing.B)という形式で記述され、コードのパフォーマンスを測定します。*testing.B型の引数を通じて、ベンチマークの実行回数（b.N）を制御したり、メモリ割り当てを報告（b.ReportAllocs()）したりできます。ベンチマークは通常、go test -bench=.コマンドで実行されます。

Goのruntimeパッケージ

runtimeパッケージは、Goプログラムのランタイムシステムと対話するための機能を提供します。これには、ガベージコレクション、ゴルーチンのスケジューリング、そしてマップやチャネルといった組み込み型の低レベルな実装の詳細が含まれます。このコミットがsrc/pkg/runtimeディレクトリ下のファイルに影響を与えているのは、マップの内部実装のテストとベンチマークを行っているためです。

ハッシュマップの内部構造とハッシュ衝突

ハッシュマップは、キーをハッシュ関数に通して得られるハッシュ値を使って、データを格納するメモリ上の位置（バケット）を決定します。理想的には、異なるキーは異なるハッシュ値を持ち、異なるバケットに格納されますが、実際には異なるキーが同じハッシュ値を持つこと（ハッシュ衝突）があります。

ハッシュ衝突が発生した場合、ハッシュマップは衝突解決メカニズム（例: チェイニング、オープンアドレス法）を用いて、同じバケット内の複数の要素を管理します。Goのマップはチェイニングに似た方法で衝突を解決します。

「シングルバケット」とは、複数のキーがハッシュ衝突を起こし、結果として同じ単一のバケットに割り当てられる状況を指します。このような状況では、そのバケット内の要素を線形に探索する必要が生じるため、マップのルックアップ性能がO(1)からO(N)に劣化する可能性があります。このコミットで追加されたテストは、特にこのようなシングルバケットのシナリオにおけるマップの挙動を検証しています。

技術的詳細

このコミットは、Goのマップ実装の堅牢性とパフォーマンスを向上させるために、以下の主要な変更を導入しています。

src/pkg/runtime/map_test.goの変更

1. stringsパッケージのインポート追加: 新しいテストで文字列操作が必要になったため。
2. BenchmarkNewEmptyMapの削除: このベンチマークはmapspeed_test.goに移動されました。
3. TestSingleBucketMapStringKeys_DupLen関数の追加:
   • このテストは、文字列キーを持つマップが「シングルバケット」の状況でどのように動作するかを検証します。
   • 特に、キーの長さが同じである文字列（例: "foo"と"bar"）と、異なる長さの文字列（例: "x", "xx", "xxxx"）を組み合わせて使用しています。さらに、非常に長い文字列キーも含まれています。
   • Goのマップ実装は、キーの長さや内容に基づいてハッシュ値を計算し、バケットを決定します。キーの長さが同じである場合、ハッシュ衝突の可能性が高まることがあります。このテストは、そのような状況下でもマップのルックアップが正しく行われることを保証します。
4. TestSingleBucketMapStringKeys_NoDupLen関数の追加:
   • こちらもシングルバケットの状況をテストしますが、すべてのキーが異なる長さを持つように設計されています。
   • キーの長さが異なることで、ハッシュ衝突のパターンが変わり、マップの内部的なハッシュ計算やバケット割り当てのロジックが異なる挙動を示す可能性があります。このテストは、そのようなケースでもマップが正しく機能することを確認します。
5. testMapLookupsヘルパー関数の追加:
   • 上記の2つのテスト関数から共通のマップルックアップ検証ロジックを抽出し、再利用可能なヘルパー関数として定義されました。これにより、テストコードの重複が減り、可読性と保守性が向上します。この関数は、与えられたマップのすべてのキーと値のペアについて、m[k] == vが成り立つことを確認します。

src/pkg/runtime/mapspeed_test.goの変更

1. BenchmarkMapStringKeysEight_*ベンチマーク群の追加:
   • BenchmarkMapStringKeysEight_16, _32, _64, _1Mといった複数のベンチマーク関数が追加されました。これらはすべてbenchmarkMapStringKeysEightヘルパー関数を呼び出します。
   • これらのベンチマークは、8つの文字列キーを持つマップでのルックアップ性能を測定します。
   • 特に注目すべきは、keySizeパラメータを通じてルックアップ対象のキーの長さを変えてテストしている点です。キーの長さは、ハッシュ計算のコストやメモリ使用量に影響を与えるため、マップのパフォーマンスに大きく関わります。このベンチマークは、異なるキー長におけるマップのルックアップ性能を評価し、潜在的なボトルネックや最適化の機会を特定するのに役立ちます。
2. benchmarkMapStringKeysEightヘルパー関数の追加:
   • この関数は、BenchmarkMapStringKeysEight_*ベンチマーク群の共通ロジックをカプセル化しています。
   • 8つの異なる長さの文字列キー（"K", "KK", ..., "KKKKKKKK"）を持つマップを作成し、指定されたkeySizeのキー（例: "K"を128回繰り返した文字列）に対するルックアップ性能を測定します。
3. BenchmarkNewEmptyMapの移動:
   • map_test.goからこのファイルに移動されました。これは、新しい空のマップを作成する際のメモリ割り当てとパフォーマンスを測定するベンチマークであり、機能テストではなく性能測定の範疇に属するため、適切なファイルに配置されました。

これらの変更は、Goのマップ実装が様々なシナリオ、特に文字列キーとハッシュ衝突の状況下で、期待通りに正確かつ効率的に動作することを保証するためのものです。

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

src/pkg/runtime/map_test.go

--- a/src/pkg/runtime/map_test.go
+++ b/src/pkg/runtime/map_test.go
@@ -10,6 +10,7 @@ import (
 	"os"
 	"runtime"
 	"sort"
+	"strings"
 	"sync"
 	"testing"
 )
@@ -317,9 +318,37 @@ func TestEmptyKeyAndValue(t *testing.T) {
 	}
 }
 
-func BenchmarkNewEmptyMap(b *testing.B) {
-	b.ReportAllocs()
-	for i := 0; i < b.N; i++ {
-		_ = make(map[int]int)
+// Tests a map with a single bucket, with same-lengthed short keys
+// ("quick keys") as well as long keys.
+func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
+	testMapLookups(t, map[string]string{
+		"x":    "x1val",
+		"xx":   "x2val",
+		"foo":  "fooval",
+		"bar":  "barval", // same key length as "foo"
+		"xxxx": "x4val",
+		strings.Repeat("x", 128): "longval1",
+		strings.Repeat("y", 128): "longval2",
+	})
+}
+
+// Tests a map with a single bucket, with all keys having different lengths.
+func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
+	testMapLookups(t, map[string]string{
+		"x":                      "x1val",
+		"xx":                     "x2val",
+		"foo":                    "fooval",
+		"xxxx":                   "x4val",
+		"xxxxx":                  "x5val",
+		"xxxxxx":                 "x6val",
+		strings.Repeat("x", 128): "longval",
+	})
+}
+
+func testMapLookups(t *testing.T, m map[string]string) {
+	for k, v := range m {
+		if m[k] != v {
+			t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
+		}
 	}
 }

src/pkg/runtime/mapspeed_test.go

--- a/src/pkg/runtime/mapspeed_test.go
+++ b/src/pkg/runtime/mapspeed_test.go
@@ -150,6 +150,23 @@ func BenchmarkSmallStrMap(b *testing.B) {
 	}
 }
 
+func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
+func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
+func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
+func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
+
+func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
+	m := make(map[string]bool)
+	for i := 0; i < 8; i++ {
+		m[strings.Repeat("K", i+1)] = true
+	}
+	key := strings.Repeat("K", keySize)
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		_ = m[key]
+	}
+}
+
 func BenchmarkIntMap(b *testing.B) {
 	m := make(map[int]bool)
 	for i := 0; i < 8; i++ {
@@ -182,3 +199,10 @@ func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
 
 func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
 func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }\n+
+func BenchmarkNewEmptyMap(b *testing.B) {
+	b.ReportAllocs()
+	for i := 0; i < b.N; i++ {
+		_ = make(map[int]int)
+	}
+}

コアとなるコードの解説

src/pkg/runtime/map_test.go

• import "strings"の追加: 新しく追加されるテスト関数内でstrings.Repeatを使用するため、stringsパッケージがインポートされました。
• TestSingleBucketMapStringKeys_DupLen: このテスト関数は、Goのマップが文字列キーをどのように処理するか、特にハッシュ衝突が発生しやすいシナリオ（「シングルバケット」）に焦点を当てています。
  • map[string]string型のマップを初期化し、様々な文字列キーと値のペアを格納しています。
  • 注目すべきは、"foo"と"bar"のように同じ長さの異なるキーが含まれている点です。Goのマップのハッシュ関数はキーの長さも考慮に入れることがあるため、同じ長さのキーはハッシュ衝突を引き起こしやすい可能性があります。
  • また、strings.Repeat("x", 128)のような非常に長いキーも含まれています。これは、長いキーがマップのパフォーマンスやメモリ使用量に与える影響をテストするためです。
  • testMapLookupsヘルパー関数を呼び出し、マップ内のすべてのキーについて正しく値が取得できるかを確認しています。
• TestSingleBucketMapStringKeys_NoDupLen: このテストもシングルバケットのシナリオを検証しますが、こちらはすべてのキーが異なる長さを持つように設計されています。
  • "x", "xx", "foo", "xxxx", "xxxxx", "xxxxxx", strings.Repeat("x", 128)といった、長さがバラバラのキーを使用しています。
  • キーの長さが異なることで、ハッシュ衝突のパターンが変わり、マップの内部的なハッシュ計算やバケット割り当てのロジックが異なる挙動を示す可能性があります。このテストは、そのようなケースでもマップが正しく機能することを確認します。
• testMapLookups: このヘルパー関数は、与えられたマップmのすべてのキーと値のペアをイテレートし、m[k]でキーkに対応する値を取得し、それが期待される値vと一致するかを検証します。一致しない場合はt.Fatalfを呼び出してテストを失敗させます。これにより、マップのルックアップ操作の正確性が保証されます。

src/pkg/runtime/mapspeed_test.go

• BenchmarkMapStringKeysEight_16, _32, _64, _1M: これらのベンチマーク関数は、benchmarkMapStringKeysEightヘルパー関数を呼び出し、異なるkeySize（キーの長さ）でマップのルックアップ性能を測定します。
  • 16, 32, 64は比較的短いキー長を、1<<20（1MB）は非常に長いキー長をシミュレートしています。
  • これにより、Goのマップが様々なキー長に対してどのようにスケールするか、特に非常に長い文字列キーがパフォーマンスに与える影響を評価できます。
• benchmarkMapStringKeysEight: このヘルパー関数は、8つの異なる長さの文字列キー（"K", "KK", ..., "KKKKKKKK"）を持つmap[string]boolを作成します。
  • その後、指定されたkeySizeを持つ単一のキー（例: strings.Repeat("K", keySize)）を生成し、そのキーに対するマップのルックアップ操作（_ = m[key]）をb.N回繰り返してベンチマークを実行します。
  • b.ResetTimer()は、マップの初期化にかかる時間をベンチマークの測定から除外するために使用されます。
  • このベンチマークは、特定の数の要素を持つマップにおいて、異なる長さの文字列キーでのルックアップがどれだけ高速に行われるかを測定し、マップのハッシュ計算や比較の効率性を評価するのに役立ちます。
• BenchmarkNewEmptyMapの移動: このベンチマークは、新しい空のmap[int]intを作成する際のメモリ割り当て（b.ReportAllocs()）とパフォーマンスを測定します。これは、マップの作成コストを評価するためのものであり、機能テストではなく性能ベンチマークに分類されるため、map_test.goからmapspeed_test.goに移動されました。これにより、テストとベンチマークの役割がより明確になりました。

これらの変更は、Goのマップ実装が様々なシナリオ、特に文字列キーとハッシュ衝突の状況下で、期待通りに正確かつ効率的に動作することを保証するためのものです。

関連リンク

• Go言語のmap型に関する公式ドキュメント: https://go.dev/blog/maps
• Go言語のtestingパッケージに関する公式ドキュメント: https://pkg.go.dev/testing
• Go言語のruntimeパッケージに関する公式ドキュメント: https://pkg.go.dev/runtime

参考にした情報源リンク

• Go言語の公式ドキュメント
• Go言語のソースコード（src/runtime/map.goなど）
• ハッシュテーブル、ハッシュ衝突に関する一般的なコンピュータサイエンスの知識
• Goのテストとベンチマークに関する一般的なプラクティス