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

このコミットは、Go言語の標準ライブラリ math/big パッケージ内の arith.go ファイルに対して行われた変更を記録しています。具体的には、divWW_g 関数内で使用されていた goto ステートメントを for ループに置き換えることで、コードの可読性と特定の環境（GopherJS）でのパフォーマンスを改善することを目的としています。

コミット

commit 547a82c36cbeb59544943848ec6c5cadbe0b770a
Author: Richard Musiol <mail@richard-musiol.de>
Date:   Thu Feb 6 14:44:30 2014 -0800

    math/big: replace goto with for loop
    I just added support for goto statements to my GopherJS project and now I am trying to get rid of my patches. These occurrences of goto however are a bit problematic:
    GopherJS has to emulate gotos, so there is some performance drawback when doing so. In this case the drawback is major, since this is a core function of math/big which is called quite often. Additionally I can't see any reason here why the implementation with gotos should be preferred over my proposal.
    That's why I would kindly ask to include this patch, even though it is functional equivalent to the existing code.

    LGTM=bradfitz
    R=golang-codereviews, bradfitz
    CC=golang-codereviews
    https://golang.org/cl/55470046

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

https://github.com/golang/go/commit/547a82c36cbeb595449438438ec6c5cadbe0b770a

元コミット内容

このコミットは、math/big パッケージの arith.go ファイルにおいて、divWW_g 関数内の goto ステートメントを for ループに置き換えるものです。コミットメッセージによると、この変更は機能的には既存のコードと等価ですが、GopherJSプロジェクトにおける goto のエミュレーションによるパフォーマンス上の問題に対処するために提案されました。特に、math/big のような頻繁に呼び出されるコア関数での goto の使用は、GopherJS環境で大きな性能低下を引き起こす可能性があったため、より効率的な for ループへの置き換えが求められました。

変更の背景

変更の主な背景は、コミット作者が開発していたGopherJSプロジェクトにおけるパフォーマンス上の課題です。

1. GopherJSにおけるgotoのエミュレーション: GopherJSはGoコードをJavaScriptにコンパイルするプロジェクトです。JavaScriptにはGoのgotoステートメントに直接対応する機能がないため、GopherJSはgotoをエミュレートする必要があります。このエミュレーションは、特に頻繁に実行されるコードパスにおいて、パフォーマンス上のオーバーヘッドを発生させます。
2. math/bigのコア関数: math/bigパッケージは、任意精度の算術演算を提供するGoの標準ライブラリであり、その中の関数は多くの数値計算で頻繁に利用されます。divWW_g関数は、大きな数値の除算における基本的な操作の一部であり、その性能は全体に影響します。
3. パフォーマンスの重要性: divWW_gのようなコア関数でgotoが使用されていると、GopherJSでコンパイルされた際にそのエミュレーションコストが積み重なり、アプリケーション全体のパフォーマンスに大きな悪影響を及ぼす可能性がありました。
4. 機能的等価性: コミット作者は、gotoを使用しない実装が機能的に既存のコードと等価であり、gotoを使用する利点が見当たらないと主張しています。このため、パフォーマンス上のデメリットを解消しつつ、コードの意図をより明確にするforループへの置き換えが正当化されました。

これらの理由から、Go標準ライブラリのコードベースからgotoを排除し、より一般的なforループに置き換えることで、GopherJSのような特定のコンパイルターゲットでの性能問題を緩和し、同時にコードの可読性を向上させることを目指しました。

前提知識の解説

このコミットを理解するためには、以下の技術的背景知識が必要です。

1. Go言語のgotoステートメント:

   • Go言語にはgotoステートメントが存在しますが、他の多くのプログラミング言語と同様に、その使用は推奨されません。gotoはプログラムの実行フローを非線形にジャンプさせるため、コードの可読性を著しく低下させ、デバッグを困難にし、「スパゲッティコード」を生み出す原因となることがあります。
   • Goでは、forループ、if/else、switch、break、continue、returnなどの構造化された制御フロー構文が豊富に用意されており、ほとんどの場合、gotoを使わずに同等かそれ以上に明確なロジックを記述できます。
   • gotoが許容される稀なケースとしては、エラーハンドリングのために複数のネストされたループや条件分岐から一箇所にジャンプする場合などが挙げられますが、それでも多くの場合、関数化やdeferステートメントで代替可能です。

