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

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

このコミットは、Go言語の標準ライブラリstrconvパッケージにおけるatof64（文字列をfloat64に変換する関数）のパフォーマンスを大幅に改善することを目的としています。具体的には、ベンチマーク結果で示されているように、最大で約4倍の高速化を実現しています。この改善は、浮動小数点数の文字列解析と変換ロジックの最適化によって達成されました。

コミット

  • コミットハッシュ: cad480440d4d826de6384d136e3c2e0072cb34b8
  • Author: Rémy Oudompheng oudomphe@phare.normalesup.org
  • Date: Sat Apr 21 13:56:51 2012 +0200
  • コミットメッセージ: strconv: 2x-4x speed improvement for atof64.

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

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

元コミット内容

strconv: 2x-4x speed improvement for atof64.

benchmark                      old ns/op    new ns/op    delta
BenchmarkAtof64Decimal               344           71  -79.22%
BenchmarkAtof64Float                 397           90  -77.15%
BenchmarkAtof64FloatExp              445          241  -45.84%
BenchmarkAtof64Big                   731          324  -55.68%
BenchmarkAtof64RandomBits            761          453  -40.47%
BenchmarkAtof64RandomFloats          690          314  -54.49%

R=dave, rsc
CC=golang-dev, remy
https://golang.org/cl/5988053

変更の背景

この変更の背景には、strconv.ParseFloat（内部でatof64を呼び出す）が、特に数値計算を多用するアプリケーションにおいてパフォーマンスのボトルネックとなっていたという問題があります。コミットメッセージに示されているベンチマーク結果は、この関数の実行時間が大幅に短縮されたことを明確に示しており、様々な種類の浮動小数点数文字列（小数点、通常の浮動小数点数、指数表記、大きな数値、ランダムなビット/浮動小数点数）に対して一貫して2倍から4倍の高速化が達成されています。これは、Go言語で数値データを扱う際の全体的な効率向上に寄与します。

前提知識の解説

  • strconvパッケージ: Go言語の標準ライブラリの一部で、基本的なデータ型（文字列、整数、浮動小数点数、ブール値など）間の変換機能を提供します。ParseFloat関数は、文字列を浮動小数点数に変換するために使用されます。
  • atof64関数: strconvパッケージの内部関数で、文字列をfloat64型に変換する主要なロジックを担っています。
  • 浮動小数点数表現: float64はIEEE 754倍精度浮動小数点数形式で表現されます。これは、符号部 (sign)、指数部 (exponent)、仮数部 (mantissa/fraction) の3つの部分から構成されます。文字列から浮動小数点数への変換は、これらの各部分を正確に解析し、バイナリ表現に変換する複雑なプロセスです。
  • decimal構造体: 変更前のコードでは、文字列で表現された10進数を内部的に保持し、その後の浮動小数点数変換の基盤となる構造体でした。
  • extFloat構造体: 浮動小数点数の内部表現をより柔軟に扱うための拡張された浮動小数点数構造体で、高精度な計算や丸め処理に利用されます。
  • ULP (Unit in the Last Place): 浮動小数点数の精度を測る単位で、ある浮動小数点数と、その次に表現可能な浮動小数点数との間の最小の差を表します。errorscaleという用語は、このULPを基準とした誤差の許容範囲を示唆しています。
  • 正確な変換 (Exact Conversion) と近似変換: 浮動小数点数は有限の精度しか持たないため、全ての10進数を正確に表現できるわけではありません。正確な変換とは、10進数表現が浮動小数点数で完全に表現できる場合に、その正確な値を生成することです。近似変換は、正確な表現が不可能な場合に、最も近い浮動小数点数を生成することを目指します。

技術的詳細

