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

このコミットは、Go言語の標準ライブラリ bytes パッケージにおけるバイトスライスと文字列の比較関数 Compare のパフォーマンスを大幅に改善するものです。特に、x86およびx86-64アーキテクチャにおいてSSE (Streaming SIMD Extensions) 命令を活用することで、16バイト単位での高速な比較を可能にしています。ARMアーキテクチャ向けには、C言語で記述された非アセンブリ実装が提供されています。

コミット

commit b3946dc119cb89fe9f3cd55daa8d8c7a708274a8
Author: Keith Randall <khr@golang.org>
Date:   Tue May 14 16:05:51 2013 -0700

    runtime/bytes: fast Compare for byte arrays and strings.
    
    Uses SSE instructions to process 16 bytes at a time.
    
    fixes #5354
    
    R=bradfitz, google
    CC=golang-dev
    https://golang.org/cl/8853048

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

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

元コミット内容

runtime/bytes: fast Compare for byte arrays and strings. Uses SSE instructions to process 16 bytes at a time. fixes #5354

このコミットは、バイト配列と文字列の高速な比較のためにSSE命令を使用し、一度に16バイトを処理することでパフォーマンスを向上させることを目的としています。また、GoのIssue #5354を修正するものです。

変更の背景

Go言語の標準ライブラリにおいて、バイトスライスや文字列の比較は頻繁に行われる操作であり、そのパフォーマンスは多くのアプリケーションのボトルネックとなり得ます。特に、大量のデータを扱う場合や、ネットワークプロトコル、ファイルシステム操作など、バイト単位での厳密な比較が求められる場面では、効率的な比較アルゴリズムが不可欠です。

このコミットが行われた2013年当時、Go言語はまだ比較的新しい言語であり、パフォーマンスの最適化は継続的な課題でした。既存の bytes.Compare および runtime.cmpstring 関数は、バイト単位でループして比較を行う一般的な実装であり、CPUのSIMD (Single Instruction, Multiple Data) 命令セットを活用していませんでした。SIMD命令は、単一の命令で複数のデータ要素に対して同じ操作を並列に実行できるため、データ並列性の高い処理（例えばバイト配列の比較）において絶大なパフォーマンス向上をもたらします。

GoのIssue #5354は、まさにこの bytes.Compare のパフォーマンスに関するもので、より高速な実装が求められていました。このコミットは、その要求に応える形で、x86/x86-64アーキテクチャで利用可能なSSE命令セットを利用して、比較処理をアセンブリ言語で最適化することを目的としています。これにより、Goプログラム全体の実行速度向上に寄与することが期待されました。

前提知識の解説

1. バイトスライスと文字列の比較

Go言語において、バイトスライス ([]byte) と文字列 (string) は、それぞれバイトのシーケンスを表します。これらの比較は、辞書順（lexicographical order）で行われます。これは、最初の異なるバイトが見つかるまで両方のシーケンスを先頭から比較し、そのバイトの値に基づいて大小を決定するというものです。もし一方のシーケンスがもう一方のプレフィックスである場合（例: "abc" と "abcd"）、短い方が小さいと判断されます。両方のシーケンスが同じであれば、0を返します。

2. SIMD (Single Instruction, Multiple Data)

SIMDは、単一の命令で複数のデータ要素に対して同じ操作を並列に実行するプロセッサの機能です。これにより、データ並列性の高い処理（画像処理、音声処理、科学技術計算、そしてバイト配列の比較など）において、従来の逐次処理に比べて大幅なパフォーマンス向上を実現できます。

3. SSE (Streaming SIMD Extensions)

SSEは、Intelが開発したSIMD命令セットの総称です。Pentium IIIプロセッサで導入され、その後SSE2, SSE3, SSSE3, SSE4などと拡張されてきました。SSE命令は、128ビットのXMMレジスタを使用し、例えば16個の8ビット整数、8個の16ビット整数、4個の32ビット整数、2個の64ビット整数などを一度に処理できます。バイト配列の比較においては、PCMPEQB (Packed Compare Equal Bytes) のような命令が特に有用で、128ビットレジスタ内の16バイトを一度に比較し、結果をマスクとして生成します。

