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

このコミットは、Go言語の標準ライブラリである index/suffixarray パッケージ内のベンチマークのデータサイズを削減する変更です。具体的には、BenchmarkSaveRestore ベンチマークが処理するデータ量を10MBから1MBに減らすことで、ベンチマークの実行時間を短縮し、特定のビルド環境でのタイムアウト問題を解消することを目的としています。

コミット

commit b0c586a8211d8d8804a6052a3646b0f2cc724f19
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Jun 24 20:37:28 2014 -0700

    index/suffixarray: reduce size of a benchmark
    A single iteration of BenchmarkSaveRestore runs for 5 seconds
    on my freebsd machine. 5 seconds looks like too long for a single
    iteration.
    This is the only benchmark that times out on freebsd-amd64-race builder.
    
    R=golang-codereviews, dave
    CC=golang-codereviews
    https://golang.org/cl/107340044

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

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

index/suffixarray: reduce size of a benchmark A single iteration of BenchmarkSaveRestore runs for 5 seconds on my freebsd machine. 5 seconds looks like too long for a single iteration. This is the only benchmark that times out on freebsd-amd64-race builder.

変更の背景

この変更の主な背景は、Go言語の継続的インテグレーション（CI）システムにおけるベンチマークの安定性問題です。コミットメッセージによると、BenchmarkSaveRestore ベンチマークがFreeBSD環境（特に freebsd-amd64-race ビルダー）でタイムアウトするという問題が発生していました。

ベンチマークの1回のイテレーションが5秒もかかるのは長すぎると判断され、これがタイムアウトの原因となっていました。CIシステムでは、テストやベンチマークの実行時間に上限が設けられていることが一般的であり、それを超えるとビルドが失敗とみなされます。このベンチマークが唯一タイムアウトするものであったため、その実行時間を短縮することが喫緊の課題でした。

ベンチマークの実行時間が長すぎると、CIパイプライン全体の速度が低下するだけでなく、不安定なビルド結果（断続的なタイムアウト）を引き起こし、開発者の生産性を阻害します。そのため、ベンチマークの目的（性能測定）を損なうことなく、実行時間を短縮する調整が必要とされました。

前提知識の解説

サフィックス配列 (Suffix Array)

サフィックス配列は、文字列処理において非常に強力なデータ構造です。これは、与えられたテキスト（文字列）のすべてのサフィックス（接尾辞）を辞書順にソートし、その開始位置のインデックスを格納した配列です。

例: テキスト "banana" サフィックス:

"banana" (インデックス 0)
"anana" (インデックス 1)
"nana" (インデックス 2)
"ana" (インデックス 3)
"na" (インデックス 4)
"a" (インデックス 5)

辞書順にソートされたサフィックスと元のインデックス:

"a" (インデックス 5)
"ana" (インデックス 3)
"anana" (インデックス 1)
"banana" (インデックス 0)
"na" (インデックス 4)
"nana" (インデックス 2)

サフィックス配列: [5, 3, 1, 0, 4, 2]

用途: サフィックス配列は、以下のような様々な文字列検索アルゴリズムやバイオインフォマティクス分野で利用されます。

高速な部分文字列検索: テキスト内に特定のパターン（部分文字列）が存在するかどうかを効率的に検索できます。
最長共通部分文字列の発見: 複数の文字列間で最も長い共通部分文字列を見つけるのに役立ちます。
繰り返しパターンの検出: テキスト内の繰り返しパターンを特定します。
データ圧縮: 圧縮アルゴリズムの一部として使用されることがあります。

Go言語の `index/suffixarray` パッケージ

Go言語の標準ライブラリには、サフィックス配列を実装した index/suffixarray パッケージが含まれています。このパッケージは、テキストのインデックス作成と効率的な部分文字列検索機能を提供します。

主な機能としては、New 関数でテキストからサフィックス配列を構築し、Lookup メソッドで部分文字列を検索する機能などがあります。サフィックス配列はメモリを消費するデータ構造であり、大きなテキストを扱う際にはその構築と利用に時間がかかることがあります。

Go言語のベンチマーク (`testing` パッケージ)

Go言語には、コードの性能を測定するためのベンチマーク機能が標準で組み込まれています。testing パッケージを使用し、Benchmark というプレフィックスを持つ関数を定義することでベンチマークを実行できます。

