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

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

このコミットは、Goランタイムにmath.sqrt関数のコピーを追加し、特にARMアーキテクチャのソフトフロート実装で使用できるようにすることを目的としています。これにより、ハードウェア浮動小数点ユニット（FPU）を持たないARMシステム上でも、Goプログラムが正しく平方根計算を実行できるようになります。

コミット

commit ee7bb07a53da1c400f4e1130517c362e302be212
Author: Russ Cox <rsc@golang.org>
Date:   Mon May 12 10:55:33 2014 -0400

    runtime: add copy of math.sqrt for use by arm softfloat
    
    If it's not used (such as on other systems or if softfloat
    is disabled) the linker will discard it.
    
    The alternative is to teach cmd/go that every binary
    depends on math implicitly on arm. I started down that
    path but it's too scary. If we're going to get dependencies
    right we should get dependencies right.
    
    Fixes #6994.
    
    LGTM=bradfitz, dave
    R=golang-codereviews, bradfitz, dave
    CC=golang-codereviews
    https://golang.org/cl/95290043

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

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

元コミット内容

runtime: add copy of math.sqrt for use by arm softfloat

If it's not used (such as on other systems or if softfloat
is disabled) the linker will discard it.

The alternative is to teach cmd/go that every binary
depends on math implicitly on arm. I started down that
path but it's too scary. If we're going to get dependencies
right we should get dependencies right.

Fixes #6994.

LGTM=bradfitz, dave
R=golang-codereviews, bradfitz, dave
CC=golang-codereviews
https://golang.org/cl/95290043

変更の背景

このコミットの主な背景は、ARMアーキテクチャにおける浮動小数点演算の取り扱いです。特に、ハードウェア浮動小数点ユニット（FPU）を持たないARMプロセッサ（例えば、古いARMv5アーキテクチャなど）では、浮動小数点演算をソフトウェアでエミュレートする「ソフトフロート」が使用されます。

Go言語の設計思想として、依存関係を明示的に扱うことが重視されています。しかし、ARMソフトフロート環境では、math.sqrtのような基本的な数学関数が、明示的なimport "math"なしにランタイム内部で必要となる場合があります。

コミットメッセージによると、この問題に対する2つのアプローチが検討されました。

  1. cmd/goに、すべてのバイナリがARM上で暗黙的にmathパッケージに依存することを教える。
    • これは、Goの依存関係管理の原則に反し、予期せぬ副作用や複雑さを招く可能性があったため、「too scary（恐ろしすぎる）」と判断されました。依存関係を「正しく」扱うべきという思想が背景にあります。
  2. math.sqrtのコピーをruntimeパッケージ内に配置する。
    • このアプローチが採用されました。runtimeパッケージ内にmath.sqrtのコピーを配置することで、mathパッケージへの暗黙的な依存を避けつつ、ソフトフロート環境で必要な平方根計算機能を提供できます。もしこのコピーが他のシステムやソフトフロートが無効な環境で使われなければ、リンカが自動的にそのコードを破棄するため、バイナリサイズへの影響も最小限に抑えられます。

この変更は、GoプログラムがFPUを持たないARMデバイスでも安定して動作するための重要なステップであり、Goの依存関係管理の健全性を保ちながら、特定のアーキテクチャの制約に対応するための実用的な解決策と言えます。コミットメッセージにあるFixes #6994は、この問題に関連する既存のバグまたは機能要求を解決したことを示唆していますが、公開されているGoのIssueトラッカーではこの番号の詳細は見つかりませんでした。これは、非常に古いIssueであるか、内部的な参照である可能性があります。

前提知識の解説

1. ARMアーキテクチャと浮動小数点演算（FPU、ソフトフロート）

  • ARMアーキテクチャ: スマートフォン、タブレット、組み込みシステムなど、幅広いデバイスで使用されているプロセッサアーキテクチャです。低消費電力と高性能を両立させる設計が特徴です。
  • FPU (Floating-Point Unit): 浮動小数点演算（実数の計算）を高速に処理するための専用ハードウェアです。FPUを搭載しているプロセッサでは、浮動小数点演算が非常に効率的に行われます。
  • ソフトフロート (Software Floating-Point): FPUを搭載していないプロセッサで浮動小数点演算を行う場合、その計算はソフトウェアによってエミュレートされます。これをソフトフロートと呼びます。ソフトフロートはハードウェアFPUに比べて処理速度が大幅に遅くなりますが、FPU非搭載のシステムでも浮動小数点演算を可能にします。Goランタイムは、GOARM環境変数などを通じて、ターゲットとするARMプロセッサのFPUの有無に応じて、ハードフロート（FPU使用）またはソフトフロート（ソフトウェアエミュレーション）のどちらを使用するかを決定できます。

