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

このコミットは、Go言語の標準ライブラリであるstrconvパッケージ内の浮動小数点数から文字列への変換機能、特にFormatFloat関数のパフォーマンス改善に関するものです。strconvパッケージは、基本的なデータ型（数値、真偽値など）と文字列との間の変換を提供します。FormatFloat関数は、float64またはfloat32型の浮動小数点数を指定されたフォーマットと精度で文字列に変換するために使用されます。

コミット

commit c1c027964e17d9c3f8acb4a9136698ae696a14e8
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sat Sep 1 16:31:46 2012 +0200

    strconv: faster FormatFloat for fixed number of digits.
    
    The performance improvement applies to the case where
    prec >= 0 and fmt is 'e' or 'g'.
    
    Additional minor optimisations are included. A small
    performance impact happens in some cases due to code
    refactoring.
    
    benchmark                              old ns/op    new ns/op    delta
    BenchmarkAppendFloat64Fixed1                 623          235  -62.28%
    BenchmarkAppendFloat64Fixed2                1050          272  -74.10%
    BenchmarkAppendFloat64Fixed3                3723          243  -93.47%
    BenchmarkAppendFloat64Fixed4               10285          274  -97.34%
    
    BenchmarkAppendFloatDecimal                  190          206   +8.42%
    BenchmarkAppendFloat                         387          377   -2.58%
    BenchmarkAppendFloatExp                      397          339  -14.61%
    BenchmarkAppendFloatNegExp                   377          336  -10.88%
    BenchmarkAppendFloatBig                      546          482  -11.72%
    
    BenchmarkAppendFloat32Integer                188          204   +8.51%
    BenchmarkAppendFloat32ExactFraction          329          298   -9.42%
    BenchmarkAppendFloat32Point                  400          372   -7.00%
    BenchmarkAppendFloat32Exp                    369          306  -17.07%
    BenchmarkAppendFloat32NegExp                 372          305  -18.01%
    
    R=golang-dev, rsc
    CC=golang-dev, remy
    https://golang.org/cl/6462049

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

https://github.com/golang/go/commit/c1c027964e17d9c3f8acb4a9136698ae696a14e8

元コミット内容

    strconv: faster FormatFloat for fixed number of digits.
    
    The performance improvement applies to the case where
    prec >= 0 and fmt is 'e' or 'g'.
    
    Additional minor optimisations are included. A small
    performance impact happens in some cases due to code
    refactoring.
    
    benchmark                              old ns/op    new ns/op    delta
    BenchmarkAppendFloat64Fixed1                 623          235  -62.28%
    BenchmarkAppendFloat64Fixed2                1050          272  -74.10%
    BenchmarkAppendFloat64Fixed3                3723          243  -93.47%
    BenchmarkAppendFloat64Fixed4               10285          274  -97.34%
    
    BenchmarkAppendFloatDecimal                  190          206   +8.42%
    BenchmarkAppendFloat                         387          377   -2.58%
    BenchmarkAppendFloatExp                      397          339  -14.61%
    BenchmarkAppendFloatNegExp                   377          336  -10.88%
    BenchmarkAppendFloatBig                      546          482  -11.72%
    
    BenchmarkAppendFloat32Integer                188          204   +8.51%
    BenchmarkAppendFloat32ExactFraction          329          298   -9.42%
    BenchmarkAppendFloat32Point                  400          372   -7.00%
    BenchmarkAppendFloat32Exp                    369          306  -17.07%
    BenchmarkAppendFloat32NegExp                 372          305  -18.01%
    
    R=golang-dev, rsc
    CC=golang-dev, remy
    https://golang.org/cl/6462049

変更の背景

浮動小数点数を文字列に変換する処理は、多くのアプリケーションで頻繁に行われる操作であり、そのパフォーマンスは全体のスループットに大きな影響を与えます。特に、Go言語のstrconv.FormatFloat関数において、特定のフォーマット（'e'または'g'）で固定の桁数（prec >= 0）を指定した場合の変換速度が課題となっていました。

従来のアルゴリズムでは、これらのケースで不要な計算やオーバーヘッドが発生し、効率が低下していました。このコミットの目的は、これらの特定のユースケースにおけるFormatFloatのパフォーマンスを劇的に改善し、Goプログラム全体の数値処理性能を向上させることにありました。ベンチマーク結果が示すように、特にFixed（固定小数点）形式での変換において、最大で97%以上の高速化が達成されています。