go test -bench=.: このコマンドでプロジェクト内のすべてのベンチマークを実行できます。
*testing.B: ベンチマーク関数は *testing.B 型の引数を受け取ります。この型はベンチマークの制御と測定のためのメソッドを提供します。
- b.N: ベンチマーク関数は b.N 回ループを実行するように設計されます。b.N の値は、ベンチマークの実行時間に基づいてGoのテストフレームワークが自動的に調整します。これにより、統計的に有意な結果を得るのに十分な回数だけ操作が繰り返されます。
- b.StopTimer() / b.StartTimer(): ベンチマークの測定範囲を制御するために使用します。b.StopTimer() はタイマーを一時停止し、セットアップコードなどの測定対象外の処理の時間を計測から除外します。b.StartTimer() はタイマーを再開します。
- b.ReportAllocs(): メモリ割り当ての情報を報告するように設定します。

ベンチマークは、コードの性能特性を理解し、最適化の効果を測定するために不可欠なツールです。しかし、ベンチマーク自体が長時間実行されると、開発サイクルやCIパイプラインの効率を低下させる可能性があります。

技術的詳細

このコミットは、src/pkg/index/suffixarray/suffixarray_test.go ファイル内の BenchmarkSaveRestore 関数に焦点を当てています。このベンチマークは、サフィックス配列の保存と復元にかかる時間を測定することを目的としています。

元のコードでは、ベンチマークの入力データとして10MBのランダムなバイト列が生成されていました。 data := make([]byte, 10<<20) // 10MB of data to index

10<<20 はビットシフト演算子で、10 * 2^20 を意味します。2^20 は1MBなので、これは正確に10MBのデータサイズを生成しています。

コミットメッセージによると、この10MBというデータサイズがFreeBSD環境でのベンチマークの実行時間を長くし、タイムアウトの原因となっていました。特に freebsd-amd64-race ビルダーは、データ競合検出のための追加のオーバーヘッドがあるため、通常のビルドよりも実行時間が長くなる傾向があります。

この問題を解決するため、コミットは入力データサイズを10MBから1MBに削減しました。 data := make([]byte, 1<<20) // 1MB of data to index

1<<20 は 2^20、つまり1MBを意味します。

この変更により、BenchmarkSaveRestore が処理するデータ量が10分の1になり、それに伴いベンチマークの実行時間も大幅に短縮されます。これにより、FreeBSD環境でのタイムアウトが解消され、CIパイプラインの安定性が向上します。

ベンチマークの目的は、特定の操作の相対的な性能を測定することであり、必ずしも非常に大きなデータセットで実行する必要はありません。適切なデータサイズに調整することで、ベンチマークの目的を達成しつつ、開発プロセスへの影響を最小限に抑えることができます。

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

変更は src/pkg/index/suffixarray/suffixarray_test.go ファイルの1箇所のみです。

--- a/src/pkg/index/suffixarray/suffixarray_test.go
+++ b/src/pkg/index/suffixarray/suffixarray_test.go
@@ -287,7 +287,7 @@ func BenchmarkNewIndexRepeat(b *testing.B) {
 func BenchmarkSaveRestore(b *testing.B) {
  	b.StopTimer()
  	r := rand.New(rand.NewSource(0x5a77a1)) // guarantee always same sequence
- 	data := make([]byte, 10<<20)            // 10MB of data to index
+ 	data := make([]byte, 1<<20)             // 1MB of data to index
  	for i := range data {
  		data[i] = byte(r.Intn(256))
  	}

コアとなるコードの解説

変更された行は data := make([]byte, 10<<20) から data := make([]byte, 1<<20) です。

data := make([]byte, 10<<20):
- これは、BenchmarkSaveRestore ベンチマークで使用されるバイトスライス data を初期化する行です。
- make([]byte, size) は、指定されたサイズのバイトスライスを作成します。
- 10<<20 は、10 * 2^20、つまり 10 * 1024 * 1024 バイト、すなわち10メガバイト（MB）を意味します。
- この行は、サフィックス配列の保存と復元の対象となる10MBのランダムなデータを生成していました。
data := make([]byte, 1<<20):
- 変更後の行です。
- 1<<20 は、1 * 2^20、つまり 1 * 1024 * 1024 バイト、すなわち1メガバイト（MB）を意味します。
- この変更により、ベンチマークが処理するデータ量が10分の1に削減されました。

このデータサイズの削減は、ベンチマークの実行時間を短縮するための直接的な手段です。サフィックス配列の構築、保存、復元といった操作は、入力データのサイズに比例して計算量が増加するため、データサイズを減らすことで実行時間を効果的に短縮できます。これにより、FreeBSD環境でのタイムアウト問題が解決され、CIの安定性が向上しました。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコード
一般的なサフィックス配列に関する情報
Go言語のベンチマークに関する情報
Web検索結果 (Go FreeBSD performance issues)

comemo