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

このコミットは、Go言語の標準ライブラリであるmath/bigパッケージ内のarith_amd64.sファイルに対する変更です。arith_amd64.sは、AMD64アーキテクチャ向けに最適化された任意精度演算（math/bigパッケージの機能）のためのアセンブリコードを含んでいます。具体的には、数値のビット長を計算するbitLen関数の実装が修正されています。

コミット

このコミットは、math/bigパッケージのbitLen関数の戻り値の型がintであることを考慮し、AMD64アーキテクチャ上でより適切な32ビット移動命令（MOVL）を使用するように変更しています。これにより、コードの効率性が向上します。

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

https://github.com/golang/go/commit/1e09031f7f9293ba032c88abb55b373d341f01bf

元コミット内容

math/big:  return type of bitLen is an int;  use MOVL on amd64.

R=golang-dev, gri
CC=golang-dev
https://golang.org/cl/5577050

変更の背景

Go言語のmath/bigパッケージは、任意精度の整数および浮動小数点数演算を提供します。このパッケージには、与えられた数値が何ビットで表現できるかを計算するbitLenという関数が存在します。

AMD64アーキテクチャにおいて、Go言語のint型は通常64ビット幅です。しかし、bitLen関数が返す「ビット数」という値は、最大でも64（64ビット整数のビット長）であり、多くの場合32ビットで十分に表現可能です。

元の実装では、bitLen関数の結果を格納する際に、64ビット操作であるINCQ（64ビットインクリメント）とMOVQ（64ビット移動）を使用していました。これは、Goのint型が64ビットであるという事実には合致しますが、実際に格納される値の範囲を考えると過剰な操作でした。

このコミットの背景には、以下の目的があります。

1. 効率性の向上: bitLenの戻り値が32ビットで収まることを利用し、より軽量で高速な32ビット操作（INCLとMOVL）に切り替えることで、アセンブリコードの実行効率を改善します。
2. 正確性の維持: 戻り値の型がint（64ビット）であっても、その値が32ビットに収まる限り、32ビット操作で値を設定しても上位ビットはゼロクリアされるため、正確性は保たれます。

この変更は、特定のアーキテクチャ（AMD64）における低レベルな最適化であり、math/bigパッケージ全体のパフォーマンス向上に寄与します。

前提知識の解説

このコミットの変更内容を理解するためには、以下の知識が役立ちます。

1. Go言語のmath/bigパッケージ

math/bigパッケージは、Go言語で任意精度の数値（整数、有理数、浮動小数点数）を扱うための機能を提供します。標準のintやfloat64型では表現できない非常に大きな数や、高い精度が求められる計算に使用されます。 bitLen関数は、big.Int型などの数値が何ビットで表現されるか（最上位ビットの位置）を計算するために内部的に使用されます。例えば、bitLen(7)は3（バイナリで111、3ビット必要）を返します。

2. x86-64 (AMD64) アセンブリ言語

Go言語は、パフォーマンスが重要な部分でアセンブリ言語を使用することがあります。arith_amd64.sは、AMD64プロセッサ向けのアセンブリコードファイルです。

• レジスタ:
  • AX: 汎用レジスタ。通常、関数の戻り値や演算結果を格納するために使用されます。AMD64ではRAXが64ビット、EAXが32ビット、AXが16ビット、AL/AHが8ビットの下位部分を指します。Goのアセンブリでは、AXと書くと文脈によって64ビットレジスタ全体を指すことが多いですが、命令によってはその下位部分に作用します。