前提知識の解説

Go言語の`strconv`パッケージと`FormatFloat`関数

strconvパッケージ: Go言語の標準ライブラリの一部で、文字列と数値、真偽値などの基本的なデータ型との間の変換機能を提供します。
FormatFloat関数: func FormatFloat(f float64, fmt byte, prec, bitSize int) stringというシグネチャを持ちます。
- f: 変換対象の浮動小数点数。
- fmt: フォーマット指定子。
  - 'f': -ddd.dddd形式（小数点以下の桁数をprecで指定）。
  - 'e'または'E': -d.ddddede±dd形式（指数表記、小数点以下の桁数をprecで指定）。
  - 'g'または'G': 'e'または'f'のどちらか短い方を選択。precは有効桁数を指定。
- prec: 精度。
  - prec < 0: 最短表現（Grisu3アルゴリズムなどが適用される）。
  - prec >= 0: 固定の桁数（'f'では小数点以下、'e'では小数点以下、'g'では有効桁数）。
- bitSize: 浮動小数点数のビットサイズ（32または64）。

浮動小数点数の表現（IEEE 754）

コンピュータ内部では、浮動小数点数はIEEE 754標準に従って表現されます。これは、符号ビット、指数部、仮数部（または有効数字部）から構成されます。この表現は、非常に広い範囲の数値を表現できる一方で、一部の十進数を正確に表現できないという特性を持ちます。このため、浮動小数点数を十進文字列に変換する際には、丸め誤差や精度の問題が常に伴います。

浮動小数点数から文字列への変換アルゴリズムの課題

浮動小数点数を文字列に変換するアルゴリズムには、主に以下の2つの課題があります。

正確性: 変換された文字列が元の浮動小数点数を正確に表現していること。特に、最短表現（元の浮動小数点数を一意に識別できる最短の十進文字列）を生成することは難しい課題です。
速度: 変換処理が高速であること。特に、大量の数値変換を行うアプリケーションでは、この速度が重要になります。

これらの課題を解決するために、Dragon4、Grisu、Ryuなど、様々なアルゴリズムが開発されてきました。

Grisu3アルゴリズム

Grisu3は、浮動小数点数を最短の十進文字列に変換するための高速なアルゴリズムの一つです。このアルゴリズムは、浮動小数点数の内部表現（二進数）から直接十進数を生成することで、従来の多倍長演算に基づくアルゴリズムよりも大幅な高速化を実現します。ただし、Grisu3は常に最短表現を生成できるわけではなく、一部の「難しい」ケースではより汎用的な（しかし遅い）アルゴリズムにフォールバックする必要があります。このコミットでは、固定桁数での変換に焦点を当てていますが、ftoa.goの変更箇所でGrisu3が最短表現の高速化に利用されていることが示唆されています。

ベンチマークの読み方

コミットメッセージに含まれるベンチマーク結果は、Goのtestingパッケージによるものです。

old ns/op: 変更前の1操作あたりの平均実行時間（ナノ秒）。
new ns/op: 変更後の1操作あたりの平均実行時間（ナノ秒）。
delta: 性能変化率。負の値は高速化、正の値は低速化を示します。例えば、-62.28%は62.28%の高速化を意味します。

このベンチマーク結果から、特にBenchmarkAppendFloat64Fixed系のテストで劇的な改善が見られることがわかります。これは、prec >= 0かつfmtが'e'または'g'の場合の最適化が成功したことを示しています。一方で、BenchmarkAppendFloatDecimalやBenchmarkAppendFloat32Integerのように、わずかに性能が低下しているケースもありますが、全体としては大幅な改善が達成されています。

技術的詳細

このコミットの主要な技術的改善点は、strconvパッケージ内の浮動小数点数変換ロジック、特にextFloat型とftoa.goのgenericFtoa関数に集約されています。

`extFloat`の役割と内部表現

extFloatは、float64よりも高い精度を持つ拡張浮動小数点数を表現するための内部構造体です。mant（仮数部）とexp（指数部）、neg（符号）で構成され、mant * (2^exp)という形式で数値を表します。この型は、浮動小数点数変換の際に発生する可能性のある精度損失を最小限に抑えるために使用されます。

`FormatFloat`の処理フローの変更

