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

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

このコミットは、Go言語のランタイムにおいて、ARMアーキテクチャ向けのソフトウェアによる除算（division）および剰余（modulo）演算のベンチマークを追加するものです。これらのベンチマークは、特にARMプロセッサ上でのGoプログラムの実行時性能を評価し、将来的な最適化の基準点を提供することを目的としています。

コミット

commit d1537809ba93f30fb538ed121e4dbdc662292b2a
Author: Dave Cheney <dave@cheney.net>
Date:   Tue Jun 26 08:58:00 2012 +1000

    runtime: add arm soft division and modulo benchmarks
    
    arm soft div and mod performance plays an important part
    in runtime performance.
    
    The currently implementation is very stable, but we believe
    we can best it. This benchmark provides a reference point.
    
    linux/arm omap4 pandaboard
    
    BenchmarkUint32Div7     10000000               298 ns/op
    BenchmarkUint32Div37    10000000               298 ns/op
    BenchmarkUint32Div123   10000000               298 ns/op
    BenchmarkUint32Div763   10000000               298 ns/op
    BenchmarkUint32Div1247  10000000               299 ns/op
    BenchmarkUint32Div9305  10000000               298 ns/op
    BenchmarkUint32Div13307 10000000               298 ns/op
    BenchmarkUint32Div52513 10000000               298 ns/op
    BenchmarkUint32Div60978747      10000000               298 ns/op
    BenchmarkUint32Div106956295     10000000               297 ns/op
    BenchmarkUint32Mod7     10000000               280 ns/op
    BenchmarkUint32Mod37    10000000               280 ns/op
    BenchmarkUint32Mod123   10000000               280 ns/op
    BenchmarkUint32Mod763   10000000               280 ns/op
    BenchmarkUint32Mod1247  10000000               280 ns/op
    BenchmarkUint32Mod9305  10000000               280 ns/op
    BenchmarkUint32Mod13307 10000000               280 ns/op
    BenchmarkUint32Mod52513 10000000               280 ns/op
    BenchmarkUint32Mod60978747      10000000               280 ns/op
    BenchmarkUint32Mod106956295     10000000               280 ns/op
    
    R=minux.ma, rsc
    CC=golang-dev
    https://golang.org/cl/6258067

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

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

元コミット内容

このコミットは、GoランタイムにARMアーキテクチャ向けのソフトウェアによる除算および剰余演算のベンチマークを追加します。これらの演算の性能はランタイムの全体的な性能に大きく影響するため、現在の実装が安定しているものの、さらなる改善の余地があると判断されました。このベンチマークは、将来的な最適化のための参照点を提供します。コミットメッセージには、linux/arm omap4 pandaboard 環境でのベンチマーク結果の例も含まれています。

変更の背景

Go言語は、様々なアーキテクチャで動作するように設計されています。ARMアーキテクチャは、モバイルデバイス、組み込みシステム、そして近年ではサーバー分野でも広く利用されています。CPUによっては、ハードウェアレベルで整数除算や剰余演算を直接サポートしていない、あるいはサポートしていても特定の条件下で性能が最適ではない場合があります。このような場合、コンパイラやランタイムはこれらの演算をソフトウェアでエミュレートする必要があります。これを「ソフトウェア除算（soft division）」と呼びます。

ソフトウェア除算および剰余演算は、ハードウェアによる直接的な演算に比べて一般的に遅く、その性能はGoプログラム全体の実行速度に大きな影響を与える可能性があります。特に、ループ内で頻繁にこれらの演算が使用される場合、その影響は顕著になります。

このコミットが作成された2012年当時、ARMプロセッサはまだハードウェアによる整数除算命令が標準的ではなかった時期であり、多くのARMベースのシステムではソフトウェアによる除算が用いられていました。Goランタイムの開発チームは、現在のソフトウェア除算の実装が安定していることを認識しつつも、さらなる性能向上の可能性を探っていました。そのため、具体的な最適化に着手する前に、現在の性能を正確に測定し、将来の改善のベースラインとなるベンチマークを確立する必要がありました。このベンチマークは、異なる除数（divisor）に対するuint32型の除算と剰余演算の性能を測定することで、ボトルネックの特定や最適化の効果を評価するための重要なツールとなります。

前提知識の解説

