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

このコミットは、Go言語の標準ライブラリstringsパッケージ内のIndexByte関数の実装を、Goランタイムのアセンブリコードに移行することで最適化するものです。これにより、特定のバイトが文字列内に最初に現れるインデックスを検索する処理のパフォーマンスが向上します。

コミット

commit 598c78967f26a0275a1f295ce3a96769f9be91bb
Author: Brad Fitzpatrick <bradfitz@golang.org>
Date:   Mon Aug 5 15:04:05 2013 -0700

    strings: use runtime assembly for IndexByte
    
    Fixes #3751
    
    R=golang-dev, khr
    CC=golang-dev
    https://golang.org/cl/12483043

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

https://github.com/golang/go/commit/598c78967f26a0275a1f295ce3a96769f9be91bb

元コミット内容

strings: use runtime assembly for IndexByte

このコミットは、stringsパッケージのIndexByte関数が、Goランタイムのアセンブリコードを使用するように変更されたことを示しています。これにより、パフォーマンスの改善が期待されます。関連するIssueは#3751です。

変更の背景

この変更の背景には、Go言語の標準ライブラリにおけるパフォーマンス最適化の継続的な取り組みがあります。特に、文字列操作のような基本的な処理は、多くのアプリケーションで頻繁に使用されるため、その効率はシステム全体のパフォーマンスに大きな影響を与えます。

IndexByte関数は、文字列（バイトスライス）内で特定のバイトを検索する操作であり、その実装はループによるバイトごとの比較が一般的です。しかし、このような低レベルの操作は、Go言語で記述された高レベルなコードよりも、CPUの命令セットを直接利用するアセンブリ言語で記述することで、より高速に実行できる可能性があります。

GoのIssue #3751（"strings: IndexByte is slow"）がこの変更の直接的なトリガーとなっています。このIssueでは、strings.IndexByteのパフォーマンスが、特に大きな文字列に対して遅いことが報告されており、アセンブリによる最適化が提案されていました。アセンブリ言語を使用することで、コンパイラが生成するコードでは実現が難しい、特定のCPU命令（例: SCASB命令など、バイト検索に特化した命令）や、より効率的なレジスタの使用、ループの最適化などが可能になります。

この最適化は、Goランタイムの低レベルな部分に手を加えることで、Goプログラム全体の文字列処理性能を底上げすることを目的としています。

前提知識の解説

Go言語のアセンブリ

Go言語は、そのコンパイラがGo言語自体で書かれているという特徴がありますが、パフォーマンスが重要な一部の関数（特にランタイムや標準ライブラリの低レベルな部分）では、アセンブリ言語が使用されています。Goのアセンブリは、一般的なアセンブリ言語とは異なり、Goツールチェーンが提供する独自の擬似命令セットと構文（Plan 9アセンブラの派生）を使用します。これは、異なるアーキテクチャ（x86, AMD64, ARMなど）間で共通の構文を保ちつつ、各アーキテクチャの特性を活かした最適化を可能にするためです。

Goのアセンブリコードは、TEXTディレクティブで関数を定義し、レジスタやメモリへのアクセス、ジャンプ命令などを記述します。Goの関数呼び出し規約に従って、引数はスタックまたはレジスタを通じて渡され、戻り値も同様に処理されます。

strings.IndexByte関数

strings.IndexByte(s string, c byte) intは、Goの標準ライブラリstringsパッケージに含まれる関数です。この関数は、バイトスライスsの中から、指定されたバイトcが最初に現れるインデックスを返します。もしcがsの中に存在しない場合は-1を返します。

例:

package main

import (
	"fmt"
	"strings"
)

func main() {
	s := "hello world"
	fmt.Println(strings.IndexByte(s, 'o')) // 出力: 4
	fmt.Println(strings.IndexByte(s, 'z')) // 出力: -1
}

SCASB命令 (x86/AMD64)

x86およびAMD64アーキテクチャには、文字列操作を高速化するための特別な命令セットが存在します。その一つがSCASB（Scan String Byte）命令です。

SCASB命令は、ALレジスタ（またはAX/EAX/RAX）に格納されたバイト（またはワード/ダブルワード/クワッドワード）と、ES:DI（またはRDI）が指すメモリ位置のバイトを比較します。比較後、DIレジスタは自動的にインクリメントまたはデクリメントされます（DFフラグの状態による）。

