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

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

このコミットは、Go言語の標準ライブラリmathパッケージにおけるSincos関数の実装を最適化し、パフォーマンスを向上させることを目的としています。具体的には、既存のアセンブリ言語による実装（sincos_amd64.s）から、より高速なGo言語による実装（sincos.go）へと切り替える変更が含まれています。

コミット

commit 06e635e46ded747737c26b74c088b48257883baa
Author: Charles L. Dorian <cldorian@gmail.com>
Date:   Wed Nov 30 15:11:44 2011 -0500

    math: faster Sincos
    
    Sincos via sincos.go is 35.4 ns/op, via sincos_amd64.s is 37.4 ns/op on 2.53 GHz Intel Core 2 Duo (Mac OS X).
    
    R=rsc, golang-dev
    CC=golang-dev
    https://golang.org/cl/5447045

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

https://github.com/golang/go/commit/06e635e46ded7474737c26b74c088b4825788baa

元コミット内容

このコミットは、mathパッケージのSincos関数を高速化することを目的としています。コミットメッセージによると、Go言語で実装されたsincos.goが、既存のアセンブリ言語で実装されたsincos_amd64.sよりも高速であることが示されています。具体的なベンチマークとして、2.53 GHz Intel Core 2 Duo (Mac OS X) 環境において、sincos.goが35.4 ns/op、sincos_amd64.sが37.4 ns/opという結果が出ています。これは、Go言語による実装が約2ナノ秒/操作速いことを意味します。

変更の背景

数値計算ライブラリにおいて、三角関数のような基本的な操作のパフォーマンスは非常に重要です。SinとCosを個別に計算するよりも、Sincosのように同時に計算する関数は、内部で共通の計算ステップを共有できるため、効率的な実装が可能です。

このコミットの背景には、Go言語のmathパッケージにおけるSincos関数の既存のアセンブリ言語実装（sincos_amd64.s）よりも、Go言語で記述された新しい実装（sincos.go）の方が優れたパフォーマンスを示すことが判明したという事実があります。通常、アセンブリ言語は低レベルな最適化が可能であるため、Goのような高水準言語よりも高速であると期待されがちです。しかし、このケースでは、Go言語のコンパイラ最適化の進歩や、新しいGo言語実装におけるアルゴリズムの改善により、アセンブリ言語実装を上回る性能を達成できたと考えられます。

この変更は、Go言語の標準ライブラリ全体のパフォーマンス向上に貢献し、特に科学技術計算やグラフィックス処理など、三角関数が頻繁に利用されるアプリケーションにおいて恩恵をもたらします。

前提知識の解説

Sincos関数

Sincos(x)関数は、与えられた角度x（ラジアン）に対するサイン（Sin(x)）とコサイン（Cos(x)）の値を同時に返す関数です。多くの数値計算ライブラリで提供されており、SinとCosを個別に呼び出すよりも効率的であることが多いです。これは、多くの場合、サインとコサインの計算が共通の内部ステップ（例えば、引数削減や多項式近似）を共有できるためです。

浮動小数点数演算

Sincos関数はfloat64型の浮動小数点数を扱います。浮動小数点数演算は、その性質上、精度とパフォーマンスのバランスが重要です。特に、三角関数のような超越関数では、無限級数や多項式近似を用いて値を計算するため、計算の効率性と結果の正確性がトレードオフの関係にあります。

引数削減 (Argument Reduction)

三角関数は周期関数であるため、任意の入力xに対して、その値を特定の小さな範囲（例えば、0からπ/2）に「削減」することができます。このプロセスを引数削減と呼びます。削減された範囲で関数値を計算し、元のxの象限に基づいて適切な符号を適用することで、広範囲の入力に対応できます。これにより、多項式近似の適用範囲を限定し、精度と効率を向上させることができます。

多項式近似 (Polynomial Approximation)

超越関数（三角関数、指数関数、対数関数など）の値をコンピュータで計算する際には、テイラー級数やチェビシェフ多項式などの多項式を用いて近似する方法が一般的に用いられます。これは、多項式の計算が基本的な算術演算（加算、乗算）のみで構成されるため、高速に実行できるためです。近似の精度は、多項式の次数や係数によって決まります。

