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

このコミットは、Go言語のstrconvパッケージにおける浮動小数点数から文字列への変換関数であるAppendFloatおよびFormatFloatのパフォーマンスを大幅に改善することを目的としています。特に、大きな構造体のゼロ初期化を排除することで、高速パスが失敗した場合にのみ必要となるリソースの無駄をなくし、処理速度を向上させています。また、float32のラウンドトリップテストが不足していたため、それも追加されています。

コミット

• コミットハッシュ: ff03482fd6c38ac41835bef2dfd75f5ecc41eb1d
• Author: Rémy Oudompheng oudomphe@phare.normalesup.org
• Date: Sun Aug 5 20:30:13 2012 +0200

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

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

元コミット内容

strconv: speedup AppendFloat/FormatFloat.

The improvement is obtained by eliminating the zero
initialization of a large structure that is only
needed when the fast path fails.

Also add a missing roundtrip test for float32s.

benchmark                              old ns/op    new ns/op    delta
BenchmarkAppendFloatDecimal                  301          180  -40.20%
BenchmarkAppendFloat                         486          388  -20.16%
BenchmarkAppendFloatExp                      492          383  -22.15%
BenchmarkAppendFloatNegExp                   478          370  -22.59%
BenchmarkAppendFloatBig                      650          541  -16.77%
BenchmarkAppendFloat32Integer                308          180  -41.56%
BenchmarkAppendFloat32ExactFraction          449          333  -25.84%
BenchmarkAppendFloat32Point                  494          390  -21.05%
BenchmarkAppendFloat32Exp                    488          387  -20.70%
BenchmarkAppendFloat32NegExp                 488          378  -22.54%

R=r, rsc
CC=golang-dev, remy
https://golang.org/cl/6346081

変更の背景

このコミットの主な背景は、Go言語のstrconvパッケージにおける浮動小数点数から文字列への変換処理のパフォーマンス改善です。特に、AppendFloatやFormatFloatといった関数は、数値の表示において頻繁に利用されるため、その性能はアプリケーション全体の応答性に大きく影響します。

元の実装では、浮動小数点数の変換処理において、特定の「高速パス」（Grisu3アルゴリズムなど、一般的なケースで高速に処理できるパス）が失敗した場合にのみ必要となる、比較的大きなデータ構造（decimal構造体）が常にゼロ初期化されていました。このゼロ初期化は、高速パスが成功した場合でも無駄に実行されるため、オーバーヘッドとなっていました。

コミットメッセージに示されているベンチマーク結果からも明らかなように、この無駄な初期化を排除することで、様々な浮動小数点数変換のシナリオにおいて、20%から40%以上の大幅な速度向上が達成されています。これは、特に数値計算を多用するアプリケーションや、大量のログ出力を行うシステムにおいて、顕著な性能改善をもたらします。

また、float32型の数値に対するラウンドトリップテスト（文字列に変換し、再度数値に戻したときに元の値と一致するかを確認するテスト）が不足していたことも、この変更の背景にあります。浮動小数点数の文字列変換は、精度が非常に重要であり、特にfloat32のような単精度浮動小数点数では、特定の境界値や特殊な値での挙動が問題となることがあります。このテストの追加は、変換の正確性と堅牢性を保証するために不可欠でした。

前提知識の解説

strconvパッケージ

strconvパッケージは、Go言語の標準ライブラリの一部であり、基本的なデータ型（数値、真偽値など）と文字列との間の変換機能を提供します。例えば、整数を文字列に変換したり、文字列を浮動小数点数にパースしたりする際に使用されます。

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

コンピュータにおける浮動小数点数は、IEEE 754標準に基づいて表現されます。これは、符号部、指数部、仮数部（または有効数字部）の3つの要素で構成されます。

• 符号部 (Sign): 数値が正か負かを示します。
• 指数部 (Exponent): 数値の大きさを表し、小数点位置を決定します。
• 仮数部 (Mantissa/Significand): 数値の精度（有効桁数）を表します。

