Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリsortパッケージのベンチマークテストにおいて、乱数生成器をより高速なものに変更するものです。これにより、特定の環境（darwin-amd64-raceビルダー）でのベンチマークの破損が修正されました。

コミット

commit 916937274938adf506040b1118e1e20f990cf2b2
Author: Dave Cheney <dave@cheney.net>
Date:   Thu Aug 29 13:21:21 2013 +1000

    sort: use a very fast random generator for benchmarks
    
    Adapted from https://golang.org/cl/11564044.
    
    Fixes breakage of darwin-amd64-race builder.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/13352045

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

https://github.com/golang/go/commit/916937274938adf506040b1118e1e20f990cf2b2

元コミット内容

sort: use a very fast random generator for benchmarks

このコミットは、sortパッケージのベンチマークテストで使用される乱数生成器を、非常に高速なものに変更することを目的としています。これは、以前の変更（https://golang.org/cl/11564044）から適応されたものであり、darwin-amd64-raceビルダーでの破損を修正します。

変更の背景

この変更の主な背景は、darwin-amd64-raceビルダーにおけるベンチマークテストの破損です。Goプロジェクトでは、様々なプラットフォームや設定（例えば、データ競合検出器が有効なraceビルド）でコードが正しく動作することを確認するために、自動化されたビルダーシステムを使用しています。

以前のベンチマークコードでは、rand.Intn関数を使用していましたが、これが特定の環境（特にdarwin-amd64-race）で問題を引き起こしていました。rand.Intnは、デフォルトのグローバルな乱数生成器を使用しており、これは並行アクセスに対して保護されていません。raceビルドでは、複数のゴルーチンが同時に乱数生成器にアクセスしようとすると、データ競合が発生し、ベンチマークが不安定になったり、クラッシュしたりする可能性がありました。

このコミットは、ベンチマークの目的（ソートアルゴリズムの性能測定）において、高品質な乱数（暗号学的に安全である必要はない）よりも、高速な乱数生成が求められるという認識に基づいています。そのため、ベンチマーク専用の、より単純で高速な擬似乱数生成器を導入することで、この問題を解決しようとしました。

前提知識の解説

Go言語のsortパッケージ

Go言語の標準ライブラリには、sortパッケージが含まれています。このパッケージは、スライスやユーザー定義のコレクションをソートするための汎用的なインターフェースとアルゴリズムを提供します。sort.Interfaceインターフェースを実装することで、任意のデータ型をソートできます。ベンチマークテストは、これらのソートアルゴリズムの性能を測定するために行われます。

Go言語のベンチマーク

Go言語には、標準でベンチマークテストを記述・実行するためのフレームワークが組み込まれています。testingパッケージの一部として提供され、go test -bench=.コマンドで実行できます。ベンチマーク関数はBenchmarkXxxという命名規則に従い、*testing.B型の引数を取ります。b.Nはベンチマークが実行されるイテレーション回数を示し、b.StopTimer()やb.StartTimer()を使って測定対象のコードブロックを制御します。

Go言語のrandパッケージと擬似乱数生成器 (PRNG)

Go言語の標準ライブラリには、math/randパッケージがあり、擬似乱数生成器（PRNG: Pseudo-Random Number Generator）を提供します。PRNGは、初期シード値に基づいて決定論的なアルゴリズムで乱数のように見える数列を生成します。

  • rand.Intn(n int): [0, n)の範囲の非負の擬似乱数整数を返します。
  • グローバルな乱数生成器: math/randパッケージのトップレベル関数（例: rand.Intn, rand.Float64）は、デフォルトで共有されるグローバルな乱数生成器を使用します。このグローバルな生成器は、並行アクセスに対して保護されていません。つまり、複数のゴルーチンが同時にこれらの関数を呼び出すと、データ競合が発生する可能性があります。
  • シード: PRNGはシード値から開始します。同じシード値を使用すると、常に同じ数列が生成されます。

darwin-amd64-raceビルダー

GoプロジェクトのCI/CD（継続的インテグレーション/継続的デリバリー）システムの一部として、様々な環境でテストが実行されます。darwin-amd64-raceは、以下の要素を組み合わせたビルド環境を指します。

  • darwin: macOSオペレーティングシステム。
  • amd64: 64ビットIntel/AMDアーキテクチャ。
  • race: Goのデータ競合検出器（Race Detector）が有効になっているビルド。Race Detectorは、並行処理におけるデータ競合を検出し、デバッグを支援するためのツールです。データ競合が発生すると、プログラムの動作が不安定になったり、予期せぬ結果になったりすることがあります。

この環境でベンチマークが破損したということは、乱数生成器への並行アクセスがデータ競合を引き起こし、Race Detectorによって検出されたか、あるいは競合によってベンチマークの結果が不安定になったことを示唆しています。

Xorshiftアルゴリズム

Xorshiftは、George Marsagliaによって開発された擬似乱数生成器のファミリーです。その名の通り、XOR（排他的論理和）とシフト演算を組み合わせて乱数を生成します。非常に高速で実装が単純なため、シミュレーションやゲームなど、高品質な乱数よりも速度が重視されるアプリケーションでよく使用されます。暗号学的に安全ではありませんが、ベンチマークのような用途には十分な統計的特性を持つことが多いです。

技術的詳細

このコミットで導入された乱数生成器は、Xorshiftアルゴリズムの一種です。具体的には、単一のuint32変数xを状態として持ち、以下の操作を繰り返すことで次の乱数を生成します。

  1. x += x (左シフト1ビット、または2倍)
  2. x ^= 1 (XOR 1)
  3. if int32(x) < 0 { x ^= 0x88888eef } (特定の条件でのXOR)

