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

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

このコミットは、Go言語の標準ライブラリである strconv パッケージにおける浮動小数点数から文字列への変換（Ftoa）のパフォーマンスを大幅に改善することを目的としています。主な変更点は、Goコンパイラの「エスケープ解析」を最適化し、decimal 型のインスタンスがヒープではなくスタックに割り当てられるようにコードを修正したことです。これにより、ガベージコレクションの負荷が軽減され、Ftoa 関連のベンチマークで最大60%以上の高速化が実現しました。この改善は、json パッケージのエンコード/マーシャリング処理にも波及し、約22%の高速化をもたらしています。

コミット

commit 0ed5e6a2be4c7248dfb6c870c445e2504f818623
Author: Russ Cox <rsc@golang.org>
Date:   Tue Nov 15 12:17:25 2011 -0500

    strconv: make Ftoa faster

    Make code amenable to escape analysis
    so that the decimal values do not escape.

    benchmark                               old ns/op    new ns/op    delta
    strconv_test.BenchmarkAtof64Decimal           229          233   +1.75%
    strconv_test.BenchmarkAtof64Float             261          263   +0.77%
    strconv_test.BenchmarkAtof64FloatExp         7760         7757   -0.04%
    strconv_test.BenchmarkAtof64Big              3086         3053   -1.07%
    strconv_test.BenchmarkFtoa64Decimal          6866         2629  -61.71%
    strconv_test.BenchmarkFtoa64Float            7211         3064  -57.51%
    strconv_test.BenchmarkFtoa64FloatExp        12587         8263  -34.35%
    strconv_test.BenchmarkFtoa64Big              7058         2825  -59.97%
    json.BenchmarkCodeEncoder               357355200    276528200  -22.62%
    json.BenchmarkCodeMarshal               360735200    279646400  -22.48%
    json.BenchmarkCodeDecoder               731528600    709460600   -3.02%
    json.BenchmarkCodeUnmarshal             754774400    731051200   -3.14%
    json.BenchmarkCodeUnmarshalReuse        713379000    704218000   -1.28%
    json.BenchmarkSkipValue                  51594300     51682600   +0.17%

    benchmark                                old MB/s     new MB/s  speedup
    json.BenchmarkCodeEncoder                    5.43         7.02    1.29x
    json.BenchmarkCodeMarshal                    5.38         6.94    1.29x
    json.BenchmarkCodeDecoder                    2.65         2.74    1.03x
    json.BenchmarkCodeUnmarshal                  2.57         2.65    1.03x
    json.BenchmarkCodeUnmarshalReuse             2.72         2.76    1.01x
    json.BenchmarkSkipValue                     38.61        38.55    1.00x

    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/5369111

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

https://github.com/golang/go/commit/0ed5e6a2be4c7248dfb6c870c445e2504f818623

元コミット内容

strconv: make Ftoa faster

このコミットは、strconv パッケージの Ftoa 関数を高速化します。 decimal の値がエスケープしないように、エスケープ解析に適したコードに変更しました。

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

ベンチマーク名old ns/opnew ns/opdelta
strconv_test.BenchmarkAtof64Decimal229233+1.75%
strconv_test.BenchmarkAtof64Float261263+0.77%
strconv_test.BenchmarkAtof64FloatExp77607757-0.04%
strconv_test.BenchmarkAtof64Big30863053-1.07%
strconv_test.BenchmarkFtoa64Decimal68662629-61.71%
strconv_test.BenchmarkFtoa64Float72113064-57.51%
strconv_test.BenchmarkFtoa64FloatExp125878263-34.35%
strconv_test.BenchmarkFtoa64Big70582825-59.97%
json.BenchmarkCodeEncoder357355200276528200-22.62%
json.BenchmarkCodeMarshal360735200279646400-22.48%
json.BenchmarkCodeDecoder731528600709460600-3.02%
json.BenchmarkCodeUnmarshal754774400731051200-3.14%
json.BenchmarkCodeUnmarshalReuse713379000704218000-1.28%
json.BenchmarkSkipValue5159430051682600+0.17%
ベンチマーク名old MB/snew MB/sspeedup
json.BenchmarkCodeEncoder5.437.021.29x
json.BenchmarkCodeMarshal5.386.941.29x
json.BenchmarkCodeDecoder2.652.741.03x
json.BenchmarkCodeUnmarshal2.572.651.03x
json.BenchmarkCodeUnmarshalReuse2.722.761.01x
json.BenchmarkSkipValue38.6138.551.00x