2. IEEE 754 浮動小数点標準

  • float64（Goのfloat64型）は、通常、IEEE 754倍精度浮動小数点数形式に従います。この標準は、浮動小数点数の表現方法（符号、指数、仮数）と、それらに対する演算（加算、減算、乗算、除算、平方根など）の規則を定めています。
  • sqrt関数は、この標準で定義されている平方根演算を正確に実装する必要があります。特殊なケース（NaN、無限大、負の数、ゼロなど）の取り扱いも標準で規定されています。

3. ビットごとの平方根計算アルゴリズム

コミットで追加されたsqrt.go内のsqrt関数は、IEEE 754浮動小数点数の平方根をビットごとに計算するアルゴリズムを実装しています。これは、ハードウェアFPUがない環境（ソフトフロート）で、正確な平方根計算を提供するために使用されます。

このアルゴリズムの基本的な考え方は以下の通りです。

  • 正規化: 入力された浮動小数点数xを、[1, 4)の範囲に正規化します。これにより、sqrt(x) = 2^k * sqrt(y)（yは正規化された値）という関係が成り立ちます。
  • ビットごとの計算: 正規化されたyに対して、平方根qをビットごとに計算していきます。これは、qの各ビットを決定するために、q^2 <= yという条件を繰り返しチェックするプロセスです。
  • 最終的な丸め: 53ビットの結果を生成した後、さらに1ビットを計算し、残りの部分（remainder）と共に、結果が正確であるか、1/2ulp（Unit in the Last Place）より大きいか小さいかを判断して、正しく丸めます。

このアルゴリズムは、Sun Microsystemsのe_sqrt.c（FreeBSDのlib/msun/src/e_sqrt.cに由来）に基づいています。これは、移植性が高く、正確な結果を保証しますが、ハードウェアFPUによる計算に比べて速度は劣ります。

4. Goのruntimeパッケージとmathパッケージ

  • runtimeパッケージ: Goプログラムの実行時環境を管理するコアパッケージです。ガベージコレクション、スケジューラ、プリミティブな型変換、低レベルのシステムコールなど、Goプログラムの動作に不可欠な機能を提供します。このパッケージは、Goの標準ライブラリの他の部分とは異なり、C言語で書かれた部分も多く含まれています。
  • mathパッケージ: 数学関数（三角関数、対数関数、平方根など）を提供するGoの標準ライブラリパッケージです。通常、Goプログラムで数学関数を使用する場合は、このパッケージをインポートします。

このコミットのポイントは、通常mathパッケージで提供されるsqrt関数を、runtimeパッケージ内にコピーとして配置した点です。これは、runtimeがmathパッケージに直接依存することなく、ARMソフトフロート環境で必要な平方根機能を提供するための設計上の選択です。

技術的詳細

このコミットは、GoランタイムがARMソフトフロート環境で平方根計算を処理する方法を改善します。具体的には、mathパッケージのsqrt関数の実装をruntimeパッケージ内にコピーし、softfloat_arm.cからこの新しいランタイム版のsqrt関数を呼び出すように変更しています。

src/pkg/runtime/softfloat_arm.cの変更

このC言語ファイルは、ARMソフトフロートの命令エミュレーションを担当しています。変更前は、math·sqrtCという関数を呼び出していました。これは、Goのmathパッケージ内のsqrt関数に対応するCのシンボルを指していたと考えられます。

変更後、呼び出しはruntime·sqrtCに変更されました。これは、新しくruntimeパッケージ内に定義されたsqrtC関数を指します。

--- a/src/pkg/runtime/softfloat_arm.c
+++ b/src/pkg/runtime/softfloat_arm.c
@@ -16,7 +16,7 @@
 #define FLAGS_V (1U << 28)
 
 void	runtime·abort(void);
-void	math·sqrtC(uint64, uint64*);
+void	runtime·sqrtC(uint64, uint64*);
 
 static	uint32	trace = 0;
 
@@ -413,7 +413,7 @@ stage3:	// regd, regm are 4bit variables
 		break;
 
 	case 0xeeb10bc0:	// D[regd] = sqrt D[regm]
-		math·sqrtC(getd(regm), &uval);
+		runtime·sqrtC(getd(regm), &uval);
 		putd(regd, uval);
 
 		if(trace)

この変更により、softfloat_arm.cはmathパッケージへの直接的な依存をなくし、runtimeパッケージ内で自己完結的に平方根計算を処理できるようになります。

src/pkg/runtime/sqrt.goの新規追加

