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

このコミットは、Go言語の標準ライブラリであるbytesパッケージとstringsパッケージ内のRepeat関数のパフォーマンス最適化に関するものです。具体的には、src/pkg/bytes/bytes.go、src/pkg/bytes/bytes_test.go、src/pkg/strings/strings.go、src/pkg/strings/strings_test.goの4つのファイルが変更されています。

コミット

commit 7bcbb65d7879f17b185cee9ab4ab392da0bd865f
Author: Rui Ueyama <ruiu@google.com>
Date:   Wed Jun 11 19:03:59 2014 -0700

    bytes, strings: optimize Repeat
    
    Call copy with as large buffer as possible to reduce the
    number of function calls.
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBytesRepeat            540          162  -70.00%
    BenchmarkStringsRepeat          563          177  -68.56%
    
    LGTM=josharian
    R=golang-codereviews, josharian, dave, dvyukov
    CC=golang-codereviews
    https://golang.org/cl/90550043

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

https://github.com/golang/go/commit/7bcbb65d7879f17b185cee9ab4ab392da0bd865f

元コミット内容

bytesおよびstringsパッケージのRepeat関数を最適化する。 可能な限り大きなバッファでcopyを呼び出すことで、関数呼び出しの回数を減らす。

ベンチマーク結果:

• BenchmarkBytesRepeat: 540 ns/op -> 162 ns/op (-70.00%)
• BenchmarkStringsRepeat: 563 ns/op -> 177 ns/op (-68.56%)

変更の背景

bytes.Repeatおよびstrings.Repeat関数は、指定されたバイトスライスまたは文字列を複数回繰り返して新しいバイトスライスまたは文字列を生成する機能を提供します。元の実装では、この繰り返し処理をループ内で1回ずつcopy関数を呼び出すことで実現していました。しかし、このアプローチは、特に繰り返し回数が多い場合に、copy関数の呼び出しオーバーヘッドが無視できないほど大きくなるというパフォーマンス上の問題がありました。

このコミットの目的は、Repeat関数の実行効率を大幅に向上させることです。ベンチマーク結果が示すように、この最適化により、処理速度が約70%改善されています。これは、Go言語の標準ライブラリの基本的な操作のパフォーマンスを向上させ、それを利用するアプリケーション全体の効率を高めることに貢献します。

前提知識の解説

bytes.Repeatとstrings.Repeat関数

• func Repeat(b []byte, count int) []byte: bytesパッケージの関数で、バイトスライスbをcount回繰り返した新しいバイトスライスを返します。
• func Repeat(s string, count int) string: stringsパッケージの関数で、文字列sをcount回繰り返した新しい文字列を返します。内部的にはバイトスライスとして処理されます。

これらの関数は、例えば特定の文字やパターンを繰り返して長い文字列を生成する際などに利用されます。

copy関数

Go言語の組み込み関数であるcopy(dst, src []Type) intは、srcスライスからdstスライスへ要素をコピーします。コピーされる要素の数は、len(dst)とlen(src)の小さい方になります。この関数は非常に効率的ですが、呼び出し自体にはわずかなオーバーヘッドが存在します。

make関数

Go言語の組み込み関数であるmakeは、スライス、マップ、チャネルなどの組み込み型を初期化するために使用されます。

• make([]Type, length, capacity): 指定されたlengthとcapacityを持つType型のスライスを作成します。lengthはスライスの初期の長さ、capacityは基盤となる配列の容量です。

Go言語におけるパフォーマンス最適化の一般的な考え方

Go言語では、パフォーマンスを最適化する際に以下の点が考慮されることが多いです。

1. アロケーションの削減: メモリのアロケーションはコストが高い操作であるため、可能な限りアロケーションの回数や量を減らすことが重要です。Repeat関数では、結果を格納するためのバイトスライスを事前にmakeで一度だけ確保しています。
2. 関数呼び出しのオーバーヘッド削減: 関数呼び出しには、スタックフレームのセットアップやレジスタの保存・復元などのオーバーヘッドが伴います。特に短い関数を頻繁に呼び出す場合、このオーバーヘッドが全体のパフォーマンスに影響を与えることがあります。今回のコミットでは、この「関数呼び出しのオーバーヘッド」を削減することが主要な目的となっています。
3. 組み込み関数の活用: copyのような組み込み関数は、Goランタイムやコンパイラによって高度に最適化されており、手動でループを記述するよりも高速に動作することが多いです。

技術的詳細

このコミットの核心は、Repeat関数におけるcopy関数の呼び出し戦略の変更にあります。

変更前の実装

変更前のRepeat関数は、以下のようなロジックでした（bytes.Repeatを例に説明）。

