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

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

このコミットは、Go言語の math/big パッケージにおける任意精度数値の文字列変換処理を大幅に高速化することを目的としています。特に、大きな数値を文字列に変換する際に「再帰的な細分化 (recursive subdivision)」というアルゴリズムを導入し、大きな除数（基数の累乗）を使用することで、最大で30倍もの速度向上を実現しています。また、この最適化のための新しいテストと、内部パラメータのチューニングコードも含まれています。

コミット

commit 4c113ffe162236d44106a1c44ab8bfb623c1c795
Author: Michael T. Jones <mtj@google.com>
Date:   Sun Nov 27 11:10:59 2011 -0800

    math/big: use recursive subdivision for significant speedup
    
    This change adds the second aspect to the conversion code, the
    use of large divisiors (powers of big base) to greatly speed up
    the divsion of large numbers. Speedups of 30x are common in the
    large cases. Also includes new tests and tuning code for the
    key internal parameters.
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/5438058

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

https://github.com/golang/go/commit/4c113ffe162236d44106a1c44ab8bfb623c1c795

元コミット内容

math/big: 著しい高速化のための再帰的細分化の使用

この変更は、変換コードに第二の側面を追加します。それは、大きな除数（大きな基数の累乗）を使用することで、大きな数値の除算を大幅に高速化することです。大規模なケースでは30倍の高速化が一般的です。また、新しいテストと、主要な内部パラメータのチューニングコードも含まれています。

変更の背景

math/big パッケージは、Go言語で任意精度の整数および浮動小数点数演算を扱うための標準ライブラリです。これらの数値は、通常の int や float64 では表現できない非常に大きな数や非常に小さな数を扱う際に必要となります。このような任意精度数値の重要な操作の一つに、数値を人間が読める文字列形式に変換する処理（例: BigInt を10進数文字列に変換）があります。

従来の文字列変換アルゴリズムは、特に非常に大きな数値を扱う場合に性能上のボトルネックとなっていました。これは、数値を基数 b で繰り返し除算し、その余りから各桁を抽出するという基本的なアプローチが、数値が大きくなるにつれて計算コストが二次関数的に増加するためです。この非効率性は、特に数万桁を超えるような巨大な数値を扱う際に顕著になり、アプリケーションのパフォーマンスに大きな影響を与えていました。

このコミットは、この性能課題を解決するために導入されました。より効率的な除算戦略を採用することで、大規模な数値の文字列変換処理を劇的に高速化し、math/big パッケージの全体的な実用性を向上させることを目的としています。

前提知識の解説

任意精度演算 (Arbitrary-Precision Arithmetic)

任意精度演算とは、コンピュータの固定長のデータ型（例: 32ビット整数、64ビット浮動小数点数）の制限を超えて、必要なだけ多くの桁数で数値を表現し、計算する能力を指します。これにより、非常に大きな整数や、高い精度が要求される浮動小数点数演算が可能になります。Go言語の math/big パッケージは、この任意精度演算を提供します。内部的には、これらの数値は通常、Word と呼ばれる固定長のワード（例: uint64）の配列として表現されます。

数値の基数変換 (Number Base Conversion)

数値をある基数（例: 2進数、10進数、16進数）から別の基数に変換するプロセスです。特に、大きな整数を10進数文字列に変換する場合、伝統的な方法は「繰り返し除算と余り」のアルゴリズムです。これは、元の数値を目的の基数で繰り返し除算し、その余りを下位桁から順に収集していく方法です。

例: 10進数 255 を16進数に変換

  1. 255 ÷ 16 = 15 余り 15 (F)
  2. 15 ÷ 16 = 0 余り 15 (F) 結果: FF

この方法の計算コストは、数値の桁数（ワード数）が増えるにつれて急速に増加します。特に、除算操作自体が大きな数値に対して高コストであるため、効率的な除算アルゴリズムが不可欠です。

再帰的細分化 (Recursive Subdivision)

再帰的細分化は、大きな問題をより小さな、管理しやすいサブ問題に分割し、それらを再帰的に解決するアルゴリズム設計パラダイムです。数値演算の文脈では、特に大きな数値の乗算や除算において、従来の「筆算」のような方法よりも高速なアルゴリズム（例: Karatsubaアルゴリズム、Toom-Cookアルゴリズム）の基盤となります。