4. Goのアセンブリ言語と //go:noescape

Go言語は、特定のパフォーマンスクリティカルな部分でアセンブリ言語を使用することをサポートしています。Goのアセンブリは、Plan 9アセンブリと呼ばれる独特の構文を持っています。Goのランタイムや標準ライブラリの低レベルな最適化には、このアセンブリが用いられることがあります。

//go:noescape は、Goコンパイラに対するディレクティブ（指示）です。このディレクティブが付与された関数は、ヒープにメモリを割り当てないことをコンパイラに保証します。これにより、コンパイラはエスケープ解析（変数がヒープに割り当てられるべきかスタックに割り当てられるべきかを判断するプロセス）をスキップし、より効率的なコードを生成できます。パフォーマンスが重要な低レベル関数でよく使用されます。

5. Goのクロスコンパイルとアーキテクチャ固有の実装

Goは強力なクロスコンパイル機能を持ち、異なるCPUアーキテクチャやOS向けにバイナリを生成できます。このコミットのように、特定のアーキテクチャ（例: x86/x86-64）で利用可能な命令セット（SSE）を活用する場合、そのアーキテクチャ向けに最適化されたアセンブリコードを提供し、他のアーキテクチャ（例: ARM）向けには汎用的なC言語（Goのランタイムでは .goc ファイルでC言語が使用されることがあります）やGo言語での実装を提供することが一般的です。これにより、各プラットフォームで最高のパフォーマンスを引き出しつつ、コードの移植性を維持します。

技術的詳細

このコミットの核心は、bytes.Compare および runtime.cmpstring 関数の実装を、x86/x86-64アーキテクチャではSSE命令を用いたアセンブリ言語に、ARMアーキテクチャではC言語（noasm_arm.goc）に切り替えることで、比較処理の効率を劇的に向上させた点にあります。

x86/x86-64アーキテクチャ向け最適化 (asm_386.s, asm_amd64.s)

1. runtime·cmpbody 関数の導入:

   • bytes.Compare と runtime.cmpstring の両方から呼び出される共通のアセンブリ関数 runtime·cmpbody が導入されました。これにより、比較ロジックの重複を避け、コードの再利用性を高めています。
   • この関数は、比較対象のバイトスライス/文字列のポインタと長さを引数として受け取ります。

2. SSE命令の活用:

   • runtime·cmpbody 内で、まずCPUがSSE2命令セットをサポートしているか runtime·cpuid_edx をチェックします。
   • サポートされている場合、cmp_largeloop というラベルのループに入ります。このループでは、MOVOU 命令を使って16バイト（128ビット）のデータをXMMレジスタにロードし、PCMPEQB 命令で両方のレジスタの内容をバイト単位で比較します。
   • PCMPEQB は、対応するバイトが等しい場合は結果レジスタの対応するバイトをすべて1に、異なる場合はすべて0にします。
   • PMOVMSKB 命令は、この結果レジスタの最上位ビットを抽出し、16ビットのマスクを生成します。このマスクは、どのバイトが一致したか（または一致しなかったか）を示します。
   • XORL $0xffff, AX (386) または XORQ $0xffff, AX (amd64) でマスクを反転させ、一致しないバイトを示すマスクに変換します。
   • JNE cmp_diff16 命令で、もし一つでも異なるバイトがあれば cmp_diff16 にジャンプし、最初の異なるバイトを特定します。
   • これにより、一度に16バイトを効率的に比較し、異なるバイトが見つかるまで高速に処理を進めることができます。

3. 異なるバイトの特定と結果の生成:

   • cmp_diff16 では、BSFL (Bit Scan Forward Low) または BSFQ (Bit Scan Forward Quad) 命令を使用して、生成されたマスクから最初の異なるバイトのインデックスを特定します。
   • その後、そのインデックスにあるバイトの値を比較し、SETHI (Set if Higher) 命令などを用いて、結果（-1, 0, 1）を生成します。

