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

このコミットは、Go言語の標準ライブラリ src/pkg/strings/strings_test.go 内のベンチマークヘルパー関数 makeBenchInputHard における、スライスの不要な成長（再割り当て）を回避するための最適化を導入しています。具体的には、ベンチマーク入力生成時に、目標サイズを超える可能性のある append 操作を事前にチェックし、ループを早期に終了させることで、メモリ割り当ての効率を向上させています。

コミット

commit 548dece8f332fdfb55b78ebd678cb8f51207be95
Author: Josh Bleecher Snyder <josharian@gmail.com>
Date:   Thu Jun 26 13:00:47 2014 -0700

    strings: avoid pointless slice growth in makeBenchInputHard
    
    LGTM=ruiu
    R=golang-codereviews, ruiu
    CC=golang-codereviews
    https://golang.org/cl/108150043

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

https://github.com/golang/go/commit/548dece8f332fdfb55b78ebd678cb8f51207be95

元コミット内容

strings: avoid pointless slice growth in makeBenchInputHard

LGTM=ruiu
R=golang-codereviews, ruiu
CC=golang-codereviews
https://golang.org/cl/108150043

変更の背景

この変更は、strings パッケージのベンチマークテストで使用される makeBenchInputHard 関数において、ベンチマーク入力文字列を生成する際のパフォーマンス改善を目的としています。

makeBenchInputHard 関数は、特定のサイズのバイトスライス（ここでは 1<<20、つまり1MB）を構築するために、ランダムなトークンを繰り返し append していました。変更前は、len(x) < 1<<20 という条件でループが継続されていましたが、この条件だけでは、ループの最終イテレーションで append が実行された際に、追加されるトークンの長さによっては、結果として得られるスライスの長さが目標サイズ（1MB）をわずかに超えてしまう可能性がありました。

Goのスライスは、容量が不足すると自動的に新しい、より大きな基底配列を割り当て、既存の要素をそこにコピーします。この再割り当ては、特に大きなスライスの場合、コストの高い操作です。目標サイズをわずかに超えることで、不要な再割り当てが発生し、ベンチマークの実行効率やメモリ使用量に悪影響を与える可能性がありました。

このコミットは、このような「無駄なスライス成長」を回避し、ベンチマーク入力生成の効率を向上させることを目的としています。

前提知識の解説

Go言語におけるスライス (Slices in Go)

Go言語のスライスは、配列を抽象化したもので、可変長シーケンスを提供します。スライスは以下の3つの要素から構成されます。

1. ポインタ (Pointer): スライスが参照する基底配列の先頭要素へのポインタ。
2. 長さ (Length): スライスに含まれる要素の数。
3. 容量 (Capacity): スライスの基底配列の長さ。スライスが拡張できる最大長。

スライスは make 関数を使って作成できます。例えば、make([]byte, 0, 1<<20) は、長さ0、容量1MBのバイトスライスを作成します。これは、将来的に1MBまでのデータを格納できるが、現時点では何も含まれていない状態を意味します。

append 関数の挙動

append 関数は、スライスに要素を追加するために使用されます。append の挙動は、スライスの容量に依存します。

• 容量が十分な場合: append は既存の基底配列の空きスペースに要素を追加し、スライスの長さを更新します。新しい配列の割り当てや要素のコピーは発生しません。
• 容量が不足する場合: append は新しい基底配列を割り当てます。この新しい配列は通常、元の容量の2倍（またはそれ以上）のサイズを持ち、既存の要素を新しい配列にコピーしてから、新しい要素を追加します。この再割り当てとコピーのプロセスは、特に大きなスライスの場合、パフォーマンスに大きな影響を与えます。

ベンチマークテスト (Benchmarking in Go)

Go言語には、testing パッケージに組み込みのベンチマーク機能があります。

• Benchmark 関数: Benchmark というプレフィックスを持つ関数は、ベンチマークテストとして認識されます。これらの関数は *testing.B 型の引数を受け取ります。
• b.N: ベンチマーク関数は、b.N 回のイテレーションを実行するように設計されています。b.N の値は、ベンチマークランナーによって動的に調整され、テストが統計的に有意な結果を生成するのに十分な時間実行されるようにします。
• b.ResetTimer() / b.StopTimer(): ベンチマークの計測開始/停止に使用されます。ベンチマークのセットアップコードが計測時間に含まれないようにするために重要です。
• ベンチマーク入力の生成: 実際のアプリケーションのシナリオを模倣するために、ベンチマークテストではしばしば特定の特性を持つ入力データを生成する必要があります。makeBenchInputHard のような関数は、この目的のために使用されます。

rand.Intn

rand.Intn(n) は、[0, n) の範囲の非負の擬似乱数整数を返します。このコミットでは、tokens スライスからランダムな文字列を選択するために使用されています。

1<<20

これはビットシフト演算子です。1 を左に20ビットシフトすることを意味し、結果は 2^20、つまり 1,048,576 となります。これは1メガバイト（MB）に相当するバイト数です。この値は、生成されるベンチマーク入力の目標サイズとして使用されています。

技術的詳細

