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

コミット

• Author: Charles L. Dorian cldorian@gmail.com
• Date: Sat Nov 5 12:25:36 2011 -0700

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

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

元コミット内容

    math: faster Gamma
    
    Having the compiler count the number of array elements speeds up Gamma from 63.7 to 56.6 ns/op.
    
    R=rsc, golang-dev, r
    CC=golang-dev
    https://golang.org/cl/5362043

変更の背景

このコミットの主な目的は、Go言語のmathパッケージに含まれるGamma関数のパフォーマンスを向上させることです。コミットメッセージによると、コンパイラに配列要素の数を数えさせることで、Gamma関数の実行速度が63.7ナノ秒/操作から56.6ナノ秒/操作へと改善されたと報告されています。これは、約11%の速度向上に相当します。

Go言語では、配列の初期化において、要素数を明示的に指定するか、コンパイラに推論させるかを選択できます。この変更は、後者の方法を採用することで、コンパイラがより効率的なコードを生成できるようになり、結果として実行時のパフォーマンスが向上することを示唆しています。特に、数値計算ライブラリのようなパフォーマンスが重視される領域では、このような微細な最適化が全体の効率に大きく寄与します。

前提知識の解説

ガンマ関数 (Gamma Function)

ガンマ関数 (Γ(z)) は、階乗の概念を複素数に拡張した特殊関数です。自然数nに対してはΓ(n) = (n-1)! となります。統計学、確率論、物理学、工学など、幅広い分野で利用されます。Go言語のmathパッケージのGamma関数は、この数学的なガンマ関数を計算するためのものです。

Go言語における配列とスライス

Go言語には、配列とスライスという2つの主要なデータ構造があります。

• 配列 (Array): 配列は、同じ型の要素の固定長シーケンスです。配列の長さは型の一部であり、コンパイル時に決定されます。例えば、[3]intは3つの整数を格納できる配列型です。配列は値型であり、代入や関数への引数として渡される際には、その内容がコピーされます。

• スライス (Slice): スライスは、配列のセグメントを参照する動的なデータ構造です。スライスは、基になる配列へのポインタ、長さ、容量の3つの要素で構成されます。スライスは参照型であり、配列とは異なり、実行時に長さを変更できます。[]float64のように角括弧内に何も指定しない場合、それはスライス型を意味します。

Go言語における配列の初期化と...演算子

Go言語で配列を初期化する際、要素数を明示的に指定する方法と、...（エリプシス）演算子を使用してコンパイラに要素数を推論させる方法があります。

• 明示的な要素数の指定:

  var a [3]int = [3]int{1, 2, 3}
  

  この場合、配列aは3つの要素を持つ整数配列として定義されます。

• ...（エリプシス）演算子による要素数の推論:

  var a [...]int = [...]int{1, 2, 3}
  

  この場合、コンパイラは初期化子リストの要素数（この場合は3）に基づいて、配列aの長さを自動的に決定します。結果として、aは[3]int型として扱われます。

このコミットでは、[]float64から[...]float64への変更が行われています。これは、スライス型から配列型への変更であり、かつその配列の長さがコンパイラによって推論されるように指示していることを意味します。

技術的詳細

このコミットの技術的な核心は、Go言語のコンパイラが配列の長さをコンパイル時に知っている場合に、より効率的なコードを生成できるという点にあります。

元のコードでは、_P, _Q, _Sは[]float64として宣言されていました。これはスライス型であり、たとえ初期化時にリテラルで全ての要素が与えられていたとしても、Goの型システム上は「スライス」として扱われます。スライスは実行時にその長さや容量が変動する可能性があるため、コンパイラはこれらの変数を「固定長の配列」として最適化することが難しい場合があります。

変更後のコードでは、[...]float64と宣言されています。これは、コンパイラに対して「この変数は配列であり、その長さは初期化子リストから推論できる」と明示的に伝えています。これにより、コンパイラは以下の最適化を行う機会を得ます。

