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

このコミットは、Go言語の math/rand パッケージにおける乱数生成関数のパフォーマンス改善を目的としています。具体的には、Float32 および Float64 関数の高速化を図るもので、その実体は Int31n および Int63n 関数におけるリトライループの回避による最適化です。この変更により、Float32 は約19.45%、Float64 は約49.47%の性能向上がベンチマークで確認されています。

コミット

commit 1a936ebcfa4fadc0662feade965ea99d96aede77
Author: Russ Cox <rsc@golang.org>
Date:   Mon Mar 3 20:43:23 2014 -0500

    math/rand: speed up Float32, Float64
    
    Actually, speed up Int31n and Int63n by avoiding retry loop.
    
    benchmark           old ns/op    new ns/op    delta
    BenchmarkFloat32           32           26  -19.45%
    BenchmarkFloat64           46           23  -49.47%
    
    Fixes #7267.
    
    LGTM=bradfitz
    R=golang-codereviews, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/69980047

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

https://github.com/golang/go/commit/1a936ebcfa4fadc0662feade965ea99d96aede77

元コミット内容

math/rand: Float32, Float64 を高速化する 実際には、リトライループを回避することで Int31n と Int63n を高速化する。

ベンチマーク 旧 ns/op 新 ns/op 差分 BenchmarkFloat32 32 26 -19.45% BenchmarkFloat64 46 23 -49.47%

Fixes #7267.

変更の背景

このコミットの主な背景は、Go言語の math/rand パッケージにおける乱数生成関数のパフォーマンス改善です。特に、Float32 および Float64 といった浮動小数点数乱数生成の速度が課題となっていました。コミットメッセージに「実際には、リトライループを回避することで Int31n と Int63n を高速化する」とあるように、浮動小数点数乱数生成の基盤となる整数乱数生成関数 Int31n と Int63n の非効率性が根本原因でした。

これらの関数は、指定された範囲 [0, n) の乱数を生成する際に、従来のGoの実装では、生成された乱数が範囲外であった場合に再試行（リトライループ）を行う方式を採用していました。特に n が2の冪乗ではない場合、このリトライループが頻繁に発生し、パフォーマンスのボトルネックとなっていました。

この非効率性を解消し、より高速な乱数生成を実現するために、特定の条件下（n が2の冪乗の場合）でより効率的なビット演算による乱数生成手法を導入することが決定されました。これにより、Float32 や Float64 のような、内部でこれらの整数乱数生成関数を利用する関数全体のパフォーマンスが向上します。

また、コミットメッセージには Fixes #7267 と記載されていますが、公開されているGoのIssueトラッカーで直接 Issue #7267 を特定することはできませんでした。これは、非常に古いIssueであるか、内部的なトラッキング番号である可能性が考えられます。しかし、この記述から、何らかのパフォーマンス上の問題が報告されており、それに対する修正としてこのコミットが作成されたことが示唆されます。

前提知識の解説

1. 擬似乱数生成 (Pseudo-Random Number Generation, PRNG)

コンピュータで生成される乱数は、実際には完全にランダムではなく、初期値（シード）に基づいて決定論的なアルゴリズムによって生成される「擬似乱数」です。同じシードを与えれば、常に同じ乱数列が生成されます。math/rand パッケージは、このような擬似乱数を生成するための機能を提供します。

2. math/rand パッケージ

Go言語の標準ライブラリ math/rand は、様々な種類の擬似乱数を生成するための関数を提供します。

• Int31(): 0から (1<<31)-1 までの範囲の擬似乱数 int32 を生成します。
• Int63(): 0から (1<<63)-1 までの範囲の擬似乱数 int64 を生成します。
• Int31n(n int32): 0から n-1 までの範囲の擬数乱数 int32 を生成します。
• Int63n(n int64): 0から n-1 までの範囲の擬数乱数 int64 を生成します。
• Float32(): 0.0から1.0未満の範囲 [0.0, 1.0) の擬似乱数 float32 を生成します。
• Float64(): 0.0から1.0未満の範囲 [0.0, 1.0) の擬似乱数 float64 を生成します。

Float32() や Float64() は、内部的に Int63() などの整数乱数生成関数を利用して浮動小数点数乱数を生成します。例えば、Float64() は63ビットの整数乱数を生成し、それを (1 << 63) で割ることで [0.0, 1.0) の範囲に正規化します。

3. 乱数生成における「リトライループ」とバイアス

Int31n(n) や Int63n(n) のように、特定の範囲 [0, n) の乱数を生成する場合、単純に Int31() % n や Int63() % n とすると、乱数の分布に偏り（バイアス）が生じる可能性があります。これは、Int31() や Int63() が生成する最大値が n の倍数でない場合に、一部の剰余が他の剰余よりも頻繁に出現するためです。

このバイアスを避けるために、一般的には「リトライループ」（または「再抽選法」「棄却サンプリング」）が用いられます。これは、まずより広い範囲の乱数を生成し、その乱数が n の倍数に収まるような「有効な範囲」を超えていた場合に、再度乱数を生成し直すという方法です。