IEEE 754 浮動小数点標準

float64はIEEE 754倍精度浮動小数点数標準に準拠しています。この標準は、浮動小数点数の表現形式、特殊な値（NaN, Inf, ±0）、および演算規則を定義しています。Sincos関数もこれらの特殊な値を適切に処理する必要があります。

Go言語のmathパッケージ

Go言語のmathパッケージは、基本的な数学関数（三角関数、指数関数、対数関数など）を提供します。これらの関数は、高い精度とパフォーマンスを両立するように設計されています。

技術的詳細

新しいSincos関数の実装は、以下の主要なステップで構成されています。

  1. 特殊ケースの処理:

    • x = 0の場合、±0, 1を返します。これは、Sin(0) = 0, Cos(0) = 1に対応します。符号付きゼロ（+0と-0）の挙動も考慮されています。
    • xがNaN（非数）またはInf（無限大）の場合、NaN, NaNを返します。これはIEEE 754標準の一般的な挙動です。MaxFloat64との比較により、IsNaNやIsInf関数を明示的に呼び出すことなく、これらの特殊ケースを処理しています。

  2. 引数削減 (Argument Reduction):

    • 入力xの符号を処理し、xを正の値に変換します。Sinは奇関数、Cosは偶関数であるため、符号は後で調整されます。
    • xをPi/4で割った整数部分jを計算します（j = int64(x * M4PI)、ここでM4PIは4/piの近似値）。これは、xがどの八分円（octant）に属するかを判断するために使用されます。
    • jが奇数の場合、jを偶数に調整します（j += 1, y += 1）。これは、位相角のテストのためにゼロを原点にマッピングするためです。
    • jを8で割った剰余（j &= 7）を計算し、xがどの八分円（0から7）に属するかを特定します。これにより、2π（360度）の周期性を利用して引数を削減します。
    • jの値に基づいて、sinSignとcosSignフラグを調整します。これにより、最終的なサインとコサインの符号が決定されます。例えば、j > 3の場合はx軸に関して反転するため、両方の符号が反転します。j > 1の場合はコサインの符号が反転します。
    • z = ((x - y*PI4A) - y*PI4B) - y*PI4Cという計算により、拡張精度でモジュラ演算を行います。PI4A, PI4B, PI4CはPi/4を3つの部分に分割したもので、浮動小数点演算の精度を維持するために使用されます。このzが、多項式近似の入力となります。

  3. 多項式近似 (Polynomial Approximation):

    • zの二乗zzを計算します。
    • cosとsinの値は、zzの多項式として計算されます。
      • cos = 1.0 - 0.5*zz + zz*zz*((((((_cos[0]*zz)+_cos[1])*zz+_cos[2])*zz+_cos[3])*zz+_cos[4])*zz+_cos[5])
      • sin = z + z*zz*((((((_sin[0]*zz)+_sin[1])*zz+_cos[2])*zz+_sin[3])*zz+_sin[4])*zz+_sin[5])
      • ここで、_cosと_sinは、pkg/math/sin.go（おそらくsin.goまたは関連ファイル）で定義されている多項式係数の配列です。これらの係数は、特定の範囲でサインとコサインを非常に高い精度で近似するように設計されています。この形式は、Horner法に似た効率的な多項式評価を示しています。

  4. 象限に基づく値の交換と符号の適用:

    • j == 1またはj == 2の場合、sinとcosの値を交換します（sin, cos = cos, sin）。これは、引数削減後の象限に応じて、サインとコサインの役割が入れ替わるためです（例: sin(x + π/2) = cos(x)）。
    • 最後に、cosSignとsinSignフラグに基づいて、最終的なcosとsinの符号を適用します。

この実装は、引数削減と多項式近似を組み合わせることで、広範囲の入力に対して高速かつ高精度なSincos計算を実現しています。特に、Pi/4を複数の部分に分割して使用する拡張精度モジュラ演算は、浮動小数点演算の累積誤差を最小限に抑え、高い精度を維持するための重要なテクニックです。

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

