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

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

このコミットは、Go言語の標準ライブラリstrconvパッケージにおける、多倍長精度浮動小数点数（multi-precision decimals）の内部バッファサイズを削減するものです。具体的には、decimal構造体内のdフィールド（桁を保持するバイト配列）のサイズを2000バイトから800バイトに縮小することで、パフォーマンスの向上とメモリ使用量の削減を図っています。特に、最小の非正規化数（smallest denormals）の表現に必要な桁数を考慮し、過剰なゼロ初期化によるオーバーヘッドを削減することが目的です。

コミット

  • Author: Rémy Oudompheng oudomphe@phare.normalesup.org
  • Date: Mon Dec 19 15:03:53 2011 -0500
  • Commit Hash: 3a2dec0246fe66af7871edd4b84840371988aeb2

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

https://github.com/golang/go/commit/3a2dec0246fe66af7871edd4b84840371988aeb2

元コミット内容

strconv: reduce buffer size for multi-precision decimals.

The longest numbers we have to represent are the smallest denormals.
Their decimal mantissa is not longer than 5^1100. Taking into
account some extra size for in-place operations, 800 digits are
enough. This saves time used for zero intiialization of extra
bytes.

                                        old ns/op  new ns/op    delta
strconv_test.BenchmarkAtof64Decimal           521        334   -35.9%
strconv_test.BenchmarkAtof64Float             572        391   -31.6%
strconv_test.BenchmarkAtof64FloatExp        10242      10036    -2.0%
strconv_test.BenchmarkAtof64Big              4229       4029    -4.7%
strconv_test.BenchmarkFormatFloatDecimal     1396        934   -33.1%
strconv_test.BenchmarkFormatFloat            4295       3341   -22.2%
strconv_test.BenchmarkFormatFloatExp        12035      11181    -7.1%
strconv_test.BenchmarkFormatFloatBig         4213       3229   -23.4%
strconv_test.BenchmarkAppendFloatDecimal     1031        600   -41.8%
strconv_test.BenchmarkAppendFloat            3971       3044   -23.3%
strconv_test.BenchmarkAppendFloatExp        11699      11003    -5.9%
strconv_test.BenchmarkAppendFloatBig         3836       2915   -24.0%

R=golang-dev, bradfitz, rsc
CC=golang-dev, remy
https://golang.org/cl/5491064

変更の背景

この変更の主な背景は、strconvパッケージにおける浮動小数点数の文字列変換処理のパフォーマンス改善です。特に、非常に小さい非正規化数（denormalized numbers）を10進数で表現する際に、必要とされる桁数が過剰に見積もられていたことが問題でした。

コミットメッセージによると、表現する必要がある最も長い数値は「最小の非正規化数（smallest denormals）」であり、その10進数での仮数部（mantissa）は「5^1100」よりも長くならないとされています。これまでの実装では、この最大桁数に対して2000バイトのバッファが確保されていましたが、実際のところ800桁で十分であることが判明しました。

バッファサイズを2000バイトから800バイトに削減することで、以下のメリットが期待されます。

  1. メモリ使用量の削減: decimal構造体を使用する際に確保されるメモリ量が減少します。
  2. ゼロ初期化のオーバーヘッド削減: Go言語では、配列などの固定サイズのデータ構造はデフォルトでゼロ値に初期化されます。バッファサイズが大きければ大きいほど、このゼロ初期化にかかる時間が増加します。バッファサイズを削減することで、この初期化コストが低減され、特に頻繁に浮動小数点数変換が行われる場合に顕著なパフォーマンス改善が見込まれます。

コミットメッセージに記載されているベンチマーク結果は、この変更が実際に多くのstrconv関連の操作（Atof64、FormatFloat、AppendFloatなど）において、大幅な速度向上（最大で約41.8%の改善）をもたらしたことを示しています。

前提知識の解説

strconvパッケージ

Go言語の標準ライブラリであるstrconvパッケージは、基本的なデータ型（真偽値、整数、浮動小数点数）と文字列との間の変換機能を提供します。例えば、文字列を整数にパースしたり（Atoi）、浮動小数点数を文字列にフォーマットしたり（FormatFloat）する際に使用されます。このパッケージは、数値の正確な表現と効率的な変換を目的としています。

浮動小数点数と非正規化数（Denormalized Numbers）

コンピュータにおける浮動小数点数は、IEEE 754規格に基づいて表現されることが一般的です。これは、数値を「符号部」「指数部」「仮数部」の3つの要素で表現します。

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

通常の浮動小数点数は、仮数部の先頭に暗黙の「1」があるものとして表現されます（正規化数）。しかし、非常に0に近い数値を表現する際には、指数部が最小値に達し、これ以上小さくできない場合があります。このような場合、仮数部の先頭の暗黙の「1」をなくし、仮数部自体で0に近い値を表現することで、より小さな数値を表現できるようにします。これが**非正規化数（Denormalized Numbers）またはサブノーマル数（Subnormal Numbers）**と呼ばれます。