2. math/bigパッケージ:

   • math/bigはGo言語の標準ライブラリの一つで、任意精度の整数（Int）、有理数（Rat）、浮動小数点数（Float）を扱うためのパッケージです。
   • 通常のGoの組み込み数値型（int, int64, float64など）は固定のビット幅を持つため、表現できる数値の範囲に限界があります。これに対し、math/bigの型は必要に応じてメモリを動的に割り当てることで、理論上はメモリが許す限り任意の大きさの数値を扱うことができます。
   • このパッケージは、暗号学、科学計算、金融アプリケーションなど、高い精度や大きな数値を扱う必要がある場面で利用されます。
   • 内部的には、これらの任意精度数値は、Word型（通常はuintまたはuint64）の配列として表現され、基本的な算術演算（加算、減算、乗算、除算など）は、これらのWord配列に対する低レベルな操作として実装されています。

3. GopherJS:

   • GopherJSは、Go言語のコードをJavaScriptにトランスパイル（変換）するコンパイラです。これにより、Goで書かれたアプリケーションをWebブラウザ上で実行できるようになります。
   • GopherJSはGoのランタイムと標準ライブラリの大部分をJavaScriptに変換するため、Goの豊富なエコシステムをWebフロントエンド開発に活用できるという利点があります。
   • しかし、GoとJavaScriptの言語機能には差異があり、特にgotoのようなJavaScriptに直接対応する構文がないGoの機能は、GopherJSによってエミュレートされる必要があります。このエミュレーションは、追加のJavaScriptコードやロジックを生成することで実現され、結果として実行時のパフォーマンスオーバーヘッドにつながることがあります。

4. Word型と_B2定数:

   • math/bigパッケージでは、大きな数値をWord型のスライスとして扱います。Word型は通常、システムのネイティブなワードサイズ（32ビットまたは64ビット）に対応する符号なし整数型（uintまたはuint64）です。
   • _B2定数は、Word型の半分（またはそれ以下）のビット幅を持つ数値の最大値を表すために使用されます。例えば、Wordがuint64（64ビット）の場合、_B2は1 << 32（2の32乗）またはそれに関連する値になることが多いです。これは、多倍長整数演算において、ワードをさらに小さな「半ワード」に分割して計算を行う際に用いられることがあります。divWW_g関数は、2つのWordを1つのWordで割る操作（u1, u0をvで割る）を行うため、このような低レベルなビット操作やワード分割の概念が重要になります。

これらの知識を前提として、コミットはgotoがGopherJSで問題を引き起こすこと、math/bigが性能が重要な低レベルな算術演算を行うこと、そしてgotoをforループに置き換えることが機能的に等価であり、より良い選択肢であるという文脈で理解できます。

技術的詳細

このコミットの技術的詳細は、math/bigパッケージのdivWW_g関数における除算アルゴリズムの最適化と、gotoステートメントからforループへの移行による制御フローの改善にあります。

divWW_g関数は、u1*B + u0という形式の2ワードの数値を、1ワードの数値vで除算し、商qと剰余rを計算するGoの内部関数です。ここでBはWord型の基数（通常は2^32または2^64）です。この関数は、多倍長整数除算アルゴリズムの基本的な構成要素であり、頻繁に呼び出されます。

元のコードでは、除算の試行商（trial quotient）を調整するためにgotoステートメントが使用されていました。これは、Knuthの「The Art of Computer Programming」Volume 2, Chapter 4.3.1, Algorithm D (Division of Nonnegative Integers) に記述されているような、多倍長整数除算アルゴリズムにおける試行商の補正ステップに相当します。

具体的には、以下の2つのセクションでgotoが使われていました。