このコミットでは、主に以下の2つのファイルが変更されています。

  1. src/pkg/math/Makefile:

    • -tsincos_amd64.$O\ の行が削除されています。
    • これは、sincos_amd64.s（AMD64アーキテクチャ向けのアセンブリ言語によるSincos実装）のオブジェクトファイルがビルドプロセスから除外されたことを意味します。これにより、Go言語による新しい実装が優先されるようになります。

  2. src/pkg/math/sincos.go:

    • 既存のシンプルなfunc Sincos(x float64) (sin, cos float64) { return Sin(x), Cos(x) }の実装が削除され、新しい、より複雑で最適化されたGo言語によるSincos関数の実装が追加されています。
    • 新しい実装には、PI4A, PI4B, PI4C, M4PIといった定数、特殊ケース処理、引数削減ロジック、そして_sinおよび_cos配列（他のファイルで定義されている多項式係数）を用いた多項式近似の計算が含まれています。

コアとなるコードの解説

src/pkg/math/Makefileの変更

--- a/src/pkg/math/Makefile
+++ b/src/pkg/math/Makefile
@@ -15,7 +15,6 @@ OFILES_amd64=\
 	exp_amd64.$O\
 	hypot_amd64.$O\
 	log_amd64.$O\
-	sincos_amd64.$O\
 	sqrt_amd64.$O\
 
 OFILES_386=\

この変更は、amd64アーキテクチャ向けのオブジェクトファイルリストからsincos_amd64.$Oを削除しています。これは、Sincos関数の実装がアセンブリ言語からGo言語に完全に移行したことを明確に示しています。これにより、ビルドシステムはGo言語で記述されたsincos.goのコードをコンパイルして使用するようになります。

src/pkg/math/sincos.goの変更

--- a/src/pkg/math/sincos.go
+++ b/src/pkg/math/sincos.go
@@ -4,9 +4,66 @@
 
 package math
 
+// Coefficients _sin[] and _cos[] are found in pkg/math/sin.go.
+
 // Sincos(x) returns Sin(x), Cos(x).
 //
 // Special conditions are:
+//	Sincos(±0) = ±0, 1
 //	Sincos(±Inf) = NaN, NaN
 //	Sincos(NaN) = NaN, NaN
