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

このコミットは、bytesパッケージ内のIndexByte関数のアセンブリ実装をruntimeパッケージに移動させるものです。これにより、strings.IndexByte関数が共通の最適化されたコードを利用できるようになります。

変更されたファイルは以下の通りです。

• src/pkg/bytes/asm_386.s: bytesパッケージの386アーキテクチャ向けIndexByteアセンブリファイル（削除）
• src/pkg/bytes/asm_amd64.s: bytesパッケージのAMD64アーキテクチャ向けIndexByteアセンブリファイル（削除）
• src/pkg/bytes/asm_arm.s: bytesパッケージのARMアーキテクチャ向けIndexByteアセンブリファイル（削除）
• src/pkg/bytes/bytes.s: 新規作成されたbytesパッケージのアセンブリファイル（Goツールがファイルを認識するために追加された空ファイル）
• src/pkg/bytes/bytes_decl.go: bytesパッケージのGo宣言ファイル。IndexByteとEqual関数のアセンブリ実装への参照パスが更新されています。
• src/pkg/runtime/asm_386.s: runtimeパッケージの386アーキテクチャ向けアセンブリファイル（IndexByteアセンブリコードが追加）
• src/pkg/runtime/asm_amd64.s: runtimeパッケージのAMD64アーキテクチャ向けアセンブリファイル（IndexByteとEqualアセンブリコードが追加）
• src/pkg/runtime/asm_arm.s: runtimeパッケージのARMアーキテクチャ向けアセンブリファイル（IndexByteとEqualアセンブリコードが追加）

コミット

commit e2a1bd68b3683980247620dc8986d533afa0764d
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Thu Aug 1 16:11:19 2013 -0700

    bytes: move IndexByte assembly to pkg runtime
    
    Per suggestion from Russ in February. Then strings.IndexByte
    can be implemented in terms of the shared code in pkg runtime.
    
    Update #3751
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/12289043

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

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

元コミット内容

このコミットは、bytesパッケージのIndexByte関数のアセンブリ実装をruntimeパッケージに移動することを目的としています。これにより、strings.IndexByte関数がruntimeパッケージ内の共有コードを利用できるようになり、最適化されたバイト検索ロジックを再利用することが可能になります。これは、Russ Coxによる2月の提案に基づいています。この変更は、Go issue #3751に関連しています。

変更の背景

この変更の背景には、Goの標準ライブラリにおける文字列およびバイトスライスの操作のパフォーマンス最適化があります。特に、strings.Index関数が単一バイトの検索を行う際に、bytes.IndexByteが既にアセンブリで最適化されていたにもかかわらず、同様の最適化が適用されていなかったという問題（Go issue #3751）がありました。

bytes.IndexByteは、バイトスライス内で特定のバイトが最初に出現するインデックスを検索する関数です。この種の操作は非常に頻繁に行われるため、パフォーマンスが重要です。Goでは、このような低レベルの最適化のためにアセンブリ言語が使用されることがあります。

Russ Coxの提案は、bytes.IndexByteのアセンブリ実装をruntimeパッケージに移動することで、strings.IndexByte（Go 1.2で追加された関数）がその共通の最適化されたコードを再利用できるようにするというものでした。これにより、コードの重複を避けつつ、両方の関数で最高のパフォーマンスを達成することが可能になります。

前提知識の解説

Goのアセンブリ言語

Goは、一部のパフォーマンスクリティカルな部分でアセンブリ言語を使用します。Goのアセンブリは、一般的なアセンブリ言語とは異なり、Goツールチェーンによって処理される独自の構文を持っています。これは、Goのランタイムや標準ライブラリの特定の関数（例: メモリ操作、文字列/バイトスライス操作）で、C言語のインラインアセンブリや外部アセンブリファイルと同様に、CPUの特定の命令セット（例: SSE、AVX）を活用してパフォーマンスを最大化するために用いられます。

• TEXT: Goアセンブリで関数を定義するためのディレクティブです。TEXT func(SB), flags, args_size-ret_sizeのような形式で記述されます。
  • func(SB): 関数のシンボル名。SBはStatic Baseを意味し、グローバルシンボルへの参照を示します。
  • flags: 関数の特性を示すフラグ（例: $0はフレームサイズが0であることを示す）。
  • args_size-ret_size: 引数と戻り値の合計サイズ。