例えば、Int63n(n) の場合、Int63() が生成する [0, (1<<63)-1] の範囲のうち、n の倍数に収まる最大の範囲 [0, max] を計算します。そして、Int63() で生成した値 v が max を超えていた場合、v が max 以下になるまで再試行します。v が max 以下になったら、v % n を計算して結果を返します。この方法は、乱数の分布の均一性を保証しますが、再試行が発生するたびにオーバーヘッドが生じ、パフォーマンスが低下する可能性があります。

4. 2の冪乗とビット演算による最適化

n が2の冪乗（例: 2, 4, 8, 16, ...）である場合、剰余演算 % n はビット演算 & (n - 1) で置き換えることができます。

• n が2の冪乗であることは、n > 0 かつ (n & (n - 1)) == 0 という条件で効率的に判定できます。例えば、n = 8 (0b1000) の場合、n - 1 = 7 (0b0111) となり、8 & 7 = 0 となります。
• Int63() & (n - 1) のようにビットAND演算を行うと、Int63() が生成する63ビットの乱数の下位 log2(n) ビットだけが残り、結果として [0, n-1] の範囲の乱数が生成されます。この方法は、リトライループを必要とせず、非常に高速です。

このコミットは、この2の冪乗の特性を利用して、Int31n と Int63n のパフォーマンスを向上させています。

技術的詳細

このコミットの核心は、math/rand パッケージの Int31n および Int63n 関数における、引数 n が2の冪乗である場合の特殊な最適化です。

従来の Int31n および Int63n の実装では、指定された範囲 [0, n) の乱数を生成するために、以下のようなリトライループ（棄却サンプリング）が用いられていました。

// Int63n returns, as an int64, a non-negative pseudo-random number in [0, n).
// It panics if n <= 0.
func (r *Rand) Int63n(n int64) int64 {
	if n <= 0 {
		panic("invalid argument to Int63n")
	}
	// max は、(1<<63)-1 のうち、n の倍数に収まる最大の範囲
	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
	v := r.Int63() // 63ビットの乱数を生成
	for v > max {  // v が有効な範囲を超えていたら再試行
		v = r.Int63()
	}
	return v % n // 剰余を計算して結果を返す
}

このリトライループは、生成される乱数の分布の均一性を保証するために必要ですが、n の値によっては v > max の条件が頻繁に真となり、r.Int63() の呼び出しが繰り返されることでパフォーマンスが低下します。特に、n が (1 << 63) に近い大きな素数などの場合、max の範囲が狭くなり、リトライの頻度が高まります。

このコミットでは、このリトライループを回避するための最適化が導入されました。その方法は、n が2の冪乗であるかどうかを判定し、もしそうであれば、より高速なビット演算を利用するというものです。

具体的には、以下の条件が追加されました。

if n&(n-1) == 0 { // n is power of two, can mask
	return r.Int63() & (n - 1)
}

• n&(n-1) == 0: この条件は、n が2の冪乗であるかどうかを効率的に判定するためのビット演算です。
  • 例: n = 8 (0b1000) の場合、n-1 = 7 (0b0111)。8 & 7 = 0b1000 & 0b0111 = 0b0000 = 0。
  • 例: n = 6 (0b0110) の場合、n-1 = 5 (0b0101)。6 & 5 = 0b0110 & 0b0101 = 0b0100 != 0。
• return r.Int63() & (n - 1): n が2の冪乗である場合、r.Int63() で生成された63ビットの乱数と (n-1) のビットAND演算を行います。これにより、乱数の下位 log2(n) ビットだけが残り、結果として [0, n-1] の範囲の乱数が生成されます。この操作は、剰余演算 % n と同等の結果を、はるかに高速に得ることができます。

この最適化により、Int31n および Int63n は、n が2の冪乗であるという比較的頻繁に発生するケースにおいて、リトライループを完全に回避できるようになりました。

なぜこの変更が Float32 と Float64 の高速化につながるのかというと、Float32 や Float64 は内部的に Int63() などの整数乱数生成関数を呼び出して浮動小数点数乱数を生成しているためです。例えば、Float64() は Int63() を呼び出し、その結果を正規化して浮動小数点数に変換します。Int63() 自体は直接この最適化の対象ではありませんが、Int63n のような他の整数乱数生成関数が高速化されることで、乱数生成器全体の効率が向上し、間接的に Float32 や Float64 のパフォーマンスにも良い影響を与えたと考えられます。

コミットメッセージのベンチマーク結果が示すように、この最適化は Float32 で約19.45%、Float64 で約49.47%という顕著な性能向上をもたらしました。これは、特に浮動小数点数乱数を大量に必要とするシミュレーションや数値計算において、大きなメリットとなります。

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

src/pkg/math/rand/rand.go ファイルの Int63n および Int31n 関数に以下の変更が加えられました。