このコミットにおけるatof64の速度改善は、主に以下の技術的変更によって実現されています。

  1. special関数の最適化:

    • "NaN", "Inf", "-Inf"などの特殊な浮動小数点数文字列の解析が最適化されました。
    • 変更前はequalIgnoreCase関数を複数回呼び出していましたが、変更後は文字列の最初の文字に基づいてswitch文で分岐し、不要な比較を減らすことで効率化を図っています。これにより、特殊なケースの処理が高速化されます。

  2. readFloat関数の導入:

    • 文字列から浮動小数点数の仮数部（mantissa）と指数部（exp）を直接読み取る新しい関数readFloatが導入されました。
    • この関数は、符号、小数点、数字、指数表記（e/E）を効率的に解析し、uint64の仮数とintの指数を返します。
    • 特に、先行ゼロの無視、小数点位置の正確な追跡、そしてuint64の範囲を超える大きな仮数に対するtrunc（切り捨て）フラグの導入により、文字列解析の初期段階でのオーバーヘッドが削減されています。
    • 以前のdecimal構造体を用いた解析よりも、より直接的かつ効率的な方法で数値部分を抽出できるようになりました。

  3. atof64exact関数の導入と最適化されたパス:

    • readFloatで抽出された仮数と指数を用いて、純粋な浮動小数点演算で正確な変換が可能かどうかを試みるatof64exact関数が追加されました。
    • この関数は、特に整数値、または整数値に10の累乗を乗算/除算した値など、浮動小数点数で正確に表現できる可能性のあるケースを高速に処理します。
    • mantissaがfloat64の仮数部のビット数を超える場合に早期リターンすることで、不必要な計算を避けています。
    • float64pow10配列を利用して10の累乗との乗算/除算を効率的に行い、正確な結果を迅速に導き出します。
    • この「高速パス」は、多くの一般的な数値に対してdecimalToFloatBitsのようなより複雑でコストのかかる変換ロジックを回避することを可能にし、大幅な速度向上に貢献しています。

  4. decimal構造体からのatof64intとatou64の削除:

    • readFloat関数の導入に伴い、decimal構造体からatof64intとatou64という、10進数から整数やuint64を抽出する関数が削除されました。
    • これは、文字列解析の初期段階で直接仮数と指数を抽出する新しいアプローチが、以前のdecimal構造体を介した処理よりも効率的であることを示しています。

  5. extFloat.AssignDecimalの変更:

    • extFloat.AssignDecimal関数が、decimal構造体ではなく、直接mantissa, exp10, neg, truncを受け取るように変更されました。
    • これにより、readFloatで解析された結果を直接extFloatに渡せるようになり、中間的なデータ構造の変換や冗長な処理が削減され、全体的な変換パイプラインが簡素化・高速化されました。
    • 特に、uint64digitsとerrorscaleを用いた精度管理と、uint64pow10配列を利用した10の累乗の乗算の最適化が引き続き行われています。

これらの変更は、文字列から浮動小数点数への変換プロセスを、より直接的で、特殊なケースや一般的なケースに対して最適化されたパスを持つように再構築することで、全体的なパフォーマンスを向上させています。

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

このコミットで主に変更されたファイルと、その中の主要な関数/メソッドは以下の通りです。

  • src/pkg/strconv/atof.go:

    • special関数: 特殊な浮動小数点数文字列の解析ロジックが変更されました。
    • readFloat関数: 新規追加。文字列から仮数と指数を直接読み取ります。
    • atof64exact関数: 新規追加。純粋な浮動小数点演算で正確な変換を試みます。
    • atof64関数: readFloatとatof64exactを利用するようにロジックが大幅に書き換えられました。
    • decimal構造体からatof64intとatou64メソッドが削除されました。

  • src/pkg/strconv/extfloat.go:

    • extFloat.AssignDecimalメソッド: 引数が変更され、decimal構造体ではなく、直接仮数、指数、符号、切り捨てフラグを受け取るようになりました。

  • src/pkg/strconv/strconv_test.go:

    • ParseFloatのベンチマークテストケースが追加されました。

コアとなるコードの解説