• MOVL, MOVQ, MOVB: それぞれ32ビット（Long）、64ビット（Quad）、8ビット（Byte）のデータを移動する命令です。
• CMP, JMP, JZ, JNE, JLT: 比較、無条件ジャンプ、ゼロフラグがセットされている場合のジャンプ、ゼロフラグがセットされていない場合のジャンプ、より小さい場合のジャンプなど、制御フローを操作する命令です。
• REPN; SCASB: x86アーキテクチャの命令で、REPNはCXレジスタがゼロになるまで次の命令を繰り返すプレフィックス、SCASBはALレジスタの値をDIレジスタが指すメモリ位置のバイトと比較し、DIをインクリメントする命令です。これは、メモリブロック内で特定のバイトを効率的に検索するために使用されます。
• SSE命令 (Streaming SIMD Extensions): Intelが開発したSIMD（Single Instruction, Multiple Data）命令セットです。複数のデータを一度に処理することで、メディア処理や科学技術計算などのパフォーマンスを向上させます。PCMPEQB（バイト単位の比較）、PMOVMSKB（比較結果のマスクを生成）、PSHUFL（シャッフル）などが含まれます。

bytesパッケージとstringsパッケージ

• bytesパッケージ: バイトスライス（[]byte）を操作するための関数を提供します。IndexByteは、バイトスライス内で特定のバイトを検索します。
• stringsパッケージ: 文字列（string）を操作するための関数を提供します。IndexByteは、文字列内で特定のバイトを検索します。Goの文字列は読み取り専用のバイトスライスとして内部的に表現されるため、bytes.IndexByteとstrings.IndexByteは類似の操作を行います。

runtimeパッケージ

Goのランタイムシステムを実装するパッケージです。ガベージコレクション、スケジューラ、低レベルのメモリ管理、システムコールなどが含まれます。パフォーマンスが非常に重要な低レベルのユーティリティ関数もここに配置されることがあります。runtimeパッケージにアセンブリコードを配置することで、Goのコア機能として利用可能になり、他のパッケージから共通して利用できるようになります。

//go:noescape

Goのコンパイラディレクティブの一つで、関数がヒープにメモリを割り当てないことを示します。これにより、コンパイラはエスケープ解析を最適化し、スタック割り当てを促進することができます。アセンブリで実装された関数によく付けられます。

技術的詳細

このコミットの主要な技術的詳細は、IndexByte関数のアセンブリ実装がbytesパッケージからruntimeパッケージに移動されたことです。これにより、Goの異なるパッケージ（特にbytesとstrings）が、バイト検索の最適化された共通ルーチンを共有できるようになります。

特に注目すべきは、AMD64アーキテクチャ向けのアセンブリコードにおける最適化です。

1. REPN; SCASB 命令の使用:

   • これは、x86/x64アーキテクチャで非常に効率的なバイト検索命令です。
   • SCASBは、ALレジスタ（検索対象のバイト）の内容をDIレジスタが指すメモリ位置のバイトと比較し、一致しない場合はゼロフラグをクリアし、DIをインクリメントします。
   • REPNプレフィックスは、CXレジスタがゼロになるか、SCASBが一致を見つけるまでSCASB命令を繰り返します。これにより、ループを明示的に記述することなく、高速なバイト検索が可能です。

2. SSE (Streaming SIMD Extensions) 命令の活用:

   • AMD64のアセンブリコードでは、16バイト以上の大きなバイトスライスに対してSSE命令が使用されています。
   • CMPQ BX, $16で、スライス長が16バイト未満の場合はindexbyte_smallラベルにジャンプし、REPN; SCASBによるシンプルな検索を行います。
   • スライス長が16バイト以上の場合、データは16バイトのチャンクで処理されます。
   • MOVD AX, X0, PUNPCKLBW X0, X0, PSHUFL $0, X0, X0: 検索対象のバイトcをSSEレジスタX0に16回複製し、16バイトすべてがcになるように準備します。
   • MOVO (DI), X1: メモリから16バイトのデータをSSEレジスタX1にロードします。
   • PCMPEQB X0, X1: X0（すべてc）とX1（データチャンク）の各バイトを比較します。一致するバイトがあれば、対応する結果バイトのすべてのビットが1に設定されます。
   • PMOVMSKB X1, DX: X1の各バイトの最上位ビット（比較結果）を抽出し、32ビットレジスタDXにマスクとして格納します。DXのビットが1であれば、その位置に対応するバイトが一致したことを示します。
   • TESTL DX, DX, JNZ ssesuccess: DXがゼロでなければ（つまり、一致するバイトが見つかれば）、ssesuccessラベルにジャンプします。
   • ADDQ $16, DI: 一致が見つからなければ、DIを16バイト進めて次のチャンクを処理します。
   • BSFW DX, DX: ssesuccessでは、DXの最下位ビット（最初に一致したバイトの位置）を検索し、そのインデックスを取得します。これにより、16バイトチャンク内の正確な位置が特定されます。