func Repeat(b []byte, count int) []byte {
	nb := make([]byte, len(b)*count) // 結果を格納するスライスを事前に確保
	bp := 0
	for i := 0; i < count; i++ {
		bp += copy(nb[bp:], b) // bを1回ずつコピーし、bpを更新
	}
	return nb
}

この実装では、count回ループを回し、その都度copy関数を呼び出していました。例えば、bが1バイトでcountが1000の場合、copy関数が1000回呼び出されることになります。

変更後の実装（「倍々コピー」戦略）

変更後のRepeat関数は、以下のようなロジックに変わりました。

func Repeat(b []byte, count int) []byte {
	nb := make([]byte, len(b)*count) // 結果を格納するスライスを事前に確保
	bp := copy(nb, b)                // 最初の1回だけbをコピー
	for bp < len(nb) {
		// nb[bp:] (コピー先の残りの部分) に nb[:bp] (既にコピーされた部分) をコピー
		// これにより、コピーされるデータ量が倍々に増えていく
		copy(nb[bp:], nb[:bp])
		bp *= 2 // コピーされたバイト数を倍にする
	}
	return nb
}

この新しい戦略は「倍々コピー（doubling copy）」または「バイナリ指数バックオフ」のような考え方に基づいています。

1. まず、元のバイトスライスbを結果スライスnbの先頭に一度だけコピーします。この時点でのコピーされたバイト数bpはlen(b)です。
2. 次に、bpがlen(nb)（結果スライスの全長）に達するまでループを続けます。
3. ループ内では、nbの既に埋まっている部分（nb[:bp]）を、nbのまだ埋まっていない部分（nb[bp:]）にコピーします。
4. この操作により、一度のcopy呼び出しでコピーされるデータ量がbpから2*bpへと倍増します。
5. bpを2*bpに更新し、次のループでさらに倍のデータをコピーします。

この戦略により、copy関数の呼び出し回数はcount回ではなく、log2(count)回程度に大幅に削減されます。例えば、countが1000の場合、log2(1000)は約10なので、copyの呼び出し回数が1000回から約10回に減ります。これにより、copy関数呼び出しのオーバーヘッドが劇的に削減され、全体的なパフォーマンスが向上します。

ベンチマーク結果

コミットメッセージに記載されているベンチマーク結果は、この最適化が非常に効果的であったことを明確に示しています。

• BenchmarkBytesRepeat: 540 ns/op から 162 ns/op へと約70%の改善。
• BenchmarkStringsRepeat: 563 ns/op から 177 ns/op へと約68.56%の改善。

ns/opは「操作あたりのナノ秒」を意味し、値が小さいほど高速であることを示します。

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

src/pkg/bytes/bytes.go

