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

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

このコミットは、Go言語の標準ライブラリ strconv パッケージにおける10進数文字列から浮動小数点数への変換（ParseFloat、atof）の性能改善を目的としています。特に、指数部を持つ数値やランダムなビットパターンを持つ数値の解析において、大幅な高速化を実現しています。

コミット

commit 2368b003e0d663e07079f1f250e954a51a64144b
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Dec 19 16:45:51 2011 -0500

    strconv: implement faster parsing of decimal numbers.
    
    The algorithm is the same as in the double-conversion library
    which also implements Florian Loitsch's fast printing algorithm.
    It uses extended floats with a 64-bit mantissa, but cannot give
    an answer for all cases.
    
                               old ns/op  new ns/op  speedup
    BenchmarkAtof64Decimal         332        322      1.0x
    BenchmarkAtof64Float           385        373      1.0x
    BenchmarkAtof64FloatExp       9777        419     23.3x
    BenchmarkAtof64Big            3934        691      5.7x
    BenchmarkAtof64RandomBits    34060        899     37.9x
    BenchmarkAtof64RandomFloats   1329        680      2.0x
    
    See F. Loitsch, ``Printing Floating-Point Numbers Quickly and
    Accurately with Integers'', Proceedings of the ACM, 2010.
    
    R=ality, rsc
    CC=golang-dev, remy
    https://golang.org/cl/5494068

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

https://github.com/golang/go/commit/2368b003e0d663e07079f1f250e954a51a64144b

元コミット内容

strconv: implement faster parsing of decimal numbers.

このコミットは、strconv パッケージにおいて、10進数文字列のより高速な解析を実装します。このアルゴリズムは、Florian Loitschの高速な浮動小数点数出力アルゴリズムも実装している double-conversion ライブラリと同じものです。64ビットの仮数部を持つ拡張浮動小数点数を使用しますが、全ての場合に正確な結果を保証できるわけではありません。

ベンチマーク結果は以下の通りです。

ベンチマーク名旧 ns/op新 ns/op速度向上
BenchmarkAtof64Decimal3323221.0x
BenchmarkAtof64Float3853731.0x
BenchmarkAtof64FloatExp977741923.3x
BenchmarkAtof64Big39346915.7x
BenchmarkAtof64RandomBits3406089937.9x
BenchmarkAtof64RandomFloats13296802.0x

参照文献として、F. Loitschの論文「Printing Floating-Point Numbers Quickly and Accurately with Integers」（Proceedings of the ACM, 2010）が挙げられています。

変更の背景

浮動小数点数の文字列解析は、計算機科学において長年の課題でした。特に、10進数表記の文字列をIEEE 754標準の2進数浮動小数点数に正確かつ効率的に変換することは複雑です。従来のアルゴリズムは、精度を保証するために多倍長演算を必要とすることが多く、これが性能のボトルネックとなっていました。

このコミットの背景には、Go言語の strconv パッケージにおける ParseFloat 関数の性能改善の必要性がありました。特に、指数部を持つ数値や、ランダムな浮動小数点数（ビットパターン）の解析において、既存の実装が非効率であることがベンチマークによって示されていました。より高速な解析アルゴリズムを導入することで、これらのケースでのパフォーマンスを大幅に向上させ、Go言語アプリケーション全体の数値処理性能を高めることが期待されました。

参照されている double-conversion ライブラリは、Googleによって開発された、浮動小数点数と文字列間の高速かつ正確な変換を提供するライブラリです。このライブラリは、Florian Loitschのアルゴリズムをベースにしており、その効率性が広く認識されていました。このコミットは、その実績あるアルゴリズムをGo言語の strconv パッケージに移植することで、性能向上を図るものです。

前提知識の解説

このコミットを理解するためには、以下の前提知識が役立ちます。

浮動小数点数表現 (IEEE 754)

コンピュータにおける浮動小数点数は、通常IEEE 754標準に従って表現されます。これは、符号ビット、指数部、仮数部（または分数部）の3つの要素で構成されます。

  • 符号ビット (Sign Bit): 数値が正か負かを示します。
  • 指数部 (Exponent): 数値の大きさを表します。基数（通常は2）の何乗かを指定します。
  • 仮数部 (Mantissa / Significand): 数値の精度を表します。有効数字の部分です。

float64 は倍精度浮動小数点数であり、64ビットで表現されます。内訳は通常、1ビットの符号、11ビットの指数、52ビットの仮数です。

10進数から2進数浮動小数点数への変換の課題

