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

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

このコミットは、Go言語の標準ライブラリstrconvパッケージにおける浮動小数点数変換関数atof（ASCII to Float）のパフォーマンス改善と、オーバーフロー・アンダーフロー処理の強化を目的としています。特に、一般的なケースでの変換速度を大幅に向上させ、同時に数値の範囲外の入力に対する堅牢性を高めています。

コミット

commit ed628ca79beefd78bb901b7ab3712391927c6f3b
Author: Russ Cox <rsc@golang.org>
Date:   Mon Nov 17 17:22:51 2008 -0800

    * faster atof for common cases
      (gets 3x speedup in go; got 40x in c)
    * handle and test overflow
    
    R=r
    DELTA=217  (200 added, 0 deleted, 17 changed)
    OCL=19399
    CL=19422

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

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

元コミット内容

このコミットの元の内容は以下の通りです。

  • 一般的なケースでのatofの高速化（Goでは3倍、Cでは40倍の速度向上を達成）。
  • オーバーフローの処理とテストの追加。

変更の背景

浮動小数点数の文字列変換（atof）は、多くのアプリケーションで頻繁に使用される基本的な操作です。特に、数値計算を多用するGo言語のようなシステムプログラミング言語においては、この変換の効率が全体のパフォーマンスに大きく影響します。

このコミットが行われた2008年当時、Go言語はまだ初期段階にあり、パフォーマンスの最適化が活発に行われていました。atofのような基本的な関数の速度向上は、Go言語の実行時性能を全体的に引き上げる上で非常に重要でした。また、数値のオーバーフローやアンダーフローといった境界条件の正確な処理は、数値計算の信頼性を保証するために不可欠です。以前の実装では、これらのエッジケースに対する処理が不十分であったか、あるいは最適化されていなかった可能性があります。

Russ Cox氏によるこの変更は、特に「一般的なケース」に焦点を当てることで、多くの実用的なシナリオでのパフォーマンスを改善しつつ、同時にIEEE 754浮動小数点数標準に準拠した正確なオーバーフロー処理を導入することを目指しました。C言語での40倍という速度向上は、この最適化が非常に効果的であったことを示しています。

前提知識の解説

浮動小数点数（Floating-Point Numbers）

コンピュータにおける浮動小数点数は、実数を近似的に表現するための形式です。一般的にIEEE 754標準に従って表現され、符号部、指数部、仮数部（または有効数字部）の3つの要素で構成されます。

  • 符号部 (Sign Bit): 数値が正か負かを示します（0: 正、1: 負）。
  • 指数部 (Exponent): 数値の大きさを表し、基数（通常は2）の何乗かを決定します。バイアス形式で表現されることが多く、実際の指数値に一定のオフセットが加算されています。
  • 仮数部 (Mantissa/Significand): 数値の精度を表す部分です。通常、正規化された形式では、仮数部の先頭には暗黙の「1」があるため、実際に格納されるのは小数点以下の部分のみです。

float32（単精度）とfloat64（倍精度）は、それぞれ32ビットと64ビットで表現される浮動小数点数です。float64はより広い範囲と高い精度を持ちます。

IEEE 754標準

IEEE 754は、浮動小数点数の表現と演算に関する国際標準です。この標準は、浮動小数点数の計算結果の一貫性と移植性を保証するために重要です。

  • 正規化数 (Normalized Numbers): 指数部が0でも最大値でもない通常の浮動小数点数。
  • 非正規化数 (Denormalized Numbers): 指数部が0で、仮数部が0でない数。非常に小さい数を表現するために使用され、精度が低下する可能性があります。
  • ゼロ (Zero): +0と-0があります。
  • 無限大 (Infinity): オーバーフローの結果として生じる+Infと-Infがあります。
  • 非数 (NaN - Not a Number): 不正な演算（例: 0/0、sqrt(-1)）の結果として生じます。

atof関数

atof（ASCII to Float）は、文字列形式の数値を浮動小数点数に変換する関数です。Go言語のstrconvパッケージでは、ParseFloat関数がこれに相当します。この変換プロセスは、文字列を解析し、符号、整数部、小数部、指数部を抽出し、それらを浮動小数点数の内部表現（符号、指数、仮数）に変換する複雑なアルゴリズムを伴います。

オーバーフローとアンダーフロー

  • オーバーフロー (Overflow): 計算結果が、そのデータ型で表現できる最大値を超えた場合に発生します。浮動小数点数の場合、結果は通常+Infまたは-Infになります。
  • アンダーフロー (Underflow): 計算結果が、そのデータ型で表現できる最小の非ゼロ値よりも小さくなった場合に発生します。浮動小数点数の場合、結果は通常0または非正規化数になります。