ARMアーキテクチャとソフトウェア除算

ARM（Advanced RISC Machine）は、低消費電力と高性能を両立するRISC（Reduced Instruction Set Computer）アーキテクチャです。スマートフォン、タブレット、組み込みシステム、そして最近ではデータセンターのサーバーなど、幅広いデバイスで採用されています。

ARMアーキテクチャの初期のバージョンや一部のプロファイル（例: ARMv5, ARMv6-M）では、整数除算命令がハードウェアで直接提供されていませんでした。そのため、コンパイラやオペレーティングシステム、またはランタイムライブラリが、加算、減算、シフト、乗算などの基本的な命令を組み合わせて除算や剰余演算をソフトウェア的に実装する必要がありました。これが「ソフトウェア除算（soft division）」です。

ソフトウェア除算の実装は、アルゴリズム（例: ニュートン・ラプソン法、バイナリ除算アルゴリズムなど）によって性能が大きく異なります。一般的に、ハードウェアによる除算命令に比べて多くのCPUサイクルを消費するため、性能がクリティカルなアプリケーションではボトルネックとなる可能性があります。

Go言語のベンチマーク

Go言語には、標準ライブラリのtestingパッケージにベンチマーク機能が組み込まれています。これにより、コードの性能を測定し、最適化の効果を定量的に評価することができます。

  • ベンチマーク関数の命名規則: ベンチマーク関数はBenchmarkXxxという形式で命名され、*testing.B型の引数を一つ取ります。
  • b.N: ベンチマーク関数内でループを回す回数を指定します。testingパッケージは、ベンチマークの実行時間を安定させるために、b.Nの値を自動的に調整します。
  • b.ResetTimer(): ベンチマーク対象のコードの実行時間を測定する前に、タイマーをリセットします。これにより、セットアップコードの時間が測定結果に含まれるのを防ぎます。
  • b.StopTimer(): タイマーを一時停止します。
  • go test -bench=.: コマンドラインからベンチマークを実行する際に使用します。.はすべてのベンチマークを実行することを意味します。
  • 結果の解釈: ベンチマーク結果は通常、ns/op（1操作あたりのナノ秒）やB/op（1操作あたりのメモリ割り当てバイト数）、allocs/op（1操作あたりのメモリ割り当て回数）などの指標で表示されます。ns/opが小さいほど、その操作は高速であることを示します。

このコミットで追加されたベンチマークは、uint32型の除算と剰余演算が、様々な異なる除数に対してどれくらいの時間を要するかを測定することで、Goランタイムのソフトウェア除算の実装性能を評価します。

技術的詳細

このコミットで追加されるベンチマークは、GoランタイムがARMアーキテクチャ上でuint32型の除算と剰余演算をどのように処理しているかを評価するためのものです。特に「ソフトウェア除算」に焦点を当てています。

ソフトウェア除算は、CPUが直接除算命令を持たない場合や、特定の条件下でハードウェア除算よりもソフトウェア実装の方が効率的である場合に用いられます。Go言語のような高水準言語のランタイムは、このような低レベルの演算を効率的に実行するために、アセンブリ言語や最適化されたCコードで実装されたルーチンを使用することがあります。

ベンチマークの目的は、異なる除数（7, 37, 123, ..., 106956295）を用いた場合のuint32除算と剰余演算の性能を測定することです。除数の値が異なると、ソフトウェア除算アルゴリズムの実行パスや必要なステップ数が変わる可能性があり、その結果、性能に影響が出ることがあります。例えば、2のべき乗による除算はビットシフトで高速化できますが、それ以外の除数ではより複雑なアルゴリズムが必要になります。

ベンチマークコードでは、randomNumerators()関数によって事前に大量のランダムなuint32型の被除数（numerator）が生成されます。これにより、ベンチマーク実行中にデータ生成のオーバーヘッドが発生せず、純粋な除算/剰余演算の性能を測定できます。numeratorsSizeは1 << 21（2097152）と定義されており、十分な数のランダムな値が用意されます。