10進数表記の文字列（例: "0.1"）を2進数浮動小数点数に変換する際、多くの10進小数は2進数で正確に表現できません。例えば、10進数の0.1は2進数では無限小数になります。このため、変換は最も近い2進数浮動小数点数に丸められる必要があります。この丸め処理を正確に行うためには、元の10進数の値を非常に高い精度で内部的に保持し、最終的な2進数表現を決定する必要があります。

従来のアルゴリズムでは、この高精度な計算に多倍長整数演算を用いることが多く、これが計算コストの増大につながっていました。

Florian Loitschのアルゴリズム

Florian Loitschの「Printing Floating-Point Numbers Quickly and Accurately with Integers」という論文（2010年）は、浮動小数点数を文字列に変換する（ftoa）ための効率的かつ正確なアルゴリズムを提案しています。このアルゴリズムは、整数演算とビットシフトを駆使することで、浮動小数点数の正確な文字列表現を高速に生成します。

このコミットでは、Loitschのアルゴリズムが「浮動小数点数から文字列への変換」だけでなく、「文字列から浮動小数点数への変換」（atof）にも応用できることを示唆しています。特に、double-conversion ライブラリがこのアルゴリズムを両方向の変換に利用している点が重要です。

double-conversion ライブラリ

double-conversion は、Googleが開発したC++ライブラリで、浮動小数点数と文字列間の高速かつ正確な変換を提供します。このライブラリは、Loitschのアルゴリズムやその他の最適化技術を組み合わせて、高い性能と精度を実現しています。このコミットは、double-conversion のアプローチをGo言語に持ち込むことで、strconv パッケージの性能を向上させようとしています。

拡張浮動小数点数 (Extended Floats)

このコミットで言及されている「extended floats with a 64-bit mantissa」は、標準の float64 (52ビット仮数) よりも高い精度を持つ内部表現を指します。これにより、変換の中間段階で発生する丸め誤差を最小限に抑え、最終的な float64 値をより正確に決定することが可能になります。この拡張された精度は、最終的な float64 への丸め処理において、正しい結果を導き出すための「余裕」を提供します。

技術的詳細

このコミットの技術的詳細は、主に extFloat という新しい型と、それを用いた atof64 関数の新しい高速パスの実装に集約されます。

extFloat 型の導入

src/pkg/strconv/extfloat.go に新しく extFloat 型が定義されています。これは、標準の float64 よりも高い精度を持つ拡張浮動小数点数を表現するための構造体です。

type extFloat struct {
	mant uint64 // 仮数部 (64ビット)
	exp  int    // 指数部
	neg  bool   // 符号 (負の場合true)
}

extFloat は mant * (2^exp) という形式で数値を表現します。mant が uint64 であるため、標準の float64 の仮数部（52ビット）よりも多くのビット（64ビット）を保持でき、これにより高い精度を実現しています。

extFloat の主要なメソッド

  • Normalize(): extFloat の仮数部を正規化します。仮数部の最上位ビットがセットされるように左シフトし、それに応じて指数部を調整します。これにより、数値の表現が一意になり、後の計算が容易になります。
  • Multiply(g extFloat): 2つの extFloat を乗算します。結果は正確に丸められますが、正規化はされません。このメソッドは、特に10のべき乗を乗算する際に使用されます。fhi, flo := f.mant>>32, uint64(uint32(f.mant)) のように、64ビットの仮数部を2つの32ビット部分に分割し、クロス積を計算することで、オーバーフローを避けつつ乗算を行います。
  • floatBits(): extFloat の値を最も近い float64 に変換し、そのビット表現を返します。このメソッド内で、extFloat の高い精度から float64 の精度への丸め処理が行われます。オーバーフローが発生した場合は overflow フラグが true になります。
  • AssignDecimal(d *decimal): decimal 型（strconv パッケージ内で10進数文字列を内部的に表現する型）の値を extFloat に割り当てます。このメソッドが、10進数文字列から extFloat への変換の核心部分です。
    • d.atou64() を使用して、10進数文字列の先頭から最大19桁（uint64 で表現できる最大桁数）の整数部分を mant10 として抽出します。
    • 10のべき乗による乗算を効率的に行うために、smallPowersOfTen と powersOfTen という定数配列が使用されます。これらは、double-conversion ライブラリから取得された、特定の10のべき乗の extFloat 表現です。
    • 変換の過程で発生する誤差を errors 変数で追跡し、最終的に float64 に丸めた際に、この誤差が結果に影響を与える可能性があるかどうかを判断します。もし誤差が大きすぎて正確な丸めが保証できない場合（return false）、従来の遅いパスにフォールバックします。

