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

[インデックス 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言語はガベージコレクタを持つ言語であり、開発者が手動でメモリを解放する必要はありません。しかし、これはメモリ割り当てがパフォーマンスに影響しないという意味ではありません。

  1. メモリ割り当てのコスト: 新しいメモリを割り当てる(ヒープにオブジェクトを確保する)操作自体には、システムコールやアロケータの処理によるオーバーヘッドがあります。
  2. ガベージコレクションの負荷: 頻繁に小さなオブジェクトが割り当てられ、すぐに不要になると、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のオーバーヘッドが発生していました。

このコミットでは、この問題を解決するために、zzr という2つの新しい nat 型の変数を導入しています。これらの変数は、中間結果を一時的に保持するために使用されます。

変更後のコードのパターンは以下のようになります。

  1. zz = zz.mul(z, z): z の二乗を計算し、結果を zz に格納します。この際、zzz とは異なる変数であるため、mul 関数はエイリアシングを心配する必要がなく、zz の基盤配列を再利用できる可能性が高まります(zz の容量が十分であれば)。
  2. zz, z = z, zz: ここが重要なポイントです。これはGoの多重代入(tuple assignment)を利用したイディオムで、zzz の値を交換しています。これにより、次のループイテレーションでは、以前の zzz として使われ、以前の zzz として使われます。この「スワップ」によって、zzz が交互に結果を保持するようになり、新しい nat スライスの割り当てを最小限に抑え、既存の基盤配列を効率的に再利用できるようになります。

同様のパターンが muldiv の両方に適用されています。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)

このパターンでは、muldiv の結果が直接 z に再代入されています。muldiv の実装では、入力引数と出力引数が同じ変数である(エイリアシングが発生する)場合、新しいメモリを割り当てて結果を格納する必要がありました。これにより、ループの各イテレーションで新しい 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 の値を複雑に交換

zzr の導入

  • zzr は、muldiv の中間結果を一時的に保持するための nat 型の変数です。
  • コメント // zz and r are used to avoid allocating in mul and div as // otherwise the arguments would alias. が示すように、これらの変数は、muldiv の引数と戻り値がエイリアシングするのを避けるために導入されました。

zz = zz.mul(z, z)zz, z = z, zz のパターン

  1. zz = zz.mul(z, z): z の二乗を計算し、その結果を zz に格納します。このとき、mul 関数は zzz が異なる変数であることを認識できるため、zz が持つ既存の基盤配列を再利用できる可能性が高まります。もし zz の容量が足りなければ拡張されますが、毎回新しい配列を割り当てるよりは効率的です。
  2. zz, z = z, zz: これはGoの多重代入機能を利用した「スワップ」イディオムです。zz の内容が z に、z の内容が zz にそれぞれ代入されます。これにより、次のループイテレーションでは、以前の計算結果が z として扱われ、以前の zzz として再利用可能な一時変数として扱われます。この巧妙なスワップによって、zzz が交互に結果を保持し、新しい nat スライスの割り当てを最小限に抑えることができます。

div の変更

div 関数は商と剰余の2つの結果を返します。変更前は q, z = q.div(z, z, m) のように、z が入力と出力の両方で使用されていました。

変更後は zz, r = zz.div(r, z, m) となり、zm で割った商が zz に、剰余が r に格納されます。そして、zz, r, q, z = q, z, zz, r という複雑なスワップが行われます。これは、qz が次のイテレーションで正しく更新されるように、そして zzr が再利用可能な一時変数として機能するように、複数の変数の値を同時に交換しています。

これらの変更により、expNN 関数はループ内で頻繁に発生していたメモリ割り当てを大幅に削減し、ガベージコレクションのオーバーヘッドを低減することで、全体的なパフォーマンスを向上させています。

関連リンク

参考にした情報源リンク