変更の背景

このコミットの主な背景は、Go言語の strconv パッケージ、特に浮動小数点数を文字列に変換する Ftoa 関数のパフォーマンス改善です。Ftoa は、数値の文字列化において頻繁に利用される基盤的な関数であり、その性能は json パッケージのような、数値を頻繁にエンコード/デコードする他のパッケージの性能にも直接影響します。

コミットメッセージに示されているベンチマーク結果は、Ftoa 関連の処理が非常に遅く、特に BenchmarkFtoa64Decimal や BenchmarkFtoa64Float では数千ナノ秒/操作を要していたことを示しています。これは、大量の浮動小数点数変換が必要なアプリケーションにおいて、顕著なパフォーマンスボトルネックとなる可能性がありました。

このパフォーマンス問題の根本原因は、Goコンパイラの「エスケープ解析」が strconv パッケージ内の decimal 型のインスタンスをヒープに割り当てていたことにありました。ヒープ割り当ては、スタック割り当てに比べてオーバーヘッドが大きく、特に短命なオブジェクトが頻繁に生成される場合、ガベージコレクション（GC）の頻度と負荷が増大し、アプリケーション全体のパフォーマンスを低下させます。

したがって、このコミットの目的は、decimal 型のインスタンスがヒープにエスケープするのを防ぎ、可能な限りスタックに割り当てられるようにコードを修正することで、Ftoa の実行速度を向上させ、それに依存する他のパッケージ（特に json）のパフォーマンスも改善することでした。

前提知識の解説

Goの strconv パッケージ

strconv パッケージは、Go言語の標準ライブラリの一部であり、基本的なデータ型（整数、浮動小数点数、真偽値など）と文字列との間の変換機能を提供します。例えば、Atoi は文字列を整数に、Itoa は整数を文字列に変換します。Ftoa は浮動小数点数を文字列に変換する関数です。これらの関数は、設定ファイル解析、ネットワークプロトコル処理、データシリアライズなど、様々な場面で利用されます。

浮動小数点数から文字列への変換 (Ftoa)

浮動小数点数を文字列に変換する処理は、見た目以上に複雑です。単に数値を10進数表記に変換するだけでなく、精度、丸め処理、指数表記の有無など、様々な要素を考慮する必要があります。Goの strconv パッケージでは、IEEE 754浮動小数点数標準に準拠しつつ、効率的かつ正確な変換を行うために、内部的にdecimalのような中間表現を用いています。

Goにおけるエスケープ解析 (Escape Analysis) の概念と重要性

エスケープ解析は、Goコンパイラが行う重要な最適化の一つです。この解析は、プログラム内の変数がどこにメモリ割り当てされるべきか（スタックかヒープか）を決定します。

  • スタック割り当て: 関数内で宣言され、その関数の実行が終了すると不要になる変数は、通常、スタックに割り当てられます。スタックは高速なメモリ領域であり、割り当てと解放が非常に効率的です。
  • ヒープ割り当て: 変数がその宣言された関数のスコープを超えて「エスケープ」する場合（例：変数のアドレスが関数の外に返される、グローバル変数に格納される、チャネルを通じて送信されるなど）、その変数はヒープに割り当てられる必要があります。ヒープはより柔軟なメモリ領域ですが、割り当てと解放にはスタックよりも時間がかかり、ガベージコレクタによる管理が必要になります。

エスケープ解析の目的は、可能な限り多くの変数をスタックに割り当てることで、ヒープ割り当ての数を減らし、ガベージコレクションの頻度と実行時間を最小限に抑えることです。GCのオーバーヘッドが減ることで、アプリケーションの全体的なパフォーマンスが向上します。

