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

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

このコミットは、Go言語の標準ライブラリである math/big パッケージ内の binaryGCD 関数におけるパフォーマンス最適化に関するものです。具体的には、大きな整数（big.Int型）の最大公約数（GCD: Greatest Common Divisor）を計算する binaryGCD 関数において、不要なメモリコピーを削減することで処理速度を向上させています。

コミット

commit 133cdb6707ba88f83746db1efd15c4cb3034ff62
Author: Adam Langley <agl@golang.org>
Date:   Wed May 15 10:03:22 2013 -0400

    math/big: save some copies in binaryGCD.

    This patch resulted from a bit of quick optimisation in response to a
    golang-nuts post. It looks like one could save a couple other copies in
    this function, but this addresses the inner loop and is fairly simple.

    benchmark                    old ns/op    new ns/op    delta
    BenchmarkGCD10x10                 1964         1711  -12.88%
    BenchmarkGCD10x100                2019         1736  -14.02%
    BenchmarkGCD10x1000               2471         2171  -12.14%
    BenchmarkGCD10x10000              6040         5778   -4.34%
    BenchmarkGCD10x100000            43204        43025   -0.41%
    BenchmarkGCD100x100              11004         8520  -22.57%
    BenchmarkGCD100x1000             11820         9446  -20.08%
    BenchmarkGCD100x10000            23846        21382  -10.33%
    BenchmarkGCD100x100000          133691       131505   -1.64%
    BenchmarkGCD1000x1000           120041        95591  -20.37%
    BenchmarkGCD1000x10000          136887       113600  -17.01%
    BenchmarkGCD1000x100000         295370       273912   -7.26%
    BenchmarkGCD10000x10000        2556126      2205198  -13.73%
    BenchmarkGCD10000x100000       3159512      2808038  -11.12%
    BenchmarkGCD100000x100000    150543094    139986045   -7.01%

    R=gri, remyoudompheng
    CC=bradfitz, gobot, golang-dev, gri
    https://golang.org/cl/9424043

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

https://github.com/golang/go/commit/133cdb6707ba88f83746db1efd15c4cb3034ff62

元コミット内容

math/big: save some copies in binaryGCD.

このパッチは、golang-nutsの投稿に応じた迅速な最適化の結果です。この関数では他にもいくつかのコピーを削減できる可能性がありますが、これは内部ループに対処しており、非常にシンプルです。

ベンチマーク結果:

benchmarkold ns/opnew ns/opdelta
BenchmarkGCD10x1019641711-12.88%
BenchmarkGCD10x10020191736-14.02%
BenchmarkGCD10x100024712171-12.14%
BenchmarkGCD10x1000060405778-4.34%
BenchmarkGCD10x1000004320443025-0.41%
BenchmarkGCD100x100110048520-22.57%
BenchmarkGCD100x1000118209446-20.08%
BenchmarkGCD100x100002384621382-10.33%
BenchmarkGCD100x100000133691131505-1.64%
BenchmarkGCD1000x100012004195591-20.37%
BenchmarkGCD1000x10000136887113600-17.01%
BenchmarkGCD1000x100000295370273912-7.26%
BenchmarkGCD10000x1000025561262205198-13.73%
BenchmarkGCD10000x10000031595122808038-11.12%
BenchmarkGCD100000x100000150543094139986045-7.01%

変更の背景

このコミットの背景には、Go言語の math/big パッケージにおける binaryGCD 関数のパフォーマンス改善の必要性がありました。コミットメッセージによると、この最適化は golang-nuts メーリングリストでの議論に端を発しているようです。binaryGCD は大きな整数の最大公約数を効率的に計算するための重要なアルゴリズムであり、その性能は数値計算や暗号化など、math/big パッケージを利用する多くのアプリケーションに影響を与えます。

特に、binaryGCD の内部ループにおける不要なメモリコピーがパフォーマンスのボトルネックとなっていたと考えられます。大きな整数を扱う場合、値のコピーはCPUサイクルとメモリ帯域を大量に消費するため、これを削減することは処理速度の向上に直結します。このコミットは、そのボトルネックを解消し、より効率的な最大公約数計算を実現することを目的としています。ベンチマーク結果が示すように、特に中規模から大規模な数値のGCD計算において顕著な性能向上が見られます。

前提知識の解説

1. 最大公約数 (GCD: Greatest Common Divisor)