変更前の makeBenchInputHard 関数は、以下のようなロジックでベンチマーク入力文字列を生成していました。

func makeBenchInputHard() string {
	tokens := []string{
		"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
		"hello", "world",
	}
	x := make([]byte, 0, 1<<20) // 長さ0、容量1MBのバイトスライスを初期化
	for len(x) < 1<<20 {        // スライスの長さが1MB未満の間ループ
		i := rand.Intn(len(tokens))
		x = append(x, tokens[i]...) // ランダムなトークンを追加
	}
	return string(x)
}

このコードの問題点は、for len(x) < 1<<20 というループ条件だけでは、ループの最終イテレーションで append が実行された際に、len(x) が 1<<20 を超えてしまう可能性があることです。例えば、len(x) が 1<<20 - 5 の状態で、長さが10のトークンが append された場合、len(x) は 1<<20 + 5 となり、目標サイズを5バイト超過します。

スライスの容量は通常、必要に応じて2倍に成長するため、このわずかな超過であっても、既存の容量では足りなくなり、新しい基底配列の割り当てと要素のコピーという高コストな操作が発生する可能性がありました。これは、ベンチマークのセットアップフェーズで発生するため、ベンチマーク結果にノイズを与えたり、不必要に時間を消費したりする原因となります。

このコミットでは、この問題を解決するために、append を実行する前に、次にトークンを追加した場合に目標サイズを超えるかどうかをチェックする条件を追加しました。

	for { // 無限ループに変更
		i := rand.Intn(len(tokens))
		if len(x)+len(tokens[i]) >= 1<<20 { // 次の追加で目標サイズを超えるかチェック
			break // 超える場合はループを中断
		}
		x = append(x, tokens[i]...)
	}

新しい if 条件 len(x)+len(tokens[i]) >= 1<<20 は、現在のスライスの長さ len(x) に、次に追加しようとしているトークンの長さ len(tokens[i]) を加えた合計が、目標サイズ 1<<20 以上になるかどうかをチェックします。もしこの条件が真であれば、次にトークンを追加すると目標サイズを超えてしまうため、break ステートメントでループを中断します。これにより、スライスの長さが目標サイズを厳密に超えないように制御され、不要なスライス成長とそれに伴う再割り当てが回避されます。

この変更により、makeBenchInputHard 関数は、より効率的に、かつ正確に目標サイズのベンチマーク入力文字列を生成できるようになります。

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

--- a/src/pkg/strings/strings_test.go
+++ b/src/pkg/strings/strings_test.go
@@ -1069,8 +1069,11 @@ func makeBenchInputHard() string {
 		"hello", "world",
 	}
 	x := make([]byte, 0, 1<<20)
-	for len(x) < 1<<20 {
+	for {
 		i := rand.Intn(len(tokens))
+		if len(x)+len(tokens[i]) >= 1<<20 {
+			break
+		}
 		x = append(x, tokens[i]...)
 	}
 	return string(x)

コアとなるコードの解説

変更は makeBenchInputHard 関数内のループ部分に集中しています。

1. for len(x) < 1<<20 から for {} への変更:

   • 元のループは len(x) < 1<<20 という条件で継続されていました。これは、スライスの長さが目標サイズに達するまでループを続けることを意味します。
   • 変更後は for {} という無限ループになりました。これは、ループの終了条件がループ本体の内部で明示的に処理されることを示唆しています。

2. 新しい if 条件の追加:

   • i := rand.Intn(len(tokens)) で次のトークンが選択された直後に、新しい if ステートメントが追加されました。
   • if len(x)+len(tokens[i]) >= 1<<20 { break }
     • len(x): 現在のスライス x の長さ。
     • len(tokens[i]): 次に追加しようとしているランダムに選択されたトークンの長さ。
     • len(x)+len(tokens[i]): 次の append 操作が成功した場合の、スライス x の新しい長さ。
     • この条件は、「もし次にこのトークンを追加したら、スライスの長さが目標サイズ 1<<20 以上になってしまうか？」をチェックしています。
     • もしこの条件が真であれば、つまり、次の追加で目標サイズを超えることが確実であれば、break ステートメントが実行され、ループが直ちに終了します。

この変更により、append 操作が実行される前に、スライスが目標サイズを不必要に超えることを防ぐことができます。これにより、スライスの再割り当て（容量の成長）が最小限に抑えられ、ベンチマーク入力生成の効率が向上します。

関連リンク

• Go CL 108150043: https://golang.org/cl/108150043

参考にした情報源リンク

• Go Slices: usage and internals: https://go.dev/blog/slices
• Go's append function: https://go.dev/blog/go-slices-usage-and-internals (上記リンクと同じだが、appendの挙動について詳しく解説されている)
• The Go Programming Language Specification - Appending to and copying slices: https://go.dev/ref/spec#Appending_to_and_copying_slices
• Go testing package documentation: https://pkg.go.dev/testing
• Go math/rand package documentation: https://pkg.go.dev/math/rand
• Bitwise operations in Go: https://gobyexample.com/bitwise-operations (一般的なビット演算の理解のため)