4. 小規模な比較の最適化:

   • 比較対象の長さが短い場合（例えば4バイト以下や8バイト以下）、SSE命令のオーバーヘッドを避けるために、よりシンプルな比較ロジック（例えば32ビットや64ビット単位での比較）にフォールバックします。
   • BSWAPL/BSWAPQ (Byte Swap) や XORL/XORQ (XOR) 命令を組み合わせて、バイトの順序を反転させたり、ビット単位の差分を検出したりすることで、効率的な比較を実現しています。

ARMアーキテクチャ向け実装 (noasm_arm.goc)

ARMアーキテクチャにはSSE命令がないため、アセンブリではなくC言語で実装されています。

• runtime.cmpstring と bytes.Compare の両方が、noasm_arm.goc 内でC言語として再実装されています。
• これらの実装は、基本的なバイト単位のループ比較ロジックに従っています。これは、x86/x64のアセンブリ実装のようなSIMD最適化は含まれていませんが、ARM環境での動作を保証し、GoのランタイムがC言語で記述された部分と連携するためのメカニズムを示しています。
• #pragma textflag 7 は、Goのコンパイラに対する指示で、この関数がGoのランタイムの一部として扱われることを示唆しています。

src/cmd/dist/goc2c.c の変更

このファイルはGoのツールチェーンの一部であり、GoのソースコードからCコードを生成する際に使用されるようです。変更内容は、関数ヘッダーの処理において、パッケージ名が既に含まれている場合のハンドリングを改善しています。これは、bytes.Compare の実装がランタイムに移動し、パッケージの指定方法が変わったことに関連する可能性があります。

bytes パッケージの変更

• src/pkg/bytes/bytes.go から既存の Compare 関数が削除されました。
• src/pkg/bytes/bytes_decl.go に、新しい Compare 関数の宣言が追加されました。この宣言には //go:noescape ディレクティブが付与され、実装がアセンブリ（../runtime/asm_{386,amd64}.s）またはARM向けのCコード（../runtime/noasm_arm.goc）で行われることがコメントで示されています。これは、Goのコンパイラがこの関数呼び出しを最適化し、ヒープ割り当てを避けるための重要な指示です。

テストの変更

• src/pkg/bytes/bytes_test.go から Compare のテストが削除され、TestEqual のテスト名が変更されました。
• src/pkg/bytes/compare_test.go という新しいテストファイルが追加されました。このファイルには、Compare 関数の網羅的なテストケースと、様々なシナリオ（等しいバイトスライス、異なる長さ、nil引数、大規模なデータなど）におけるベンチマークテストが含まれています。これにより、新しいアセンブリ実装の正確性とパフォーマンスが検証されます。

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

このコミットのコアとなる変更は、主に以下のファイルに集中しています。

1. src/pkg/bytes/bytes.go:

   • 既存の Compare 関数のGo言語実装が削除されました。

2. src/pkg/bytes/bytes_decl.go:

   • func Compare(a, b []byte) int の宣言が追加され、その実装がランタイムのアセンブリまたはCコードに委ねられることが示されました。//go:noescape ディレクティブが追加されています。

3. src/pkg/runtime/asm_386.s:

   • TEXT runtime·cmpstring(SB) と TEXT bytes·Compare(SB) のエントリポイントが追加され、これらが共通の runtime·cmpbody(SB) を呼び出すようになりました。
   • TEXT runtime·cmpbody(SB) が新しく追加され、386アーキテクチャ向けにSSE2命令（MOVOU, PCMPEQB, PMOVMSKB など）を用いたバイトスライス/文字列比較の高速なアセンブリ実装が記述されました。短い長さの比較や、異なるバイトが見つかった場合の処理も含まれます。