最大公約数とは、2つ以上の整数に共通する約数の中で最大のものです。例えば、12と18の最大公約数は6です。GCDの計算は、暗号学（RSAなど）、分数計算の簡約化、ユークリッド互除法に基づくアルゴリズムなど、様々な分野で基礎的な演算として利用されます。

2. バイナリGCDアルゴリズム (Binary GCD Algorithm)

ユークリッド互除法はGCDを計算する古典的なアルゴリズムですが、除算と剰余演算を多用するため、特に大きな整数に対しては計算コストが高くなることがあります。バイナリGCDアルゴリズム（またはスタインのアルゴリズム）は、除算や剰余演算の代わりに、シフト演算（2で割る）、減算、偶奇性の判定といったビット演算を主に使用することで、より高速にGCDを計算します。

バイナリGCDアルゴリズムの基本的な考え方は以下の通りです。

  • gcd(0, n) = n
  • gcd(m, n) = gcd(n, m)
  • 両方が偶数の場合: gcd(m, n) = 2 * gcd(m/2, n/2)
  • 片方が偶数、もう片方が奇数の場合: gcd(m, n) = gcd(m/2, n) （mが偶数の場合）
  • 両方が奇数の場合: gcd(m, n) = gcd((m-n)/2, n) （m > n の場合）

このアルゴリズムは、特にコンピュータ上での実装において、ビット演算が高速であるため効率的です。

3. Go言語の math/big パッケージ

math/big パッケージは、Go言語で任意精度の整数、有理数、浮動小数点数を扱うための標準ライブラリです。Go言語の組み込み型（int, int64など）は固定のビット幅を持つため、非常に大きな数値を扱う場合にはオーバーフローの問題が発生します。math/big パッケージは、これらの制限を克服し、メモリが許す限り任意の大きさの数値を正確に表現し、演算することを可能にします。

big.Int 型は、内部的に数値の各桁をスライス（[]Word）として保持します。このため、数値に対する演算（加算、減算、乗算、除算、GCDなど）は、このスライスを操作することによって行われます。このような操作では、新しいスライスを割り当てたり、既存のスライスの内容をコピーしたりすることが頻繁に発生し、これがパフォーマンスに影響を与える可能性があります。

4. メモリコピーとパフォーマンス

プログラミングにおいて、データのコピーはしばしばパフォーマンスのボトルネックとなります。特に大きなデータ構造（この場合は big.Int の内部表現であるスライス）をコピーする場合、以下のコストが発生します。

  • CPUサイクル: データをメモリから読み出し、別のメモリ位置に書き込むためのCPU時間。
  • メモリ帯域: メモリバスを介してデータを転送するための帯域幅の消費。
  • ガベージコレクション: 新しいメモリが割り当てられ、古いメモリが不要になった場合、ガベージコレクタがそれらを回収するオーバーヘッド。

これらのコストは、特にループ内で頻繁にコピーが行われる場合に累積し、プログラム全体の実行速度を著しく低下させることがあります。したがって、不要なコピーを削減することは、パフォーマンス最適化の重要な戦略の一つです。

技術的詳細

このコミットは、math/big パッケージの binaryGCD 関数における、big.Int オブジェクトの不要なコピーを削減することに焦点を当てています。binaryGCD アルゴリズムの内部ループでは、t、u、v といった big.Int 型の変数が頻繁に更新されます。

元のコードでは、t.neg（t が負の値であるか）の条件分岐内で、v.Neg(t) または u.Set(t) のように、t の値を v または u に「コピー」していました。Neg メソッドはレシーバの符号を反転させ、Set メソッドはレシーバに引数の値をコピーします。これらの操作は、内部的に big.Int の基盤となるスライスデータのコピーを伴う可能性があります。

このコミットの主要な変更点は、これらの明示的なコピー操作を、Go言語の多重代入（v, t = t, v）を利用した変数の「スワップ」に置き換えたことです。

  • v.Neg(t) の代わりに v, t = t, v を使用し、その後 v.neg = len(v.abs) > 0 && !v.neg で符号を調整。
  • u.Set(t) の代わりに u, t = t, u を使用。

Go言語において、v, t = t, v のような多重代入は、変数の参照（ポインタ）を交換する操作として解釈されることが多く、これにより基盤となる大きな数値データ自体のコピーを回避できます。これは、big.Int がポインタレシーバを持つメソッド（例: Neg, Set, Sub, Lsh など）を多く持つことからも示唆されます。変数のスワップは、新しいメモリ割り当てやデータコピーを伴わないため、非常に効率的です。