このシーケンスは、非常に少ないCPUサイクルで実行できるため、従来のrand.Intn（内部でより複雑なロジックやロックを伴う可能性がある）よりもはるかに高速です。

各操作の解説:

  • x += x: これはx <<= 1と同じ効果を持ちます。xの値を左に1ビットシフトします。これにより、ビットが循環的に移動し、乱数としての特性を向上させます。
  • x ^= 1: xの最下位ビットを反転させます。これにより、生成される数値の偶奇性が交互に変化し、より均等な分布に寄与します。
  • if int32(x) < 0 { x ^= 0x88888eef }: この条件付きXORは、Xorshiftアルゴリズムのバリエーションでよく見られるものです。int32(x) < 0は、xの最上位ビットがセットされている（つまり、符号ビットが1である）ことを意味します。この条件が満たされた場合に、特定の定数0x88888eefとXORを取ることで、乱数系列の周期を長くし、統計的特性を改善します。この定数は、Xorshiftアルゴリズムの設計において、良好な乱数特性を持つように選ばれたマジックナンバーです。

最終的に、生成されたxの値はuint32(n/5)で剰余演算され、data[i].aに代入されます。これは、ソート対象のデータが特定の範囲内の値を持つようにするためです。

この高速な乱数生成器は、ベンチマークの目的（ソートアルゴリズム自体の性能を測定すること）に特化しており、乱数生成のオーバーヘッドを最小限に抑えることで、より正確なベンチマーク結果を得ることを可能にします。また、グローバルな乱数生成器を使用しないため、データ競合の問題も回避できます。

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

--- a/src/pkg/sort/sort_test.go
+++ b/src/pkg/sort/sort_test.go
@@ -520,10 +520,16 @@ func TestCountSortOps(t *testing.T)   { countOps(t, Sort, "Sort  ") }
 func bench(b *testing.B, size int, algo func(Interface), name string) {
  	b.StopTimer()
  	data := make(intPairs, size)
+	x := ^uint32(0)
  	for i := 0; i < b.N; i++ {\n \t\tfor n := size - 3; n <= size+3; n++ {\n \t\t\tfor i := 0; i < len(data); i++ {\n-\t\t\t\tdata[i].a = rand.Intn(n / 5)\n+\t\t\t\tx += x\n+\t\t\t\tx ^= 1\n+\t\t\t\tif int32(x) < 0 {\n+\t\t\t\t\tx ^= 0x88888eef\n+\t\t\t\t}\n+\t\t\t\tdata[i].a = int(x % uint32(n/5))\n \t\t\t}\n \t\t\tdata.initB()\n \t\t\tb.StartTimer()\n```

## コアとなるコードの解説

変更は`src/pkg/sort/sort_test.go`ファイルの`bench`関数内で行われています。この関数は、ソートアルゴリズムのベンチマークを実行するための共通のロジックを含んでいます。

**変更前:**

```go
				data[i].a = rand.Intn(n / 5)

以前は、math/randパッケージのグローバルな乱数生成器を使用していました。rand.Intn(n / 5)は、[0, n/5)の範囲の乱数を生成し、それをdata[i].aに代入していました。このアプローチは、前述の通り、並行環境でのデータ競合のリスクがありました。

変更後:

+	x := ^uint32(0)
 	for i := 0; i < b.N; i++ {
 		for n := size - 3; n <= size+3; n++ {
 			for i := 0; i < len(data); i++ {
+				x += x
+				x ^= 1
+				if int32(x) < 0 {
+					x ^= 0x88888eef
+				}
+				data[i].a = int(x % uint32(n/5))
 			}
 			data.initB()
 			b.StartTimer()

  1. x := ^uint32(0):

    • ^uint32(0)は、uint32型の0のビットを反転させた値、つまりすべてのビットが1であるuint32の最大値（0xFFFFFFFF）をxの初期シードとして設定します。これは、乱数生成器の初期状態を決定します。

  2. x += x:

    • 現在のxの値を2倍します。これはビット演算の左シフト（x <<= 1）と同じ効果を持ちます。これにより、xのビットパターンが変化し、次の乱数生成の基礎となります。

  3. x ^= 1:

    • xと1の排他的論理和（XOR）を取ります。これにより、xの最下位ビットが反転します。これは、乱数系列の周期性と分布を改善するための一般的な手法です。

  4. if int32(x) < 0 { x ^= 0x88888eef }:

    • xをint32型にキャストし、その値が負であるかどうかをチェックします。uint32の値をint32にキャストした場合、最上位ビットが1であれば負の値として解釈されます。
    • もし負であれば（つまり、uint32の最上位ビットが1であれば）、xとマジックナンバー0x88888eefの排他的論理和を取ります。この条件付きXORは、Xorshiftアルゴリズムのバリエーションで、乱数系列の統計的品質を向上させ、周期を長くするために使用されます。

  5. data[i].a = int(x % uint32(n/5)):

    • 新しく生成されたxの値をuint32(n/5)で割った余りを計算し、それをint型に変換してdata[i].aに代入します。これにより、ソート対象のデータが[0, n/5)の範囲に収まるようにします。

この変更により、ベンチマークテストは、グローバルな乱数生成器のデータ競合問題から解放され、より高速かつ安定した乱数生成が可能になりました。

関連リンク

参考にした情報源リンク