このコミットの主要な変更は、src/pkg/runtime/sqrt.goという新しいファイルが追加されたことです。このファイルには、mathパッケージのsqrt関数の実装とほぼ同じコードが含まれています。

  • パッケージ: package runtimeとして定義されており、runtimeパッケージの一部であることを示します。
  • コメント: ファイルの冒頭には、「Copy of math/sqrt.go, here for use by ARM softfloat.」と明記されており、ARMソフトフロートのためにmath/sqrt.goのコピーであることを示しています。また、オリジナルのCコード（FreeBSDのe_sqrt.c）に関する著作権表示と、ビットごとの平方根計算アルゴリズムの詳細な説明が含まれています。
  • 定数: IEEE 754浮動小数点数に関連する定数（NaN、無限大、マスク、シフト、バイアスなど）が定義されています。
  • float64bitsとfloat64frombits: float64とuint64の間でビット表現を変換するためのヘルパー関数です。unsafe.Pointerを使用して、型安全性をバイパスし、メモリ上のビットパターンを直接解釈します。
  • sqrt(x float64) float64関数:
    • この関数は、入力xの平方根を計算するメインのロジックを含んでいます。
    • 特殊ケースの処理: xが0、NaN、無限大、負の数、またはmaxFloat64を超える場合の特殊なケースを最初に処理します。負の数の場合はNaNを返します。
    • 正規化: 入力xのビット表現を操作し、指数部を調整して、計算に適した形式に正規化します。サブノーマル数（非常に小さい数）の処理も含まれます。
    • ビットごとの計算: 正規化された値に対して、ビットごとの平方根アルゴリズムを実行します。これは、q（平方根の結果）とs（中間変数）、ix（残りの値）を繰り返し更新することで行われます。rは、現在のビット位置を示すための移動ビットです。
    • 最終的な丸め: 計算された平方根のビットに加えて、残りの値ixがゼロでない場合（つまり、結果が正確でない場合）には、IEEE 754標準に従って結果を丸めます。
    • 結果の再構築: 計算された仮数部と調整された指数部を組み合わせて、最終的なfloat64のビット表現を構築し、float64frombitsでfloat64に変換して返します。
  • sqrtC(f float64, r *float64)関数:
    • この関数は、C言語から呼び出されることを意図したラッパー関数です。
    • 引数としてfloat64型のfと、結果を格納するための*float64型のポインタrを受け取ります。
    • 内部でsqrt(f)を呼び出し、その結果をポインタrが指すメモリ位置に格納します。これにより、CコードからGoの平方根関数を呼び出し、結果を受け取ることが可能になります。

この変更により、Goランタイムはmathパッケージに依存することなく、ARMソフトフロート環境で必要な平方根計算を内部で完結できるようになりました。これにより、Goのビルドシステムがmathパッケージへの暗黙的な依存を扱う複雑さを回避し、依存関係の管理をより明確に保つことができます。

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

src/pkg/runtime/softfloat_arm.c

--- a/src/pkg/runtime/softfloat_arm.c
+++ b/src/pkg/runtime/softfloat_arm.c
@@ -16,7 +16,7 @@
 #define FLAGS_V (1U << 28)
 
 void	runtime·abort(void);
-void	math·sqrtC(uint64, uint64*);
+void	runtime·sqrtC(uint64, uint64*);
 
 static	uint32	trace = 0;
 
@@ -413,7 +413,7 @@ stage3:	// regd, regm are 4bit variables
 		break;
 
 	case 0xeeb10bc0:	// D[regd] = sqrt D[regm]
-		math·sqrtC(getd(regm), &uval);
+		runtime·sqrtC(getd(regm), &uval);
 		putd(regd, uval);
 
 		if(trace)
  • math·sqrtCへの関数呼び出しがruntime·sqrtCに変更されました。
  • 関数のプロトタイプ宣言も同様にmath·sqrtCからruntime·sqrtCに修正されました。

src/pkg/runtime/sqrt.go (新規ファイル)

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Copy of math/sqrt.go, here for use by ARM softfloat.

package runtime

import "unsafe"