float64は倍精度浮動小数点数、float32は単精度浮動小数点数であり、それぞれ異なるビット数でこれらの要素を表現するため、表現できる数値の範囲と精度が異なります。

AppendFloatとFormatFloat

• AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte: 浮動小数点数fを文字列に変換し、既存のバイトスライスdstに追加します。fmtはフォーマット（'e', 'E', 'f', 'g', 'G'）、precは精度、bitSizeは元の浮動小数点数のビットサイズ（32または64）を指定します。
• FormatFloat(f float64, fmt byte, prec, bitSize int) string: AppendFloatと同様の変換を行い、結果を新しい文字列として返します。

これらの関数は、内部で浮動小数点数を10進数表現に変換する複雑なアルゴリズムを使用します。

Grisu3アルゴリズム

Grisu3は、浮動小数点数を最短かつ正確な10進数文字列に変換するための高速なアルゴリズムです。このアルゴリズムは、ほとんどの浮動小数点数に対して非常に効率的ですが、一部の特殊なケースでは失敗することがあります。Grisu3が失敗した場合、より汎用的だが低速なアルゴリズム（例えば、正確な10進数表現を計算する方法）にフォールバックする必要があります。

extFloatとdecimal型

strconvパッケージの内部では、浮動小数点数の変換処理を効率的に行うために、extFloatとdecimalというカスタムデータ型が使用されています。

• extFloat: 浮動小数点数をより高い精度で内部的に表現するための構造体です。特に、変換処理の中間段階で精度を失わないようにするために利用されます。
• decimal: 浮動小数点数を10進数の桁列として表現するための構造体です。変換の最終段階で、この10進数表現から文字列が生成されます。

技術的詳細

このコミットの技術的な核心は、strconvパッケージ内の浮動小数点数から文字列への変換ロジック、特にftoa.goとextfloat.goファイルにおける最適化です。

ゼロ初期化の排除とdecimalSliceの導入

変更前は、genericFtoa関数内でd := new(decimal)という行があり、これはdecimal構造体へのポインタを割り当て、その構造体をゼロ初期化していました。このdecimal構造体は、浮動小数点数を10進数表現で保持するためのもので、比較的大きなメモリ領域を占めます。問題は、Grisu3アルゴリズムのような高速パスが成功した場合でも、このdecimal構造体が常に初期化されていた点です。高速パスが成功すれば、このdecimal構造体は不要になるため、その初期化は無駄なオーバーヘッドとなっていました。

このコミットでは、この無駄なゼロ初期化を排除するために、decimalSliceという新しい型が導入されました。decimalSliceは、decimal構造体全体を割り当てるのではなく、バイトスライス（[]byte）と、そのスライス内の有効な桁数（nd）、小数点位置（dp）、符号（neg）を保持する軽量な構造体です。

具体的には、genericFtoa関数内で、var digs decimalSliceと宣言され、var buf [32]byteというスタック上に確保された小さなバイト配列をdigs.d = buf[:]として利用するように変更されました。これにより、Grisu3アルゴリズムが成功するケースでは、ヒープアロケーションとそれに伴うゼロ初期化が不要になり、スタック上のメモリを再利用できるようになります。これは、Goのガベージコレクタの負荷を軽減し、キャッシュ効率を向上させるため、顕著なパフォーマンス向上に繋がります。

Grisu3が失敗し、より正確な（しかし遅い）変換が必要な場合には、以前と同様にd := new(decimal)が実行され、decimal構造体がヒープに割り当てられます。しかし、これは高速パスが失敗した場合に限定されるため、全体としてのオーバーヘッドは大幅に削減されます。

extfloat.goの変更

extfloat.goでは、ShortestDecimal関数のシグネチャが変更されました。以前は*decimalポインタを受け取っていましたが、新しいdecimalSlice型を受け取るように変更されました。

// Before
func (f *extFloat) ShortestDecimal(d *decimal, lower, upper *extFloat) bool