文字列変換における再帰的細分化は、大きな数 N を直接基数 b で繰り返し除算するのではなく、N を N = Q * D + R の形式で、より大きな「ビッグベース」D で一度除算し、商 Q と余り R を得ます。この Q と R はそれぞれ元の数よりも小さくなり、それぞれを再帰的に変換することで、全体の計算量を削減します。特に、D を N のおおよそ平方根に近い値に選ぶことで、効率的な分割が可能になります。

divW() と div() の違い

  • divW(): 任意精度数 nat を単一ワード Word で除算する操作。比較的低コスト。
  • div(): 任意精度数 nat を別の任意精度数 nat で除算する操作。これは「長除算 (long division)」に相当し、非常に高コストな操作です。

従来の文字列変換では、divW() を繰り返し使用していましたが、再帰的細分化では、高コストな div() を戦略的に使用して、全体の divW() の呼び出し回数を削減します。

技術的詳細

このコミットの核心は、math/big パッケージの nat 型（符号なし任意精度整数）の string() メソッドにおける基数変換ロジックの改善です。特に、b == b&-b (基数が2の累乗) ではない一般的なケース（例: 10進数変換）において、再帰的細分化が導入されました。

convertWords 関数

新しく導入された convertWords 関数が、再帰的細分化による変換処理の主要な部分を担います。 この関数は、大きな nat 型の数値を、指定された基数 b の文字列に変換します。

  1. 間接変換 (Indirect Conversion):

    • leafSize パラメータが 0 より大きく、かつ現在の数値 q のワード数が leafSize を超える場合、再帰的細分化が適用されます。
    • divisors 関数によって生成された「除数テーブル」table を使用します。このテーブルには、bb (大きな基数) の累乗が格納されており、これらは q を分割するための除数として機能します。
    • q を table 内の適切な除数 table[index].bbb で除算し、q と r の2つの部分に分割します (q, r = q.div(r, q, table[index].bbb))。ここで div() は高コストな任意精度除算です。
    • 分割された r は、r.convertWords() を再帰的に呼び出して変換されます。
    • q は、残りの部分として処理が続行されます。
    • このプロセスは、q のワード数が leafSize 以下になるまで繰り返されます。

  2. 直接変換 (Direct Conversion):

    • q のワード数が leafSize 以下になった場合、または再帰的細分化が無効な場合（leafSize == 0）、従来の「繰り返し除算と余り」の方法が適用されます。
    • この段階では、q.divW(q, bb) を使用して、q を「ビッグベース」bb で繰り返し除算し、各桁を抽出します。divW() は単一ワード除算であり、div() よりもはるかに高速です。
    • 10進数変換 (b == 10) の場合は、r-(t<<3+t<<1) のようなビットシフトと加算による最適化が適用され、r%10 や r/10 の代わりに高速な演算が行われます。これは r - 10*int(r/10) と同等で、r mod 10 を計算します。

leafSize パラメータ

leafSize は、再帰的細分化を停止し、直接変換に切り替える閾値となるワード数です。

  • leafSize > 0: 再帰的細分化が有効になります。
  • leafSize == 0: 再帰的細分化が無効になり、常に直接変換が使用されます。
  • コメントによると、leafSize の値は 8 または 16 が良いパフォーマンスを示すとされています。これは、nat/nat 除算（div()) のオーバーヘッドと、nat/Word 除算（divW()) の回数とのバランスによって決まります。最適な leafSize は、CPUのキャッシュラインサイズなどのハードウェア特性に依存するため、ベンチマーク (BenchmarkLeafSize テスト) を用いてチューニングすることが推奨されています。

divisors 関数とキャッシュ

  • divisors 関数は、再帰的細分化で使用する除数（bbb）のテーブルを構築します。これらの除数は、bb (大きな基数) の累乗であり、x のおおよその平方根に近いビット長を持つように選ばれます。
  • cacheBase10 と cacheLock を使用して、基数10の除数テーブルをキャッシュし、複数の変換呼び出し間で再利用することで、テーブル構築のオーバーヘッドを削減しています。これにより、特に同じ基数での変換が頻繁に行われる場合に性能が向上します。

expWW 関数

新しく追加された expWW 関数は、Word 型の基数 x と指数 y を受け取り、x**y を計算して nat 型で返します。これは主にベンチマークテストで使用され、大きな数値を効率的に生成するために導入されました。

性能向上メカニズム

