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

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

このコミットは、Go言語の標準ライブラリであるmath/bigパッケージ内のnat.goファイルに対する変更です。nat.goは、任意精度整数（big.Int型）の内部表現であるnat型（自然数、非負整数）の算術演算、特に乗算処理を実装しています。

コミット

math/bigパッケージにおけるKaratsuba乗算アルゴリズムのしきい値（karatsubaThreshold）を、より最適な値に調整する変更です。この調整により、特定のベンチマーク（BenchmarkMul）でパフォーマンスが改善されました。

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

https://github.com/golang/go/commit/6a135a0894fff5bbb1885c27fd9eb41b9a2b4e51

元コミット内容

mat/big: more optimal Karatsuba threshold

benchmark           old ns/op    new ns/op    delta
BenchmarkHilbert      6253043      6267289   +0.23%
BenchmarkMul         45355940     39490633  -12.93%

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

変更の背景

任意精度算術ライブラリにおいて、大きな数値の乗算は計算コストの高い操作です。Go言語のmath/bigパッケージでは、この乗算を効率的に行うために、オペランドのサイズに応じて異なるアルゴリズムを使い分けています。具体的には、オペランドが小さい場合は「筆算」（または「小学校の乗算」と呼ばれる、桁ごとに計算する基本的な方法）を、大きい場合はより高速なKaratsubaアルゴリズムを使用します。

この二つのアルゴリズムを切り替える境界となるのが「しきい値（threshold）」です。このしきい値は、両アルゴリズムの性能特性に基づいて決定されます。しきい値が適切でない場合、アルゴリズムの切り替えが非効率になり、全体のパフォーマンスが低下する可能性があります。

このコミットの背景には、既存のkaratsubaThreshold（32）が、実際のワークロードにおいて必ずしも最適ではないという認識がありました。ベンチマークの結果が示すように、特に一般的な乗算操作（BenchmarkMul）において、より良いパフォーマンスを引き出す余地があったため、しきい値の再評価と調整が行われました。

前提知識の解説

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

math/bigパッケージは、Go言語の標準ライブラリの一つで、任意精度の算術演算を提供します。これは、Goの組み込み型（int, int64など）では表現できない非常に大きな整数や、高い精度が要求される浮動小数点数、有理数を扱うために設計されています。暗号学、科学計算、金融アプリケーションなど、精度が重要な分野で利用されます。

math/bigパッケージの内部では、big.Int型などの数値は、nat型と呼ばれる[]Word（Wordはuintまたはuint64）のスライスとして表現されます。このnat型が、数値の各「桁」（基数_Wに基づく）を保持し、その上で加算、減算、乗算などの基本的な算術演算が実装されています。

Karatsubaアルゴリズム

Karatsubaアルゴリズムは、大きな数の乗算を高速に行うためのアルゴリズムです。1960年にアナトリー・カラツバによって考案され、従来の「筆算」乗算（O(n^2)の計算量）よりも効率的（O(n^log2(3)) ≈ O(n^1.585)の計算量）に計算できます。ここでnは数値の桁数です。

原理: Karatsubaアルゴリズムは、「分割統治法」に基づいています。2つのn桁の数xとyを乗算する場合、それぞれを約n/2桁の2つの部分に分割します。

x = x1 * B^(n/2) + x0 y = y1 * B^(n/2) + y0

ここでBは基数です。 通常の乗算では、x * y = (x1 * B^(n/2) + x0) * (y1 * B^(n/2) + y0) を展開すると、4つの部分乗算（x1*y1, x1*y0, x0*y1, x0*y0）が必要になります。

Karatsubaアルゴリズムでは、以下の3つの部分乗算で結果を導き出します。

  1. P1 = x1 * y1
  2. P2 = x0 * y0
  3. P3 = (x1 + x0) * (y1 + y0)

そして、x * y = P1 * B^n + (P3 - P1 - P2) * B^(n/2) + P2 のように計算します。 これにより、4つのn/2桁の乗算を3つのn/2桁の乗算に減らすことができます。このプロセスを再帰的に適用することで、計算量を削減します。

Karatsubaアルゴリズムの「しきい値（Threshold）」

Karatsubaアルゴリズムは、非常に大きな数に対しては効率的ですが、小さな数に対しては、再帰呼び出しのオーバーヘッドや追加の加算・減算操作のために、従来の筆算乗算よりも遅くなることがあります。そのため、ある程度の桁数（またはワード数）以下のオペランドに対しては筆算乗算を、それ以上のオペランドに対してはKaratsubaアルゴリズムを適用するという「しきい値」を設定するのが一般的です。

このしきい値は、システムのアーキテクチャ、コンパイラ、具体的な実装、そしてベンチマークによって最適な値が異なります。math/bigパッケージのコメントにある// computed by calibrate.goは、このしきい値が自動的に（または半自動的に）最適な値を探索するツールによって決定されたことを示唆しています。

「筆算」乗算 (Grade School Multiplication)

「筆算」乗算は、私たちが小学校で学ぶような、桁ごとに計算していく基本的な乗算アルゴリズムです。n桁の数とm桁の数を乗算する場合、計算量はO(n*m)となります。同じ桁数nの数同士であればO(n^2)です。Karatsubaアルゴリズムと比較して、小さな数ではオーバーヘッドが少ないため高速ですが、大きな数になると計算量が爆発的に増加します。