性能最適化の一般的なアプローチ

文字列から数値への変換のような処理では、以下の最適化手法がよく用いられます。

  1. 共通ケースの高速化: 頻繁に発生する入力パターン（例: 整数、小数点以下が少ない数、指数部が小さい数）に対して、より単純で高速なアルゴリズムを適用します。
  2. ルックアップテーブル: 繰り返し計算される値（例: 10の累乗）を事前に計算して配列に格納し、ルックアップで取得することで計算コストを削減します。
  3. 分岐予測の最適化: 条件分岐を減らすか、予測しやすいようにコードを構造化することで、CPUのパイプライン効率を向上させます。
  4. 直接的な浮動小数点演算: 可能な限り、高精度な任意精度演算ではなく、CPUの浮動小数点ユニット（FPU）による直接的な演算を利用します。

技術的詳細

このコミットの技術的詳細は、主にstrconv/atof.goファイルにおけるStringToDecimal、DecimalToFloatBits、そして新しく追加されたDecimalToFloat64/DecimalToFloat32関数に見られます。

StringToDecimalの変更

StringToDecimal関数は、文字列をDecimal型（内部的に数値の各桁と小数点位置を保持する構造体）に変換する役割を担います。この関数における変更点は、指数部の処理にあります。

		for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
			if e < 10000 { // 追加された行
				e = e*10 + int(s[i]) - '0';
			}
		}

この変更は、指数eが非常に大きくなるのを防ぐためのものです。もし指数が10000を超えた場合、その数値はほぼ確実にfloat64の表現範囲を超えて無限大になるため、正確な指数値を計算し続ける必要がありません。これにより、非常に長い指数を持つ文字列に対する処理が高速化されます。

DecimalToFloatBitsの変更とオーバーフロー処理

DecimalToFloatBits関数は、Decimal型で表現された数値を、最終的な浮動小数点数のビット表現（符号、指数、仮数）に変換する中心的なロジックです。このコミットでは、特にオーバーフローとアンダーフローの検出と処理が強化されました。

	// Obvious overflow/underflow.
	// These bounds are for 64-bit floats.
	// Will have to change if we want to support 80-bit floats in the future.
	if d.dp > 310 { // オーバーフローの境界チェック
		goto overflow;
	}
	if d.dp < -330 { // アンダーフローの境界チェック
		// zero
		mant = 0;
		exp = flt.bias;
		goto out;
	}

ここでd.dpは小数点位置を示し、これが非常に大きい（310より大きい）場合はオーバーフロー、非常に小さい（-330より小さい）場合はアンダーフロー（ゼロに丸められる）と判断されます。これらのマジックナンバーは、float64（IEEE 754倍精度浮動小数点数）の最大値（約1.8e+308）と最小の非ゼロ正規化数（約2.2e-308）の範囲に基づいています。

また、丸め処理によって仮数部が桁上がりした場合の指数部の調整と、それに伴うオーバーフローチェックも追加されています。

	// Rounding might have added a bit; shift down.
	if mant == 2<<flt.mantbits {
		mant >>= 1;
		exp++;
		if exp-flt.bias >= 1<<flt.expbits - 1 {
			goto overflow;
		}
	}

goto overflowとgoto outラベルが導入され、コードの可読性とエラーハンドリングの一貫性が向上しています。overflowラベルでは、結果を±Inf（無限大）に設定し、overflowフラグをtrueに設定します。

DecimalToFloat64/DecimalToFloat32と高速化

このコミットの最も重要なパフォーマンス改善は、DecimalToFloat64とDecimalToFloat32という新しいヘルパー関数の導入です。これらの関数は、特定の「一般的なケース」において、より複雑なDecimalToFloatBitsのロジックを迂回し、直接的な浮動小数点演算で結果を導き出すことを試みます。

「一般的なケース」とは、主に以下の3つのパターンを指します。

  1. 厳密な整数 (Exact Integer): 例: "123", "-45"
  2. 厳密な整数 × 10の厳密な累乗 (Exact Integer * Exact Power of Ten): 例: "123e5", "4500"
  3. 厳密な整数 ÷ 10の厳密な累乗 (Exact Integer / Exact Power of Ten): 例: "1.23", "0.0045"

これらのケースでは、文字列をまず整数として読み込み、その後で10の累乗を乗算または除算することで、正確かつ高速に浮動小数点数に変換できます。