atof.go における高速パスの追加

src/pkg/strconv/atof.go の atof64 関数に、新しい高速パスが追加されています。

		// Try another fast path.
		ext := new(extFloat)
		if ok := ext.AssignDecimal(&d); ok {
			b, ovf := ext.floatBits()
			f = math.Float64frombits(b)
			if ovf {
				err = rangeError(fnParseFloat, s)
			}
			return f, err
		}

このコードブロックは、decimal 型の d を extFloat に変換し、その変換が成功した場合（ok が true の場合）に、extFloat から float64 のビット表現を取得して結果を返します。AssignDecimal が false を返した場合、つまり extFloat を用いた変換では正確な丸めが保証できないと判断された場合は、この高速パスはスキップされ、従来のより汎用的だが遅いアルゴリズムが実行されます。

atof_test.go におけるベンチマークとテストの追加

src/pkg/strconv/atof_test.go には、新しいベンチマークとランダムな入力に対するテストが追加されています。

  • TestAtofRandom: ランダムに生成された float64 値を文字列に変換し、その文字列を再度 ParseFloat で解析して元の値と比較するテストです。これにより、新しい解析アルゴリズムの正確性が広範囲の入力で検証されます。
  • BenchmarkAtof64FloatExp: 指数部を持つ浮動小数点数の解析性能を測定します。コミットメッセージのベンチマーク結果で最も大きな速度向上が見られた項目です。
  • BenchmarkAtof64Big: 非常に大きな整数部分を持つ数値の解析性能を測定します。
  • BenchmarkAtof64RandomBits: ランダムなビットパターンを持つ float64 値を文字列に変換し、その文字列を解析する性能を測定します。これも大きな速度向上が見られた項目です。
  • BenchmarkAtof64RandomFloats: rand.NormFloat64() で生成された正規分布に従うランダムな浮動小数点数の解析性能を測定します。

これらのテストとベンチマークは、新しいアルゴリズムが実際に性能向上をもたらし、かつ正確であることを確認するために不可欠です。

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

このコミットにおけるコアとなるコードの変更箇所は以下の4ファイルです。

  1. src/pkg/strconv/Makefile:

    • extfloat.go がビルド対象のGoファイルリストに追加されています。 
      --- a/src/pkg/strconv/Makefile
+++ b/src/pkg/strconv/Makefile
@@ -10,6 +10,7 @@ GOFILES=\
 	atof.go\
 	atoi.go\
 	decimal.go\
+\textfloat.go\
 	ftoa.go\
 	itoa.go\
 	quote.go\

  2. src/pkg/strconv/atof.go:

    • decimal 型に atou64() メソッドが追加されました。これは、10進数文字列から uint64 の仮数部を読み取るためのヘルパー関数です。
    • atof64 関数内に、extFloat を使用した新しい高速パスが追加されました。 
      // Reads a uint64 decimal mantissa, which might be truncated.
func (d *decimal) atou64() (mant uint64, digits int) {
	const uint64digits = 19
	for i, c := range d.d[:d.nd] {
		if i == uint64digits {
			return mant, i
		}
		mant = 10*mant + uint64(c-'0')
	}
	return mant, d.nd
}

// ... (中略) ...

	// Try another fast path.
	ext := new(extFloat)
	if ok := ext.AssignDecimal(&d); ok {
		b, ovf := ext.floatBits()
		f = math.Float64frombits(b)
		if ovf {
			err = rangeError(fnParseFloat, s)
		}
		return f, err
	}

  3. src/pkg/strconv/atof_test.go:

    • atofRandomTests などの新しいテストデータ構造が追加されました。
    • init() 関数内で、ランダムな浮動小数点数文字列を生成し、テストおよびベンチマーク用のデータとして準備するロジックが追加されました。
    • TestAtofRandom 関数が追加され、ランダムな入力に対する ParseFloat の正確性を検証します。
    • BenchmarkAtof64FloatExp, BenchmarkAtof64Big, BenchmarkAtof64RandomBits, BenchmarkAtof64RandomFloats といった新しいベンチマーク関数が追加され、新しいアルゴリズムの性能を測定します。

  4. src/pkg/strconv/extfloat.go:

    • このファイルが新規作成されました。
    • extFloat 構造体とその関連メソッド（Normalize, Multiply, floatBits, AssignDecimal など）が定義されています。
    • smallPowersOfTen と powersOfTen という、double-conversion ライブラリから派生した10のべき乗の extFloat 表現の定数配列が定義されています。