bmUint32DivとbmUint32Mod関数は、実際のベンチマークロジックをカプセル化しています。これらの関数は、b.N回ループを実行し、numerators配列から被除数を取得して、指定されたdivisorで除算または剰余演算を行います。i&(numeratorsSize-1)という式は、numerators配列のサイズでインデックスをラップアラウンドさせることで、配列の境界を越えないようにし、かつキャッシュの挙動を考慮したアクセスパターンを提供します。sum変数に結果を加算しているのは、コンパイラが演算を最適化して削除してしまう（dead code elimination）のを防ぐためです。

コミットメッセージに示されているベンチマーク結果（例: BenchmarkUint32Div7 10000000 298 ns/op）は、各操作が約298ナノ秒（除算）または280ナノ秒（剰余）で完了したことを示しています。これは、当時のlinux/arm omap4 pandaboard環境におけるGoランタイムのソフトウェア除算のベースライン性能を表しています。このデータは、将来の最適化が実際に性能向上をもたらしたかどうかを判断するための重要な指標となります。

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

このコミットでは、src/pkg/runtime/vlop_arm_test.goという新しいファイルが追加されています。このファイルは、ARMアーキテクチャ向けのソフトウェア除算および剰余演算のベンチマークコードを含んでいます。

--- /dev/null
+++ b/src/pkg/runtime/vlop_arm_test.go
@@ -0,0 +1,70 @@
+// Copyright 2012 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.
+
+package runtime_test
+
+import "testing"
+
+// arm soft division benchmarks adapted from 
+// http://ridiculousfish.com/files/division_benchmarks.tar.gz
+
+const numeratorsSize = 1 << 21
+
+var numerators = randomNumerators()
+
+type randstate struct {
+	hi, lo uint32
+}
+
+func (r *randstate) rand() uint32 {
+	r.hi = r.hi<<16 + r.hi>>16
+	r.hi += r.lo
+	r.lo += r.hi
+	return r.hi
+}
+
+func randomNumerators() []uint32 {
+	numerators := make([]uint32, numeratorsSize)
+	random := &randstate{2147483563, 2147483563 ^ 0x49616E42}
+	for i := range numerators {
+		numerators[i] = random.rand()
+	}
+	return numerators
+}
+
+func bmUint32Div(divisor uint32, b *testing.B) {
+	var sum uint32
+	for i := 0; i < b.N; i++ {
+		sum += numerators[i&(numeratorsSize-1)] / divisor
+	}
+}
+
+func BenchmarkUint32Div7(b *testing.B)         { bmUint32Div(7, b) }
+func BenchmarkUint32Div37(b *testing.B)        { bmUint32Div(37, b) }
+func BenchmarkUint32Div123(b *testing.B)       { bmUint32Div(123, b) }
+func BenchmarkUint32Div763(b *testing.B)       { bmUint32Div(763, b) }
+func BenchmarkUint32Div1247(b *testing.B)      { bmUint32Div(1247, b) }
+func BenchmarkUint32Div9305(b *testing.B)      { bmUint32Div(9305, b) }
+func BenchmarkUint32Div13307(b *testing.B)     { bmUint32Div(13307, b) }
+func BenchmarkUint32Div52513(b *testing.B)     { bmUint32Div(52513, b) }
+func BenchmarkUint32Div60978747(b *testing.B)  { bmUint32Div(60978747, b) }
+func BenchmarkUint32Div106956295(b *testing.B) { bmUint32Div(106956295, b) }
+
+func bmUint32Mod(divisor uint32, b *testing.B) {
+	var sum uint32
+	for i := 0; i < b.N; i++ {
+		sum += numerators[i&(numeratorsSize-1)] % divisor
+	}
+}
+
+func BenchmarkUint32Mod7(b *testing.B)         { bmUint32Mod(7, b) }
+func BenchmarkUint32Mod37(b *testing.B)        { bmUint32Mod(37, b) }
+func BenchmarkUint32Mod123(b *testing.B)       { bmUint32Mod(123, b) }
+func BenchmarkUint32Mod763(b *testing.B)       { bmUint32Mod(763, b) }
+func BenchmarkUint32Mod1247(b *testing.B)      { bmUint32Mod(1247, b) }
+func BenchmarkUint32Mod9305(b *testing.B)      { bmUint32Mod(9305, b) }
+func BenchmarkUint32Mod13307(b *testing.B)     { bmUint32Mod(13307, b) }
+func BenchmarkUint32Mod52513(b *testing.B)     { bmUint32Mod(52513, b) }
+func BenchmarkUint32Mod60978747(b *testing.B)  { bmUint32Mod(60978747, b) }
+func BenchmarkUint32Mod106956295(b *testing.B) { bmUint32Mod(106956295, b) }