1. q1の調整:

   again1:
   	if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
   		q1--
   		rhat += vn1
   		if rhat < _B2 {
   			goto again1
   		}
   	}
   

   ここでは、計算された試行商q1が大きすぎる場合に、q1をデクリメントし、rhat（部分剰余）をインクリメントして調整します。rhatが_B2（ワードの半分）未満である限り、goto again1によってこの調整プロセスを繰り返します。これは、試行商が正確な商に収束するまで繰り返されるループ処理です。

2. q0の調整:

   again2:
   	if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
   		q0--
   		rhat += vn1
   		if rhat < _B2 {
   			goto again2
   		}
   	}
   

   同様に、q0（商のもう一方の半分）についても同様の調整が行われます。

変更点と技術的意義:

コミットは、これらのgotoベースのループを標準的なforループに置き換えています。

--- a/src/pkg/math/big/arith.go
+++ b/src/pkg/math/big/arith.go
@@ -131,12 +131,11 @@ func divWW_g(u1, u0, v Word) (q, r Word) {
 	q1 := un32 / vn1
 	rhat := un32 - q1*vn1
 
-again1:
-	if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
+	for q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
 		q1--
 		rhat += vn1
-		if rhat < _B2 {
-			goto again1
+		if rhat >= _B2 {
+			break
 		}
 	}
 
@@ -144,12 +143,11 @@ again1:
 	q0 := un21 / vn1
 	rhat = un21 - q0*vn1
 
-again2:
-	if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
+	for q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
 		q0--
 		rhat += vn1
-		if rhat < _B2 {
-			goto again2
+		if rhat >= _B2 {
+			break
 		}
 	}

• gotoからforへの変換:

  • 元のgotoループは、label: if condition { ... if inner_condition { goto label } }というパターンでした。
  • これをfor condition { ... if inner_condition { break } }というパターンに変換しています。
  • if rhat < _B2 { goto again1 }という条件は、rhatが_B2未満である限りループを継続するという意味でした。
  • 新しいforループでは、rhat >= _B2になった場合にbreakすることで、同じロジックを実現しています。つまり、rhatが_B2以上になったらループを終了するという逆の条件でループを抜けるようにしています。

• _B2定数: _B2はmath/bigパッケージ内で定義されている内部定数で、Word型の半分（またはそれ以下）のビット幅を持つ数値の最大値を表します。例えば、Wordがuint64の場合、_B2は1 << 32（2の32乗）に相当し、これは32ビットの最大値+1です。多倍長整数演算では、ワードをさらに小さな単位（半ワード）に分割して計算を行うことがあり、この_B2はその境界値として機能します。除算アルゴリズムにおいて、試行商の調整や剰余の正規化の際にこの値が使われます。

この変更は、機能的な振る舞いを一切変えることなく、コードの制御フローをより構造化されたものにすることで、以下の利点をもたらします。

1. 可読性の向上: forループはgotoよりも意図が明確であり、コードの論理的な流れを追いやすくなります。
2. GopherJSのパフォーマンス改善: コミットメッセージで述べられているように、GopherJSはgotoをエミュレートする必要があり、これがパフォーマンスのボトルネックとなっていました。forループはJavaScriptのネイティブなループ構文に直接マッピングできるため、エミュレーションのオーバーヘッドがなくなります。math/bigのような頻繁に呼び出されるコア関数でのこの改善は、GopherJSでコンパイルされたアプリケーション全体の性能に大きな影響を与えます。
3. Goのイディオムへの準拠: Goコミュニティではgotoの使用は一般的に避けられ、構造化された制御フローが推奨されます。この変更は、Goのコーディングイディオムにより合致するものです。

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

変更は src/pkg/math/big/arith.go ファイルの divWW_g 関数内で行われました。

--- a/src/pkg/math/big/arith.go
+++ b/src/pkg/math/big/arith.go
@@ -131,12 +131,11 @@ func divWW_g(u1, u0, v Word) (q, r Word) {
 	q1 := un32 / vn1
 	rhat := un32 - q1*vn1
 
-again1:
-	if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
+	for q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
 		q1--
 		rhat += vn1
-		if rhat < _B2 {
-			goto again1
+		if rhat >= _B2 {
+			break
 		}
 	}
 
@@ -144,12 +143,11 @@ again1:
 	q0 := un21 / vn1
 	rhat = un21 - q0*vn1
 
-again2:
-	if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
+	for q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
 		q0--
 		rhat += vn1
-		if rhat < _B2 {
-			goto again2
+		if rhat >= _B2 {
+			break
 		}
 	}

コアとなるコードの解説

変更されたコードは、divWW_g 関数内の2つのセクションです。この関数は、多倍長整数除算の基本的なステップである、2ワードの数値を1ワードの数値で割る操作を実行します。

元のコードでは、again1: と again2: というラベルと goto ステートメントを使用して、試行商 q1 と q0 を調整するためのループが実装されていました。

元のコードのロジック（q1の調整部分を例に）:

again1: // ラベル
	if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { // ループ継続条件
		q1--         // q1をデクリメント
		rhat += vn1  // rhatをインクリメント
		if rhat < _B2 { // 内部条件
			goto again1 // 条件を満たせばラベルにジャンプしてループを継続
		}
	}

この構造は、「q1 >= _B2 || q1*vn0 > _B2*rhat+un1 が真である限り、q1 をデクリメントし、rhat をインクリメントする。ただし、rhat が _B2 以上になったら、それ以上調整は不要なのでループを抜ける」というロジックを表しています。goto は、rhat < _B2 の場合にループの先頭に戻るために使われていました。

変更後のコードのロジック（q1の調整部分を例に）:

	for q1 >= _B2 || q1*vn0 > _B2*rhat+un1 { // forループの条件
		q1--         // q1をデクリメント
		rhat += vn1  // rhatをインクリメント
		if rhat >= _B2 { // 内部条件
			break // 条件を満たせばループを抜ける
		}
	}

変更後のコードでは、goto again1: と if rhat < _B2 { goto again1 } の部分が、for ループと if rhat >= _B2 { break } に置き換えられています。

• for ループの条件 q1 >= _B2 || q1*vn0 > _B2*rhat+un1 は、元の if ステートメントの条件と全く同じです。これにより、ループがいつ実行されるかが明確になります。
• ループ本体内で q1-- と rhat += vn1 が実行されるのも同じです。
• 最も重要な変更は、if rhat < _B2 { goto again1 } が if rhat >= _B2 { break } になった点です。
  • 元の goto は、「rhat が _B2 未満ならループを継続する」という意味でした。
  • 新しい break は、「rhat が _B2 以上になったらループを終了する」という意味です。
  • これら二つの条件は論理的に等価であり、同じループの終了条件を表現しています。

この変更により、コードの意図がより明確になり、goto の使用による可読性の低下や、GopherJSのような環境でのエミュレーションコストが解消されました。機能的には全く同じ動作をしますが、より現代的でGoのイディオムに沿った、そして特定のコンパイルターゲットでより効率的な実装になっています。

関連リンク

• Go言語のmath/bigパッケージのドキュメント: https://pkg.go.dev/math/big
• GopherJSプロジェクトのGitHubリポジトリ: https://github.com/gopherjs/gopherjs
• Go言語におけるgotoステートメントに関する議論（Go Wiki）: https://go.dev/wiki/CodeReviewComments#goto

参考にした情報源リンク

• Go言語の公式ドキュメント
• GopherJSの公式ドキュメントおよび関連情報
• 多倍長整数演算アルゴリズムに関する一般的な情報（例: Donald Knuth, "The Art of Computer Programming", Volume 2, Chapter 4.3.1, Algorithm D）
• コミットメッセージに記載されているGoのコードレビューシステム（Gerrit）のリンク: https://golang.org/cl/55470046
• GitHub上のGoリポジトリ: https://github.com/golang/go
• math/bigパッケージのソースコード (arith.go): https://github.com/golang/go/blob/master/src/math/big/arith.go