変更前は、FormatFloat（内部的にはgenericFtoa）が最短表現と固定桁数表現の両方を処理していました。このコミットでは、固定桁数（prec >= 0）かつfmtが'e'または'g'の場合に、新しい高速パスを導入しています。

optimizeフラグ: コミットメッセージには明示されていませんが、ftoa.goの変更を見ると、optimizeという内部フラグ（おそらくSetOptimize関数で制御される）が導入され、高速パスの有効/無効を切り替えることができるようになっています。これにより、テストやデバッグ時に従来の遅いパスと比較することが可能になります。
bigFtoaへの処理の分離: 従来の多倍長演算に基づく浮動小数点数変換ロジックは、bigFtoaという新しい関数に分離されました。これにより、genericFtoaは高速パスとbigFtoaへのフォールバックを管理する役割に特化します。
FixedDecimalメソッドの導入: extFloat型にFixedDecimal(d *decimalSlice, n int) boolという新しいメソッドが追加されました。このメソッドは、extFloatの値を指定された桁数nで十進数表現に変換し、結果をdecimalSliceに格納します。このメソッドが、固定桁数での高速変換の核心を担っています。
- frexp10()の呼び出しにより、数値を適切なスケールに調整します。
- 整数部と小数部を分離し、それぞれから桁を抽出します。
- adjustLastDigitFixed関数を呼び出し、丸め処理を行います。
- 不確実性が大きすぎる場合はfalseを返し、bigFtoaへのフォールバックを促します。
frexp10およびfrexp10Manyの変更:
- extfloat.goのfrexp10関数は、引数として受け取っていたexpMinとexpMaxを内部定数として持つように変更されました。これにより、関数の呼び出しが簡素化され、特定の範囲での指数調整に特化するようになりました。
- frexp10Manyも同様に引数が簡素化されています。
- これらの関数は、浮動小数点数を10の適切なべき乗でスケーリングし、その二進指数を特定の範囲に収める役割を担います。これは、十進数への変換を効率的に行うための前処理です。
adjustLastDigitFixed関数の役割: この新しい関数は、FixedDecimal内で呼び出され、計算された十進数表現の最後の桁を適切に丸める役割を担います。浮動小数点数の変換では、わずかな誤差が最後の桁に影響を与える可能性があるため、この丸め処理は正確な結果を得るために不可欠です。不確実性が大きすぎて正確な丸めができない場合はfalseを返します。
fmtE関数の最適化: 指数表記（'e'または'E'）のフォーマットを行うfmtE関数も、末尾のゼロの処理や指数部のフォーマットに関して、より効率的なコードにリファクタリングされています。

`strconv/extfloat.go`の変更点

mathパッケージのインポートが削除されました。これは、Assign関数が削除されたためです。
Assign関数が削除されました。この関数はextFloatにfloat64を割り当てるものでしたが、おそらくより効率的なAssignComputeBoundsが使われるようになったため不要になったと考えられます。
frexp10関数のシグネチャが変更され、expMinとexpMaxが引数から削除され、関数内部で定数として定義されるようになりました。これにより、特定の指数範囲に特化した処理が明確になりました。
FixedDecimalメソッドが追加されました。これが固定桁数変換の新しい高速パスの主要な部分です。
adjustLastDigitFixed関数が追加されました。これはFixedDecimal内で使用される丸め処理のヘルパー関数です。
ShortestDecimal関数内のminExpとmaxExp定数が削除され、frexp10Manyの呼び出しも引数なしに変更されました。

`strconv/ftoa.go`の変更点

genericFtoa関数が大幅にリファクタリングされました。
shortest（最短表現）と固定桁数表現のロジックが明確に分離されました。
固定桁数表現の場合に、新しく追加されたextFloat.FixedDecimalメソッドを呼び出す高速パスが導入されました。
FixedDecimalがfalseを返した場合（つまり、高速パスで正確な結果が得られない場合）や、最適化が有効でない場合に、従来の多倍長演算に基づくbigFtoa関数にフォールバックするようになりました。
bigFtoa関数が新しく定義され、従来の多倍長演算による変換ロジックがここに移動しました。
formatDigitsというヘルパー関数が導入され、genericFtoaとbigFtoaの両方から呼び出されるようになりました。これにより、桁のフォーマットロジックが共通化されました。
fmtE関数（指数表記のフォーマット）が最適化され、特に小数点以下の桁の追加と指数部のゼロパディングのロジックが改善されました。