• 命令:
  • BSRQ (Bit Scan Reverse Quadword): 64ビットオペランド（QはQuadword、64ビットを意味）の最上位セットビット（1になっているビット）のインデックスを検索し、結果をデスティネーションオペランドに格納します。例えば、BSRQ 0b00100000, AXはAXに5を格納します（0から数えて5番目のビットがセットされているため）。入力が0の場合は、フラグがセットされ、結果は未定義になります。
  • JZ (Jump if Zero): 直前の命令の結果がゼロフラグ（ZF）をセットした場合に、指定されたラベルにジャンプします。BSRQ命令は、入力が0の場合にゼロフラグをセットします。
  • INCQ (Increment Quadword): 64ビットオペランドの値を1増やします。
  • INCL (Increment Longword): 32ビットオペランドの値を1増やします。
  • MOVQ (Move Quadword): 64ビットデータをソースからデスティネーションへ移動します。
  • MOVL (Move Longword): 32ビットデータをソースからデスティネーションへ移動します。
  • RET: サブルーチンから戻ります。
• Goアセンブリのディレクティブ:
  • TEXT ·bitLen(SB),7,$0: bitLenという関数を定義します。SBはStatic Baseで、グローバルシンボルを指します。7はスタックフレームのフラグ、$0はローカル変数のサイズを示します。
  • x+0(FP): 関数引数xへのオフセット指定。FPはフレームポインタで、スタックフレーム内の引数やローカル変数にアクセスするために使用されます。
  • n+8(FP): 戻り値nへのオフセット指定。Goの関数呼び出し規約では、戻り値もスタックフレームに配置されることがあります。

3. Go言語のint型のサイズ

Go言語のint型は、実行されるアーキテクチャに依存します。32ビットシステムでは32ビット、64ビットシステムでは64ビットの符号付き整数です。AMD64は64ビットシステムであるため、intはint64として扱われます。

技術的詳細

このコミットの核心は、bitLen関数のアセンブリ実装におけるデータ移動とインクリメントの命令を、64ビット操作から32ビット操作へと変更した点にあります。

元のコードは以下のようになっていました。

TEXT ·bitLen(SB),7,$0
 	BSRQ x+0(FP), AX
 	JZ Z1
 	INCQ AX             // AXを64ビットでインクリメント
 	MOVQ AX, n+8(FP)    // AXの64ビット値を戻り値nに格納
 	RET

Z1:	MOVQ $0, n+8(FP)    // 0を64ビットで戻り値nに格納
 	RET

変更後のコードは以下の通りです。

TEXT ·bitLen(SB),7,$0
 	BSRQ x+0(FP), AX
 	JZ Z1
 	INCL AX             // AXの下位32ビットをインクリメント
 	MOVL AX, n+8(FP)    // AXの下位32ビット値を戻り値nに格納
 	RET

Z1:	MOVL $0, n+8(FP)    // 0を32ビットで戻り値nに格納
 	RET

変更の論理:

1. BSRQ x+0(FP), AX: この命令は、入力値xの最上位セットビットのインデックスをAXレジスタ（64ビット）に格納します。bitLenが返す値は、最大でも64（64ビット整数のビット長）です。この値は、32ビット整数で十分に表現できます。
2. INCQ AX から INCL AX:
   • INCQ AXはAXレジスタ全体（64ビット）をインクリメントします。
   • INCL AXはAXレジスタの下位32ビット（EAX部分）のみをインクリメントします。上位32ビットは変更されません。
   • bitLenの戻り値が32ビットで収まるため、INCLを使用しても結果の正確性は保たれます。これにより、プロセッサはより小さなデータパスで操作を実行でき、効率が向上する可能性があります。
3. MOVQ AX, n+8(FP) から MOVL AX, n+8(FP):
   • MOVQ AX, n+8(FP)はAXレジスタ全体（64ビット）の値を、戻り値nが格納されるメモリ位置n+8(FP)に64ビットで移動します。
   • MOVL AX, n+8(FP)はAXレジスタの下位32ビット（EAX部分）の値を、戻り値nが格納されるメモリ位置に32ビットで移動します。
   • Goのint型は64ビットですが、MOVLで32ビット値を格納した場合、残りの上位32ビットはゼロクリアされます。bitLenの戻り値は常に非負であり、32ビットで収まるため、このゼロクリアは問題ありません。むしろ、不要な64ビット操作を避けることで、メモリ帯域幅の節約やキャッシュ効率の向上に繋がる可能性があります。
