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

このコミットは、Go言語のregexpパッケージのベンチマークにおいて、乱数生成器のパフォーマンスを改善することを目的としています。具体的には、ベンチマーク用のテキスト生成関数makeText内で使用されていたmath/randパッケージの呼び出しを、より高速な擬似乱数生成器（PRNG）の実装に置き換えることで、ベンチマーク実行時間を短縮しています。

コミット

• コミットハッシュ: 21b9d1473838b34911629e754f5cd2165411c1f4
• Author: Rémy Oudompheng oudomphe@phare.normalesup.org
• Date: Sat Jul 20 23:31:51 2013 +0200

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

https://github.com/golang/go/commit/21b9d1473838b34911629e754f5cd2165411c1f4

元コミット内容

regexp: use a very fast random generator for benchmarks.

Calls into math/rand are very slow, especially under race
detector because of heap accesses.

go test -bench . -run none -benchtime .1s
Before: 23.0s
After:  17.4s

Fixes #5837.

R=golang-dev, dave, r
CC=golang-dev
https://golang.org/cl/11564044

変更の背景

この変更の背景には、regexpパッケージのベンチマーク実行時に発生していたパフォーマンス上の問題があります。元の実装では、ベンチマーク用のランダムなテキストデータを生成するためにmath/randパッケージが使用されていました。しかし、math/randパッケージは、特にGoのレース検出器（Race Detector）が有効な環境下では、ヒープへのアクセスが頻繁に発生するため、非常に低速になるという問題がありました。

コミットメッセージに記載されているように、この変更によってベンチマークの実行時間が大幅に短縮されています。具体的には、go test -bench . -run none -benchtime .1sコマンドの実行時間が、変更前の23.0秒から変更後の17.4秒へと改善されました。これは、ベンチマークの効率を向上させ、開発者がより迅速にパフォーマンスの回帰を検出できるようにするために重要な改善でした。

この問題は、GoのIssue #5837として報告されており、このコミットはその問題を解決するためのものです。

前提知識の解説

1. math/randパッケージ

Go言語の標準ライブラリであるmath/randパッケージは、擬似乱数生成機能を提供します。このパッケージは、暗号学的に安全ではないが、一般的なシミュレーションやゲームなどで使用される乱数を生成するのに適しています。

• グローバルな乱数生成器: math/randパッケージのトップレベル関数（例: rand.Intn, rand.Float64）は、内部的にグローバルな乱数生成器インスタンスを使用します。このグローバルインスタンスは、デフォルトでシードが固定されているため、プログラムを再実行すると同じ乱数列が生成されます。異なる乱数列を得るには、rand.Seed関数でシードを設定する必要があります。
• 並行性: グローバルな乱数生成器は、複数のGoroutineから同時にアクセスされる可能性があるため、内部的にミューテックス（相互排他ロック）を使用して状態を保護しています。これにより、スレッドセーフ性は確保されますが、並行アクセスが多い場合にはロックの競合が発生し、パフォーマンスのボトルネックとなる可能性があります。
• ヒープアクセス: math/randの内部状態は、ヒープ上に割り当てられることがあります。特にレース検出器が有効な場合、ヒープへのアクセスは追加のオーバーヘッドを伴うため、パフォーマンスが低下する要因となります。

2. Goのレース検出器（Race Detector）

Goのレース検出器は、Goプログラムにおけるデータ競合（data race）を検出するためのツールです。データ競合は、複数のGoroutineが同時に同じメモリ位置にアクセスし、少なくとも1つのアクセスが書き込みであり、かつそれらのアクセスが同期されていない場合に発生します。データ競合は、予測不能なプログラムの動作やバグの原因となるため、Goでは非常に重要な問題とされています。

• 有効化: レース検出器は、go run -race、go build -race、go test -raceなどのコマンドで-raceフラグを指定することで有効にできます。
• 動作原理: レース検出器は、プログラムの実行中にメモリアクセスを監視し、データ競合のパターンを検出します。これには、メモリ割り当て、読み書き、Goroutineのスケジューリングなど、さまざまな操作に対する追加のインストルメンテーション（計測コードの挿入）が含まれます。
• パフォーマンスへの影響: レース検出器を有効にすると、プログラムの実行速度が大幅に低下し、メモリ使用量が増加します。これは、検出器が詳細な情報を収集するために必要なオーバーヘッドによるものです。そのため、通常は開発時やテスト時にのみ有効にし、本番環境では無効にします。

3. ベンチマーク（Benchmarking）

Go言語には、標準でベンチマークを記述し実行するためのフレームワークが組み込まれています。ベンチマークは、特定のコードのパフォーマンスを測定するために使用されます。

• testingパッケージ: ベンチマーク関数は、testingパッケージの*testing.B型を引数にとり、BenchmarkXxxという命名規則に従って定義されます。
• go test -bench: ベンチマークは、go test -bench .のようなコマンドで実行されます。-benchtimeフラグは、ベンチマークを実行する最小時間を指定します。
• 目的: ベンチマークの主な目的は、コードの変更がパフォーマンスに与える影響を定量的に評価することです。安定した、再現性のあるベンチマーク結果を得るためには、ベンチマーク対象のコード以外の要因（例: 乱数生成器のオーバーヘッド）を最小限に抑えることが重要です。

4. 擬似乱数生成器（Pseudo-Random Number Generator, PRNG）

擬似乱数生成器は、初期シード値に基づいて、統計的にランダムに見える数値のシーケンスを生成するアルゴリズムです。真の乱数とは異なり、PRNGは決定論的であり、同じシード値からは常に同じシーケンスが生成されます。