この命令は通常、REPプレフィックス（Repeat）と組み合わせて使用されます。REPN（Repeat while Not Equal）またはREPE（Repeat while Equal）プレフィックスをSCASBと組み合わせることで、CX（またはRCX）レジスタがゼロになるか、比較結果が特定の条件を満たすまで、一連のバイト比較を繰り返すことができます。

REPN SCASBは、ALレジスタの値とメモリ上のバイトが一致するまで、またはCXがゼロになるまで、メモリをスキャンします。一致が見つかった場合、DIは一致したバイトの次のアドレスを指し、CXは残りの要素数を示します。一致が見つからなかった場合、CXはゼロになり、DIはスキャン終了後のアドレスを指します。

この命令は、C言語のmemchrのような関数で内部的に使用され、バイト検索を非常に効率的に行うことができます。

技術的詳細

このコミットの主要な技術的変更は、strings.IndexByte関数の実装をGo言語から各アーアーキテクチャ（386, AMD64, ARM）のアセンブリ言語に移行した点です。これにより、各CPUの特性を最大限に活かした最適化が可能になります。

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

386アーキテクチャ向けの実装では、SCASB命令が活用されています。

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

• SIレジスタに文字列の開始アドレス、CXレジスタに文字列の長さ、ALレジスタに検索対象のバイトがそれぞれロードされます。
• DIレジスタにSIの値をコピーし、スキャン操作の宛先ポインタとして設定します。
• CLD命令は方向フラグをクリアし、SCASB命令がメモリを前方（アドレスが増加する方向）にスキャンするように設定します。
• REPN; SCASBは、ALレジスタのバイトとDIが指すメモリ上のバイトを比較し、一致が見つかるかCXがゼロになるまで繰り返します。
• JZ 3(PC)は、SCASB命令が一致を見つけた場合（ゼロフラグがセットされる）に、一致が見つかった場合の処理にジャンプします。
• 一致が見つからなかった場合、-1が戻り値として設定されます。
• 一致が見つかった場合、DIは一致したバイトの次のアドレスを指しています。DIから元の開始アドレスSIを引くことで、一致したバイトのオフセット（長さ）が得られます。そこから1を引くことで、0ベースのインデックスが計算され、それが戻り値として設定されます。

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

AMD64アーキテクチャでは、runtime·indexbytebodyというヘルパー関数が導入され、より複雑な最適化が行われています。これは、SSE命令（Streaming SIMD Extensions）を活用して、一度に複数のバイトを比較するSIMD（Single Instruction, Multiple Data）処理を試みるものです。

TEXT strings·IndexByte(SB),7,$0
	MOVQ s+0(FP), SI
	MOVQ s_len+8(FP), BX
	MOVB c+16(FP), AL
	CALL runtime·indexbytebody(SB) // ヘルパー関数を呼び出し
	MOVQ AX, ret+24(FP)
	RET

// input:
//   SI: data
//   BX: data len
//   AL: byte sought
// output:
//   AX
TEXT runtime·indexbytebody(SB),7,$0
	MOVQ SI, DI

	CMPQ BX, $16 // 長さが16バイト未満かチェック
	JB indexbyte_small // 16バイト未満なら小さい文字列用の処理へ

	// ... (SSE命令を使った高速パスのコードが続く) ...
	// PANDN, PCMPEQB, PMOVMSKB, TESTQ, JZなどの命令で、16バイト単位で検索

indexbyte_small: // 長さが16バイト未満の場合の処理
	MOVQ BX, CX
	REPN; SCASB // SCASB命令でバイトスキャン
	JZ success
	MOVQ $-1, AX // 見つからなければ-1
	RET

success:
	SUBQ SI, DI
	SUBL $1, DI
	MOVQ DI, AX // 見つかったインデックスをAXに設定
	RET

• strings.IndexByteは、引数をレジスタにロードした後、runtime·indexbytebodyを呼び出します。
• runtime·indexbytebodyでは、まず文字列の長さが16バイト未満かどうかをチェックします。
  • 16バイト未満の場合、indexbyte_smallラベルにジャンプし、386版と同様にREPN; SCASB命令を使用してバイトスキャンを行います。
  • 16バイト以上の場合、SSE命令（PANDN, PCMPEQB, PMOVMSKB, TESTQなど）を使用して、16バイト単位で並列にバイトを比較する高速パスが実行されます。これにより、一度に多くのバイトを処理できるため、パフォーマンスが大幅に向上します。
• 最終的に、見つかったインデックスがAXレジスタに設定され、呼び出し元に返されます。

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