ベンチマーク (Benchmark)

Go言語のベンチマークは、コードのパフォーマンスを測定するための機能です。go test -bench=.コマンドなどで実行され、関数の実行にかかる時間（ns/op - ナノ秒/操作）や、割り当てられたメモリ量などを測定します。

  • ns/op (nanoseconds per operation): 1回の操作にかかる平均時間（ナノ秒）。この値が小さいほど高速であることを意味します。
  • delta: 変更前と変更後のパフォーマンスの差をパーセンテージで示します。負の値はパフォーマンスの改善（高速化）、正の値はパフォーマンスの低下（低速化）を意味します。

このコミットのベンチマーク結果では、BenchmarkMulが約12.93%高速化されており、BenchmarkHilbertはわずかに（0.23%）遅くなっています。これは、karatsubaThresholdの変更が、一般的な乗算操作に良い影響を与えたことを示しています。

技術的詳細

math/bigパッケージのnat.goファイルには、karatsubaThresholdというグローバル変数が定義されています。この変数は、Karatsubaアルゴリズムを適用するか、それともより単純な筆算乗算を適用するかの境界となるオペランドのワード数（Word型の要素数）を決定します。

変更前はkaratsubaThresholdが32に設定されていました。これは、オペランドのワード数が32未満の場合は筆算乗算を、32以上の場合はKaratsubaアルゴリズムを使用するという意味です。

このコミットでは、karatsubaThresholdの値が32から40に変更されました。 これは、以下のことを意味します。

  1. 筆算乗算の適用範囲の拡大: 変更前はワード数31までだった筆算乗算の適用範囲が、ワード数39までに拡大されました。
  2. Karatsubaアルゴリズムの適用開始点の遅延: Karatsubaアルゴリズムが適用されるのは、ワード数が40以上の場合に限定されるようになりました。

この調整は、calibrate.goというツールによって計算された結果に基づいています。calibrate.goは、異なるkaratsubaThreshold値でベンチマークを実行し、最もパフォーマンスの良い値を見つけるためのユーティリティスクリプトであると推測されます。

ベンチマーク結果から、karatsubaThresholdを40に設定することで、BenchmarkMul（一般的な乗算操作を測定するベンチマーク）のパフォーマンスが大幅に改善されたことがわかります。これは、ワード数が32から39の範囲の乗算において、Karatsubaアルゴリズムのオーバーヘッドが筆算乗算の効率を上回っていたことを示唆しています。つまり、この範囲では筆算乗算の方が高速であったため、その適用範囲を広げたことで全体のパフォーマンスが向上したと考えられます。

BenchmarkHilbertはわずかに遅くなっていますが、これは特定の数学的構造を持つ行列の乗算ベンチマークであり、一般的な乗算とは異なる特性を持つ可能性があります。全体として、より一般的な乗算操作の高速化が優先されたと見られます。

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

--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -236,7 +236,7 @@ func karatsubaSub(z, x nat, n int) {
 // Operands that are shorter than karatsubaThreshold are multiplied using
 // "grade school" multiplication; for longer operands the Karatsuba algorithm
 // is used.
-var karatsubaThreshold int = 32 // computed by calibrate.go
+var karatsubaThreshold int = 40 // computed by calibrate.go
 
 // karatsuba multiplies x and y and leaves the result in z.
 // Both x and y must have the same length n and n must be a

コアとなるコードの解説

変更されたのは、src/pkg/math/big/nat.goファイル内のkaratsubaThreshold変数の初期値です。

-var karatsubaThreshold int = 32 // computed by calibrate.go
+var karatsubaThreshold int = 40 // computed by calibrate.go

この一行の変更が、math/bigパッケージが大きな数の乗算を行う際に、どのアルゴリズムを選択するかという内部ロジックに影響を与えます。

  • 変更前 (32):

    • 乗算される数のワード数が32未満の場合: 筆算乗算（"grade school" multiplication）が使用されます。
    • 乗算される数のワード数が32以上の場合: Karatsubaアルゴリズムが使用されます。

  • 変更後 (40):

    • 乗算される数のワード数が40未満の場合: 筆算乗算が使用されます。
    • 乗算される数のワード数が40以上の場合: Karatsubaアルゴリズムが使用されます。

この変更により、ワード数が32から39の範囲の乗算において、Karatsubaアルゴリズムではなく筆算乗算が選択されるようになりました。ベンチマーク結果が示すように、この範囲では筆算乗算の方が効率的であったため、全体の乗算性能が向上しました。これは、Karatsubaアルゴリズムの再帰呼び出しや中間計算のオーバーヘッドが、このサイズのオペランドでは筆算乗算の単純さを上回っていたことを意味します。

コメント// computed by calibrate.goは、このしきい値が手動で適当に決められたものではなく、専用のツールやプロセスによってパフォーマンスが最適化されるように計算された値であることを示しています。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメントおよびソースコード
  • Karatsubaアルゴリズムに関する一般的な情報源（Wikipediaなど）
  • ベンチマーク結果の解釈に関する一般的な知識
  • Go言語のmath/bigパッケージの内部実装に関する情報