コアとなるコードの解説

新しく追加されたsrc/pkg/runtime/vlop_arm_test.goファイルは、Goのtestingパッケージを利用して、ARMアーキテクチャにおけるuint32の除算と剰余演算の性能を測定します。

  1. パッケージとインポート:

    • package runtime_test: このファイルはruntimeパッケージのテストであり、runtimeパッケージ自体とは別のパッケージとして定義されています。これにより、runtimeパッケージの内部実装に依存せずにテストを行うことができます。
    • import "testing": Goのベンチマーク機能を提供するためにtestingパッケージをインポートしています。

  2. ベンチマークの元ネタ:

    • コメントに// arm soft division benchmarks adapted from // http://ridiculousfish.com/files/division_benchmarks.tar.gzとあり、このベンチマークがridiculousfish.comで公開されている除算ベンチマークから着想を得ていることが示されています。これは、様々な除数に対する除算性能を評価する一般的な手法です。

  3. 乱数生成器:

    • const numeratorsSize = 1 << 21: 被除数（numerator）の配列サイズを定義しています。2^21 = 2097152個のuint32値が生成されます。
    • var numerators = randomNumerators(): ベンチマークで使用するランダムな被除数のスライスをグローバル変数として初期化しています。これにより、ベンチマーク実行ごとに乱数を生成するオーバーヘッドを避けています。
    • type randstate struct { hi, lo uint32 }: 擬似乱数生成器の状態を保持するための構造体です。
    • func (r *randstate) rand() uint32: 擬似乱数を生成するメソッドです。これはXorshiftのようなシンプルなアルゴリズムに基づいているようです。hiとloの値をビットシフトと加算で更新し、新しい乱数を生成します。
    • func randomNumerators() []uint32: numeratorsSizeで指定された数のランダムなuint32値を生成し、スライスとして返します。初期シード値として2147483563と2147483563 ^ 0x49616E42を使用しています。

  4. 共通ベンチマーク関数:

    • func bmUint32Div(divisor uint32, b *testing.B): uint32の除算ベンチマークの共通ロジックを実装しています。
      • var sum uint32: コンパイラによる最適化（dead code elimination）を防ぐために、演算結果をsumに加算しています。sumが使用されないと、コンパイラが除算演算自体を削除してしまう可能性があります。
      • for i := 0; i < b.N; i++: testing.Bによって決定される回数だけループを実行します。
      • sum += numerators[i&(numeratorsSize-1)] / divisor: numerators配列から被除数を取得し、指定されたdivisorで除算を行います。i&(numeratorsSize-1)は、numeratorsSizeが2のべき乗であるため、i % numeratorsSizeと同じ効果を持ち、配列のインデックスを循環させます。
    • func bmUint32Mod(divisor uint32, b *testing.B): uint32の剰余ベンチマークの共通ロジックを実装しています。bmUint32Divと同様の構造で、除算の代わりに剰余演算（%）を行っています。

  5. 個別のベンチマーク関数:

    • func BenchmarkUint32Div7(b *testing.B) { bmUint32Div(7, b) } のように、様々な異なる除数（7, 37, 123, ..., 106956295）に対して、bmUint32DivとbmUint32Modを呼び出す個別のベンチマーク関数が定義されています。これにより、特定の除数に対する除算/剰余演算の性能を個別に測定し、比較することが可能になります。除数の選択は、小さい素数から大きな合成数まで幅広く、ソフトウェア除算アルゴリズムの様々なケースをカバーするように意図されています。

これらのベンチマークは、Goランタイムのソフトウェア除算の実装が、異なる入力に対してどれだけ効率的に動作するかを定量的に評価するための堅牢なフレームワークを提供します。

関連リンク

参考にした情報源リンク

  • Go言語のベンチマークに関する公式ドキュメントやチュートリアル
  • ARMアーキテクチャにおける整数除算命令の歴史とソフトウェア除算の必要性に関する情報
  • 擬似乱数生成器（Xorshiftなど）に関する情報
  • コンパイラの最適化（Dead Code Elimination）に関する情報