スタックとヒープのメモリ割り当て

  • スタック: LIFO（Last-In, First-Out）構造を持つメモリ領域で、関数の呼び出しフレーム、ローカル変数、関数の引数などが格納されます。高速で、コンパイラがメモリの割り当てと解放を自動的に管理します。
  • ヒープ: プログラムの実行中に動的にメモリを割り当てるための領域です。スタックとは異なり、ヒープに割り当てられたメモリは、その変数が不要になったときにガベージコレクタによって自動的に解放されます。ヒープ割り当てはスタック割り当てよりも遅く、GCの負荷を伴います。

Goのベンチマーク結果の読み方 (ns/op, MB/s, delta, speedup)

Goのベンチマークは、go test -bench=. コマンドで実行でき、プログラムの性能を測定します。

  • ns/op (nanoseconds per operation): 1回の操作にかかる平均時間（ナノ秒）。この値が小さいほど高速です。
  • MB/s (megabytes per second): 1秒あたりに処理できるデータ量（メガバイト）。この値が大きいほど高速です。主にI/Oやデータ処理のベンチマークで使われます。
  • delta: 変更前と変更後の性能変化率。負の値は高速化、正の値は低速化を示します。
  • speedup: 変更後の性能が変更前の何倍になったかを示します。1より大きい値は高速化、1より小さい値は低速化を示します。

このコミットのベンチマーク結果では、Ftoa 関連の ns/op が大幅に減少（負の delta）しており、処理時間が短縮されたことを示しています。また、json 関連の MB/s が増加（speedup が1より大きい）しており、スループットが向上したことを示しています。

decimal 構造体の役割

strconv パッケージの内部で使われる decimal 構造体は、浮動小数点数を正確な10進数表現で扱うための中間データ構造です。浮動小数点数の内部表現（バイナリ）と人間が読む10進数表現の間には、しばしば丸め誤差の問題が生じます。decimal 構造体は、このような誤差を最小限に抑えつつ、正確な丸め処理や桁操作を行うために利用されます。

技術的詳細

このコミットの技術的な核心は、strconv パッケージ内で使用される decimal 構造体のインスタンスが、Goコンパイラのエスケープ解析によってヒープに割り当てられるのを防ぐためのコード変更です。

変更前は、strconv/decimal.go 内に newDecimal というヘルパー関数が存在し、これが *decimal 型のポインタを返していました。また、decimal 構造体の Round, RoundDown, RoundUp といったメソッドも *decimal を返していました。

// 変更前: newDecimal は *decimal を返す
func newDecimal(i uint64) *decimal {
	a := new(decimal)
	a.Assign(i)
	return a
}

// 変更前: Round, RoundDown, RoundUp も *decimal を返す
func (a *decimal) Round(nd int) *decimal {
	// ...
	return a // または a.RoundUp(nd) / a.RoundDown(nd)
}

Goのエスケープ解析のルールでは、関数がポインタを返す場合、そのポインタが指すデータは関数のスコープ外でも使用される可能性があるため、ヒープに割り当てられると判断される傾向があります。newDecimal や Round メソッドが *decimal を返すことで、これらの関数内で生成または操作された decimal インスタンスがヒープに「エスケープ」し、ガベージコレクションの対象となっていました。

このコミットでは、以下の変更が行われました。

  1. newDecimal 関数の削除: src/pkg/strconv/decimal.go から newDecimal 関数が削除されました。

  2. decimal メソッドの戻り値の変更: Round, RoundDown, RoundUp メソッドのシグネチャが変更され、*decimal を返す代わりに void（何も返さない）になりました。これらのメソッドは、レシーバである decimal インスタンスを直接変更するようになりました。

    // 変更後: Round, RoundDown, RoundUp は何も返さない (void)