この最適化を可能にするために、float64pow10とfloat32pow10という、10の累乗を事前に計算して格納したルックアップテーブルが導入されました。

var float64pow10 = []float64 {
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
	1e20, 1e21, 1e22
}
var float32pow10 = []float32 {
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10
}

DecimalToFloat64関数内では、入力Decimalの桁数d.ndと小数点位置d.dpを基に、上記の3つのケースのいずれかに該当するかを判断します。

  • d.dp == d.nd: 整数
  • d.dp > d.nd: 整数に10の累乗を乗算するケース
  • d.dp < d.nd: 整数を10の累乗で除算するケース

これらのケースに該当する場合、DecimalToFloat64Int（またはDecimalToFloat32Int）で整数部分を抽出し、float64pow10（またはfloat32pow10）を使って適切な10の累乗を乗算/除算します。これにより、高精度な任意精度演算を必要とするDecimalToFloatBitsの呼び出しを回避し、大幅な速度向上を実現しています。

atof64関数の変更

atof64関数は、strconvパッケージの外部に公開される主要な関数であり、文字列をfloat64に変換します。このコミットにより、atof64は変換結果のfloat64値と、変換中にオーバーフローが発生したかどうかを示すoverflowブール値を返すようになりました。

export func atof64(s string) (f float64, overflow bool, ok bool) {
	neg, d, trunc, ok1 := StringToDecimal(s);
	if !ok1 {
		return 0, false, false; // 変更点: overflowも返す
	}
	// ...
	f, overflow = DecimalToFloat64(neg, d, trunc); // 変更点: overflowも受け取る
	if overflow {
		return f, overflow, true;
	}
	// ...
	f, overflow = DecimalToFloatBits(neg, d, trunc, &float64info); // 変更点: overflowも受け取る
	return f, overflow, true;
}

この変更により、呼び出し元は変換が成功したかどうか（ok）だけでなく、結果が無限大になった原因がオーバーフローによるものかどうかも正確に判断できるようになります。

テストの追加

src/lib/strconv/testatof.goには、新しいテストケースが多数追加されました。これらは、特に以下のシナリオを網羅しています。

  • float64の最大値と、それをわずかに超える値（+Infになることを確認）。
  • float64の最小の非ゼロ正規化数と、それをわずかに下回る値（0になることを確認）。
  • 非常に大きな指数を持つ数値（オーバーフローして+Infになることを確認）。
  • 非常に小さな指数を持つ数値（アンダーフローして0になることを確認）。
  • 不正な形式の入力文字列（エラーになることを確認）。

これらのテストは、新しいオーバーフロー/アンダーフロー処理が正しく機能すること、および一般的なケースの高速化が既存の正確性を損なわないことを保証するために不可欠です。テストフレームワークも、atof64が返すoverflowフラグを適切にチェックするように更新されています。

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

このコミットにおけるコアとなるコードの変更箇所は、主に以下のファイルと関数に集中しています。

  • src/lib/strconv/atof.go:
    • StringToDecimal関数における指数部の処理（e < 10000のチェック）。
    • DecimalToFloatBits関数におけるオーバーフロー/アンダーフローの境界チェックとgotoによる処理フローの変更。
    • DecimalToFloatBits関数における丸め処理後の指数部調整とオーバーフローチェック。
    • float64pow10およびfloat32pow10という定数配列の追加。
    • DecimalToFloat64IntおよびDecimalToFloat32Int関数の追加。
    • DecimalToFloat64およびDecimalToFloat32関数の追加。
    • atof64関数の戻り値にoverflowブール値の追加。
  • src/lib/strconv/testatof.go:
    • tests変数に多数の新しいテストケースの追加。
    • テスト実行ロジックにおいて、atof64のoverflow戻り値のチェックを追加。

コアとなるコードの解説

src/lib/strconv/atof.go

StringToDecimalの指数部処理

		for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
			if e < 10000 { // ここで指数eが大きくなりすぎないように制限
				e = e*10 + int(s[i]) - '0';
			}
		}

この変更は、指数部が非常に長い文字列（例: "1e1000000"）を処理する際のパフォーマンスを向上させます。float64の最大指数は約308なので、指数が10000を超えるような場合は、最終的な結果はほぼ確実に無限大になります。そのため、正確な指数値を計算し続ける必要がなく、計算を途中で打ち切ることで無駄な処理を省いています。