1. メモリ割り当ての最適化: コンパイラは配列の正確なサイズをコンパイル時に知るため、実行時の動的なメモリ割り当て（ヒープ割り当て）を避けて、スタック上に直接配列を割り当てることが可能になる場合があります。スタック割り当てはヒープ割り当てよりも高速です。
2. インデックスアクセスの最適化: 配列の長さが固定であるため、コンパイラは配列の境界チェックをより効率的に行ったり、場合によってはループのアンロールなどの最適化を適用したりできる可能性があります。スライスの場合、実行時に長さが変わる可能性があるため、より汎用的な（そして遅い）境界チェックが必要になることがあります。
3. データ配置の最適化: 固定長の配列は、キャッシュ効率の良い方法でメモリに配置される可能性が高まります。

math.Gamma関数は、これらの定数配列_P, _Q, _Sを使用して計算を行います。これらの配列へのアクセスが頻繁に行われるため、配列の初期化とアクセスがより効率的になることで、関数全体のパフォーマンスが向上したと考えられます。コミットメッセージにある「コンパイラに配列要素の数を数えさせる」という表現は、まさに...演算子を使用することでコンパイラが配列の長さを推論し、それに基づいて最適化を行うことを指しています。

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

diff --git a/src/pkg/math/gamma.go b/src/pkg/math/gamma.go
index 01365070eb..e117158fee 100644
--- a/src/pkg/math/gamma.go
+++ b/src/pkg/math/gamma.go
@@ -63,7 +63,7 @@ package math
 //   Stephen L. Moshier
 //   moshier@na-net.ornl.gov
 
-var _P = []float64{\
+var _P = [...]float64{\
 	1.60119522476751861407e-04,\
 	1.19135147006586384913e-03,\
 	1.04213797561761569935e-02,\
@@ -72,7 +72,7 @@ var _P = []float64{\
 	4.94214826801497100753e-01,\
 	9.99999999999999996796e-01,\
 }\
-var _Q = []float64{\
+var _Q = [...]float64{\
 	-2.31581873324120129819e-05,\
 	5.39605580493303397842e-04,\
 	-4.45641913851797240494e-03,\
@@ -82,7 +82,7 @@ var _Q = []float64{\
 	7.14304917030273074085e-02,\
 	1.00000000000000000320e+00,\
 }\
-var _S = []float64{\
+var _S = [...]float64{\
 	7.87311395793093628397e-04,\
 	-2.29549961613378126380e-04,\
 	-2.68132617805781232825e-03,\

コアとなるコードの解説

このコミットでは、src/pkg/math/gamma.goファイル内の3つのグローバル変数_P, _Q, _Sの宣言が変更されています。

変更前:

var _P = []float64{ ... }
var _Q = []float64{ ... }
var _S = []float64{ ... }

これらの変数は、float64型のスライスとして宣言されていました。初期化子リストが与えられていますが、型はあくまでスライスです。

変更後:

var _P = [...]float64{ ... }
var _Q = [...]float64{ ... }
var _S = [...]float64{ ... }

変更後では、[]float64が[...]float64に置き換えられています。この...（エリプシス）は、Goコンパイラに対して「初期化子リストの要素数に基づいて配列の長さを推論しなさい」という指示を与えます。これにより、これらの変数はスライスではなく、コンパイル時に長さが固定されたfloat64型の「配列」として扱われるようになります。

例えば、_Pの初期化子リストには8つの要素があります。したがって、変更後には_Pは[8]float64という型の配列として扱われます。同様に、_Qは[8]float64、_Sは[10]float64という配列型になります。

この変更により、コンパイラはこれらの定数データに対してより積極的な最適化を適用できるようになり、結果としてGamma関数の実行速度が向上しました。これは、Go言語のコンパイラが固定長の配列をより効率的に扱うことができるという特性を利用した、パフォーマンスチューニングの一例です。

関連リンク

• Go CL (Code Review) へのリンク: https://golang.org/cl/5362043

参考にした情報源リンク

• Go言語の公式ドキュメント (Arrays): https://go.dev/tour/moretypes/6
• Go言語の公式ドキュメント (Slices): https://go.dev/tour/moretypes/7
• Wikipedia: ガンマ関数: https://ja.wikipedia.org/wiki/%E3%82%AC%E3%83%B3%E3%83%9E%E9%96%A2%E6%95%B0
• Go言語における配列とスライスの違いと使い分けに関する一般的な情報源 (例: 各種技術ブログ、Go言語の書籍など)