func (a *decimal) Round(nd int) {
    // ...
}
func (a *decimal) RoundDown(nd int) {
    // ...
}
func (a *decimal) RoundUp(nd int) {
    // ...
}

  3. ftoa.go での decimal インスタンス生成方法の変更: src/pkg/strconv/ftoa.go 内で newDecimal を呼び出していた箇所が、d := new(decimal); d.Assign(mant) の形式に置き換えられました。

    // 変更前: newDecimal を呼び出し
// d := newDecimal(mant)

// 変更後: new(decimal) でインスタンスを生成し、Assign メソッドを呼び出す
d := new(decimal)
d.Assign(mant)

これらの変更により、decimal インスタンスが関数からポインタとして返されることがなくなり、コンパイラはこれらのインスタンスが関数のスコープ内で完結すると判断しやすくなりました。結果として、decimal インスタンスの多くがヒープではなくスタックに割り当てられるようになり、ガベージコレクションの負荷が大幅に軽減されました。

ガベージコレクションの負荷軽減は、特に Ftoa のような頻繁に呼び出される関数において、顕著なパフォーマンス向上をもたらします。ベンチマーク結果が示すように、Ftoa 関連の処理時間は最大60%以上短縮され、それに依存する json パッケージのエンコード/マーシャリング処理も約22%高速化されました。これは、Goアプリケーション全体の数値処理性能に大きな影響を与える改善です。

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

src/pkg/strconv/decimal.go

newDecimal 関数の削除と、Round, RoundDown, RoundUp メソッドの戻り値の型変更（*decimal から void へ）。

--- a/src/pkg/strconv/decimal.go
+++ b/src/pkg/strconv/decimal.go
@@ -102,12 +102,6 @@ func (a *decimal) Assign(v uint64) {
 	trim(a)
 }

-func newDecimal(i uint64) *decimal {
-	a := new(decimal)
-	a.Assign(i)
-	return a
-}
-
 // Maximum shift that we can do in one pass without overflow.
 // Signed int has 31 bits, and we have to be able to accommodate 9<<k.
 const maxShift = 27
