[インデックス 13998] ファイルの概要
このコミットは、Go言語の標準ライブラリである math/big
パッケージ内の src/pkg/math/big/nat.go
ファイルに対する変更です。math/big
パッケージは、任意精度の整数および浮動小数点数演算を提供します。nat.go
ファイルは、このパッケージ内で自然数(非負整数)の内部表現と、それらに対する基本的な算術演算(乗算、除算、冪乗など)を実装しています。特に、この変更はモジュラ冪乗を行う expNN
関数に焦点を当てています。
コミット
このコミットは、math/big
パッケージの Exp
関数(内部的には expNN
関数が使用される)における不要なメモリ割り当てを削減することを目的としています。これにより、特にRSA暗号の復号処理のような、モジュラ冪乗を多用する操作のパフォーマンスが大幅に向上しています。ベンチマーク結果は、RSA1024、RSA2048、および3素数RSA2048の復号において、それぞれ13.51%、8.48%、12.72%の高速化が達成されたことを示しています。
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/9070d5759ff2d9b99dbe3d44c26300b54ab021e8
元コミット内容
math/big: avoid some allocation in Exp
benchmark old ns/op new ns/op delta
BenchmarkRSA1024Decrypt 745686 644964 -13.51%
BenchmarkRSA2048Decrypt 5517318 5049200 -8.48%
Benchmark3PrimeRSA2048Decrypt 3767386 3288048 -12.72%
R=gri
CC=gobot, golang-dev
https://golang.org/cl/6566043
変更の背景
Go言語では、ガベージコレクション(GC)が自動的にメモリ管理を行いますが、頻繁なメモリ割り当てはGCの負荷を増大させ、アプリケーションのパフォーマンスに悪影響を与える可能性があります。特に、math/big
パッケージのような数値計算ライブラリでは、大きな数値を扱うために内部的にスライス([]_W
)を使用しており、演算のたびに新しいスライスが割り当てられると、そのオーバーヘッドが無視できなくなります。
このコミットの背景には、math/big
パッケージの Exp
関数(モジュラ冪乗)が、RSA暗号の復号処理などで頻繁に呼び出されるため、その性能が全体のパフォーマンスに大きく影響するという認識があります。既存の実装では、中間結果を格納するために一時的な nat
型の変数が頻繁に生成され、これがメモリ割り当てとGCのボトルネックとなっていました。
この変更の目的は、expNN
関数内で発生するこれらの不要なメモリ割り当てを特定し、既存のメモリ領域を再利用するようなコードパターンに修正することで、GCの負荷を軽減し、結果としてRSA復号などの計算を高速化することです。ベンチマーク結果が示すように、この最適化は実際に顕著な性能向上をもたらしました。
前提知識の解説
math/big
パッケージ
math/big
パッケージは、Go言語で任意精度の数値演算を行うための標準ライブラリです。Goの組み込み型(int
, int64
など)は固定のビット幅を持つため、非常に大きな数値を扱う場合にはオーバーフローの問題が発生します。math/big
パッケージは、このような制限を克服し、メモリが許す限り任意の大きさの整数(Int
)、有理数(Rat
)、浮動小数点数(Float
)を扱うことができます。暗号化、科学計算、金融アプリケーションなど、高い精度や大きな数値を必要とする場面で利用されます。
nat
型
math/big
パッケージの内部では、nat
型が非負整数(自然数)の基本的な表現として使用されています。nat
は実際には []_W
のエイリアスであり、_W
はシステムのワードサイズ(32ビットまたは64ビット)に対応する符号なし整数型です。つまり、nat
型の変数は、大きな整数をワードの配列として表現します。例えば、64ビットシステムでは nat
は []uint64
と同等になります。この配列の各要素が、大きな数値の一部を構成します。
モジュラ冪乗 (Modular Exponentiation)
モジュラ冪乗は、a^b mod n
の形式の計算です。ここで、a
は基数、b
は指数、n
は法(モジュラス)です。この演算は、特に公開鍵暗号システム(RSAなど)において非常に重要です。RSA暗号では、メッセージの暗号化と復号の両方にモジュラ冪乗が使用されます。
モジュラ冪乗を効率的に計算するために、通常は「バイナリ法」(または「右から左のバイナリ法」、「繰り返し二乗法」)と呼ばれるアルゴリズムが用いられます。このアルゴリズムは、指数 b
をバイナリ表現で展開し、そのビットに応じて基数 a
を二乗したり、結果に乗算したりすることを繰り返します。各ステップでモジュラス n
で剰余を取ることで、中間結果が大きくなりすぎるのを防ぎます。
expNN
関数は、このモジュラ冪乗のアルゴリズムを nat
型の数値に対して実装しています。
Goにおけるメモリ割り当てとガベージコレクション (GC)
Go言語はガベージコレクタを持つ言語であり、開発者が手動でメモリを解放する必要はありません。しかし、これはメモリ割り当てがパフォーマンスに影響しないという意味ではありません。
- メモリ割り当てのコスト: 新しいメモリを割り当てる(ヒープにオブジェクトを確保する)操作自体には、システムコールやアロケータの処理によるオーバーヘッドがあります。
- ガベージコレクションの負荷: 頻繁に小さなオブジェクトが割り当てられ、すぐに不要になると、GCがそれらを回収するために多くの時間を費やすことになります。GCが実行される間、アプリケーションの実行が一時停止(ストップ・ザ・ワールド)することがあり、これがレイテンシの原因となります。
したがって、Go言語で高性能なコードを書く際には、不要なメモリ割り当てを避け、既存のメモリ領域を再利用する「アロケーションを避ける」最適化が非常に重要になります。特に、ループ内で頻繁に呼び出される関数や、大量のデータを処理する関数では、この最適化が性能に大きな影響を与えます。
技術的詳細
このコミットの技術的な核心は、math/big
パッケージの expNN
関数におけるモジュラ冪乗の計算中に発生する一時的な nat
型のオブジェクトの生成を抑制することです。
nat
型はスライス([]_W
)であるため、nat
型の変数を関数呼び出しの引数として渡したり、関数の戻り値として受け取ったりする際に、そのスライスのヘッダ(ポインタ、長さ、容量)がコピーされます。しかし、スライスの基盤となる配列(データ)は共有されます。問題は、mul
(乗算)や div
(除算)のような操作が、結果を新しい nat
スライスに書き込む場合です。もし、結果を格納する nat
スライスが、入力引数と同じ基盤配列を指している場合(エイリアシング)、元の入力データが上書きされてしまい、正しく計算できません。そのため、これらの関数はエイリアシングを避けるために、必要に応じて新しい基盤配列を割り当てていました。
変更前のコードでは、z = z.mul(z, z)
のように、演算結果を同じ変数 z
に再代入していました。z.mul(z, z)
の呼び出しでは、z
が入力と出力の両方に使われるため、mul
関数はエイリアシングを検出し、新しい nat
スライスを割り当てて結果をそこに書き込み、その新しいスライスを返していました。この新しいスライスが z
に代入されるたびに、古い z
が指していたスライスは不要になり、GCの対象となっていました。これが頻繁に繰り返されるループ内で発生するため、大量のメモリ割り当てとGCのオーバーヘッドが発生していました。
このコミットでは、この問題を解決するために、zz
と r
という2つの新しい nat
型の変数を導入しています。これらの変数は、中間結果を一時的に保持するために使用されます。
変更後のコードのパターンは以下のようになります。
zz = zz.mul(z, z)
:z
の二乗を計算し、結果をzz
に格納します。この際、zz
はz
とは異なる変数であるため、mul
関数はエイリアシングを心配する必要がなく、zz
の基盤配列を再利用できる可能性が高まります(zz
の容量が十分であれば)。zz, z = z, zz
: ここが重要なポイントです。これはGoの多重代入(tuple assignment)を利用したイディオムで、z
とzz
の値を交換しています。これにより、次のループイテレーションでは、以前のzz
がz
として使われ、以前のz
がzz
として使われます。この「スワップ」によって、z
とzz
が交互に結果を保持するようになり、新しいnat
スライスの割り当てを最小限に抑え、既存の基盤配列を効率的に再利用できるようになります。
同様のパターンが mul
と div
の両方に適用されています。div
の場合は、商と剰余の2つの結果を返すため、zz, r = zz.div(r, z, m)
と zz, r, q, z = q, z, zz, r
のように、さらに複雑なスワップが行われています。
この最適化により、expNN
関数はループの各イテレーションで新しい nat
スライスを割り当てる必要がなくなり、既存のメモリ領域を再利用することで、GCの負荷を大幅に軽減し、結果としてRSA復号のパフォーマンスが向上しました。
コアとなるコードの変更箇所
--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -1264,15 +1264,21 @@ func (z nat) expNN(x, y, m nat) nat {
// we also multiply by x, thus adding one to the power.
w := _W - int(shift)
+ // zz and r are used to avoid allocating in mul and div as
+ // otherwise the arguments would alias.
+ var zz, r nat
for j := 0; j < w; j++ {
- z = z.mul(z, z)
+ zz = zz.mul(z, z)
+ zz, z = z, zz
if v&mask != 0 {
- z = z.mul(z, x)
+ zz = zz.mul(z, x)
+ zz, z = z, zz
}
if m != nil {
- q, z = q.div(z, z, m)
+ zz, r = zz.div(r, z, m)
+ zz, r, q, z = q, z, zz, r
}
v <<= 1
@@ -1282,14 +1288,17 @@ func (z nat) expNN(x, y, m nat) nat {
v = y[i]
for j := 0; j < _W; j++ {
- z = z.mul(z, z)
+ zz = zz.mul(z, z)
+ zz, z = z, zz
if v&mask != 0 {
- z = z.mul(z, x)
+ zz = zz.mul(z, x)
+ zz, z = z, zz
}
if m != nil {
- q, z = q.div(z, z, m)
+ zz, r = zz.div(r, z, m)
+ zz, r, q, z = q, z, zz, r
}
v <<= 1
コアとなるコードの解説
変更は expNN
関数内の2つの主要なループ(最初の部分的なワード処理と、残りのワード処理)に集中しています。
変更前:
z = z.mul(z, z)
// ...
z = z.mul(z, x)
// ...
q, z = q.div(z, z, m)
このパターンでは、mul
や div
の結果が直接 z
に再代入されています。mul
や div
の実装では、入力引数と出力引数が同じ変数である(エイリアシングが発生する)場合、新しいメモリを割り当てて結果を格納する必要がありました。これにより、ループの各イテレーションで新しい nat
スライスが頻繁に割り当てられ、GCの負荷が増大していました。
変更後:
var zz, r nat // 新しい一時変数の導入
// ...
zz = zz.mul(z, z) // zの二乗を計算し、結果をzzに格納
zz, z = z, zz // zzとzの値を交換(スワップ)
// ...
zz = zz.mul(z, x) // zとxの積を計算し、結果をzzに格納
zz, z = z, zz // zzとzの値を交換(スワップ)
// ...
zz, r = zz.div(r, z, m) // zをmで割った商をzzに、剰余をrに格納
zz, r, q, z = q, z, zz, r // q, z, zz, r の値を複雑に交換
zz
と r
の導入
zz
とr
は、mul
やdiv
の中間結果を一時的に保持するためのnat
型の変数です。- コメント
// zz and r are used to avoid allocating in mul and div as // otherwise the arguments would alias.
が示すように、これらの変数は、mul
やdiv
の引数と戻り値がエイリアシングするのを避けるために導入されました。
zz = zz.mul(z, z)
と zz, z = z, zz
のパターン
zz = zz.mul(z, z)
:z
の二乗を計算し、その結果をzz
に格納します。このとき、mul
関数はz
とzz
が異なる変数であることを認識できるため、zz
が持つ既存の基盤配列を再利用できる可能性が高まります。もしzz
の容量が足りなければ拡張されますが、毎回新しい配列を割り当てるよりは効率的です。zz, z = z, zz
: これはGoの多重代入機能を利用した「スワップ」イディオムです。zz
の内容がz
に、z
の内容がzz
にそれぞれ代入されます。これにより、次のループイテレーションでは、以前の計算結果がz
として扱われ、以前のz
がzz
として再利用可能な一時変数として扱われます。この巧妙なスワップによって、z
とzz
が交互に結果を保持し、新しいnat
スライスの割り当てを最小限に抑えることができます。
div
の変更
div
関数は商と剰余の2つの結果を返します。変更前は q, z = q.div(z, z, m)
のように、z
が入力と出力の両方で使用されていました。
変更後は zz, r = zz.div(r, z, m)
となり、z
を m
で割った商が zz
に、剰余が r
に格納されます。そして、zz, r, q, z = q, z, zz, r
という複雑なスワップが行われます。これは、q
と z
が次のイテレーションで正しく更新されるように、そして zz
と r
が再利用可能な一時変数として機能するように、複数の変数の値を同時に交換しています。
これらの変更により、expNN
関数はループ内で頻繁に発生していたメモリ割り当てを大幅に削減し、ガベージコレクションのオーバーヘッドを低減することで、全体的なパフォーマンスを向上させています。
関連リンク
- Go CL 6566043: https://golang.org/cl/6566043
参考にした情報源リンク
- Go言語の
math/big
パッケージに関する公式ドキュメントやソースコード - Go言語におけるメモリ管理とガベージコレクションに関する一般的な情報源
- モジュラ冪乗アルゴリズムに関する情報源
- Go言語におけるスライスとエイリアシングに関する情報源
- Go言語の多重代入に関する情報源
- Go言語のベンチマークに関する情報源
- RSA暗号の仕組みに関する情報源
- Go言語のメモリ管理とGCの仕組み (一般的な情報源として)
- Go言語の
math/big
パッケージのドキュメント - 繰り返し二乗法 (Modular Exponentiation) (Wikipedia)