`strconv/ftoa_test.go`の変更点

TestFtoaRandom関数に、'e'フォーマットと固定精度でのランダムな浮動小数点数変換のテストが追加されました。これにより、新しい高速パスの正確性が検証されます。
新しいベンチマーク関数が追加されました。
- BenchmarkAppendFloat64Fixed1からBenchmarkAppendFloat64Fixed4：float64の固定桁数変換の性能を測定します。これらのベンチマークで劇的な改善が示されています。

これらの変更により、FormatFloatは、特に固定桁数での変換において、より効率的かつ高速に動作するようになりました。

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

`src/pkg/strconv/extfloat.go`

import "math" の削除。
Assign 関数の削除。

frexp10 関数のシグネチャ変更と内部定数化。

--- a/src/pkg/strconv/extfloat.go
+++ b/src/pkg/strconv/extfloat.go
@@ -354,16 +341,17 @@ func (f *extFloat) AssignDecimal(mantissa uint64, exp10 int, neg bool, trunc boo
 // f by an approximate power of ten 10^-exp, and returns exp10, so
 // that f*10^exp10 has the same value as the old f, up to an ulp,
 // as well as the index of 10^-exp in the powersOfTen table.
-// The arguments expMin and expMax constrain the final value of the
-// binary exponent of f.\n-func (f *extFloat) frexp10(expMin, expMax int) (exp10, index int) {
-// it is illegal to call this function with a too restrictive exponent range.\n-// if expMax-expMin <= 25 {
-// panic("strconv: invalid exponent range")
-// }\n+func (f *extFloat) frexp10() (exp10, index int) {
++	// The constants expMin and expMax constrain the final value of the
++	// binary exponent of f. We want a small integral part in the result
++	// because finding digits of an integer requires divisions, whereas
++	// digits of the fractional part can be found by repeatedly multiplying
++	// by 10.
++	const expMin = -60
++	const expMax = -32
 	// Find power of ten such that x * 10^n has a binary exponent
-// between expMin and expMax\n-	approxExp10 := -(f.exp + 100) * 28 / 93 // log(10)/log(2) is close to 93/28.\n+	// between expMin and expMax.
++	approxExp10 := ((expMin+expMax)/2 - f.exp) * 28 / 93 // log(10)/log(2) is close to 93/28.
 	i := (approxExp10 - firstPowerOfTen) / stepPowerOfTen
 Loop:
 	for {

FixedDecimal メソッドの追加。
adjustLastDigitFixed 関数の追加。

`src/pkg/strconv/ftoa.go`

genericFtoa 関数のロジック変更。
- optimize フラグによる高速パスの分岐。
- extFloat.FixedDecimal の呼び出し。
- bigFtoa へのフォールバック。
bigFtoa 関数の新規追加（従来の多倍長演算ロジックを分離）。
formatDigits 関数の新規追加（共通のフォーマットロジック）。
fmtE 関数の最適化。

`src/pkg/strconv/ftoa_test.go`

TestFtoaRandom に固定精度での'e'フォーマットのテストケースを追加。
BenchmarkAppendFloat64Fixed 系のベンチマーク関数を新規追加。

コアとなるコードの解説

`extfloat.go`における`FixedDecimal`と`adjustLastDigitFixed`

FixedDecimalメソッドは、固定桁数での浮動小数点数変換の高速化の鍵となります。

// FixedDecimal stores in d the first n significant digits
// of the decimal representation of f. It returns false
// if it cannot be sure of the answer.
func (f *extFloat) FixedDecimal(d *decimalSlice, n int) bool {
	// ... (ゼロ値のハンドリング、n=0のパニックチェック)

	f.Normalize() // extFloatを正規化
	exp10, _ := f.frexp10() // 10のべき乗でスケーリングし、指数を調整

	shift := uint(-f.exp) // シフト量
	integer := uint32(f.mant >> shift) // 整数部
	fraction := f.mant - (uint64(integer) << shift) // 小数部
	ε := uint64(1) // 不確実性（誤差）

	// 整数部の桁を計算し、decimalSliceに書き込む
	// ...

	// 小数部の桁を計算し、decimalSliceに書き込む
	if needed > 0 {
		// ...
		for needed > 0 {
			fraction *= 10
			ε *= 10 // 不確実性もスケール
			if 2*ε > 1<<shift {
				// 誤差が大きすぎて正確な桁を決定できない場合、falseを返す
				return false
			}
			digit := fraction >> shift
			d.d[nd] = byte(digit + '0')
			fraction -= digit << shift
			nd++
			needed--
		}
		d.nd = nd
	}

	// 丸め処理
	ok := adjustLastDigitFixed(d, uint64(rest)<<shift|fraction, pow10, shift, ε)
	if !ok {
		return false
	}
	// 末尾のゼロをトリム
	// ...
	return true
}

このFixedDecimalは、extFloatの仮数部と指数部から直接十進数の桁を抽出し、decimalSliceに格納します。特に重要なのは、ε（不確実性）を追跡し、誤差が大きくなりすぎて正確な桁を決定できない場合にfalseを返す点です。これにより、高速だが限定的なアルゴリズムの適用範囲を明確にし、必要に応じてより堅牢なbigFtoaにフォールバックするメカニズムを提供します。

adjustLastDigitFixed関数は、FixedDecimalによって生成された桁列の最後の桁を、残りの小数部と不確実性に基づいて適切に丸める役割を担います。

// adjustLastDigitFixed assumes d contains the representation of the integral part
// of some number, whose fractional part is num / (den << shift). The numerator
// num is only known up to an uncertainty of size ε, assumed to be less than
// (den << shift)/2.
// ...
func adjustLastDigitFixed(d *decimalSlice, num, den uint64, shift uint, ε uint64) bool {
	// ... (入力チェック)

	if 2*(num+ε) < den<<shift {
		// 丸め不要
		return true
	}
	if 2*(num-ε) > den<<shift {
		// 最後の桁をインクリメント
		// ...
		return true
	}
	// 不確実性が大きすぎて丸めを決定できない場合
	return false
}

この関数は、残りの小数部が0.5より大きいか小さいかを判断し、必要に応じて最後の桁をインクリメントします。ここでも、不確実性εが考慮され、丸めを確実に決定できない場合はfalseが返されます。

`ftoa.go`における`genericFtoa`の変更

genericFtoa関数は、FormatFloatの主要な実装であり、このコミットでその内部ロジックが大きく変更されました。

func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
	// ... (特殊な値のハンドリング)

	if !optimize { // 最適化が無効な場合、常にbigFtoaを使用
		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	}

	var digs decimalSlice
	ok := false
	shortest := prec < 0 // 最短表現モードか

	if shortest {
		// Grisu3アルゴリズムを試行 (ShortestDecimal)
		// ...
		ok = f.ShortestDecimal(&digs, &lower, &upper)
		if !ok {
			return bigFtoa(dst, prec, fmt, neg, mant, exp, flt) // 失敗したらbigFtoaにフォールバック
		}
		// 最短表現モードでの精度設定
		// ...
	} else if fmt != 'f' { // 固定桁数かつ'e'または'g'フォーマットの場合
		digits := prec
		switch fmt {
		case 'e', 'E':
			digits++
		case 'g', 'G':
			if prec == 0 {
				prec = 1
			}
			digits = prec
		}
		if digits <= 15 { // 桁数が妥当な範囲の場合、高速アルゴリズムを試行
			var buf [24]byte
			digs.d = buf[:]
			f := extFloat{mant, exp - int(flt.mantbits), neg}
			ok = f.FixedDecimal(&digs, digits) // FixedDecimalを呼び出す
		}
	}

	if !ok { // 高速パスが失敗した場合、bigFtoaにフォールバック
		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	}
	return formatDigits(dst, shortest, neg, digs, prec, fmt) // 結果をフォーマット
}

この変更により、genericFtoaは、まず高速なFixedDecimal（固定桁数）またはShortestDecimal（最短表現、Grisu3）を試行し、これらのアルゴリズムが適用できない場合や、不確実性により正確な結果が得られない場合にのみ、より汎用的な（しかし遅い）bigFtoaにフォールバックするようになりました。これにより、多くの一般的なケースで変換速度が大幅に向上します。

参考にした情報源リンク

Go言語のソースコード (src/pkg/strconv/extfloat.go, src/pkg/strconv/ftoa.go, src/pkg/strconv/ftoa_test.go)
コミットメッセージとベンチマーク結果
浮動小数点数から文字列への変換アルゴリズムに関する一般的な知識 (Grisu3など)
Go言語のベンチマークに関するドキュメント

comemo