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

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

このコミットは、Goランタイムのsrc/pkg/runtime/runtime.cファイルに対する変更です。このファイルはGo言語のランタイムシステムの中核をなす部分であり、メモリ管理、スケジューリング、プリミティブな操作など、Goプログラムが動作するために必要な低レベルの機能を提供します。具体的には、runtime.cはC言語で記述されており、Goのコンパイラやアセンブラでは直接表現できないような、OSとのインタラクションやハードウェアに密接な処理を実装するために使用されます。

コミット

commit a05237f20ae6230238a9e44bc8bfc974e6d51422
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Wed Jul 31 23:37:23 2013 +0200

    runtime: save 8 stack bytes in timediv on arm.
    
    Operations on int64 are very stack consuming with 5c.
    Fixes netbsd/arm build.
    
    Before: TEXT    runtime.timediv+0(SB),7,$52-16
    After:  TEXT    runtime.timediv+0(SB),7,$44-16
    
    The stack usage is unchanged on 386:
            TEXT    runtime.timediv+0(SB),7,$8-16
    
    R=golang-dev, dvyukov, bradfitz
    CC=golang-dev
    https://golang.org/cl/12182044

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

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

元コミット内容

diff --git a/src/pkg/runtime/runtime.c b/src/pkg/runtime/runtime.c
index 5bca6f87b4..a0e9a194c6 100644
--- a/src/pkg/runtime/runtime.c
+++ b/src/pkg/runtime/runtime.c
@@ -421,16 +421,16 @@ runtime·timediv(int64 v, int32 div, int32 *rem)
 {
 	int32 res, bit;
 
-	if(v >= div*0x7fffffffLL) {
+	if(v >= (int64)div*0x7fffffffLL) {
 		if(rem != nil)
 			*rem = 0;
 		return 0x7fffffff;
 	}
 	res = 0;
-	for(bit = 0x40000000; bit != 0; bit >>= 1) {
-		if(v >= (int64)bit*div) {
-			v = v - (int64)bit*div;
-			res += bit;
+	for(bit = 30; bit >= 0; bit--) {
+		if(v >= ((int64)div<<bit)) {
+			v = v - ((int64)div<<bit);
+			res += 1<<bit;
 		}
 	}
 	if(rem != nil)

変更の背景

このコミットの主な背景は、ARMアーキテクチャにおけるint64（64ビット整数）演算のスタック消費量の多さです。特に、当時のGoコンパイラである5c（Plan 9 CコンパイラをベースにしたGoのCコンパイラ）がARMターゲット向けに生成するコードにおいて、int64の操作が過度にスタックを消費するという問題がありました。

この問題は、NetBSD/ARMビルドの失敗として顕在化しました。スタック消費量が多いと、スタックオーバーフローのリスクが高まるだけでなく、パフォーマンスにも悪影響を及ぼします。runtime.timediv関数はGoランタイムの重要な一部であり、時間関連の計算（例：time.Durationの処理）で頻繁に使用されるため、その効率性はGoプログラム全体のパフォーマンスに直結します。

コミットメッセージに記載されているように、変更前はruntime.timediv関数のスタックフレームサイズが52バイトでしたが、変更後は44バイトに削減され、8バイトのスタック領域が節約されました。これは、特にリソースが限られた環境や、スタックサイズが厳しく管理される組み込みシステムにおいて重要な改善となります。x86（386）アーキテクチャではこの問題は発生しておらず、スタック使用量に変化がないことも明記されており、ARM特有の最適化であることが示唆されています。

前提知識の解説

1. int64と64ビット整数演算

int64は、64ビット（8バイト）の符号付き整数型です。32ビットアーキテクチャ（ARMv5, ARMv6, ARMv7など）では、CPUのレジスタが通常32ビット幅であるため、64ビットの値を直接単一のレジスタで扱うことができません。このため、int64の演算（加算、減算、乗算、除算など）は、複数の32ビットレジスタを組み合わせて処理するか、あるいはメモリ（スタック）を一時的に使用して処理する必要があります。この「複数のレジスタを使う」または「メモリを使う」という処理が、32ビットアーキテクチャにおけるint64演算の複雑さと、それに伴うスタック消費量の増加の主な原因となります。

2. ARMアーキテクチャ

ARM（Advanced RISC Machine）は、モバイルデバイスや組み込みシステムで広く使用されているRISC（Reduced Instruction Set Computer）ベースのプロセッサアーキテクチャです。ARMには32ビット版と64ビット版（ARM64/ARMv8-A以降）がありますが、このコミットが作成された2013年時点では、32ビットARMが主流でした。32ビットARMでは、レジスタが32ビット幅であるため、64ビットのint64値を扱う際には特別な処理が必要になります。

3. Goの5cコンパイラ

5cは、Go言語の初期のコンパイラツールチェーンの一部で、Plan 9 Cコンパイラをベースにしていました。Goのコンパイラは、ターゲットアーキテクチャごとに異なるバックエンドを持っており、5cはARMアーキテクチャ向けのCコンパイラを指します。当時の5cコンパイラは、int64のような大きなデータ型を扱う際に、最適化が不十分であったり、特定のアーキテクチャの特性を十分に考慮していなかったりする可能性がありました。これが、ARMにおけるint64演算のスタック消費量増加の一因と考えられます。

4. スタックとスタックフレーム

プログラムが関数を呼び出す際、その関数が必要とするローカル変数、引数、戻りアドレスなどを格納するために、メモリ上に「スタックフレーム」が割り当てられます。スタックはLIFO（Last-In, First-Out）構造のメモリ領域で、関数呼び出しごとにスタックフレームが積まれ、関数からのリターン時に解放されます。スタックフレームのサイズは、関数が使用するローカル変数の数や型、引数の数、そしてコンパイラが生成するコードの効率性によって決まります。スタック消費量が多いということは、より多くのメモリがスタックに割り当てられることを意味し、スタックオーバーフローのリスクやメモリ効率の低下につながります。

5. timediv関数とビットシフトによる除算

runtime.timediv関数は、Goランタイム内で使用される時間関連の除算を行う関数です。この関数は、int64型の被除数vをint32型の除数divで除算し、商と（オプションで）剰余を計算します。

この関数は、一般的なCPUの除算命令を使用する代わりに、ビットシフトと減算を組み合わせたアルゴリズムで除算を実装しています。これは、特に特定のアーキテクチャで除算命令が遅い場合や、より細かい制御が必要な場合に用いられる最適化手法です。

基本的な考え方は、除数を2のべき乗倍（左シフト）していき、被除数から引ける最大の値を繰り返し見つけていくことで商を構築するというものです。例えば、v / divを計算する際に、div * 2^Nがv以下である最大のNを見つけ、vからdiv * 2^Nを引いて、商に2^Nを加算します。これを繰り返すことで、最終的な商が得られます。

変更前のコードでは、for(bit = 0x40000000; bit != 0; bit >>= 1)というループで、bitが2^30から2^0まで変化していました。これは、int32の最上位ビットから順にチェックしていくことを意味します。

技術的詳細

このコミットは、runtime.timediv関数におけるint64除算の最適化に焦点を当てています。特にARMアーキテクチャの32ビット版において、int64の演算がスタックを多く消費するという問題に対処しています。

変更の核心は、除算アルゴリズムにおけるビット操作の変更です。

変更前:

	for(bit = 0x40000000; bit != 0; bit >>= 1) {
		if(v >= (int64)bit*div) {
			v = v - (int64)bit*div;
			res += bit;
		}
	}

このコードでは、bit変数が0x40000000（2の30乗）から始まり、右シフトによって1まで変化します。ループ内でbit*divという乗算が行われています。bitはint32ですが、divもint32であり、その積がint64にキャストされています。32ビットARMでは、int32同士の乗算であっても、結果がint64になる場合、コンパイラは64ビット乗算をエミュレートするための追加の命令を生成する必要があります。このエミュレーションは、複数のレジスタを使用したり、一時的にスタックに値を保存したりすることで実現されるため、スタック消費量が増加する可能性があります。

変更後:

	for(bit = 30; bit >= 0; bit--) {
		if(v >= ((int64)div<<bit)) {
			v = v - ((int64)div<<bit);
			res += 1<<bit;
		}
	}

変更後のコードでは、ループ変数がbit（int32）から30で初期化され、0までデクリメントされます。最も重要な変更点は、if文の条件式と減算式です。

  • if(v >= ((int64)div<<bit))
  • v = v - ((int64)div<<bit);

ここでは、divをint64にキャストしてから左シフトbitしています。((int64)div<<bit)という操作は、divをint64として扱い、それをbit回左シフトすることでdiv * 2^bitを計算します。この操作は、int64の乗算bit*divよりも、コンパイラがより効率的なコードを生成できる可能性があります。特に、シフト操作は乗算よりも単純なCPU命令で実現できることが多く、64ビット値に対するシフト操作は、32ビットアーキテクチャでも比較的効率的に処理できる場合があります。

また、res += 1<<bit;という部分も変更されています。変更前はres += bit;でしたが、これは論理的に誤りです。bitはループのインデックスであり、2^bitの値ではありません。正しい商のビットを加算するためには1<<bitが必要です。この修正は、スタック消費量の削減とは直接関係ありませんが、アルゴリズムの正確性を保証する上で重要です。

この変更により、5cコンパイラがARM向けに生成するアセンブリコードにおいて、int64の乗算エミュレーションに伴う不要なスタック使用が削減されたと考えられます。結果として、runtime.timediv関数のスタックフレームサイズが52バイトから44バイトに減少し、8バイトのスタック領域が節約されました。これは、特にスタックが限られている環境や、多数の関数呼び出しが行われるGoランタイムにおいて、メモリ効率と安定性の向上に貢献します。

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

src/pkg/runtime/runtime.cファイルのruntime·timediv関数内。

  1. 最初のif文の条件式:

    -	if(v >= div*0x7fffffffLL) {
+	if(v >= (int64)div*0x7fffffffLL) {

    divを明示的にint64にキャストしてから乗算を行うように変更。これにより、コンパイラがint64の乗算を正しく処理し、潜在的なオーバーフローや不正確な計算を防ぐことを意図している可能性があります。

  2. forループの初期化と条件式:

    -	for(bit = 0x40000000; bit != 0; bit >>= 1) {
+	for(bit = 30; bit >= 0; bit--) {

    ループ変数のbitを、2^30の値から30という指数値に変更。ループの進行も、値を右シフトするのではなく、指数をデクリメントするように変更。

  3. if文の条件式と減算式:

    -		if(v >= (int64)bit*div) {
-			v = v - (int64)bit*div;
+		if(v >= ((int64)div<<bit)) {
+			v = v - ((int64)div<<bit);

    int64の乗算bit*divを、int64にキャストしたdivをbit回左シフトする((int64)div<<bit)に置き換え。これにより、div * 2^bitを計算する。

  4. 商の加算式:

    -			res += bit;
+			res += 1<<bit;

    商に加算する値を、ループインデックスのbitから、2^bitを表す1<<bitに修正。これはアルゴリズムの論理的な修正であり、スタック消費量の削減とは直接関係ないが、正確な除算結果を得るために必要。

コアとなるコードの解説

このコミットの核心は、runtime.timediv関数におけるint64除算のアルゴリズムを、スタック消費を抑えるように変更した点にあります。

変更前のコードでは、for(bit = 0x40000000; bit != 0; bit >>= 1)というループと、その中のif(v >= (int64)bit*div)という条件式が問題でした。

  • bit変数はint32型で、0x40000000（2の30乗）から始まり、ループごとに右シフトされていきます。
  • bit*divという乗算は、int32同士の乗算ですが、結果がint64にキャストされています。32ビットARMアーキテクチャでは、64ビットの結果を生成する乗算は、単一のCPU命令で完結せず、複数の命令や一時的なスタック領域を必要とすることがあります。当時の5cコンパイラは、このint64乗算のエミュレーションにおいて、効率の悪いコードを生成し、余分なスタック領域を消費していたと考えられます。

変更後のコードでは、この問題に対処するために以下の変更が行われました。

  • for(bit = 30; bit >= 0; bit--)：ループ変数をbit（指数）に変更し、30から0までデクリメントするようにしました。これにより、ループの意図がより明確になります。
  • if(v >= ((int64)div<<bit))：最も重要な変更点です。bit*divという乗算を、((int64)div<<bit)というビットシフト操作に置き換えました。
    • divをまずint64にキャストします。
    • そのint64値をbit回左シフトします。これは数学的にdiv * 2^bitと同じ意味です。
    • ビットシフト操作は、多くのCPUアーキテクチャにおいて、乗算よりも高速かつ効率的な単一の命令で実行できることが多いです。特に、64ビット値に対するシフト操作は、32ビットアーキテクチャでもコンパイラがより最適化されたコードを生成しやすい傾向があります。これにより、int64乗算のエミュレーションに伴う不要なスタック使用が回避され、スタック消費量が削減されました。
  • res += 1<<bit;：これはアルゴリズムの論理的な修正です。変更前はres += bit;となっていましたが、これは誤りです。商に加算すべきは、現在のビット位置に対応する値（2^bit）であり、ループインデックスのbitそのものではありません。この修正により、timediv関数が正確な除算結果を返すことが保証されます。

これらの変更、特にint64乗算をint64シフトに置き換えることで、ARMアーキテクチャにおける5cコンパイラが生成するコードの効率が向上し、runtime.timediv関数のスタックフレームサイズが8バイト削減されました。これにより、NetBSD/ARMビルドの問題が解決され、Goランタイムの安定性と効率性が向上しました。

関連リンク

参考にした情報源リンク