readFloat関数

func readFloat(s string) (mantissa uint64, exp int, neg, trunc, ok bool) {
	// ... (省略) ...
	// optional sign
	// ... (省略) ...
	// digits
	// ... (省略) ...
	// optional exponent moves decimal point.
	// ... (省略) ...
	exp = dp - ndMant
	ok = true
	return
}

readFloatは、文字列sを解析し、浮動小数点数の数値部分をmantissa (仮数部、uint64型), exp (指数部、int型), neg (負の数かどうか), trunc (仮数部が切り捨てられたかどうか) として抽出します。

  • 符号の処理: 文字列の先頭の+または-を処理し、negフラグを設定します。
  • 数字の解析: 小数点（.）と数字（0-9）を読み取ります。
    • 先行ゼロは無視されます。
    • mantissaは、uint64digits（19桁）の範囲内で数字を累積します。
    • uint64digitsを超える桁数がある場合、truncフラグがtrueに設定され、仮数部が切り捨てられたことを示します。これは、後続のより高精度な変換パスが必要になる可能性を示唆します。
    • dpは小数点の位置を追跡し、ndMantは仮数部の有効桁数を記録します。
  • 指数部の解析: eまたはEに続く指数部分を解析します。
    • 指数はesign（符号）とe（数値）に分解され、dpに加算されます。
    • 非常に大きな指数は、e < 10000のチェックでクリップされますが、これは浮動小数点数の範囲を考慮すると十分な精度を提供します。
  • 結果の計算: 最終的なexpは、小数点の位置dpから仮数部の有効桁数ndMantを引いた値として計算されます。

この関数は、文字列から浮動小数点数の構成要素を直接かつ効率的に抽出するための重要なステップです。

atof64exact関数

func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) {
	if mantissa>>float64info.mantbits != 0 {
		return
	}
	f = float64(mantissa)
	if neg {
		f = -f
	}
	switch {
	case exp == 0: // an integer.
		return f, true
	case exp > 0 && exp <= 15+22: // int * 10^k
		// ... (省略) ...
		return f * float64pow10[exp], true
	case exp < 0 && exp >= -22: // int / 10^k
		return f / float64pow10[-exp], true
	}
	return
}

atof64exactは、readFloatで得られたmantissa、exp、negを用いて、純粋な浮動小数点演算で正確なfloat64への変換が可能かどうかを試みます。

  • 仮数部のチェック: mantissa>>float64info.mantbits != 0は、mantissaがfloat64の仮数部で表現できる範囲を超えているかどうかをチェックします。超えている場合は、正確な変換は不可能なのでfalseを返します。
  • 基本値の設定: f = float64(mantissa)で仮数部をfloat64に変換し、必要に応じて符号を適用します。
  • ケースごとの処理:
    • exp == 0: 仮数部がそのまま整数として表現できる場合。
    • exp > 0: 仮数部に10の累乗を乗算するケース（例: 123e2 -> 123 * 10^2）。float64pow10配列を使用して効率的に乗算を行います。expが非常に大きい場合でも、1e15や-1e15の範囲を超えないようにチェックし、オーバーフローを防ぎます。
    • exp < 0: 仮数部を10の累乗で除算するケース（例: 123e-2 -> 123 / 10^2）。同様にfloat64pow10配列を使用します。
  • 成功時のリターン: 変換が成功し、正確なfloat64が得られた場合はf, trueを返します。それ以外の場合はf, falseを返します。

この関数は、多くの一般的な数値に対して、より複雑な高精度変換ロジックを回避し、高速なパスを提供することで、atof64全体のパフォーマンス向上に大きく貢献しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード（src/pkg/strconv/atof.go, src/pkg/strconv/extfloat.go, src/pkg/strconv/strconv_test.go）
  • IEEE 754 浮動小数点数標準に関する一般的な知識
  • Go言語のstrconvパッケージに関するドキュメント