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

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

このコミットは、Go言語のベンチマークスイートの一部である test/bench/shootout/mandelbrot.go ファイルに対する変更です。このファイルは、マンデルブロ集合の計算と描画を行うプログラムであり、主に異なるプログラミング言語間でのパフォーマンス比較を目的とした「The Computer Language Benchmarks Game」(通称「Shootout」)のベンチマークの一つとして使用されています。

コミット

このコミットの目的は、Go言語版のマンデルブロ集合ベンチマークコードを、そのC言語版のコードにより近づけることです。具体的には、C言語版がカウンターに浮動小数点数を使用していることに合わせて、Go言語版でも同様に浮動小数点数を使用するように変更されました。これにより、両言語間の比較がより公平で意味のあるものになるように調整されています。コミットメッセージによると、この変更がパフォーマンスに大きな影響を与えることはないとのことです。

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

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

元コミット内容

shootout: make mandelbrot.go more like mandelbrot.c

Surprise! The C code is using floating point values for its counters.
Its off the critical path, but the Go code and C code are supposed to
be as similar as possible to make comparisons meaningful.

It doesn't have a significant effect.

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

変更の背景

この変更の背景には、「The Computer Language Benchmarks Game」というプロジェクトの性質があります。このプロジェクトは、様々なプログラミング言語で同じアルゴリズムを実装し、その実行速度やメモリ使用量などを比較することで、各言語の特性やパフォーマンスを評価することを目的としています。

公平な比較を行うためには、各言語の実装が可能な限り同じアルゴリズムとロジックに従っている必要があります。このコミットでは、Go言語版のマンデルブロ集合ベンチマークが、対応するC言語版の実装と完全に一致していないことが発見されました。具体的には、C言語版がループカウンターや画像サイズを表す変数に浮動小数点数型を使用していたのに対し、Go言語版では整数型を使用していた点が異なっていました。

この差異は、マンデルブロ集合の計算におけるクリティカルパス(性能に最も影響を与える部分)には直接関係しないものの、ベンチマークの比較の「意味合い」を損なう可能性がありました。そのため、より厳密な比較を可能にするために、Go言語版もC言語版に合わせて浮動小数点数を使用するように修正されました。コミットメッセージにある「Surprise!」という表現は、このC言語版の意外な実装(カウンターに浮動小数点数を使用している点)に対する発見の驚きを示しています。

前提知識の解説

The Computer Language Benchmarks Game (Shootout)

「The Computer Language Benchmarks Game」は、異なるプログラミング言語のパフォーマンスを比較するためのベンチマークスイートです。このプロジェクトでは、様々なアルゴリズム(例: N-Queens、Fannkuch-redux、Mandelbrotなど)を複数の言語で実装し、それぞれの実行時間、メモリ使用量、コードサイズなどを測定します。目的は、特定のタスクにおいてどの言語がより効率的であるかを示すことであり、言語設計やコンパイラの最適化の進歩を追跡するのにも役立ちます。このプロジェクトは、しばしば「Shootout」とも呼ばれます。

マンデルブロ集合

マンデルブロ集合は、複素平面上の点の集合で、特定の反復関数 z_{n+1} = z_n^2 + c (ここで c は複素定数、z_0 = 0)が発散しないような c の値の集合として定義されます。この集合はフラクタル図形であり、非常に複雑で美しいパターンを生成します。

マンデルブロ集合の描画は、通常、以下の手順で行われます。

  1. 複素平面上の各点 c に対して、反復計算 z_{n+1} = z_n^2 + c を行います。
  2. z_n の絶対値が一定の限界値(例: 2.0)を超えた場合、その点 c はマンデルブロ集合の外部にあると判断し、発散するまでの反復回数を記録します。
  3. 反復回数が最大反復回数(例: 50回)に達しても発散しない場合、その点 c はマンデルブロ集合の内部にあると判断します。
  4. 発散までの反復回数に応じて色を割り当てることで、マンデルブロ集合の美しい画像が生成されます。