この最適化の主要なアイデアは、大きな数値の除算の計算量が、その桁数に対して二次関数的に増加するという性質を利用することです。

  • 従来の直接変換 (divW() の繰り返し) は、n ワードの数値に対して約 n(n+1)/2 回の divW() 呼び出しを必要とし、全体として O(n^2) の計算量となります。
  • 再帰的細分化は、数値を約半分のサイズの2つの部分に分割し、それぞれを再帰的に処理します。これにより、divW() の呼び出し回数は約半分に削減されます。分割のための div() 操作は高コストですが、全体の計算量を O(n log n) に近づけることができます（Karatsubaのような乗算アルゴリズムと同様の原理）。
  • leafSize は、この再帰が効率的でなくなる（div() のオーバーヘッドが divW() の削減効果を上回る）ポイントを決定し、そこで直接変換に切り替えることで、最適なパフォーマンスを実現します。

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

src/pkg/math/big/nat.go

  • import 文の追加: math と sync パッケージがインポートされました。
  • nat.string() メソッドの変更:
    • x.bitLen()/log2(b) の計算が float64(x.bitLen())/math.Log2(float64(b)) を使用するように変更され、より正確な桁数見積もりが行われるようになりました。
    • 基数が2の累乗ではない場合の処理ロジックが大幅に変更され、convertWords 関数を呼び出すようになりました。
  • convertWords 関数の追加:
    • func (q nat) convertWords(lo, hi int, s []byte, charset string, b Word, ndigits int, bb Word, table []divisor) int
    • 再帰的細分化と直接変換のロジックを実装。
    • 10進数変換の高速化のためのビットシフト演算が導入されました。
  • leafSize 変数の追加:
    • var leafSize int = 8
    • 再帰的細分化の閾値を定義。
  • divisor 構造体の追加:
    • type divisor struct { bbb nat; nbits int; ndigits int }
    • 除数テーブルのエントリを定義。
  • キャッシュ関連の変数の追加:
    • const maxCache = 64
    • var cacheBase10 [maxCache]divisor
    • var cacheLock sync.Mutex
  • divisors 関数の追加:
    • func divisors(m int, b Word, ndigits int, bb Word) []divisor
    • 再帰的細分化で使用する除数テーブルを構築。
    • 基数10のテーブルをキャッシュするロジックを含む。
  • expWW 関数の追加:
    • func (z nat) expWW(x, y Word) nat
    • Word 型の基数と指数で累乗を計算するヘルパー関数。

src/pkg/math/big/nat_test.go

  • ベンチマーク関数の変更:
    • 既存の BenchmarkScan* および BenchmarkString* 関数が、より簡潔な命名規則 (BenchmarkScan10000Base10 など) に変更され、expWW を使用してテスト対象の数値を生成するようになりました。
  • LeafSizeHelper 関数の追加:
    • func LeafSizeHelper(b *testing.B, base Word, size int)
    • 異なる leafSize の値で string() 変換のパフォーマンスを測定するためのヘルパー関数。
  • BenchmarkLeafSize* ベンチマークの追加:
    • BenchmarkLeafSize0 から BenchmarkLeafSize64 まで、様々な leafSize の値で性能を評価するためのベンチマークが追加されました。
  • resetTable 関数の追加:
    • func resetTable(table []divisor)
    • ベンチマーク間でキャッシュされた除数テーブルをリセットするためのヘルパー関数。
  • TestStringPowers 関数の追加:
    • func TestStringPowers(t *testing.T)
    • expWW で生成された数値の文字列変換が正しく行われることを検証するテスト。

コアとなるコードの解説

nat.string() の変更点

// src/pkg/math/big/nat.go
func (x nat) string(charset string) string {
	// ... (既存の特殊ケース処理) ...

	// allocate buffer for conversion
	// 桁数の見積もりをより正確に
	i := int(float64(x.bitLen())/math.Log2(float64(b))) + 1 // off by one at most
	s := make([]byte, i)

	// convert power of two and non power of two bases separately
	if b == b&-b { // 基数が2の累乗の場合 (既存の高速パス)
		// ... (既存のロジック) ...
	} else { // 一般的な基数 (非2の累乗) の場合
		// determine "big base" as in 10^19 for 19 decimal digits in a 64 bit Word
		bb := Word(1) // big base is b**ndigits
		ndigits := 0  // number of base b digits
		for max := Word(_M / b); bb <= max; bb *= b {
			ndigits++ // maximize ndigits where bb = b**ndigits, bb <= _M
		}

		// construct table of successive squares of bb*leafSize to use in subdivisions
		table := divisors(len(x), b, ndigits, bb)

		// preserve x, create local copy for use in divisions
		q := nat(nil).set(x)

		// convert q to string s in base b with index of MSD indicated by return value
		i = q.convertWords(0, i, s, charset, b, ndigits, bb, table)
	}

	return string(s[i:])
}