--- a/src/pkg/math/rand/rand.go
+++ b/src/pkg/math/rand/rand.go
@@ -60,6 +60,9 @@ func (r *Rand) Int63n(n int64) int64 {
 	if n <= 0 {
 		panic("invalid argument to Int63n")
 	}
+	if n&(n-1) == 0 { // n is power of two, can mask
+		return r.Int63() & (n - 1)
+	}
 	max := int64((1 << 63) - 1 - (1<<63)%uint64(n))
 	v := r.Int63()
 	for v > max {
@@ -74,6 +77,9 @@ func (r *Rand) Int31n(n int32) int32 {
 	if n <= 0 {
 		panic("invalid argument to Int31n")
 	}
+	if n&(n-1) == 0 { // n is power of two, can mask
+		return r.Int31() & (n - 1)
+	}
 	max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
 	v := r.Int31()
 	for v > max {

また、ベンチマークの追加として src/pkg/math/rand/rand_test.go に BenchmarkFloat64 が追加されています。

--- a/src/pkg/math/rand/rand_test.go
+++ b/src/pkg/math/rand/rand_test.go
@@ -376,6 +376,13 @@ func BenchmarkFloat32(b *testing.B) {
 	}
 }
 
+func BenchmarkFloat64(b *testing.B) {
+	r := New(NewSource(1))
+	for n := b.N; n > 0; n-- {
+		r.Float64()
+	}
+}
+
 func BenchmarkPerm3(b *testing.B) {
 	r := New(NewSource(1))
 	for n := b.N; n > 0; n-- {

コアとなるコードの解説

Int63n および Int31n の変更点

追加されたコードは、Int63n と Int31n の両関数において、引数 n が2の冪乗である場合に、従来の効率の悪いリトライループをスキップし、より高速なビット演算による乱数生成を行うためのものです。

// Int63n 関数内
if n&(n-1) == 0 { // n is power of two, can mask
	return r.Int63() & (n - 1)
}

1. if n&(n-1) == 0:

   • これは、n が2の冪乗（例: 1, 2, 4, 8, 16, ...）であるかを判定するための慣用的なビット演算です。
   • 2の冪乗のバイナリ表現は、常に1つのビットだけが1で、残りが0です（例: 8 は 0b1000）。
   • n-1 は、その1のビットより下位のビットがすべて1になります（例: 8-1=7 は 0b0111）。
   • したがって、n と n-1 のビットAND (&) を取ると、結果は常に 0 になります。
   • この条件が真の場合、n は2の冪乗であると判断されます。

2. return r.Int63() & (n - 1):

   • n が2の冪乗であると判定された場合、この行が実行されます。
   • r.Int63() は、0から (1<<63)-1 までの範囲の63ビットの擬似乱数を生成します。
   • (n - 1) は、n が2の冪乗であるため、バイナリ表現で下位のビットがすべて1のマスク値となります（例: n=8 なら n-1=7 (0b0111)）。
   • r.Int63() & (n - 1) のビットAND演算は、r.Int63() が生成した乱数の下位 log2(n) ビットだけを抽出します。これにより、結果として [0, n-1] の範囲の乱数が生成されます。
   • このビット演算は、従来の剰余演算 % n やリトライループよりもはるかに高速に実行できます。

Int31n 関数についても同様のロジックが適用され、r.Int31() & (n - 1) が使用されます。

この変更により、n が2の冪乗であるという比較的頻繁に発生するケースにおいて、乱数生成のオーバーヘッドが大幅に削減され、Int31n および Int63n のパフォーマンスが向上します。そして、これらの関数を内部的に利用する Float32 や Float64 といった浮動小数点数乱数生成関数も、その恩恵を受けて高速化されるという仕組みです。

rand_test.go の変更点

BenchmarkFloat64 が追加されました。これは、Float64() 関数のパフォーマンスを測定するためのベンチマークテストです。

func BenchmarkFloat64(b *testing.B) {
	r := New(NewSource(1)) // シードを固定した乱数生成器を作成
	for n := b.N; n > 0; n-- {
		r.Float64() // Float64() を繰り返し呼び出す
	}
}

このベンチマークは、Float64() 関数の呼び出しにかかる平均時間を測定し、変更前後のパフォーマンス比較を可能にします。コミットメッセージに記載されているベンチマーク結果は、この種のテストによって得られたものです。

関連リンク

• Go言語の公式ドキュメント: https://pkg.go.dev/math/rand
• Go言語の変更リスト (CL): https://golang.org/cl/69980047

参考にした情報源リンク

• Go's math/rand package documentation: https://pkg.go.dev/math/rand
• Explanation of power-of-two optimization in Int31n/Int63n: https://go.dev/src/math/rand/rand.go (Go source code comments)
• General information on Float32/Float64 implementation in Go: https://go.dev/src/math/rand/rand.go (Go source code comments)
• Stack Overflow discussions on Go's random number generation: https://stackoverflow.com/questions/tagged/go+random
• GeeksforGeeks articles on Go's math/rand package: https://www.geeksforgeeks.org/go-math-rand-package/
• TutorialsPoint on Go's math/rand package: https://www.tutorialspoint.com/go/go_math_rand_package.htm
• Blog post discussing Go's Float64 implementation details: https://brandur.org/go-float64 (Note: This is a third-party blog, not official Go documentation, but provides good insights.)
• Go issue tracker (general search for context, though #7267 was not directly found): https://github.com/golang/go/issues