4. src/pkg/runtime/asm_amd64.s:

   • TEXT runtime·cmpstring(SB) と TEXT bytes·Compare(SB) のエントリポイントが追加され、これらが共通の runtime·cmpbody(SB) を呼び出すようになりました。
   • TEXT runtime·cmpbody(SB) が新しく追加され、amd64アーキテクチャ向けにSSE2命令を用いたバイトスライス/文字列比較の高速なアセンブリ実装が記述されました。基本的なロジックは386版と似ていますが、64ビットレジスタや命令が使用されています。

5. src/pkg/runtime/noasm_arm.goc:

   • ARMアーキテクチャ向けに、func cmpstring(s1 String, s2 String) (v int) と func bytes·Compare(s1 Slice, s2 Slice) (v int) のC言語実装が追加されました。これらはSIMD命令を使用せず、バイト単位でループして比較を行います。

6. src/pkg/runtime/string.goc:

   • 既存の cmpstring 関数のC言語実装が削除されました。

7. src/pkg/bytes/compare_test.go:

   • bytes.Compare 関数の機能とパフォーマンスを検証するための、新しいテストケースとベンチマークが追加されました。

コアとなるコードの解説

src/pkg/runtime/asm_amd64.s (amd64版 runtime·cmpbody の抜粋と解説)

TEXT runtime·cmpbody(SB),7,$0
	MOVQ	s1+0(FP), SI // s1のポインタをSIにロード
	MOVQ	s1+8(FP), BX // s1の長さをBXにロード (alen)
	MOVQ	s2+16(FP), DI // s2のポインタをDIにロード
	MOVQ	s2+24(FP), DX // s2の長さをDXにロード (blen)

	CMPQ	SI, DI
	JEQ	cmp_allsame // ポインタが同じなら、同じスライスなので0を返す

	CMPQ	BX, DX
	MOVQ	DX, BP
	CMOVQLT	BX, BP // BP = min(alen, blen) = 比較するバイト数

	CMPQ	BP, $8
	JB	cmp_small // 8バイト未満ならcmp_smallへ（SSEを使わない）

cmp_loop:
	CMPQ	BP, $16
	JBE	cmp_0through16 // 残り16バイト以下ならcmp_0through16へ

	MOVOU	(SI), X0 // SIから16バイトをX0レジスタにロード
	MOVOU	(DI), X1 // DIから16バイトをX1レジスタにロード
	PCMPEQB X0, X1 // X0とX1の各バイトを比較し、結果をX1に格納 (等しければFF, 異なれば00)
	PMOVMSKB X1, AX // X1の各バイトの最上位ビットを抽出し、AXに16ビットマスクとして格納
	XORQ	$0xffff, AX // マスクを反転 (等しければ00, 異なればFF -> 等しければFF, 異なれば00)
	JNE	cmp_diff16 // AXが0でなければ（異なるバイトがあれば）cmp_diff16へ

	ADDQ	$16, SI // SIを16バイト進める
	ADDQ	$16, DI // DIを16バイト進める
	SUBQ	$16, BP // 残りバイト数を16減らす
	JMP	cmp_loop // ループを継続

cmp_diff16:
	BSFQ	AX, BX // AXの最下位ビットから最初のセットされたビットのインデックスをBXに格納 (最初の異なるバイトのオフセット)
	XORQ	AX, AX // AXをクリア
	MOVB	(SI)(BX*1), CX // SI+BX（最初の異なるバイト）の値をCXにロード
	CMPB	CX, (DI)(BX*1) // CXとDI+BXの値を比較
	SETHI	AX // CX > (DI+BX) ならAXを1にセット
	LEAQ	-1(AX*2), AX // AXを1/0から+1/-1に変換 (1 -> 1, 0 -> -1)
	RET // 結果を返す

このアセンブリコードは、Goの bytes.Compare 関数がどのように高速化されているかを示しています。