-func Sincos(x float64) (sin, cos float64) { return Sin(x), Cos(x) }\n+func Sincos(x float64) (sin, cos float64) {
+\tconst (
+\t\tPI4A = 7.85398125648498535156E-1                             // 0x3fe921fb40000000, Pi/4 split into three parts
+\t\tPI4B = 3.77489470793079817668E-8                             // 0x3e64442d00000000,
+\t\tPI4C = 2.69515142907905952645E-15                            // 0x3ce8469898cc5170,\
+\t\tM4PI = 1.273239544735162542821171882678754627704620361328125 // 4/pi
+\t)\n+\t// TODO(rsc): Remove manual inlining of IsNaN, IsInf
+\t// when compiler does it for us
+\t// special cases
+\tswitch {\n+\tcase x == 0:\n+\t\treturn x, 1 // return ±0.0, 1.0\n+\tcase x != x || x < -MaxFloat64 || x > MaxFloat64: // IsNaN(x) || IsInf(x, 0):\n+\t\treturn NaN(), NaN()\n+\t}\n+\n+\t// make argument positive\n+\tsinSign, cosSign := false, false\n+\tif x < 0 {\n+\t\tx = -x\n+\t\tsinSign = true\n+\t}\n+\n+\tj := int64(x * M4PI) // integer part of x/(Pi/4), as integer for tests on the phase angle\n+\ty := float64(j)      // integer part of x/(Pi/4), as float\n+\n+\tif j&1 == 1 { // map zeros to origin\n+\t\tj += 1\n+\t\ty += 1\n+\t}\n+\tj &= 7     // octant modulo 2Pi radians (360 degrees)\n+\tif j > 3 { // reflect in x axis\n+\t\tj -= 4\n+\t\tsinSign, cosSign = !sinSign, !cosSign\n+\t}\n+\tif j > 1 {\n+\t\tcosSign = !cosSign\n+\t}\n+\n+\tz := ((x - y*PI4A) - y*PI4B) - y*PI4C // Extended precision modular arithmetic\n+\tzz := z * z\n+\tcos = 1.0 - 0.5*zz + zz*zz*((((((_cos[0]*zz)+_cos[1])*zz+_cos[2])*zz+_cos[3])*zz+_cos[4])*zz+_cos[5])\n+\tsin = z + z*zz*((((((_sin[0]*zz)+_sin[1])*zz+_sin[2])*zz+_sin[3])*zz+_sin[4])*zz+_sin[5])\n+\tif j == 1 || j == 2 {\n+\t\tsin, cos = cos, sin\n+\t}\n+\tif cosSign {\n+\t\tcos = -cos\n+\t}\n+\tif sinSign {\n+\t\tsin = -sin\n+\t}\n+\treturn\n+}\n```

このコードは、`Sincos`関数の新しいGo言語実装です。

*   **定数**: `PI4A`, `PI4B`, `PI4C`は`π/4`を3つの部分に分割したもので、浮動小数点演算の精度を向上させるために使用されます。`M4PI`は`4/π`の近似値で、引数削減に使用されます。
*   **特殊ケース**: `x == 0`と`NaN`/`Inf`のケースを最初に処理し、関数の堅牢性を確保しています。`x != x`は`NaN`をチェックする一般的な方法です。
*   **引数削減**:
    *   `x`の符号を`sinSign`と`cosSign`で管理し、`x`を正の値に変換します。
    *   `j := int64(x * M4PI)`で`x`が`π/4`の何倍であるかの整数部分を計算します。
    *   `j&1 == 1`のチェックと`j += 1`, `y += 1`は、`j`が奇数の場合に位相角のテストのためにゼロを原点にマッピングする処理です。
    *   `j &= 7`は、`j`を8で割った剰余を取り、`0`から`7`の範囲に正規化します。これは、`2π`（8 * `π/4`）の周期性を利用して、角度を八分円にマッピングします。
    *   `j`の値に基づいて`sinSign`と`cosSign`を反転させることで、元の角度の象限に応じた正しい符号を適用します。
    *   `z := ((x - y*PI4A) - y*PI4B) - y*PI4C`は、拡張精度で引数削減を行うための重要なステップです。これにより、`z`は非常に小さな値になり、多項式近似の精度が向上します。
*   **多項式近似**: `cos`と`sin`は、`z`の二乗`zz`を用いた多項式として計算されます。`_cos`と`_sin`は、`pkg/math/sin.go`で定義されている係数配列であり、これらの多項式は特定の範囲でサインとコサインを非常に正確に近似するように設計されています。この多項式評価の形式は、Horner法に似ており、効率的な計算を可能にします。
*   **最終調整**: `j == 1 || j == 2`の場合に`sin`と`cos`を交換し、最後に`cosSign`と`sinSign`に基づいて最終的な符号を適用することで、正しい`Sin(x)`と`Cos(x)`のペアが返されます。

この新しいGo言語実装は、アセンブリ言語実装よりも高速であることがベンチマークで示されており、Go言語のコンパイラとランタイムの最適化能力、およびアルゴリズム設計の重要性を示しています。

## 関連リンク

*   Go言語の`math`パッケージのドキュメント: [https://pkg.go.dev/math](https://pkg.go.dev/math)
*   Go言語の`Sin`関数のソースコード（関連する多項式係数`_sin`と`_cos`が定義されている可能性が高い）: [https://github.com/golang/go/blob/master/src/math/sin.go](https://github.com/golang/go/blob/master/src/math/sin.go) (コミット当時のパスとは異なる可能性がありますが、現在のGoリポジトリの構造を示しています)

## 参考にした情報源リンク

*   Go言語のコミット履歴: [https://github.com/golang/go/commits/master](https://github.com/golang/go/commits/master)
*   浮動小数点数演算と精度に関する一般的な情報源（例: IEEE 754標準、数値解析の教科書）
*   三角関数の多項式近似に関する情報源（例: 数値計算の教科書、専門論文）
*   Go言語の`math`パッケージの設計に関する議論（Go言語のメーリングリストやIssueトラッカー）
*   Go言語の`math`パッケージのソースコード（特に`sin.go`や`cos.go`など、`Sincos`と関連するファイル）
*   Go言語のベンチマークに関する情報源