これらの最適化により、特に大きなバイトスライスに対するIndexByteの操作が大幅に高速化されます。アセンブリコードは、CPUの低レベルな機能を直接利用することで、Goのコンパイラが生成するコードよりもさらに効率的な処理を実現します。

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

このコミットのコアとなる変更は、bytesパッケージのアセンブリファイルからIndexByte関数の実装を削除し、それをruntimeパッケージのアセンブリファイルに移動したことです。

具体的には：

• 削除されたファイル:

  • src/pkg/bytes/asm_386.s
  • src/pkg/bytes/asm_amd64.s
  • src/pkg/bytes/asm_arm.s これらのファイルからTEXT ·IndexByte(SB)で始まるアセンブリコードが完全に削除されました。

• 新規追加されたファイル:

  • src/pkg/bytes/bytes.s このファイルは、Goツールがbytesパッケージのアセンブリファイルを認識するために作成された空のファイルです。

• 変更されたファイル:

  • src/pkg/bytes/bytes_decl.go: IndexByte関数の宣言のコメントが変更され、アセンブリ実装のパスがasm_$GOARCH.sから../runtime/asm_$GOARCH.sに変更されました。これは、実装がruntimeパッケージに移動したことを示します。

    --- a/src/pkg/bytes/bytes_decl.go
    +++ b/src/pkg/bytes/bytes_decl.go
    @@ -7,13 +7,13 @@ package bytes
     //go:noescape
     
     // IndexByte returns the index of the first instance of c in s, or -1 if c is not present in s.
    -func IndexByte(s []byte, c byte) int // asm_$GOARCH.s
    +func IndexByte(s []byte, c byte) int // ../runtime/asm_$GOARCH.s
     
     //go:noescape
     
     // Equal returns a boolean reporting whether a == b.
     // A nil argument is equivalent to an empty slice.
    -func Equal(a, b []byte) bool // asm_arm.s or ../runtime/asm_{386,amd64}.s
    +func Equal(a, b []byte) bool // ../runtime/asm_$GOARCH.s
     
     //go:noescape
    

    Equal関数も同様にruntimeパッケージに移動されたため、そのコメントも更新されています。

• 追加されたファイル:

  • src/pkg/runtime/asm_386.s: TEXT bytes·IndexByte(SB)で始まる386アーキテクチャ向けのアセンブリコードが追加されました。これは、以前src/pkg/bytes/asm_386.sにあった内容とほぼ同じです。
  • src/pkg/runtime/asm_amd64.s: TEXT bytes·IndexByte(SB)で始まるAMD64アーキテクチャ向けのアセンブリコードが追加されました。これは、以前src/pkg/bytes/asm_amd64.sにあった内容とほぼ同じですが、bytes·Equalもこのファイルに移動されています。
  • src/pkg/runtime/asm_arm.s: TEXT bytes·IndexByte(SB)で始まるARMアーキテクチャ向けのアセンブリコードが追加されました。これは、以前src/pkg/bytes/asm_arm.sにあった内容とほぼ同じですが、bytes·Equalもこのファイルに移動されています。

コアとなるコードの解説

移動されたIndexByteのアセンブリコードは、各アーキテクチャ（386, amd64, arm）で特定のバイトを効率的に検索するための最適化されたロジックを含んでいます。

src/pkg/runtime/asm_386.s (386アーキテクチャ)