非正規化数は、アンダーフロー（underflow）を回避し、0へのスムーズな移行を可能にするために導入されました。しかし、非正規化数の演算は、正規化数に比べて処理が遅くなる傾向があります。

5^1100の桁数

コミットメッセージにある「Their decimal mantissa is not longer than 5^1100」という記述は、非正規化数を10進数で表現した際の仮数部の最大桁数に関するものです。

5^1100という数値の桁数を概算するには、常用対数（底が10の対数）を使用します。 log10(5^1100) = 1100 * log10(5) log10(5)は約0.69897です。 1100 * 0.69897 = 768.867

この計算結果から、5^1100は約769桁の10進数であることがわかります。これは、非正規化数を10進数で表現する際に、最大で約769桁の仮数部が必要になることを示唆しています。コミットメッセージでは「800 digits are enough」とされており、これはこの概算値に少し余裕を持たせた値であることが理解できます。

技術的詳細

このコミットは、strconvパッケージ内部のdecimal構造体における固定長配列のサイズを最適化するものです。

decimal構造体は、浮動小数点数を10進数として内部的に表現するために使用されます。この構造体には、10進数の各桁をバイトとして格納するdという配列が含まれています。

変更前は、d配列のサイズが[2000]byteと定義されていました。これは、最大で2000桁の10進数を表現できることを意味します。しかし、前述の通り、最も長い非正規化数でも約769桁で表現できるため、2000バイトというサイズは過剰でした。

変更後は、d配列のサイズが[800]byteに削減されました。この800バイトというサイズは、5^1100の桁数（約769桁）に加えて、内部的な操作（例えば、桁のシフトや丸め処理など）のための十分な余裕を考慮した上で決定されたものです。

この変更がもたらす技術的な影響は以下の通りです。

  1. スタックまたはヒープメモリの削減: decimal構造体がスタックに割り当てられる場合（小さい構造体の場合や、関数内で一時的に使用される場合）、スタックフレームのサイズが小さくなります。ヒープに割り当てられる場合（エスケープ解析によってヒープに割り当てられると判断された場合）、ヒープの断片化が減少し、ガベージコレクションの負荷が軽減される可能性があります。
  2. キャッシュ効率の向上: 構造体のサイズが小さくなることで、CPUのキャッシュラインに収まりやすくなり、データアクセスが高速化される可能性があります。
  3. ゼロ初期化の高速化: Go言語では、固定長配列は宣言時にゼロ値で初期化されます。2000バイトの配列をゼロ初期化するよりも、800バイトの配列をゼロ初期化する方が、CPUサイクルが少なくて済みます。これは、特に浮動小数点数変換が頻繁に行われるアプリケーションにおいて、顕著なパフォーマンス向上に繋がります。

ベンチマーク結果が示すように、この変更はstrconvパッケージの多くの関数で大幅な性能改善を実現しており、特に浮動小数点数の文字列変換における効率が向上したことを裏付けています。

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

変更はsrc/pkg/strconv/decimal.goファイルにあります。

--- a/src/pkg/strconv/decimal.go
+++ b/src/pkg/strconv/decimal.go
@@ -14,9 +14,9 @@ package strconv
 type decimal struct {
 	// TODO(rsc): Can make d[] a bit smaller and add
 	// truncated bool;
-	d   [2000]byte // digits
-	nd  int        // number of digits used
-	dp  int        // decimal point
+	d   [800]byte // digits
+	nd  int       // number of digits used
+	dp  int       // decimal point
 	neg bool
 }

具体的には、decimal構造体の定義において、dフィールドの配列サイズが[2000]byteから[800]byteに変更されています。

コアとなるコードの解説

decimal構造体は、strconvパッケージが浮動小数点数を10進数として内部的に操作するために使用するデータ構造です。

  • d [N]byte: このフィールドは、10進数の各桁をバイトとして格納する固定長配列です。例えば、数値「123」はd[0]=1, d[1]=2, d[2]=3のように格納されます。このコミットでは、このNの値が2000から800に変更されました。
  • nd int: d配列の中で実際に使用されている桁数を示します。
  • dp int: 小数点の位置を示します。
  • neg bool: 数値が負であるかどうかを示します。

このコミットの核心は、d配列のサイズを2000から800に減らした点にあります。これは、Goのコンパイラがこの構造体を扱う際に、より少ないメモリを割り当て、初期化にかかる時間を短縮することを可能にします。

以前の2000バイトというサイズは、おそらく最悪ケースを想定して大きめに設定されていたか、あるいは初期の段階で厳密な分析が行われていなかった可能性があります。しかし、詳細な分析（最小の非正規化数の10進数表現が5^1100の桁数を超えないという知見）により、800バイトで十分であることが判明し、この最適化が実施されました。

この変更は、strconvパッケージが浮動小数点数を文字列に変換する際の内部的な処理効率を直接的に改善し、結果としてGoプログラム全体のパフォーマンス向上に貢献します。

関連リンク

参考にした情報源リンク