nat.string() は、基数が2の累乗でない場合に、新しい convertWords 関数を呼び出すように変更されました。bb (ビッグベース) は、Word に収まる最大の b の累乗として計算されます。divisors 関数で再帰的細分化のための除数テーブルを構築し、q のコピーを作成してから convertWords を呼び出します。

convertWords 関数

// src/pkg/math/big/nat.go
func (q nat) convertWords(lo, hi int, s []byte, charset string, b Word, ndigits int, bb Word, table []divisor) int {
	// indirect conversion: split larger blocks to reduce quadratic expense of iterated nat/W division
	if leafSize > 0 && len(q) > leafSize && table != nil {
		var r nat
		index := len(table) - 1
		for len(q) > leafSize {
			// find divisor close to sqrt(q) if possible, but in any case < q
			// ... (適切な除数を見つけるロジック) ...

			// split q into the two digit number (q'*bbb + r) to form independent subblocks
			q, r = q.div(r, q, table[index].bbb) // ここで高コストな nat/nat 除算が発生

			// convert subblocks and collect results in s[lo:partition] and s[partition:hi]
			partition := hi - table[index].ndigits
			r.convertWords(partition, hi, s, charset, b, ndigits, bb, table[0:index]) // 再帰呼び出し
			hi = partition // i.e., q.convertWords(lo, partition, s, charset, b, ndigits, bb, table[0:index+1])
		}
	} // having split any large blocks now process the remaining small block

	// direct conversion: process smaller blocks monolithically to avoid overhead of nat/nat division
	var r Word
	if b == 10 { // 10進数変換の最適化
		for len(q) > 0 {
			q, r = q.divW(q, bb) // nat/Word 除算
			// ... (10進数桁抽出の高速化ロジック) ...
		}
	} else { // その他の基数
		for len(q) > 0 {
			q, r = q.divW(q, bb) // nat/Word 除算
			// ... (一般的な桁抽出ロジック) ...
		}
	}

	// ... (先行ゼロの処理) ...

	return hi
}

convertWords は、leafSize を閾値として、再帰的細分化（q.div() を使用）と直接変換（q.divW() を使用）を切り替えます。再帰的細分化のフェーズでは、q をより小さな r と q に分割し、r を再帰的に変換します。直接変換のフェーズでは、bb で繰り返し除算して桁を抽出します。特に10進数変換では、r-(t<<3+t<<1) のようなビット演算による高速化が施されています。

divisors 関数

// src/pkg/math/big/nat.go
func divisors(m int, b Word, ndigits int, bb Word) []divisor {
	// only build table when indirect conversion is enabled and x is large
	if leafSize == 0 || m <= leafSize {
		return nil
	}

	// determine k where (bb**leafSize)**(2**k) >= sqrt(x)
	k := 1
	for words := leafSize; words < m>>1 && k < maxCache; words <<= 1 {
		k++
	}

	// create new table of divisors or extend and reuse existing table as appropriate
	var cached bool
	var table []divisor
	switch b {
	case 10:
		table = cacheBase10[0:k] // reuse old table for this conversion
		cached = true
	default:
		table = make([]divisor, k) // new table for this conversion
	}

	// extend table
	if table[k-1].ndigits == 0 {
		if cached {
			cacheLock.Lock() // begin critical section
		}

		// ... (テーブルの構築ロジック) ...
		// table[i].bbb = nat(nil).expWW(bb, Word(leafSize)) (i=0の場合)
		// table[i].bbb = nat(nil).mul(table[i-1].bbb, table[i-1].bbb) (i>0の場合)

		if cached {
			cacheLock.Unlock() // end critical section
		}
	}

	return table
}

divisors 関数は、再帰的細分化で使用する除数のテーブルを生成します。このテーブルは、bb (大きな基数) の累乗を格納し、q を分割する際に使用されます。基数10の場合、cacheBase10 を使用してテーブルをキャッシュし、sync.Mutex で並行アクセスから保護します。これにより、同じ基数での変換が繰り返される際のオーバーヘッドが削減されます。

関連リンク

参考にした情報源リンク