// After
func (f *extFloat) ShortestDecimal(d *decimalSlice, lower, upper *extFloat) bool

また、extFloatが正確な整数である場合の処理も変更されました。以前はd.Assign(f.mant)でdecimal構造体に直接値を割り当てていましたが、新しい実装では、スタック上に一時的なバイト配列bufを作成し、そこに数値を桁ごとに書き込み、その内容をdecimalSliceにコピーするように変更されました。これにより、decimal構造体のメソッドを呼び出すことなく、直接decimalSliceを操作できるようになり、効率が向上しています。

atof_test.goの変更

atof_test.goには、float32のラウンドトリップテストが追加されました。これは、特定のfloat32値（2^92）が文字列に変換され、その後再びfloat32にパースされたときに、元の値と正確に一致するかどうかを検証するものです。このテストは、浮動小数点数変換の精度と堅牢性を保証するために重要です。特に、float32はfloat64よりも精度が低いため、このような境界値でのテストは不可欠です。

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

src/pkg/strconv/extfloat.go

• ShortestDecimal関数の引数型が*decimalから*decimalSliceに変更。
• extFloatが正確な整数である場合の処理で、decimal構造体への直接割り当てから、スタック上のバイト配列bufを使ったdecimalSliceへのコピーに変更。
• adjustLastDigit関数の引数型も*decimalから*decimalSliceに変更。

src/pkg/strconv/ftoa.go

• genericFtoa関数内で、decimal構造体の代わりにdecimalSlice型digsが導入され、スタック上のバイト配列bufをその基盤として使用。
• Grisu3アルゴリズム（f.ShortestDecimal）の呼び出しで、decimalSliceのポインタを渡すように変更。
• Grisu3が失敗した場合のフォールバックパスでのみnew(decimal)が実行されるように変更。
• fmtE, fmtF関数がdecimalSliceを引数として受け取るように変更。
• decimalSlice構造体の定義が追加。

src/pkg/strconv/atof_test.go

• atof32testsスライスに、float32のラウンドトリップテストケースが追加。

コアとなるコードの解説

src/pkg/strconv/ftoa.goにおける変更

// Before
-	d := new(decimal)
// After
+	var digs decimalSlice
    if shortest {
        ok := false
        if optimize {
            f := new(extFloat)
            lower, upper := f.AssignComputeBounds(mant, exp, neg, flt)
// Before
-			ok = f.ShortestDecimal(d, &lower, &upper)
// After
+			var buf [32]byte
+			digs.d = buf[:]
+			ok = f.ShortestDecimal(&digs, &lower, &upper)
        }
        if !ok {
            // Create exact decimal representation.
// Before
-			d := new(decimal) // This line was not here before, it was just 'd.Assign(mant)'
// After
+			d := new(decimal) // This line is now here, only if !ok
            d.Assign(mant)
            d.Shift(exp - int(flt.mantbits))
            roundShortest(d, mant, exp, flt)
+			digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
        }
        // ... (precision calculation using digs)
    } else {
        // Create exact decimal representation.
// Before
-		d := new(decimal) // This line was not here before, it was just 'd.Assign(mant)'
// After
+		d := new(decimal) // This line is now here
        d.Assign(mant)
        d.Shift(exp - int(flt.mantbits))
        // ... (rounding logic)
+		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
    }

    switch fmt {
    case 'e', 'E':
// Before
-		return fmtE(dst, neg, d, prec, fmt)
// After
+		return fmtE(dst, neg, digs, prec, fmt)
    // ... similar changes for fmtF and fmtG
    }

この変更の核心は、decimal構造体のヒープアロケーションとゼロ初期化を、必要な場合にのみ行うように遅延させた点です。