TEXT bytes·IndexByte(SB),7,$0
	MOVL	s+0(FP), SI      // s (バイトスライス) の開始アドレスを SI にロード
	MOVL	s_len+4(FP), CX  // s の長さを CX にロード (REPN のカウンタ)
	MOVB	c+12(FP), AL     // 検索対象のバイト c を AL にロード
	MOVL	SI, DI           // SI を DI にコピー (検索開始アドレス)
	CLD; REPN; SCASB         // DI が指すメモリを AL と比較し、DI をインクリメント。CX が 0 になるか一致するまで繰り返す。
	JZ 3(PC)                 // ゼロフラグがセットされていれば (一致が見つからなければ) 3バイト先にジャンプ (次の命令をスキップ)
	MOVL	$-1, ret+16(FP)  // -1 を戻り値に設定 (見つからなかった場合)
	RET                      // 関数から戻る
	SUBL	SI, DI           // DI から SI を引く (DI は一致した位置の次を指すので、開始アドレスからのオフセットを計算)
	SUBL	$1, DI           // 1 を引く (正確な一致位置のインデックスにするため)
	MOVL	DI, ret+16(FP)   // 計算されたインデックスを戻り値に設定
	RET                      // 関数から戻る

このコードは、REPN; SCASB命令の組み合わせを利用して、バイトスライス内のバイトを高速に検索します。SCASBはALレジスタの値をDIが指すメモリと比較し、DIをインクリメントします。REPNプレフィックスは、CXレジスタがゼロになるか、一致が見つかるまでこの操作を繰り返します。

src/pkg/runtime/asm_amd64.s (AMD64アーキテクチャ)

AMD64版は、より高度な最適化としてSSE命令を使用しています。

TEXT bytes·IndexByte(SB),7,$0
	MOVQ s+0(FP), SI         // s の開始アドレスを SI にロード
	MOVQ s_len+8(FP), BX     // s の長さを BX にロード
	MOVB c+24(FP), AL        // 検索対象のバイト c を AL にロード
	MOVQ SI, DI              // SI を DI にコピー

	CMPQ BX, $16             // スライス長が16未満かチェック
	JLT indexbyte_small      // 16未満なら小さいスライス用の処理へ

	// round up to first 16-byte boundary
	TESTQ $15, SI            // SI が16バイト境界にアラインされているかチェック
	JZ aligned               // アラインされていれば aligned へ
	MOVQ SI, CX
	ANDQ $~15, CX
	ADDQ $16, CX             // 次の16バイト境界を計算

	// search the beginning
	SUBQ SI, CX              // 検索するバイト数を計算
	REPN; SCASB              // 最初の非アライン部分を検索
	JZ success               // 見つかれば success へ

// DI is 16-byte aligned; get ready to search using SSE instructions
aligned:
	// round down to last 16-byte boundary
	MOVQ BX, R11
	ADDQ SI, R11
	ANDQ $~15, R11           // 検索範囲の最後の16バイト境界を計算

	// shuffle X0 around so that each byte contains c
	MOVD AX, X0              // AL (c) を X0 に移動
	PUNPCKLBW X0, X0         // X0 を拡張して cccc cccc に
	PUNPCKLBW X0, X0         // X0 をさらに拡張して cccc cccc cccc cccc に
	PSHUFL $0, X0, X0        // X0 の全バイトを c に複製 (16バイトすべて c)
	JMP condition            // condition へジャンプ

sse:
	// move the next 16-byte chunk of the buffer into X1
	MOVO (DI), X1            // DI が指す16バイトを X1 にロード
	// compare bytes in X0 to X1
	PCMPEQB X0, X1           // X0 と X1 の各バイトを比較 (一致すれば対応ビットが1に)
	// take the top bit of each byte in X1 and put the result in DX
	PMOVMSKB X1, DX          // X1 の各バイトの最上位ビットを DX にマスクとして格納
	TESTL DX, DX             // DX がゼロかチェック (一致するバイトがあったか)
	JNZ ssesuccess           // ゼロでなければ ssesuccess へ
	ADDQ $16, DI             // 次の16バイトチャンクへ進む

condition:
	CMPQ DI, R11             // 現在位置が最後の16バイト境界を超えたかチェック
	JLT sse                  // 超えていなければ sse へ

	// search the end
	MOVQ SI, CX
	ADDQ BX, CX
	SUBQ R11, CX             // 残りの非アライン部分の長さを計算
	// if CX == 0, the zero flag will be set and we\'ll end up
	// returning a false success
	JZ failure               // 残り部分がなければ failure へ
	REPN; SCASB              // 残りの非アライン部分を検索
	JZ success               // 見つかれば success へ

failure:
	MOVQ $-1, ret+32(FP)     // -1 を戻り値に設定
	RET