4. Z1:ラベル内の変更:
   • 入力値がゼロの場合にbitLenが0を返すパスでも、同様にMOVQ $0, n+8(FP)からMOVL $0, n+8(FP)に変更されています。これは、0という値も32ビットで表現可能であるため、一貫した最適化が適用されています。

この変更は、Goのコンパイラやランタイムが生成するアセンブリコードの品質を向上させるための、細かながらも重要な最適化の一例です。

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

src/pkg/math/big/arith_amd64.sファイルにおいて、以下の行が変更されました。

--- a/src/pkg/math/big/arith_amd64.s
+++ b/src/pkg/math/big/arith_amd64.s
@@ -266,9 +266,9 @@ E7:	SUBL $1, BX		// i--
 TEXT ·bitLen(SB),7,$0
 	BSRQ x+0(FP), AX
 	JZ Z1
-	INCQ AX
-	MOVQ AX, n+8(FP)
+	INCL AX
+	MOVL AX, n+8(FP)
 	RET
 
-Z1:	MOVQ $0, n+8(FP)
+Z1:	MOVL $0, n+8(FP)
 	RET

コアとなるコードの解説

• - INCQ AX から + INCL AX:

  • INCQ AXは、AXレジスタ（64ビット）の値を1だけインクリメントする命令です。
  • INCL AXは、AXレジスタの下位32ビット（EAX）の値を1だけインクリメントする命令です。
  • bitLen関数が返すビット長は最大でも64であり、32ビットで表現可能なため、より効率的な32ビットインクリメント命令に置き換えられました。

• - MOVQ AX, n+8(FP) から + MOVL AX, n+8(FP):

  • MOVQ AX, n+8(FP)は、AXレジスタ（64ビット）の値を、戻り値nが格納されるスタック上のメモリ位置（n+8(FP)）に64ビットで移動する命令です。
  • MOVL AX, n+8(FP)は、AXレジスタの下位32ビット（EAX）の値を、同じメモリ位置に32ビットで移動する命令です。
  • Goのint型は64ビットですが、bitLenの戻り値が32ビットで収まるため、32ビット移動命令を使用しても問題ありません。これにより、不要な64ビット操作を削減し、パフォーマンスを向上させます。

• -Z1: MOVQ $0, n+8(FP) から +Z1: MOVL $0, n+8(FP):

  • Z1ラベルは、bitLenの入力値がゼロの場合にジャンプする場所です。この場合、ビット長は0となります。
  • ここでも同様に、0という値を戻り値に格納する際に、64ビット移動命令（MOVQ）から32ビット移動命令（MOVL）に置き換えられました。これは、0も32ビットで表現可能であるため、一貫した最適化が適用されています。

これらの変更は、bitLen関数のアセンブリ実装において、実際に扱われる値の範囲に合わせて命令のビット幅を最適化することで、実行効率を高めることを目的としています。

関連リンク

• Go Code Review (CL):
  • https://golang.org/cl/5577050 このリンクは、このコミットがGoのコードレビューシステム（Gerrit）でどのように議論され、承認されたかを示すものです。詳細な議論や背景情報が含まれている場合があります。

参考にした情報源リンク

• Go言語公式ドキュメント:
  • math/bigパッケージ: https://pkg.go.dev/math/big
  • Goのアセンブリ言語に関するドキュメント: https://go.dev/doc/asm
• x86-64 (AMD64) 命令セットリファレンス:
  • Intel 64 and IA-32 Architectures Software Developer's Manuals (特にVolume 2A: Instruction Set Reference, A-M): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
  • BSR, INC, MOVなどの命令の詳細を確認できます。
• Go言語のint型のサイズに関する情報:
  • Go言語の仕様: https://go.dev/ref/spec#Numeric_types
  • Goのint型がアーキテクチャ依存であることを確認できます。