浮動小数点数と整数

  • 整数 (Integer): 小数点以下の部分を持たない数値です。コンピュータ内部では通常、固定されたビット数(例: 32ビット、64ビット)で正確に表現されます。計算は高速ですが、表現できる数値の範囲や精度には限界があります。
  • 浮動小数点数 (Floating-point number): 小数点以下の部分を持つ数値を近似的に表現するための形式です。IEEE 754標準に従って、符号部、指数部、仮数部で構成されます。これにより、非常に広い範囲の数値を表現できますが、精度には限界があり、特に大きな数値や非常に小さな数値を扱う際には丸め誤差が生じる可能性があります。計算は整数演算に比べて一般的に遅い傾向があります。

Go言語では、int はプラットフォーム依存の整数型(通常32ビットまたは64ビット)、float64 は倍精度浮動小数点数型(64ビット)です。

技術的詳細

このコミットの主要な変更点は、マンデルブロ集合の描画に使用される画像サイズ (w, h) およびピクセル座標 (x, y) の型を整数 (int) から倍精度浮動小数点数 (float64) に変更したことです。

元のコードでは、画像サイズ wh はコマンドライン引数から取得した整数値 *n を直接使用していました。ループカウンター xy も整数でした。

// 変更前
w := *n
h := *n
// ...
for y := 0; y < h; y++ {
    for x := 0; x < w; x++ {
        Cr := (2*float64(x)/float64(w) - 1.5)
        Ci := (2*float64(y)/float64(h) - 1.0)

変更後、whfloat64(*n) となり、*n(元の整数値)を float64 にキャストして初期化されます。同様に、ループ for y := 0; y < h; y++for x := 0; x < w; x++ のカウンター yx0.0 から始まる float64 型に変更されました。

// 変更後
w := float64(*n)
h := float64(*n)
// ...
for y := 0.0; y < h; y++ {
    for x := 0.0; x < w; x++ {
        Cr := (2*x/w - 1.5)
        Ci := (2*y/h - 1.0)

この変更により、マンデルブロ集合の複素数 CrCi の計算式 (2*x/w - 1.5) および (2*y/h - 1.0) において、x, y, w, h がすべて float64 型として扱われるようになり、明示的な float64() キャストが不要になりました。これは、C言語版のベンチマークコードが同様に浮動小数点数でこれらの値を扱っていたため、Go言語版もそれに合わせることで、より直接的な比較を可能にするためのものです。

ただし、出力フォーマットに関する部分には注意が必要です。 fmt.Fprintf(out, "P4\\n%d %d\\n", w, h)fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n) に変更されています。これは、画像ヘッダーの幅と高さは依然として整数値として出力する必要があるため、元の整数引数 *n を使用するように戻されたことを意味します。wh は内部計算で float64 として使用されますが、最終的な画像サイズは元の整数値に基づいています。

また、バイトアキュムレータのビットシフト計算 byte_acc <<= uint(8 - w%8)byte_acc <<= uint(8 - uint(*n)%8) に変更されています。ここでも、wfloat64 になったため、剰余演算子 % を使用するために uint(*n)(元の整数値)にキャストし直しています。これは、wfloat64 になったことで % 演算子が使えなくなったため、元の整数値 *n を利用して計算を継続するための措置です。

コミットメッセージにあるように、これらの変更は「クリティカルパスから外れている」ため、パフォーマンスに「大きな影響はない」とされています。これは、マンデルブロ集合の計算の大部分は Iter 回のループ内で行われる複素数演算であり、画像サイズや座標の型が整数か浮動小数点数かという点は、そのループの実行回数や内部演算の複雑さに比べて二次的な影響しかないためと考えられます。

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

--- a/test/bench/shootout/mandelbrot.go
+++ b/test/bench/shootout/mandelbrot.go
@@ -50,21 +50,21 @@ func main() {
 	out := bufio.NewWriter(os.Stdout)
 	defer out.Flush()

-	w := *n
-	h := *n
+	w := float64(*n)
+	h := float64(*n)
 	bit_num := 0
 	byte_acc := byte(0)
 	const Iter = 50
 	const Zero float64 = 0
 	const Limit = 2.0

-	fmt.Fprintf(out, "P4\\n%d %d\\n", w, h)
+	fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n)

-	for y := 0; y < h; y++ {
-		for x := 0; x < w; x++ {
+	for y := 0.0; y < h; y++ {
+		for x := 0.0; x < w; x++ {
 			Zr, Zi, Tr, Ti := Zero, Zero, Zero, Zero
-			Cr := (2*float64(x)/float64(w) - 1.5)
-			Ci := (2*float64(y)/float64(h) - 1.0)
+			Cr := (2*x/w - 1.5)
+			Ci := (2*y/h - 1.0)

 			for i := 0; i < Iter && (Tr+Ti <= Limit*Limit); i++ {
 				Zi = 2*Zr*Zi + Ci
@@ -85,7 +85,7 @@ func main() {
 				byte_acc = 0
 				bit_num = 0
 			} else if x == w-1 {
-				byte_acc <<= uint(8 - w%8)
+				byte_acc <<= uint(8 - uint(*n)%8)
 				out.WriteByte(byte_acc)
 				byte_acc = 0
 				bit_num = 0

コアとなるコードの解説

  1. w := *n から w := float64(*n) へ、h も同様:

    • 変更前は、画像幅 w と高さ h は、コマンドライン引数から渡される整数値 *n をそのまま整数型として使用していました。
    • 変更後は、*nfloat64 型に明示的にキャストして wh を初期化しています。これにより、これらの変数が浮動小数点数として扱われるようになります。これは、C言語版のベンチマークがこれらの値を浮動小数点数として扱っていたことに合わせたものです。
  2. fmt.Fprintf(out, "P4\\n%d %d\\n", w, h) から fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n):

    • PPM (Portable Pixmap) 形式の画像ヘッダーを出力する部分です。PPMのP4形式はバイナリ形式で、ヘッダーには画像の幅と高さを整数で指定する必要があります。
    • 変更前は wh を直接渡していましたが、これらが float64 になったため、%d フォーマット指定子と型が一致しなくなります。
    • 変更後は、元の整数値である *n を直接渡すことで、正しい整数形式で幅と高さが出力されるように修正されています。これは、内部計算で whfloat64 であっても、最終的な画像サイズは元の整数入力に基づくべきであることを示しています。
  3. for y := 0; y < h; y++ から for y := 0.0; y < h; y++ へ、x も同様:

    • 画像ピクセルを走査するための二重ループのカウンター yx の初期値が 0 から 0.0 に変更され、型が float64 になりました。
    • これにより、ループの条件 y < hx < w の比較も浮動小数点数同士で行われるようになります。
  4. Cr := (2*float64(x)/float64(w) - 1.5) から Cr := (2*x/w - 1.5) へ、Ci も同様:

    • マンデルブロ集合の計算における複素数 c の実部 Cr と虚部 Ci を計算する部分です。
    • 変更前は、整数型の x, y, w, h を明示的に float64 にキャストしてから計算を行っていました。
    • 変更後は、x, y, w, h 自体が float64 型になったため、冗長な float64() キャストが不要になり、コードが簡潔になりました。計算自体は以前と同じ浮動小数点演算で行われます。
  5. byte_acc <<= uint(8 - w%8) から byte_acc <<= uint(8 - uint(*n)%8):

    • これは、PPM P4形式のビットマップデータをバイト単位で出力する際に、行の終端で残りのビットをパディングするためのシフト量を計算する部分です。
    • 変更前は w%8 を使用していましたが、wfloat64 になったため、浮動小数点数に対して剰余演算子 % を直接適用することはできません。
    • 変更後は、元の整数値 *nuint にキャストし、それに対して %8 演算を行うことで、正しいシフト量を計算しています。これは、画像データのバイトパディングは元の整数幅に基づいて行われるべきであるためです。

これらの変更は、Go言語版のマンデルブロベンチマークをC言語版の挙動に合わせることで、ベンチマークの公平性を高めることを目的としています。

関連リンク

参考にした情報源リンク

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

このコミットは、Go言語のベンチマークスイートの一部である test/bench/shootout/mandelbrot.go ファイルに対する変更です。このファイルは、マンデルブロ集合の計算と描画を行うプログラムであり、主に異なるプログラミング言語間でのパフォーマンス比較を目的とした「The Computer Language Benchmarks Game」(通称「Shootout」)のベンチマークの一つとして使用されています。

コミット

このコミットの目的は、Go言語版のマンデルブロ集合ベンチマークコードを、そのC言語版のコードにより近づけることです。具体的には、C言語版がカウンターに浮動小数点数を使用していることに合わせて、Go言語版でも同様に浮動小数点数を使用するように変更されました。これにより、両言語間の比較がより公平で意味のあるものになるように調整されています。コミットメッセージによると、この変更がパフォーマンスに大きな影響を与えることはないとのことです。

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

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

元コミット内容

shootout: make mandelbrot.go more like mandelbrot.c

Surprise! The C code is using floating point values for its counters.
Its off the critical path, but the Go code and C code are supposed to
be as similar as possible to make comparisons meaningful.

It doesn't have a significant effect.

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

変更の背景

この変更の背景には、「The Computer Language Benchmarks Game」というプロジェクトの性質があります。このプロジェクトは、様々なプログラミング言語で同じアルゴリズムを実装し、その実行速度やメモリ使用量などを比較することで、各言語の特性やパフォーマンスを評価することを目的としています。

公平な比較を行うためには、各言語の実装が可能な限り同じアルゴリズムとロジックに従っている必要があります。このコミットでは、Go言語版のマンデルブロ集合ベンチマークが、対応するC言語版の実装と完全に一致していないことが発見されました。具体的には、C言語版がループカウンターや画像サイズを表す変数に浮動小数点数型を使用していたのに対し、Go言語版では整数型を使用していた点が異なっていました。

この差異は、マンデルブロ集合の計算におけるクリティカルパス(性能に最も影響を与える部分)には直接関係しないものの、ベンチマークの比較の「意味合い」を損なう可能性がありました。そのため、より厳密な比較を可能にするために、Go言語版もC言語版に合わせて浮動小数点数を使用するように修正されました。コミットメッセージにある「Surprise!」という表現は、このC言語版の意外な実装(カウンターに浮動小数点数を使用している点)に対する発見の驚きを示しています。

前提知識の解説

The Computer Language Benchmarks Game (Shootout)

「The Computer Language Benchmarks Game」は、異なるプログラミング言語のパフォーマンスを比較するためのベンチマークスイートです。このプロジェクトでは、様々なアルゴリズム(例: N-Queens、Fannkuch-redux、Mandelbrotなど)を複数の言語で実装し、それぞれの実行時間、メモリ使用量、コードサイズなどを測定します。目的は、特定のタスクにおいてどの言語がより効率的であるかを示すことであり、言語設計やコンパイラの最適化の進歩を追跡するのにも役立ちます。このプロジェクトは、しばしば「Shootout」とも呼ばれます。

マンデルブロ集合

マンデルブロ集合は、複素平面上の点の集合で、特定の反復関数 z_{n+1} = z_n^2 + c (ここで c は複素定数、z_0 = 0)が発散しないような c の値の集合として定義されます。この集合はフラクタル図形であり、非常に複雑で美しいパターンを生成します。

マンデルブロ集合の描画は、通常、以下の手順で行われます。

  1. 複素平面上の各点 c に対して、反復計算 z_{n+1} = z_n^2 + c を行います。
  2. z_n の絶対値が一定の限界値(例: 2.0)を超えた場合、その点 c はマンデルブロ集合の外部にあると判断し、発散するまでの反復回数を記録します。
  3. 反復回数が最大反復回数(例: 50回)に達しても発散しない場合、その点 c はマンデルブロ集合の内部にあると判断します。
  4. 発散までの反復回数に応じて色を割り当てることで、マンデルブロ集合の美しい画像が生成されます。

浮動小数点数と整数

  • 整数 (Integer): 小数点以下の部分を持たない数値です。コンピュータ内部では通常、固定されたビット数(例: 32ビット、64ビット)で正確に表現されます。計算は高速ですが、表現できる数値の範囲や精度には限界があります。
  • 浮動小数点数 (Floating-point number): 小数点以下の部分を持つ数値を近似的に表現するための形式です。IEEE 754標準に従って、符号部、指数部、仮数部で構成されます。これにより、非常に広い範囲の数値を表現できますが、精度には限界があり、特に大きな数値や非常に小さな数値を扱う際には丸め誤差が生じる可能性があります。計算は整数演算に比べて一般的に遅い傾向があります。

Go言語では、int はプラットフォーム依存の整数型(通常32ビットまたは64ビット)、float64 は倍精度浮動小数点数型(64ビット)です。

技術的詳細

このコミットの主要な変更点は、マンデルブロ集合の描画に使用される画像サイズ (w, h) およびピクセル座標 (x, y) の型を整数 (int) から倍精度浮動小数点数 (float64) に変更したことです。

元のコードでは、画像サイズ wh はコマンドライン引数から取得した整数値 *n を直接使用していました。ループカウンター xy も整数でした。

// 変更前
w := *n
h := *n
// ...
for y := 0; y < h; y++ {
    for x := 0; x < w; x++ {
        Cr := (2*float64(x)/float64(w) - 1.5)
        Ci := (2*float64(y)/float64(h) - 1.0)

変更後、whfloat64(*n) となり、*n(元の整数値)を float64 にキャストして初期化されます。同様に、ループ for y := 0; y < h; y++for x := 0; x < w; x++ のカウンター yx0.0 から始まる float64 型に変更されました。

// 変更後
w := float64(*n)
h := float64(*n)
// ...
for y := 0.0; y < h; y++ {
    for x := 0.0; x < w; x++ {
        Cr := (2*x/w - 1.5)
        Ci := (2*y/h - 1.0)

この変更により、マンデルブロ集合の複素数 CrCi の計算式 (2*x/w - 1.5) および (2*y/h - 1.0) において、x, y, w, h がすべて float64 型として扱われるようになり、明示的な float64() キャストが不要になりました。これは、C言語版のベンチマークコードが同様に浮動小数点数でこれらの値を扱っていたため、Go言語版もそれに合わせることで、より直接的な比較を可能にするためのものです。

ただし、出力フォーマットに関する部分には注意が必要です。 fmt.Fprintf(out, "P4\\n%d %d\\n", w, h)fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n) に変更されています。これは、画像ヘッダーの幅と高さは依然として整数値として出力する必要があるため、元の整数引数 *n を使用するように戻されたことを意味します。wh は内部計算で float64 として使用されますが、最終的な画像サイズは元の整数値に基づいています。

また、バイトアキュムレータのビットシフト計算 byte_acc <<= uint(8 - w%8)byte_acc <<= uint(8 - uint(*n)%8) に変更されています。ここでも、wfloat64 になったため、剰余演算子 % を使用するために uint(*n)(元の整数値)にキャストし直しています。これは、wfloat64 になったことで % 演算子が使えなくなったため、元の整数値 *n を利用して計算を継続するための措置です。

コミットメッセージにあるように、これらの変更は「クリティカルパスから外れている」ため、パフォーマンスに「大きな影響はない」とされています。これは、マンデルブロ集合の計算の大部分は Iter 回のループ内で行われる複素数演算であり、画像サイズや座標の型が整数か浮動小数点数かという点は、そのループの実行回数や内部演算の複雑さに比べて二次的な影響しかないためと考えられます。

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

--- a/test/bench/shootout/mandelbrot.go
+++ b/test/bench/shootout/mandelbrot.go
@@ -50,21 +50,21 @@ func main() {
 	out := bufio.NewWriter(os.Stdout)
 	defer out.Flush()

-	w := *n
-	h := *n
+	w := float64(*n)
+	h := float64(*n)
 	bit_num := 0
 	byte_acc := byte(0)
 	const Iter = 50
 	const Zero float64 = 0
 	const Limit = 2.0

-	fmt.Fprintf(out, "P4\\n%d %d\\n", w, h)
+	fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n)

-	for y := 0; y < h; y++ {
-		for x := 0; x < w; x++ {
+	for y := 0.0; y < h; y++ {
+		for x := 0.0; x < w; x++ {
 			Zr, Zi, Tr, Ti := Zero, Zero, Zero, Zero
-			Cr := (2*float64(x)/float64(w) - 1.5)
-			Ci := (2*float64(y)/float64(h) - 1.0)
+			Cr := (2*x/w - 1.5)
+			Ci := (2*y/h - 1.0)

 			for i := 0; i < Iter && (Tr+Ti <= Limit*Limit); i++ {
 				Zi = 2*Zr*Zi + Ci
@@ -85,7 +85,7 @@ func main() {
 				byte_acc = 0
 				bit_num = 0
 			} else if x == w-1 {
-				byte_acc <<= uint(8 - w%8)
+				byte_acc <<= uint(8 - uint(*n)%8)
 				out.WriteByte(byte_acc)
 				byte_acc = 0
 				bit_num = 0

コアとなるコードの解説

  1. w := *n から w := float64(*n) へ、h も同様:

    • 変更前は、画像幅 w と高さ h は、コマンドライン引数から渡される整数値 *n をそのまま整数型として使用していました。
    • 変更後は、*nfloat64 型に明示的にキャストして wh を初期化しています。これにより、これらの変数が浮動小数点数として扱われるようになります。これは、C言語版のベンチマークがこれらの値を浮動小数点数として扱っていたことに合わせたものです。
  2. fmt.Fprintf(out, "P4\\n%d %d\\n", w, h) から fmt.Fprintf(out, "P4\\n%d %d\\n", *n, *n):

    • PPM (Portable Pixmap) 形式の画像ヘッダーを出力する部分です。PPMのP4形式はバイナリ形式で、ヘッダーには画像の幅と高さを整数で指定する必要があります。
    • 変更前は wh を直接渡していましたが、これらが float64 になったため、%d フォーマット指定子と型が一致しなくなります。
    • 変更後は、元の整数値である *n を直接渡すことで、正しい整数形式で幅と高さが出力されるように修正されています。これは、内部計算で whfloat64 であっても、最終的な画像サイズは元の整数入力に基づくべきであることを示しています。
  3. for y := 0; y < h; y++ から for y := 0.0; y < h; y++ へ、x も同様:

    • 画像ピクセルを走査するための二重ループのカウンター yx の初期値が 0 から 0.0 に変更され、型が float64 になりました。
    • これにより、ループの条件 y < hx < w の比較も浮動小数点数同士で行われるようになります。
  4. Cr := (2*float64(x)/float64(w) - 1.5) から Cr := (2*x/w - 1.5) へ、Ci も同様:

    • マンデルブロ集合の計算における複素数 c の実部 Cr と虚部 Ci を計算する部分です。
    • 変更前は、整数型の x, y, w, h を明示的に float64 にキャストしてから計算を行っていました。
    • 変更後は、x, y, w, h 自体が float64 型になったため、冗長な float64() キャストが不要になり、コードが簡潔になりました。計算自体は以前と同じ浮動小数点演算で行われます。
  5. byte_acc <<= uint(8 - w%8) から byte_acc <<= uint(8 - uint(*n)%8):

    • これは、PPM P4形式のビットマップデータをバイト単位で出力する際に、行の終端で残りのビットをパディングするためのシフト量を計算する部分です。
    • 変更前は w%8 を使用していましたが、wfloat64 になったため、浮動小数点数に対して剰余演算子 % を直接適用することはできません。
    • 変更後は、元の整数値 *nuint にキャストし、それに対して %8 演算を行うことで、正しいシフト量を計算しています。これは、画像データのバイトパディングは元の整数幅に基づいて行われるべきであるためです。

これらの変更は、Go言語版のマンデルブロベンチマークをC言語版の挙動に合わせることで、ベンチマークの公平性を高めることを目的としています。

関連リンク

参考にした情報源リンク