コアとなるコードの解説

このコミットの核心は、src/pkg/strconv/extfloat.go で定義される extFloat 型と、それを利用して strconv/atof.go の atof64 関数に導入された新しい高速パスです。

extFloat の役割

extFloat は、float64 (倍精度浮動小数点数) よりも高い精度で数値を表現するための内部データ構造です。float64 の仮数部が52ビットであるのに対し、extFloat は64ビットの仮数部 (uint64 mant) を持ちます。これにより、10進数文字列を2進数浮動小数点数に変換する際の中間計算で発生する丸め誤差を最小限に抑え、最終的な float64 値をより正確に決定するための「余裕」を提供します。

AssignDecimal メソッドの重要性

extFloat の AssignDecimal(d *decimal) メソッドは、この高速パスの鍵となる部分です。

  1. 10進数仮数部の抽出: まず、入力された decimal 型のデータから、atou64() ヘルパー関数を使って、uint64 に収まる範囲の10進数仮数部 (mant10) を抽出します。
  2. 10のべき乗の乗算: 抽出した仮数部と、元の10進数の指数部 (exp10) を考慮して、適切な10のべき乗を extFloat に乗算します。この乗算には、事前に計算された smallPowersOfTen と powersOfTen という extFloat の定数配列が使用されます。これらの定数は、double-conversion ライブラリから得られたもので、特定の10のべき乗を効率的に表現します。
  3. 誤差の追跡と保証: 変換の過程で発生する誤差を errors 変数で追跡します。この誤差が、最終的に float64 に丸める際に結果を曖昧にするほど大きいかどうかを判断します。具体的には、extFloat の仮数部と誤差の範囲を比較し、丸め方向が不確定になる可能性がある場合は false を返します。

高速パスの動作原理

atof64 関数内で、extFloat を使用した高速パスが試行されます。

  • ext.AssignDecimal(&d) が true を返した場合、それは extFloat を用いた変換で正確な float64 値を決定できることを意味します。この場合、ext.floatBits() を呼び出して extFloat から float64 のビット表現を取得し、それを math.Float64frombits() で float64 に変換して返します。これにより、従来の多倍長演算を伴う複雑なパスをスキップし、大幅な高速化が実現されます。
  • ext.AssignDecimal(&d) が false を返した場合、extFloat だけでは正確な丸めが保証できないため、この高速パスはスキップされ、従来のより堅牢だが遅いアルゴリズム（おそらく多倍長演算を使用するもの）にフォールバックします。

このアプローチにより、多くの場合（特にコミットメッセージのベンチマークで示されたようなケース）で高速な変換が可能になり、正確性が保証できない稀なケースでは従来のアルゴリズムに頼ることで、堅牢性を維持しています。

ベンチマーク結果の分析

コミットメッセージのベンチマーク結果は、この変更の有効性を明確に示しています。

  • BenchmarkAtof64Decimal と BenchmarkAtof64Float は、比較的単純な10進数や浮動小数点数の文字列解析であり、既存のパスでも効率的だったため、速度向上はわずかです（約1.0x）。
  • BenchmarkAtof64FloatExp (指数部を持つ数値) と BenchmarkAtof64RandomBits (ランダムなビットパターンを持つ数値) では、それぞれ 23.3x と 37.9x という劇的な速度向上が見られます。これは、これらのケースで従来のアルゴリズムが非常に非効率であったこと、そして新しい extFloat ベースの高速パスがこれらのケースに特に有効であることを示しています。
  • BenchmarkAtof64Big (大きな整数部分を持つ数値) も 5.7x の速度向上を示しており、extFloat の64ビット仮数部が大きな数値の処理にも寄与していることがわかります。

これらの結果は、新しいアルゴリズムがGo言語の strconv パッケージの浮動小数点数解析性能を大幅に改善したことを裏付けています。

関連リンク

参考にした情報源リンク

  • F. Loitsch, ``Printing Floating-Point Numbers Quickly and Accurately with Integers'', Proceedings of the ACM, 2010. (論文への直接リンクは提供されていませんが、ACM Digital Libraryなどで検索可能です。)
  • Go言語の変更リスト (CL): https://golang.org/cl/5494068
    • このコミットの元となったGo言語のコードレビューと変更提案のページです。詳細な議論や追加のコンテキストが含まれている場合があります。
  • IEEE 754 浮動小数点数標準: 浮動小数点数の表現に関する国際標準。
  • Go言語の math パッケージ: math.Float64frombits など、浮動小数点数操作に関連する関数が定義されています。