ARMアーキテクチャ向けの実装は、x86/AMD64のような専用の文字列スキャン命令がないため、ループとバイトごとの比較をアセンブリで直接記述しています。

TEXT strings·IndexByte(SB),7,$0
	MOVW	s+0(FP), R0    // 文字列の開始アドレスをR0レジスタにロード
	MOVW	s_len+4(FP), R1 // 文字列の長さをR1レジスタにロード
	MOVBU	c+8(FP), R2	// 検索対象のバイトをR2レジスタにロード
	MOVW	R0, R4		// R0 (開始アドレス) をR4に保存
	ADD	R0, R1		// R0にR1を足して、文字列の終了アドレスをR0に設定

_sib_loop: // ループ開始
	CMP	R0, R1         // 現在のアドレスR0が終了アドレスR1に達したか比較
	B.EQ	_sib_notfound  // 達していたら見つからなかった処理へジャンプ
	MOVBU.P	1(R0), R3      // R0が指すメモリから1バイト読み込み、R0を1インクリメント。読み込んだバイトをR3に格納
	CMP	R2, R3         // 検索対象バイトR2と読み込んだバイトR3を比較
	B.NE	_sib_loop      // 一致しなければループを継続

	SUB	$1, R0		// R0は一致したバイトの次のアドレスを指しているので、1を引く
	SUB	R4, R0		// R0から元の開始アドレスR4を引く
	MOVW	R0, ret+12(FP) // 計算されたインデックスを戻り値に設定
	RET

_sib_notfound: // 見つからなかった場合の処理
	MOVW	$-1, R0
	MOVW	R0, ret+12(FP)
	RET

• R0に文字列の開始アドレス、R1に文字列の長さ、R2に検索対象のバイトがロードされます。
• R4に開始アドレスを保存し、R0に長さを加算して文字列の終了アドレスを計算します。
• _sib_loop内で、現在のアドレスが終了アドレスに達したかチェックし、達していなければMOVBU.P命令で1バイト読み込み、R0をインクリメントします。
• 読み込んだバイトと検索対象バイトを比較し、一致しなければループを続行します。
• 一致が見つかった場合、R0から1を引き、さらに元の開始アドレスR4を引くことで、インデックスを計算します。
• 見つからなかった場合、-1が戻り値として設定されます。

strings.goからの削除

元のsrc/pkg/strings/strings.goから、Go言語で書かれていたIndexByte関数の実装が削除されました。これは、アセンブリ実装が優先されるため、Go言語での実装は不要になったためです。

strings.sとstrings_decl.goの追加

• src/pkg/strings/strings.sは、Goツールチェーンがアセンブリファイルを認識するために追加された空のファイルです。Goのビルドシステムは、stringsパッケージ内にアセンブリファイルが存在することを示すために、このファイルが必要とします。
• src/pkg/strings/strings_decl.goは、strings.IndexByte関数がGo言語ではなく、外部のアセンブリファイル（../runtime/asm_$GOARCH.s）で実装されていることをGoコンパイラに宣言するためのファイルです。これにより、Goのコードからstrings.IndexByteを呼び出す際に、コンパイラは適切なアセンブリ実装にリンクできるようになります。

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

このコミットにおけるコアとなるコードの変更箇所は以下のファイルに集中しています。

1. src/pkg/runtime/asm_386.s: 32ビットx86アーキテクチャ向けのアセンブリ実装が追加されました。
2. src/pkg/runtime/asm_amd64.s: 64ビットAMD64アーキテクチャ向けのアセンブリ実装が追加・修正されました。特にruntime·indexbytebodyというヘルパー関数が導入されています。
3. src/pkg/runtime/asm_arm.s: ARMアーキテクチャ向けのアセンブリ実装が追加されました。
4. src/pkg/strings/strings.go: Go言語で書かれていたIndexByte関数の実装が削除されました。
5. src/pkg/strings/strings.s: 新規作成された空のアセンブリファイル。Goツールチェーンがアセンブリ実装を認識するために必要です。
6. src/pkg/strings/strings_decl.go: 新規作成されたファイルで、strings.IndexByteがアセンブリで実装されていることをGoコンパイラに宣言します。

コアとなるコードの解説

src/pkg/strings/strings.go からの IndexByte 削除

--- a/src/pkg/strings/strings.go
+++ b/src/pkg/strings/strings.go
@@ -160,16 +160,6 @@ func Index(s, sep string) int {
 	return -1
 }
 