DecimalToFloatBitsのオーバーフロー/アンダーフロー処理

	if d.dp > 310 { // float64の最大指数に対応する小数点位置の閾値
		goto overflow;
	}
	if d.dp < -330 { // float64の最小非ゼロ正規化数に対応する小数点位置の閾値
		// zero
		mant = 0;
		exp = flt.bias;
		goto out;
	}

d.dpはDecimal構造体内の小数点位置を表します。この値が310より大きい場合、数値はfloat64の表現可能な最大値を超え、オーバーフローします。逆に-330より小さい場合、数値はfloat64の表現可能な最小の非ゼロ正規化数よりも小さくなり、アンダーフローしてゼロに丸められます。これらのチェックにより、高精度な計算に入る前に、明らかなオーバーフロー/アンダーフローを早期に検出して処理できます。

DecimalToFloat64 / DecimalToFloat32

func DecimalToFloat64(neg bool, d *Decimal, trunc bool) (f float64, ok bool) {
	// Exact integers are <= 10^15.
	// Exact powers of ten are <= 10^22.
	if d.nd > 15 { // 桁数が多すぎる場合は、高速パスをスキップ
		return;
	}
	switch {
	case d.dp == d.nd:	// int (例: "123")
		f := DecimalToFloat64Int(neg, d);
		return f, true;

	case d.dp > d.nd && d.dp <= 15+22:	// int * 10^k (例: "123e5")
		f := DecimalToFloat64Int(neg, d);
		k := d.dp - d.nd;
		// If exponent is big but number of digits is not,
		// can move a few zeros into the integer part.
		if k > 22 { // 10の累乗が大きすぎる場合、一部を整数部に含める
			f *= float64pow10[k-22];
			k = 22;
		}
		return f*float64pow10[k], true;

	case d.dp < d.nd && d.nd - d.dp <= 22:	// int / 10^k (例: "1.23")
		f := DecimalToFloat64Int(neg, d);
		return f/float64pow10[d.nd - d.dp], true;
	}
	return;
}

この関数は、このコミットのパフォーマンス改善の核心です。入力されたDecimalが、事前に計算された10の累乗（float64pow10）と直接的な浮動小数点演算で処理できる「一般的なケース」に該当するかどうかを判断します。該当する場合、DecimalToFloatBitsのような複雑な任意精度演算をスキップし、CPUのFPUを直接利用することで、大幅な速度向上を実現します。d.nd（桁数）とd.dp（小数点位置）を基に、整数、整数×10の累乗、整数÷10の累乗の3つのパターンを効率的に処理します。

src/lib/strconv/testatof.go

新しいテストケース

	// largest float64
	Test{ "1.7976931348623157e308", "1.7976931348623157e+308" },
	Test{ "-1.7976931348623157e308", "-1.7976931348623157e+308" },
	// next float64 - too large
	Test{ "1.7976931348623159e308", "+Inf" },
	Test{ "-1.7976931348623159e308", "-Inf" },
	// ...
	// way too large
	Test{ "1e310", "+Inf" },
	Test{ "-1e310", "-Inf" },
	// ...
	// denormalized
	Test{ "1e-305", "1e-305" },
	// ...
	// too small
	Test{ "4e-324", "0" },
	// ...
	// try to overflow exponent
	Test{ "1e-4294967296", "0" },
	Test{ "1e+4294967296", "+Inf" },

これらのテストケースは、float64の表現可能な範囲の境界値、オーバーフロー、アンダーフロー、非正規化数、そして非常に大きな/小さな指数を持つ数値に対するatofの挙動を厳密に検証します。これにより、変更が数値の正確性と堅牢性を損なわないことが保証されます。

テストロジックの変更

		if overflow && !sys.isInf(f, 0) {
			panicln("overflow but not inf:", t.in, f);
		}
		if sys.isInf(f, 0) && !overflow {
			panicln("inf but not overflow:", t.in, f);
		}

atof64がoverflowブール値を返すようになったため、テストロジックもこれを活用して、結果が無限大である場合にoverflowフラグが正しく設定されているか、またはその逆を検証します。これにより、オーバーフロー検出の正確性が保証されます。

関連リンク

  • Go言語のstrconvパッケージのドキュメント: https://pkg.go.dev/strconv
  • IEEE 754浮動小数点数標準に関する情報（Wikipediaなど）

参考にした情報源リンク

  • Go言語のソースコード（src/lib/strconv/atof.goおよびsrc/lib/strconv/testatof.go）
  • IEEE 754浮動小数点数標準に関する一般的な情報源
  • 数値解析および浮動小数点演算に関する書籍やオンラインリソース