--- a/src/pkg/bytes/bytes.go
+++ b/src/pkg/bytes/bytes.go
@@ -377,9 +377,10 @@ func Map(mapping func(r rune) rune, s []byte) []byte {
 // Repeat returns a new byte slice consisting of count copies of b.
 func Repeat(b []byte, count int) []byte {
  	nb := make([]byte, len(b)*count)
- 	bp := 0
- 	for i := 0; i < count; i++ {
- 		bp += copy(nb[bp:], b)
+ 	bp := copy(nb, b)
+ 	for bp < len(nb) {
+ 		copy(nb[bp:], nb[:bp])
+ 		bp *= 2
  	}
  	return nb
 }

src/pkg/bytes/bytes_test.go

--- a/src/pkg/bytes/bytes_test.go
+++ b/src/pkg/bytes/bytes_test.go
@@ -1232,3 +1232,9 @@ func BenchmarkTrimSpace(b *testing.B) {
  	\tTrimSpace(s)
  	}
  }
+\n+func BenchmarkRepeat(b *testing.B) {
+\tfor i := 0; i < b.N; i++ {
+\t\tRepeat([]byte(\"-\"), 80)\n+\t}\n+}\n

src/pkg/strings/strings.go

--- a/src/pkg/strings/strings.go
+++ b/src/pkg/strings/strings.go
@@ -423,9 +423,10 @@ func Map(mapping func(rune) rune, s string) string {
 // Repeat returns a new string consisting of count copies of the string s.
 func Repeat(s string, count int) string {
  	b := make([]byte, len(s)*count)
- 	bp := 0
- 	for i := 0; i < count; i++ {
- 		bp += copy(b[bp:], s)
+ 	bp := copy(b, s)
+ 	for bp < len(b) {
+ 		copy(b[bp:], b[:bp])
+ 		bp *= 2
  	}
  	return string(b)
 }

src/pkg/strings/strings_test.go

--- a/src/pkg/strings/strings_test.go
+++ b/src/pkg/strings/strings_test.go
@@ -1174,3 +1174,9 @@ func BenchmarkSplit3(b *testing.B) {
  	\tSplit(benchInputHard, \"hello\")
  	}
  }
+\n+func BenchmarkRepeat(b *testing.B) {
+\tfor i := 0; i < b.N; i++ {
+\t\tRepeat(\"-\", 80)\n+\t}\n+}\n

コアとなるコードの解説

bytes.Repeat および strings.Repeat の変更点

両方のRepeat関数で、以下の変更が加えられています。

変更前:

 	nb := make([]byte, len(b)*count) // または b := make([]byte, len(s)*count)
 	bp := 0
 	for i := 0; i < count; i++ {
 		bp += copy(nb[bp:], b) // または copy(b[bp:], s)
 	}

• bp := 0: コピー先の現在の位置を示すインデックスを0で初期化。
• for i := 0; i < count; i++: count回繰り返すループ。
• bp += copy(nb[bp:], b): b（またはs）の内容をnbのbp以降にコピーし、コピーされたバイト数をbpに加算して次のコピー位置を更新。

この旧来のループは、countが大きくなるにつれてcopy関数の呼び出し回数が増え、そのオーバーヘッドが顕著になるという問題がありました。

変更後:

 	nb := make([]byte, len(b)*count) // または b := make([]byte, len(s)*count)
 	bp := copy(nb, b)                // または copy(b, s)
 	for bp < len(nb) {
 		copy(nb[bp:], nb[:bp])
 		bp *= 2
 	}

• bp := copy(nb, b): まず、元のバイトスライスb（または文字列sのバイト表現）を、結果スライスnbの先頭に一度だけコピーします。bpには、この最初のコピーで実際にコピーされたバイト数（つまりlen(b)またはlen(s)）が格納されます。
• for bp < len(nb): ループの条件は、bp（現在までにコピーされたバイト数）が結果スライスnbの全長len(nb)に達するまで、つまり全ての領域が埋まるまで繰り返すことを意味します。
• copy(nb[bp:], nb[:bp]): この行が最適化の核心です。
  • nb[:bp]: これは、nbスライスの先頭からbpバイト目まで、つまり既にコピーされたデータ全体を表します。
  • nb[bp:]: これは、nbスライスのbpバイト目から最後まで、つまりまだデータがコピーされていない残りの部分を表します。
  • このcopy呼び出しは、「既にコピーされたデータ全体」を「まだ空いている領域の先頭」にコピーします。これにより、コピーされるデータ量がbpから2*bpへと倍増します。
• bp *= 2: bpの値を2倍に更新します。これにより、次のループイテレーションでは、さらに倍のデータ量をコピーしようとします。

この「倍々コピー」戦略により、copy関数の呼び出し回数は対数的に減少します。例えば、結果スライスの長さが1000バイトで、元の要素が1バイトの場合、最初のコピーで1バイト、次に1バイトをコピーして2バイト、次に2バイトをコピーして4バイト、...というように、コピーされるデータ量が指数関数的に増えていきます。これにより、copy関数の呼び出し回数が大幅に削減され、それに伴うオーバーヘッドも減少するため、全体的なパフォーマンスが向上します。

ベンチマークコードの追加

src/pkg/bytes/bytes_test.goとsrc/pkg/strings/strings_test.goには、それぞれBenchmarkRepeat関数が追加されています。

func BenchmarkRepeat(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Repeat([]byte("-"), 80) // または Repeat("-", 80)
	}
}

• b *testing.B: ベンチマークテストのコンテキストを提供します。
• b.N: ベンチマークを実行する回数。Goのテストフレームワークが自動的に適切な回数を決定します。
• Repeat([]byte("-"), 80): 1バイトのハイフンを80回繰り返す操作をベンチマークしています。これは、Repeat関数の一般的な使用シナリオをシミュレートし、最適化の効果を測定するために選ばれた具体的なケースです。

これらのベンチマークの追加により、将来の変更がRepeat関数のパフォーマンスに与える影響を継続的に監視できるようになります。

関連リンク

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

参考にした情報源リンク

• Go言語の公式ドキュメント: bytesパッケージ, stringsパッケージ, copy関数, make関数
• Go言語のベンチマークに関するドキュメント: testingパッケージ
• 一般的なアルゴリズムとデータ構造の最適化手法（特に指数バックオフや倍々戦略）に関する知識
• Go言語のソースコードリーディング I have generated the detailed explanation in Markdown format, following all the instructions, including the specific chapter structure, language, and level of detail. I have also incorporated the commit information, benchmark results, and explanations of prerequisite knowledge and technical details. The output is now ready to be presented to the user.