-// IndexByte returns the index of the first instance of c in s, or -1 if c is not present in s.
-func IndexByte(s string, c byte) int {
-	for i := 0; i < len(s); i++ {
-		if s[i] == c {
-			return i
-		}
-	}
-	return -1
-}
-
 // LastIndex returns the index of the last instance of sep in s, or -1 if sep is not present in s.
 func LastIndex(s, sep string) int {
 	n := len(sep)

この変更は、IndexByte関数のGo言語による実装が完全に削除されたことを示しています。これは、この関数の実装がGoランタイムのアセンブリコードに完全に移行されたためです。これにより、Goコンパイラはstrings.IndexByteの呼び出しを、各アーキテクチャに特化した最適化されたアセンブリルーチンに直接リンクするようになります。

src/pkg/strings/strings.s の新規追加

--- /dev/null
+++ b/src/pkg/strings/strings.s
@@ -0,0 +1,5 @@
+// Copyright 2013 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.
+
+// This file is here just to make the go tool happy.

このファイルは、実質的に何もコードを含んでいません。コメントにあるように、「goツールを満足させるためだけにここにある」と書かれています。Goのビルドシステムは、パッケージ内にアセンブリファイルが存在するかどうかを判断する際に、.s拡張子を持つファイルを探索します。この空のファイルが存在することで、stringsパッケージがアセンブリコードを含んでいると認識され、Goランタイムのアセンブリ実装が正しくリンクされるようになります。

src/pkg/strings/strings_decl.go の新規追加

--- /dev/null
+++ b/src/pkg/strings/strings_decl.go
@@ -0,0 +1,8 @@
+// Copyright 2013 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 strings
+
+// IndexByte returns the index of the first instance of c in s, or -1 if c is not present in s.
+func IndexByte(s string, c byte) int // ../runtime/asm_$GOARCH.s

このファイルは、Go言語のソースコード内でstrings.IndexByte関数がどのように宣言されているかを示しています。注目すべきは、関数のシグネチャの後に// ../runtime/asm_$GOARCH.sというコメントが付いている点です。これは、この関数がGo言語で実装されているのではなく、../runtime/asm_$GOARCH.sというパスにあるアセンブリファイルで実装されていることをGoコンパイラに伝えるための特殊な構文です。$GOARCHは、ビルドターゲットのアーキテクチャ（例: amd64, 386, arm）に置き換えられます。これにより、GoのコードからIndexByteを呼び出すと、コンパイラは対応するアセンブリ実装にディスパッチするようになります。

src/pkg/runtime/asm_386.s, src/pkg/runtime/asm_amd64.s, src/pkg/runtime/asm_arm.s へのアセンブリ実装追加

これらのファイルには、それぞれのアーキテクチャに特化したstrings·IndexByte（またはAMD64の場合はruntime·indexbytebody）のアセンブリコードが追加されています。前述の「技術的詳細」セクションで詳しく解説したように、これらのアセンブリ実装は、各CPUの命令セット（特にx86/AMD64のSCASBやSSE命令）を直接利用することで、Go言語で書かれたループよりもはるかに高速なバイト検索を実現しています。

これらの変更により、Go言語のstrings.IndexByte関数は、ユーザーからはGoの関数として透過的に利用できる一方で、内部的には各プラットフォームで最適化されたアセンブリコードが実行されるようになり、Goプログラム全体の文字列処理性能が向上しました。

関連リンク

• Go Issue #3751: strings: IndexByte is slow
• Go CL 12483043: strings: use runtime assembly for IndexByte (これはコミットメッセージに記載されているGoのコードレビューシステムへのリンクです)

参考にした情報源リンク

• Go Assembly Language (Go公式ドキュメントのアセンブリ言語に関するページ)
• Intel 64 and IA-32 Architectures Software Developer's Manuals (SCASB命令などの詳細な情報源)
• ARM Architecture Reference Manuals (ARMアセンブリ命令の詳細な情報源)
• Go strings.IndexByte optimization (Goのstringsパッケージの現在のソースコード。このコミット後の状態を確認できます)
• Go runtime assembly files (Goランタイムのアセンブリファイル群)
• Go issue 3751 discussion (Issueの議論内容)
• Go strings package documentation (stringsパッケージの公式ドキュメント)
• SIMD (Single Instruction, Multiple Data) - Wikipedia
• SSE (Streaming SIMD Extensions) - Wikipedia