1. decimalSliceの導入: var digs decimalSliceとvar buf [32]byteにより、スタック上にdecimalSliceのメタデータと、最大32バイトの桁データを格納するバッファが確保されます。これにより、Grisu3アルゴリズムが成功するほとんどのケースで、ヒープアロケーションが完全に回避されます。
2. 条件付きヒープアロケーション: if !okブロック内でd := new(decimal)が実行されるのは、Grisu3アルゴリズム（高速パス）が浮動小数点数を最短の10進数に変換できなかった場合のみです。この場合、より複雑で正確な変換が必要となり、decimal構造体が必要になります。
3. decimalSliceへの変換: decimal構造体が作成された場合でも、最終的にはその内容がdecimalSliceにコピーされ、以降のフォーマット処理はdecimalSliceを介して行われます。これにより、コードの統一性が保たれます。
4. 関数シグネチャの変更: fmtEやfmtFなどのフォーマット関数がdecimalSliceを直接受け取るように変更されたことで、これらの関数もヒープアロケーションを伴わない効率的な処理が可能になります。

src/pkg/strconv/extfloat.goにおける変更

// Before
-func (f *extFloat) ShortestDecimal(d *decimal, lower, upper *extFloat) bool {
// After
+func (f *extFloat) ShortestDecimal(d *decimalSlice, lower, upper *extFloat) bool {
    // ...
    if f.exp == 0 && *lower == *f && *lower == *upper {
        // an exact integer.
// Before
-		d.Assign(f.mant)
// After
+		var buf [24]byte
+		n := len(buf) - 1
+		for v := f.mant; v > 0; {
+			v1 := v / 10
+			v -= 10 * v1
+			buf[n] = byte(v + '0')
+			n--
+			v = v1
+		}
+		nd := len(buf) - n - 1
+		for i := 0; i < nd; i++ {
+			d.d[i] = buf[n+1+i]
+		}
+		d.nd, d.dp = nd, nd
+		for d.nd > 0 && d.d[d.nd-1] == '0' {
+			d.nd--
+		}
+		if d.nd == 0 {
+			d.dp = 0
+		}
        d.neg = f.neg
        return true
    }
    // ...
}

ShortestDecimal関数は、Grisu3アルゴリズムの実装の一部であり、浮動小数点数を最短の10進数表現に変換しようとします。この関数がdecimalSliceを受け取るように変更されたことで、Grisu3の高速パスもヒープアロケーションなしで動作するようになります。

特に、extFloatが正確な整数である場合の処理は、decimal構造体のAssignメソッドを呼び出す代わりに、直接バイト配列bufに桁を書き込み、それをdecimalSliceに設定するように変更されました。これは、decimal構造体のメソッド呼び出しによるオーバーヘッドを排除し、より低レベルで効率的な操作を可能にします。

src/pkg/strconv/atof_test.goにおける変更

// ...
	// 2^92 = 8388608p+69 = 4951760157141521099596496896 (4.9517602e27)
	// is an exact power of two that needs 8 decimal digits to be correctly
	// parsed back.
	// The float32 before is 16777215p+68 = 4.95175986e+27
	// The halfway is 4.951760009. A bad algorithm that thinks the previous
	// float32 is 8388607p+69 will shorten incorrectly to 4.95176e+27.
	{"4951760157141521099596496896", "4.9517602e+27", nil},
}

このテストケースは、float32の変換における特定の境界条件を検証します。2^92という値は、float32で正確に表現できる2の累乗ですが、これを10進数文字列に変換し、再度float32にパースする際に、丸め誤差やアルゴリズムの不正確さによって元の値と異なる結果になる可能性があります。このテストは、変換アルゴリズムがこのようなケースでも正確に動作することを保証するために追加されました。

関連リンク

• https://golang.org/cl/6346081

参考にした情報源リンク

• IEEE 754 - Wikipedia
• Grisu3 algorithm - Google Search
• Go strconv package documentation
• Go's floating point to string conversion - The Go Programming Language (このコミットの後の記事ですが、関連する背景知識として有用です)
• Go: strconv.FormatFloat and strconv.AppendFloat performance - Stack Overflow (一般的な議論や関連情報)
• Go's strconv package source code (直接の参照元)