• 線形合同法（Linear Congruential Generator, LCG）: 最も単純で広く知られているPRNGの一つです。X_{n+1} = (aX_n + c) mod mという漸化式で定義されます。
• Xorshift: XOR演算とシフト演算を組み合わせたPRNGの一種で、LCGよりも高速で、より良い統計的特性を持つことが多いです。このコミットで採用されたカスタムPRNGは、Xorshiftに似た特性を持っています。

技術的詳細

このコミットでは、regexpパッケージのベンチマーク用テキスト生成関数makeTextにおいて、math/randパッケージの代わりに、非常に単純で高速な擬似乱数生成器がインラインで実装されています。

新しい乱数生成器は、以下のようなロジックに基づいています。

x := ^uint32(0) // 初期シード値として uint32 の最大値を使用

// ループ内で乱数を生成
x += x
x ^= 1
if int32(x) < 0 {
    x ^= 0x88888eef
}
// x % 31 == 0 で改行文字を挿入
// x % (0x7E+1-0x20) + 0x20 で印字可能ASCII文字を生成

このPRNGは、Xorshiftアルゴリズムに似た特性を持っています。

• x += x は x <<= 1 と同等で、ビットを左にシフトします。
• x ^= 1 は、最下位ビットを反転させます。
• if int32(x) < 0 { x ^= 0x88888eef } の部分は、特定のビットパターンをXORすることで、乱数の周期を長くしたり、統計的特性を改善したりするためのハッシュ関数的な操作です。0x88888eefは、マジックナンバーとして使用される定数です。

このカスタムPRNGの利点は以下の通りです。

1. ヒープアクセスなし: math/randのようにグローバルな状態やヒープ上のメモリを使用しないため、レース検出器によるオーバーヘッドが大幅に削減されます。
2. ロックなし: グローバルなミューテックスを使用しないため、並行アクセスによるロック競合が発生しません。
3. インライン化の可能性: 非常に単純なロジックであるため、Goコンパイラによってインライン化されやすく、関数呼び出しのオーバーヘッドがなくなります。
4. 十分なランダム性: ベンチマークの目的（ランダムなテキストを生成すること）に対しては、この程度の単純なPRNGでも十分なランダム性を提供します。暗号学的な安全性は不要であり、統計的な偏りが多少あってもベンチマーク結果に大きな影響を与えません。

この変更により、ベンチマークの実行が高速化され、開発サイクルが短縮されるという実用的なメリットが得られました。

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

--- a/src/pkg/regexp/exec_test.go
+++ b/src/pkg/regexp/exec_test.go
@@ -9,7 +9,6 @@ import (
 	"compress/bzip2"
 	"fmt"
 	"io"
-	"math/rand"
 	"os"
 	"path/filepath"
 	"regexp/syntax"
@@ -643,11 +642,17 @@ func makeText(n int) []byte {
 		return text[:n]
 	}
 	text = make([]byte, n)
+	x := ^uint32(0)
 	for i := range text {
-		if rand.Intn(30) == 0 {
+		x += x
+		x ^= 1
+		if int32(x) < 0 {
+			x ^= 0x88888eef
+		}
+		if x%31 == 0 {
 			text[i] = '\n'
 		} else {
-			text[i] = byte(rand.Intn(0x7E+1-0x20) + 0x20)
+			text[i] = byte(x%(0x7E+1-0x20) + 0x20)
 		}
 	}
 	return text

コアとなるコードの解説

変更はsrc/pkg/regexp/exec_test.goファイル内のmakeText関数に集中しています。この関数は、正規表現のベンチマークで使用されるランダムなバイト列を生成します。

1. math/randのインポート削除: - "math/rand" の行が削除され、math/randパッケージへの依存がなくなりました。

2. カスタムPRNGの導入: x := ^uint32(0): uint32型の変数xが導入され、初期シード値としてuint32の最大値（すべてのビットが1）で初期化されます。これは、擬似乱数生成器の内部状態となります。

3. 乱数生成ロジックの変更: ループ内で、以前はrand.Intn(30)とrand.Intn(0x7E+1-0x20)が使用されていましたが、これらがカスタムPRNGのロジックに置き換えられました。

   • x += x: xを2倍します（左シフト1ビットに相当）。
   • x ^= 1: xの最下位ビットを反転させます。
   • if int32(x) < 0 { x ^= 0x88888eef }: xをint32として解釈したときに負数であれば、特定の定数0x88888eefとXORします。これは、乱数の周期を長くし、より均一な分布を得るためのハッシュ操作です。
   • if x%31 == 0 { text[i] = '\n' }: 以前のrand.Intn(30) == 0の代わりに、xを31で割った余りが0の場合に改行文字を挿入します。これにより、約1/31の確率で改行が挿入されることになります。
   • else { text[i] = byte(x%(0x7E+1-0x20) + 0x20) }: 以前のbyte(rand.Intn(0x7E+1-0x20) + 0x20)の代わりに、カスタムPRNGのxを0x7E+1-0x20（印字可能ASCII文字の範囲のサイズ）で割った余りを計算し、0x20（スペース文字）を加えることで、印字可能なASCII文字を生成します。

この変更により、makeText関数は外部のmath/randパッケージに依存せず、自己完結型の高速な乱数生成ロジックを持つようになりました。これにより、特にレース検出器が有効な環境下でのベンチマーク実行時のパフォーマンスが大幅に向上しました。

関連リンク

• Go CL (Code Review): https://golang.org/cl/11564044
• Go Issue: https://code.google.com/p/go/issues/detail?id=5837 (現在はGitHubのIssueにリダイレクトされます: https://github.com/golang/go/issues/5837)

参考にした情報源リンク

• (Web検索は行っていませんが、必要に応じてここに記載します。)