// The original C code and the long comment below are
// from FreeBSD's /usr/src/lib/msun/src/e_sqrt.c and
// came with this notice.  The go code is a simplified
// version of the original C.
//
// ====================================================
// Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
//
// Developed at SunPro, a Sun Microsystems, Inc. business.
// Permission to use, copy, modify, and distribute this
// software is freely granted, provided that this notice
// is preserved.
// ====================================================
//
// __ieee754_sqrt(x)
// Return correctly rounded sqrt.
//           -----------------------------------------
//           | Use the hardware sqrt if you have one |
//           -----------------------------------------
// Method:
//   Bit by bit method using integer arithmetic. (Slow, but portable)
//   1. Normalization
//      Scale x to y in [1,4) with even powers of 2:
//      find an integer k such that  1 <= (y=x*2**(2k)) < 4, then
//              sqrt(x) = 2**k * sqrt(y)
//   2. Bit by bit computation
//      Let q  = sqrt(y) truncated to i bit after binary point (q = 1),
//           i                                                   0
//                                     i+1         2
//          s  = 2*q , and      y  =  2   * ( y - q  ).          (1)
//           i      i            i                 i
//
//      To compute q    from q , one checks whether
//                  i+1       i
//
//                            -(i+1) 2
//                      (q + 2      )  <= y.                     (2)
//                        i
//                                                            -(i+1)
//      If (2) is false, then q   = q ; otherwise q   = q  + 2      .
//                             i+1   i             i+1   i
//
//      With some algebraic manipulation, it is not difficult to see
//      that (2) is equivalent to
//                             -(i+1)
//                      s  +  2       <= y                       (3)
//                       i                i
//
//      The advantage of (3) is that s  and y  can be computed by
//                                    i      i
//      the following recurrence formula:
//          if (3) is false
//
//          s     =  s  ,       y    = y   ;                     (4)
//           i+1      i          i+1    i
//
//      otherwise,
//                         -i                      -(i+1)
//          s     =  s  + 2  ,  y    = y  -  s  - 2              (5)
//           i+1      i          i+1    i     i
//
//      One may easily use induction to prove (4) and (5).\n//      Note. Since the left hand side of (3) contain only i+2 bits,\n//            it does not necessary to do a full (53-bit) comparison\n//            in (3).\n//   3. Final rounding\n//      After generating the 53 bits result, we compute one more bit.\n//      Together with the remainder, we can decide whether the\n//      result is exact, bigger than 1/2ulp, or less than 1/2ulp\n//      (it will never equal to 1/2ulp).\n//      The rounding mode can be detected by checking whether\n//      huge + tiny is equal to huge, and whether huge - tiny is\n//      equal to huge for some floating point number "huge" and "tiny".
//
//
// Notes:  Rounding mode detection omitted.

const (
	uvnan      = 0x7FF8000000000001
	uvinf      = 0x7FF0000000000000
	uvneginf   = 0xFFF0000000000000
	mask       = 0x7FF
	shift      = 64 - 11 - 1
	bias       = 1023
	maxFloat64 = 1.797693134862315708145274237317043567981e+308 // 2**1023 * (2**53 - 1) / 2**52
)

func float64bits(f float64) uint64     { return *(*uint64)(unsafe.Pointer(&f)) }
func float64frombits(b uint64) float64 { return *(*float64)(unsafe.Pointer(&b)) }

func sqrt(x float64) float64 {
	// special cases
	switch {
	case x == 0 || x != x || x > maxFloat64:
		return x
	case x < 0:
		return nan
	}
	ix := float64bits(x)
	// normalize x
	exp := int((ix >> shift) & mask)
	if exp == 0 { // subnormal x
		for ix&1<<shift == 0 {
			ix <<= 1
			exp--
		}
		exp++
	}
	exp -= bias // unbias exponent
	ix &^= mask << shift
	ix |= 1 << shift
	if exp&1 == 1 { // odd exp, double x to make it even
		ix <<= 1
	}
	exp >>= 1 // exp = exp/2, exponent of square root
	// generate sqrt(x) bit by bit
	ix <<= 1
	var q, s uint64               // q = sqrt(x)
	r := uint64(1 << (shift + 1)) // r = moving bit from MSB to LSB
	for r != 0 {
		t := s + r
		if t <= ix {
			s = t + r
			ix -= t
			q += r
		}
		ix <<= 1
		r >>= 1
	}
	// final rounding
	if ix != 0 { // remainder, result not exact
		q += q & 1 // round according to extra bit
	}
	ix = q>>1 + uint64(exp-1+bias)<<shift // significand + biased exponent
	return float64frombits(ix)
}

func sqrtC(f float64, r *float64) {
	*r = sqrt(f)
}
  • runtimeパッケージに属する新しいGoファイルとして追加されました。
  • sqrt関数は、IEEE 754倍精度浮動小数点数の平方根をビットごとに計算するアルゴリズムを実装しています。
  • sqrtC関数は、C言語から呼び出されるためのラッパーとして機能し、sqrt関数を呼び出して結果をポインタ経由で返します。

コアとなるコードの解説

sqrt(x float64) float64 関数