@@ -303,32 +297,32 @@ func shouldRoundUp(a *decimal, nd int) bool {
 // If nd is zero, it means we're rounding
 // just to the left of the digits, as in
 // 0.09 -> 0.1.
-func (a *decimal) Round(nd int) *decimal {
+func (a *decimal) Round(nd int) {
 	if nd < 0 || nd >= a.nd {
-\t\treturn a
+\t\treturn
 	}
 	if shouldRoundUp(a, nd) {
-\t\treturn a.RoundUp(nd)
+\t\ta.RoundUp(nd)
+\t} else {
+\t\ta.RoundDown(nd)
 	}
-\treturn a.RoundDown(nd)
 }

 // Round a down to nd digits (or fewer).
 // Returns receiver for convenience.
-func (a *decimal) RoundDown(nd int) *decimal {
+func (a *decimal) RoundDown(nd int) {
 	if nd < 0 || nd >= a.nd {
-\t\treturn a
+\t\treturn
 	}
 	a.nd = nd
 	trim(a)
-\treturn a
 }

 // Round a up to nd digits (or fewer).
 // Returns receiver for convenience.
-func (a *decimal) RoundUp(nd int) *decimal {
+func (a *decimal) RoundUp(nd int) {
 	if nd < 0 || nd >= a.nd {
-\t\treturn a
+\t\treturn
 	}

 	// round up
@@ -337,7 +331,7 @@ func (a *decimal) RoundUp(nd int) *decimal {
 		if c < '9' { // can stop after this digit
 			a.d[i]++
 			a.nd = i + 1
-\t\t\treturn a
+\t\t\treturn
 		}
 	}

@@ -346,7 +340,6 @@ func (a *decimal) RoundUp(nd int) *decimal {
 	a.d[0] = '1'
 	a.nd = 1
 	a.dp++
-\treturn a
 }

 // Extract integer part, rounded appropriately.

src/pkg/strconv/ftoa.go

newDecimal の呼び出しを new(decimal) と Assign メソッドの組み合わせに置き換え。

--- a/src/pkg/strconv/ftoa.go
+++ b/src/pkg/strconv/ftoa.go
@@ -98,7 +98,8 @@ func genericFtoa(bits uint64, fmt byte, prec int, flt *floatInfo) string {
 	// The shift is exp - flt.mantbits because mant is a 1-bit integer
 	// followed by a flt.mantbits fraction, and we are treating it as
 	// a 1+flt.mantbits-bit integer.
-\td := newDecimal(mant)\n+\td := new(decimal)\n+\td.Assign(mant)
 	d.Shift(exp - int(flt.mantbits))

 	// Round appropriately.
@@ -184,7 +185,8 @@ func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
 	// d = mant << (exp - mantbits)
 	// Next highest floating point number is mant+1 << exp-mantbits.
 	// Our upper bound is halfway inbetween, mant*2+1 << exp-mantbits-1.
-\tupper := newDecimal(mant*2 + 1)\n+\tupper := new(decimal)\n+\tupper.Assign(mant*2 + 1)
 \tupper.Shift(exp - int(flt.mantbits) - 1)\n \n 	// d = mant << (exp - mantbits)\n@@ -203,7 +205,8 @@ func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
 		mantlo = mant*2 - 1
 		explo = exp - 1
 	}\n-\tlower := newDecimal(mantlo*2 + 1)\n+\tlower := new(decimal)\n+\tlower.Assign(mantlo*2 + 1)
 \tlower.Shift(explo - int(flt.mantbits) - 1)\n \n 	// The upper and lower bounds are possible outputs only if

コアとなるコードの解説

このコミットのコアとなる変更は、decimal 型のインスタンスがヒープに割り当てられるのを防ぐためのものです。

  1. newDecimal 関数の削除: 変更前は、newDecimal(i uint64) *decimal という関数が decimal 型の新しいインスタンスを生成し、そのポインタを返していました。Goのエスケープ解析では、関数がポインタを返す場合、そのポインタが指すデータは関数の呼び出し元に「エスケープ」すると判断され、ヒープに割り当てられる可能性が高まります。この関数を削除することで、decimal インスタンスの生成時にポインタが返される経路の一つがなくなりました。

  2. Round, RoundDown, RoundUp メソッドの戻り値の変更: これらのメソッドは、decimal インスタンスの丸め処理を行います。変更前は、これらのメソッドも *decimal を返していました。これは、メソッドチェーンを可能にするための一般的なパターンですが、ここでも同様に、返されたポインタがエスケープ解析によってヒープ割り当てを誘発する原因となっていました。 変更後は、これらのメソッドは何も返さなくなり（void）、レシーバである decimal インスタンスを直接変更するようになりました。これにより、メソッドの呼び出し元に新しいポインタが渡されることがなくなり、エスケープ解析が decimal インスタンスをスタックに割り当てやすくなりました。

  3. ftoa.go でのインスタンス生成の変更: ftoa.go 内では、decimal インスタンスを生成するために newDecimal 関数が使われていました。この変更により、newDecimal(mant) のような呼び出しは、d := new(decimal); d.Assign(mant) という形式に置き換えられました。 new(decimal) は decimal 型のゼロ値のインスタンスをヒープに割り当て、そのポインタを返しますが、このポインタはすぐにローカル変数 d に代入され、その後の操作（d.Assign(mant) や d.Shift(...) など）もすべてこのローカル変数 d に対して行われます。もし d が関数の外にエスケープしない限り、コンパイラは d が指す decimal インスタンスをスタックに割り当てることが可能になります。

これらの変更の組み合わせにより、decimal インスタンスが関数の境界を越えてポインタとして渡されるケースが減り、Goコンパイラのエスケープ解析がより効果的に機能するようになりました。結果として、decimal インスタンスの多くがヒープではなくスタックに割り当てられるようになり、ガベージコレクションの頻度と負荷が大幅に軽減され、Ftoa および json パッケージのパフォーマンスが劇的に向上しました。

関連リンク

参考にした情報源リンク