1. 引数の受け渡し: Goの呼び出し規約に従い、スタックフレームからバイトスライス/文字列のポインタと長さをレジスタ（SI, DI, BX, DX）にロードします。
2. 同一ポインタのチェック: 比較対象のポインタが同じであれば、同じスライスなので即座に0を返します。これは高速パスです。
3. 最小長の計算: min(alen, blen) を計算し、BP レジスタに格納します。これが実際に比較するバイト数になります。
4. SSE最適化ループ (cmp_loop):
   • 比較するバイト数が16バイト以上の場合、このループに入ります。
   • MOVOU 命令で、両方のスライスから16バイトずつをXMMレジスタ X0 と X1 にロードします。
   • PCMPEQB 命令は、X0 と X1 の対応するバイトを並列に比較します。結果は X1 に格納され、一致するバイトは 0xFF、一致しないバイトは 0x00 となります。
   • PMOVMSKB 命令は、X1 の各バイトの最上位ビット（0xFF なら1、0x00 なら0）を抽出し、16ビットのマスクを AX レジスタに生成します。
   • XORQ $0xffff, AX は、このマスクを反転させます。これにより、AX のビットが1であれば対応するバイトが異なることを示します。
   • JNE cmp_diff16 は、AX がゼロでなければ（つまり、少なくとも1つの異なるバイトが見つかれば）、cmp_diff16 ラベルにジャンプします。
   • 異なるバイトが見つからなければ、ポインタと残りバイト数を更新し、次の16バイトブロックの比較のためにループを継続します。
5. 異なるバイトの特定 (cmp_diff16):
   • BSFQ AX, BX は、AX の中で最も下位のセットされたビット（1になっているビット）のインデックスを BX に格納します。これは、16バイトブロック内で最初に異なるバイトが見つかったオフセットを示します。
   • そのオフセットを使って、両方のスライスから実際に異なるバイトをロードし、CMPB 命令で比較します。
   • SETHI AX は、比較結果に基づいて AX を1に設定します（CX > (DI+BX) の場合）。
   • LEAQ -1(AX*2), AX は、AX の値を 1 または -1 に変換します。これは、Goの Compare 関数が期待する戻り値（a > b なら1、a < b なら-1）です。
6. 小規模な比較 (cmp_small, cmp_0through16):
   • 比較するバイト数が少ない場合（8バイト未満や16バイト未満）、SSE命令のオーバーヘッドを避けるために、よりシンプルな64ビットまたは32ビット単位での比較にフォールバックします。ここでも BSWAPQ や XORQ などの命令を駆使して効率的な比較を行います。
7. 完全に一致する場合 (cmp_allsame):
   • すべてのバイトが一致した場合、最終的に長さの比較を行います。長い方が大きいと判断され、短い方が小さいと判断されます。長さも同じであれば0を返します。

このアセンブリ実装により、特に長いバイトスライスや文字列の比較において、従来のバイト単位のループに比べて大幅なパフォーマンス向上が実現されます。

関連リンク

• Go Issue #5354: https://github.com/golang/go/issues/5354
• Go CL 8853048: https://golang.org/cl/8853048 (Gerrit Code Review)

参考にした情報源リンク

• Go Assembly Language (Plan 9 Assembly): https://go.dev/doc/asm
• Intel® 64 and IA-32 Architectures Software Developer’s Manuals (SSE instructions): https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
• SIMD (Single Instruction, Multiple Data) - Wikipedia: https://en.wikipedia.org/wiki/SIMD
• Streaming SIMD Extensions (SSE) - Wikipedia: https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions
• Go: //go:noescape directive: https://pkg.go.dev/cmd/go#hdr-Build_constraints (indirectly, as it's a build constraint)
• Go bytes package documentation: https://pkg.go.dev/bytes
• Go runtime package documentation: https://pkg.go.dev/runtime
• Go testing package documentation: https://pkg.go.dev/testing
• Go cmd/dist documentation (for goc2c.c context): https://go.dev/src/cmd/dist/README (This is a general overview, specific details on goc2c.c might require source code diving.)