この関数は、IEEE 754倍精度浮動小数点数xの平方根を計算します。その実装は、ハードウェアFPUに依存しない、ビットごとのアルゴリズムに基づいています。

  1. 特殊ケースの処理:
    • x == 0 || x != x || x > maxFloat64: xがゼロ、NaN（Not a Number）、またはfloat64の最大値を超える場合、xをそのまま返します。これは、IEEE 754標準で定義されている動作です。
    • x < 0: xが負の場合、平方根は実数ではないため、nan（NaNのビット表現）を返します。
  2. ビット表現の取得:
    • ix := float64bits(x): 入力xのfloat64値をuint64のビット表現に変換します。これにより、浮動小数点数の内部構造（符号、指数、仮数）をビットレベルで操作できるようになります。
  3. 正規化:
    • exp := int((ix >> shift) & mask): ixから指数部を抽出し、expに格納します。
    • if exp == 0 { ... }: xがサブノーマル数（非常に小さい非正規化数）の場合の処理です。サブノーマル数を正規化し、指数部を適切に調整します。
    • exp -= bias: 指数部からバイアス（IEEE 754で指数を表現するために加えられるオフセット）を引いて、実際の指数値を取得します。
    • ix &^= mask << shift; ix |= 1 << shift: 仮数部から指数部と符号ビットを取り除き、暗黙の先頭ビット（1）を設定して正規化された仮数部を準備します。
    • if exp&1 == 1 { ix <<= 1 }: 指数部が奇数の場合、ixを1ビット左シフト（2倍）します。これは、平方根の計算を容易にするために、指数部を偶数にするためです。
    • exp >>= 1: 指数部を2で割ります。これは、sqrt(2^E) = 2^(E/2)という関係に基づいています。
  4. ビットごとの平方根計算:
    • ix <<= 1: ixをさらに1ビット左シフトします。これは、計算の準備のためです。
    • var q, s uint64: qは計算中の平方根の結果、sは中間変数です。
    • r := uint64(1 << (shift + 1)): rは、現在のビット位置を示すためのマスクで、最上位ビットから最下位ビットへと移動します。
    • for r != 0 { ... }: rがゼロになるまでループを繰り返します。これは、すべてのビットを処理するまで続きます。
      • t := s + r: tは、現在のビットを試行的に追加した場合のsの値です。
      • if t <= ix { ... }: もしtが現在の残りの値ix以下であれば、現在のビットが平方根の正しいビットであることを意味します。
        • s = t + r: sを更新します。
        • ix -= t: ixからtを引きます。
        • q += r: qに現在のビットを追加します。
      • ix <<= 1: ixを1ビット左シフトします。
      • r >>= 1: rを1ビット右シフトし、次のビット位置に移動します。
  5. 最終的な丸め:
    • if ix != 0 { q += q & 1 }: ixがゼロでない場合（つまり、計算が正確な結果で終わらなかった場合）、IEEE 754の「最も近い偶数への丸め」（round-to-nearest-even）規則に従ってqを丸めます。q & 1は、qの最下位ビットが1かどうかをチェックし、それに応じて丸めます。
  6. 結果の再構築:
    • ix = q>>1 + uint64(exp-1+bias)<<shift: 計算された仮数部qと、調整された指数部exp、そしてバイアスを組み合わせて、最終的なfloat64のビット表現を構築します。
    • return float64frombits(ix): 構築されたビット表現をfloat64値に変換して返します。

sqrtC(f float64, r *float64) 関数

この関数は、C言語のコード（softfloat_arm.c）からGoのsqrt関数を呼び出すためのブリッジとして機能します。

  • f float64: 平方根を計算する入力値です。
  • r *float64: 計算結果を格納するためのfloat64型へのポインタです。C言語では、関数が複数の値を返すことができない場合や、大きなデータ構造を効率的に渡す場合にポインタがよく使用されます。
  • *r = sqrt(f): sqrt(f)を呼び出して平方根を計算し、その結果をポインタrが指すメモリ位置に書き込みます。これにより、CコードはGoのsqrt関数によって計算された結果を取得できます。

このsqrtC関数は、GoのランタイムがC言語で書かれた部分と連携するための典型的なパターンを示しています。Goの関数は、CのABI（Application Binary Interface）に従ってエクスポートされ、Cコードから直接呼び出せるようになります。

関連リンク

  • Go CL 95290043: https://golang.org/cl/95290043
  • Go Issue #6994 (詳細不明): コミットメッセージで参照されていますが、公開されているGoのIssueトラッカーでは詳細が見つかりませんでした。

参考にした情報源リンク