また、最後の return u.Lsh(u, k) が return z.Lsh(u, k) に変更されています。これは、binaryGCD 関数のレシーバ z を結果の格納先として利用することで、最終的な結果を返す際にも不要なコピーを避けるための最適化です。z は関数の呼び出し元から渡された big.Int オブジェクトであり、その場で結果を計算して z に格納することで、新しい big.Int オブジェクトを作成して返すオーバーヘッドを削減できます。

これらの変更により、binaryGCD の内部ループにおけるメモリ割り当てとデータコピーの回数が減少し、結果としてベンチマークが示すような顕著なパフォーマンス向上が実現されました。特に、大きな数値のGCD計算では、この最適化の効果が大きくなります。

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

変更は src/pkg/math/big/int.go ファイルの binaryGCD 関数内で行われています。

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -703,14 +703,15 @@ func (z *Int) binaryGCD(a, b *Int) *Int {
 		// reduce t
 		t.Rsh(t, t.abs.trailingZeroBits())
 		if t.neg {
-			v.Neg(t)
+			v, t = t, v
+			v.neg = len(v.abs) > 0 && !v.neg // 0 has no sign
 		} else {
-			u.Set(t)
+			u, t = t, u
 		}
 		t.Sub(u, v)
 	}

-	return u.Lsh(u, k)
+	return z.Lsh(u, k)
 }

 // ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.

コアとなるコードの解説

1. 変数のスワップによるコピーの削減

元のコードでは、t が負の場合に v.Neg(t) を呼び出し、t が負でない場合に u.Set(t) を呼び出していました。

  • 変更前:

    if t.neg {
    v.Neg(t) // t の値を反転させて v にコピー
} else {
    u.Set(t) // t の値を u にコピー
}

    Neg や Set メソッドは、t の内部データを v や u の内部データにコピーする操作を伴う可能性がありました。

  • 変更後:

    if t.neg {
    v, t = t, v // v と t の参照をスワップ
    v.neg = len(v.abs) > 0 && !v.neg // スワップ後の v の符号を調整
} else {
    u, t = t, u // u と t の参照をスワップ
}

    v, t = t, v や u, t = t, u という多重代入は、v と t（または u と t）が指す big.Int オブジェクトのポインタを交換します。これにより、大きな数値データそのものをコピーすることなく、変数が参照するオブジェクトを効率的に切り替えることができます。 v.neg = len(v.abs) > 0 && !v.neg の行は、スワップによって v が元の t の値を持つようになった後、その符号を適切に反転させるために追加されました。len(v.abs) > 0 は、v がゼロでないことを確認するための条件です。ゼロは符号を持たないため、ゼロの場合は符号を反転させる必要がありません。

2. 結果の格納先としてのレシーバ z の利用

binaryGCD 関数の最後の行も変更されています。

  • 変更前:

    return u.Lsh(u, k)

    これは、u の値を k ビット左シフトした結果を新しい big.Int オブジェクトとして返し、そのオブジェクトが u のレシーバとして使われていました。

  • 変更後:

    return z.Lsh(u, k)

    この変更では、binaryGCD 関数のレシーバである z を Lsh メソッドのレシーバとして使用しています。これにより、u を k ビット左シフトした結果が z に直接格納され、その z が返されます。このアプローチは、新しい big.Int オブジェクトを割り当てて結果を格納し、それを返すというオーバーヘッドを回避します。z は関数呼び出し元から提供されたオブジェクトであるため、結果をその場で更新することで、メモリ割り当てとガベージコレクションの負荷を軽減できます。

これらの変更は、binaryGCD の内部ループと最終的な結果の生成において、big.Int オブジェクトの不要なコピーとメモリ割り当てを徹底的に削減することを目的としています。これにより、特に大きな数値のGCD計算において、CPU時間とメモリ使用量の両面でパフォーマンスが向上します。

関連リンク

参考にした情報源リンク

  • バイナリGCDアルゴリズムに関する情報:
  • Go言語の多重代入とパフォーマンスに関する一般的な情報（Go言語の効率的なプログラミングに関する記事やドキュメント）
  • Go言語の math/big パッケージのソースコード（int.go）
  • golang-nuts メーリングリストのアーカイブ（具体的な投稿は特定できませんでしたが、コミットメッセージに言及があります）