// handle for lengths < 16
indexbyte_small:
	MOVQ BX, CX
	REPN; SCASB              // 小さいスライスを検索
	JZ success
	MOVQ $-1, ret+32(FP)
	RET

// we\'ve found the chunk containing the byte
// now just figure out which specific byte it is
ssesuccess:
	// get the index of the least significant set bit
	BSFW DX, DX              // DX の最下位ビットのインデックスを取得 (一致したバイトの位置)
	SUBQ SI, DI              // DI から SI を引く (開始アドレスからのオフセット)
	ADDQ DI, DX              // オフセットにチャンク内での位置を加算
	MOVQ DX, ret+32(FP)      // 最終的なインデックスを戻り値に設定
	RET

success:
	SUBQ SI, DI
	SUBL $1, DI
	MOVQ DI, ret+32(FP)
	RET

このコードは、まずスライス長が16バイト未満かどうかをチェックし、そうであればシンプルなREPN; SCASBを使用します。16バイト以上の場合は、アラインメントを考慮し、SSE命令（PCMPEQB, PMOVMSKBなど）を使って16バイト単位で並列にバイトを比較します。これにより、一度に多くのバイトを処理できるため、非常に高速な検索が可能です。

src/pkg/runtime/asm_arm.s (ARMアーキテクチャ)

ARM版もループとバイト比較を最適化しています。

TEXT bytes·IndexByte(SB),7,$0
	MOVW	s+0(FP), R0      // s の開始アドレスを R0 にロード
	MOVW	s_len+4(FP), R1  // s の長さを R1 にロード
	MOVBU	c+12(FP), R2     // 検索対象のバイト c を R2 にロード
	MOVW	R0, R4           // R0 を R4 に保存 (ベースアドレス)
	ADD	R0, R1           // R0 に R1 を加算 (終了アドレス)

_loop:
	CMP	R0, R1           // 現在位置が終了アドレスに達したかチェック
	B.EQ	_notfound        // 達していれば _notfound へ
	MOVBU.P	1(R0), R3        // R0 が指すメモリから1バイト読み込み、R0 をインクリメント
	CMP	R2, R3           // 読み込んだバイトと検索対象バイトを比較
	B.NE	_loop            // 一致しなければ _loop へ

	SUB	$1, R0           // R0 を1減らす (一致した位置の次を指すため)
	SUB	R4, R0           // R0 から R4 を引く (ベースアドレスからのオフセット)
	MOVW    R0, ret+16(FP)   // 計算されたインデックスを戻り値に設定
	RET

_notfound:
	MOVW	$-1, R0          // -1 を R0 に設定
	MOVW	R0, ret+16(FP)   // -1 を戻り値に設定
	RET

ARM版は、ループ内でMOVBU.P命令（バイトを読み込み、ポインタをポストインクリメント）とCMP命令を組み合わせて、効率的なバイト検索ループを実装しています。

これらのアセンブリコードの移動により、bytes.IndexByteとstrings.IndexByteの両方が、各アーキテクチャで利用可能な最も効率的なバイト検索ルーチンを共有できるようになり、Goプログラム全体のパフォーマンス向上に貢献します。

関連リンク

• Go issue #3751: https://github.com/golang/go/issues/3751
• Go CL 12289043: https://golang.org/cl/12289043

参考にした情報源リンク

• https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQHOzPVXBRbvsK7PXfT6f6tDGES5qFEzxqLxoqqXqssNEWCjHKybIV5YJ4Ppg8YcGqsPUhuwDVymhh8pFS9Z0BfGNCVta5GQJRFbI90eIDng8sejooGJCR3TUKckfsUmAVM8oXU=
• https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQE5iS5ERPp78aLw1LWkGK1tXquVs_0bqSlqtWXjgkSreooNmaX5fTee0y2uju8OvH2Gtcfj3WQ6chezyLFYf0fhiUbDd4Twsdafl71ExTeqKEy1A1ax
• https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQFbIL7Of5MmP16z2stTnH-ASRJPDH7gbgo2_HqArx6iLnO8dcnw8Cb78B1jQwNesWjIahpYukiDGL0nNMHSFIu_CL2L5vD5lj10O2eswEOA674zQDjJWI1c4qzVEyLyHdIrR88r68ZIqfLTMaC7E3RmIEtXUW0zZB6r_6eyJH1kONzzNJIei8biwVKGNG4=