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

このコミットは、Goランタイムにおける文字列およびバイトスライスの比較処理（Equal関数）を高速化するための変更を導入しています。特にamd64および386アーキテクチャにおいて、アセンブリ言語による最適化されたmemeq関数を導入することで、大幅なパフォーマンス向上を実現しています。

コミット

commit 3d5daa23198f4b7ee71dd7647d5d061e1c883fce
Author: Keith Randall <khr@golang.org>
Date:   Tue Apr 2 16:26:15 2013 -0700

    runtime: Implement faster equals for strings and bytes.
    
    (amd64)
    benchmark           old ns/op    new ns/op    delta
    BenchmarkEqual0            16            6  -63.15%
    BenchmarkEqual9            22            7  -65.37%
    BenchmarkEqual32           36            9  -74.91%
    BenchmarkEqual4K         2187          120  -94.51%
    
    benchmark            old MB/s     new MB/s  speedup
    BenchmarkEqual9        392.22      1134.38    2.89x
    BenchmarkEqual32       866.72      3457.39    3.99x
    BenchmarkEqual4K      1872.73     33998.87   18.15x
    
    (386)
    benchmark           old ns/op    new ns/op    delta
    BenchmarkEqual0            16            5  -63.85%
    BenchmarkEqual9            22            7  -67.84%
    BenchmarkEqual32           34           12  -64.94%
    BenchmarkEqual4K         2196          113  -94.85%
    
    benchmark            old MB/s     new MB/s  speedup
    BenchmarkEqual9        405.81      1260.18    3.11x
    BenchmarkEqual32       919.55      2631.21    2.86x
    BenchmarkEqual4K      1864.85     36072.54   19.34x
    
    Update #3751
    
    R=bradfitz, r, khr, dave, remyoudompheng, fullung, minux.ma, ality
    CC=golang-dev
    https://golang.org/cl/8056043

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

https://github.com/golang/go/commit/3d5daa23198f4b7ee71dd7647d5d061e1c883fce

元コミット内容

このコミットは、Goランタイムにおける文字列とバイトスライスの比較処理を高速化します。特にamd64と386アーキテクチャにおいて、ベンチマーク結果は大幅な性能向上を示しています。例えば、4KBの比較では最大で約94%の実行時間短縮、スループットでは約18倍の向上が見られます。これは、memeqという新しいアセンブリ関数を導入し、既存の比較ロジックを置き換えることで実現されています。

変更の背景

Go言語において、文字列やバイトスライスの比較は非常に頻繁に行われる操作です。特に、ハッシュマップのキーとして文字列が使われる場合や、大量のデータを処理するアプリケーションでは、比較処理の性能が全体のパフォーマンスに大きく影響します。従来の比較処理はバイト単位での逐次比較が主であり、これは短い文字列やバイトスライスでは問題ありませんが、長くなるにつれてオーバーヘッドが顕著になります。

このコミットの背景には、Issue 3751（"runtime: faster string/byte equality checks"）があります。このIssueでは、Goの文字列/バイトスライス比較がC言語のmemcmpのような最適化された関数に比べて遅いことが指摘されており、特に大きなデータサイズでの性能改善が求められていました。このコミットは、その性能ギャップを埋め、Goプログラム全体の実行速度を向上させることを目的としています。

前提知識の解説

1. Goにおける文字列とバイトスライス

Go言語において、string型は不変なバイトのシーケンスであり、[]byte型は可変なバイトのシーケンスです。どちらも内部的にはポインタと長さ（len）を持つ構造体として表現されます。比較操作は、まず長さが等しいかを確認し、その後、内容がバイト単位で一致するかを検証します。

2. memeq関数

memeqは"memory equal"の略で、2つのメモリ領域の内容が等しいかどうかを効率的に比較するための関数です。C言語の標準ライブラリにはmemcmpという同様の機能を持つ関数がありますが、このコミットで導入されるruntime·memeqは、Goランタイム内部で使用されるアセンブリ最適化されたバージョンです。

3. SIMD命令（SSE2）

SIMD (Single Instruction, Multiple Data) 命令は、単一の命令で複数のデータ要素に対して同じ操作を同時に実行できるCPUの拡張命令セットです。SSE2 (Streaming SIMD Extensions 2) はIntel Pentium 4で導入されたSIMD命令セットで、128ビットのXMMレジスタを使用して、一度に16バイト（8ビット整数）や8ワード（16ビット整数）、4ダブルワード（32ビット整数）、2クワッドワード（64ビット整数）などのデータを処理できます。

このコミットでは、PCMPEQB (Packed Compare Equal Bytes) や PMOVMSKB (Packed Move Mask Bytes) といったSSE2命令が活用されています。

• PCMPEQB: 2つのXMMレジスタ内の対応するバイトを比較し、一致すれば結果レジスタの対応するバイトをすべて1に、一致しなければすべて0に設定します。
• PMOVMSKB: XMMレジスタの各バイトの最上位ビット（マスクビット）を抽出し、それを汎用レジスタに格納します。これにより、16バイトの比較結果を16ビットのマスクとして効率的に取得できます。

これらの命令を組み合わせることで、一度に大量のバイトを並列に比較し、その結果を迅速に集約することが可能になります。

4. メモリのアライメントとページ境界

CPUがメモリからデータを読み書きする際、特定のバイト境界（アライメント）にデータが配置されていると、より効率的にアクセスできます。また、オペレーティングシステムはメモリを「ページ」という固定サイズのブロックで管理しています。メモリ比較関数がページ境界をまたいで不正なメモリ領域にアクセスしようとすると、ページフォルト（セグメンテーション違反）が発生し、プログラムがクラッシュする可能性があります。

TestEqualNearPageBoundaryテストは、このページ境界付近でのmemeqの挙動を検証するために追加されました。syscall.Mprotectは、特定のメモリ領域の保護属性（読み取り、書き込み、実行）を変更するシステムコールです。このテストでは、Mprotectを使ってページ境界の前後をアクセス不可に設定し、memeqが安全に動作することを確認しています。

技術的詳細

このコミットの核心は、runtime·memeqという新しいアセンブリ関数の導入です。この関数は、与えられた2つのメモリ領域が指定された長さだけ等しいかを効率的に比較します。

runtime·memeqの実装戦略

runtime·memeqは、比較するバイト数（count）に応じて異なる最適化戦略を採用しています。

1. 短い比較 (small):

   • amd64では8バイト未満、386では4バイト未満の比較に適用されます。
   • この場合、SSE2のようなSIMD命令はオーバーヘッドが大きいため使用せず、直接レジスタにロードして比較します。
   • 特に、メモリのアライメントやページ境界を考慮し、不正なメモリアクセスを防ぐためのロジックが含まれています。例えば、SIやDIレジスタが指すアドレスがページ境界に近い場合でも、安全にデータをロードできるように調整されます。これは、MOVQ -8(SI)(BX*1), CXのような命令で、オフセットとスケールファクタを使ってバイト数を考慮したロードを行うことで実現されます。

2. 中程度の比較 (bigloop):

   • amd64では8バイト以上64バイト未満、386では4バイト以上64バイト未満の比較に適用されます。
   • この範囲では、64ビット（amd64）または32ビット（386）のレジスタを使い、一度に8バイトまたは4バイトずつ比較します。これは、バイト単位の比較よりも効率的です。

3. 長い比較 (hugeloop):

   • 64バイト以上の比較に適用されます。
   • この部分でSSE2命令が最大限に活用されます。MOVOU命令で一度に16バイトをXMMレジスタにロードし、PCMPEQBで並列比較を行います。
   • 4つのXMMレジスタ（X0-X7）を使い、一度に64バイト（16バイト * 4）を比較します。
   • PAND命令で比較結果を論理積（AND）し、すべてのバイトが一致しているかを確認します。
   • PMOVMSKBでXMMレジスタのマスクビットを抽出し、その結果がすべて1（0xffff）であれば、64バイトすべてが一致していると判断し、次の64バイトの比較に進みます。
   • 一つでも不一致があれば、即座にRET（リターン）してfalseを返します。

既存コードへの統合

runtime·memeqが導入されたことで、Goランタイム内の既存の比較ロジックがこの新しい関数を使用するように変更されました。

• src/pkg/runtime/alg.c内のruntime·memequal（汎用的なメモリ比較）とruntime·strequal（文字列比較）が、手動のバイトループからruntime·memeqの呼び出しに置き換えられました。
• src/pkg/runtime/string.goc内のeqstring関数も同様にruntime·memeqを使用するように変更されました。
• src/pkg/bytes/bytes_decl.goでは、bytes.Equal関数の実装が、各アーキテクチャのアセンブリファイルではなく、runtime·memeqを使用するように変更されたことがコメントで示されています。
• src/pkg/runtime/hashmap.cでは、ハッシュマップのキー比較に使用されるEQFUNCマクロがruntime·mcmpからruntime·memeqに更新されました。

テストの追加

性能向上だけでなく、正確性と堅牢性を保証するために、新しいテストが追加されました。

• src/pkg/bytes/bytes_test.goには、TestEqualとTestNotEqualが追加され、様々な長さと内容のバイトスライスに対してEqual関数が正しく動作するかを検証しています。
• src/pkg/bytes/equal_test.goには、TestEqualNearPageBoundaryが追加されました。これは、memeqがメモリページ境界付近で安全に動作するかを確認するための重要なテストです。syscall.Mprotectを使用して、アクセス不可のメモリページを作成し、memeqがその境界を越えて読み取ろうとしないことを保証します。
• src/pkg/runtime/mapspeed_test.goには、BenchmarkMegEqMapが追加され、大きな文字列をキーとするマップの比較性能を測定しています。
• src/pkg/runtime/string_test.goには、大きな文字列の比較に関するベンチマークが追加されました。

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

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

• src/pkg/bytes/asm_386.s: 既存のbytes·Equalアセンブリ実装が削除され、runtime·memeqを呼び出すように変更されました。
• src/pkg/bytes/asm_amd64.s: 既存のbytes·Equalアセンブリ実装が削除され、runtime·memeqを呼び出すように変更されました。
• src/pkg/runtime/alg.c: runtime·memequalとruntime·strequalが、手動のバイト比較ループからruntime·memeqの呼び出しに置き換えられました。
• src/pkg/runtime/asm_386.s: runtime·memeq関数の386アーキテクチャ向けアセンブリ実装が追加されました。これにはSSE2命令を活用した高速な比較ロジックが含まれます。
• src/pkg/runtime/asm_amd64.s: runtime·memeq関数のamd64アーキテクチャ向けアセンブリ実装が追加されました。これにはSSE2命令を活用した高速な比較ロジックが含まれます。
• src/pkg/runtime/asm_arm.s: runtime·memeq関数のARMアーキテクチャ向けアセンブリ実装が追加されました。
• src/pkg/runtime/hashmap.c: ハッシュマップのキー比較ロジックがruntime·mcmpからruntime·memeqを使用するように変更されました。
• src/pkg/runtime/runtime.h: runtime·memeq関数のプロトタイプ宣言が追加されました。
• src/pkg/runtime/string.goc: eqstring関数が、手動のバイト比較ループからruntime·memeqの呼び出しに置き換えられました。
• src/pkg/bytes/bytes_test.go: TestEqualとTestNotEqualベンチマークが追加されました。
• src/pkg/bytes/equal_test.go: TestEqualNearPageBoundaryテストが新規追加されました。
• src/pkg/runtime/mapspeed_test.go: BenchmarkMegEqMapベンチマークが追加されました。
• src/pkg/runtime/string_test.go: 大きな文字列の比較に関するベンチマークが追加されました。

コアとなるコードの解説

src/pkg/runtime/asm_amd64.s (amd64アーキテクチャのruntime·memeqの抜粋)

TEXT runtime·memeq(SB),7,$0
	MOVQ	a+0(FP), SI
	MOVQ	b+8(FP), DI
	MOVQ	count+16(FP), BX
	JMP	runtime·memeqbody(SB)

// a in SI
// b in DI
// count in BX
TEXT runtime·memeqbody(SB),7,$0
	XORQ	AX, AX

	CMPQ	BX, $8
	JB	small
	
	// 64 bytes at a time using xmm registers
hugeloop:
	CMPQ	BX, $64
	JB	bigloop
	MOVOU	(SI), X0
	MOVOU	(DI), X1
	MOVOU	16(SI), X2
	MOVOU	16(DI), X3
	MOVOU	32(SI), X4
	MOVOU	32(DI), X5
	MOVOU	48(SI), X6
	MOVOU	48(DI), X7
	PCMPEQB	X1, X0
	PCMPEQB	X3, X2
	PCMPEQB	X5, X4
	PCMPEQB	X7, X6
	PAND	X2, X0
	PAND	X6, X4
	PAND	X4, X0
	PMOVMSKB X0, DX
	ADDQ	$64, SI
	ADDQ	$64, DI
	SUBQ	$64, BX
	CMPL	DX, $0xffff
	JEQ	hugeloop
	RET

	// 8 bytes at a time using 64-bit register
bigloop:
	CMPQ	BX, $8
	JBE	leftover
	MOVQ	(SI), CX
	MOVQ	(DI), DX
	ADDQ	$8, SI
	ADDQ	$8, DI
	SUBQ	$8, BX
	CMPQ	CX, DX
	JEQ	bigloop
	RET

	// remaining 0-8 bytes
leftover:
	MOVQ	-8(SI)(BX*1), CX
	MOVQ	-8(DI)(BX*1), DX
	CMPQ	CX, DX
	SETEQ	AX
	RET

small:
	CMPQ	BX, $0
	JEQ	equal

	LEAQ	0(BX*8), CX
	NEGQ	CX

	CMPB	SI, $0xf8
	JA	si_high

	// load at SI won't cross a page boundary.
	MOVQ	(SI), SI
	JMP	si_finish
si_high:
	// address ends in 11111xxx.  Load up to bytes we want, move to correct position.
	MOVQ	-8(SI)(BX*1), SI
	SHRQ	CX, SI
si_finish:

	// same for DI.
	CMPB	DI, $0xf8
	JA	di_high
	MOVQ	(DI), DI
	JMP	di_finish
di_high:
	MOVQ	-8(DI)(BX*1), DI
	SHRQ	CX, DI
di_finish:

	SUBQ	SI, DI
	SHLQ	CX, DI
equal:
	SETEQ	AX
	RET

このアセンブリコードは、runtime·memeq関数のamd64アーキテクチャ向け実装です。

1. 引数の受け渡し:

   • a+0(FP): 最初のメモリ領域のポインタ（a）をSIレジスタにロードします。
   • b+8(FP): 2番目のメモリ領域のポインタ（b）をDIレジスタにロードします。
   • count+16(FP): 比較するバイト数（count）をBXレジスタにロードします。
   • その後、runtime·memeqbodyにジャンプして実際の比較ロジックを実行します。

2. runtime·memeqbody:

   • XORQ AX, AX: 戻り値（AXレジスタ）を0に初期化します。比較結果が等しければ1、そうでなければ0が設定されます。

3. 分岐ロジック:

   • CMPQ BX, $8: 比較するバイト数が8未満の場合、smallラベルにジャンプします。
   • hugeloop: 比較するバイト数が64以上の場合に実行されます。
     • CMPQ BX, $64: 残りのバイト数が64未満の場合、bigloopにジャンプします。
     • MOVOU (SI), X0 など: SIとDIが指すメモリから、一度に16バイトずつXMMレジスタ（X0-X7）に非アライメントロードします。これにより、合計64バイトがロードされます。
     • PCMPEQB X1, X0 など: ロードしたXMMレジスタペア（例: X0とX1）の対応するバイトを比較し、結果をX0に格納します。
     • PAND X2, X0 など: 複数の比較結果を論理積（AND）で結合し、すべてのバイトが一致しているかを確認します。最終的にX0レジスタに結合された比較結果が格納されます。
     • PMOVMSKB X0, DX: X0レジスタの各バイトの最上位ビットを抽出し、DXレジスタに16ビットのマスクとして格納します。
     • ADDQ $64, SI / ADDQ $64, DI: ポインタを64バイト進めます。
     • SUBQ $64, BX: 残りのバイト数を64減らします。
     • CMPL DX, $0xffff: DXレジスタのマスクが0xffff（すべてのビットが1、つまり64バイトすべてが一致）であるかを確認します。
     • JEQ hugeloop: すべて一致していれば、次の64バイトの比較のためにhugeloopに戻ります。
     • RET: 一致しないバイトがあれば、即座にRETしてfalse（AXは0のまま）を返します。
   • bigloop: 比較するバイト数が8以上64未満の場合に実行されます。
     • CMPQ BX, $8: 残りのバイト数が8未満の場合、leftoverにジャンプします。
     • MOVQ (SI), CX / MOVQ (DI), DX: SIとDIが指すメモリから、一度に8バイトずつ64ビットレジスタにロードします。
     • ADDQ $8, SI / ADDQ $8, DI: ポインタを8バイト進めます。
     • SUBQ $8, BX: 残りのバイト数を8減らします。
     • CMPQ CX, DX: ロードした8バイトを比較します。
     • JEQ bigloop: 一致していれば、次の8バイトの比較のためにbigloopに戻ります。
     • RET: 一致しないバイトがあれば、即座にRETしてfalseを返します。
   • leftover: 残りのバイト数が0から7の場合に実行されます。
     • MOVQ -8(SI)(BX*1), CX / MOVQ -8(DI)(BX*1), DX: 残りのバイト数を考慮して、最大8バイトをロードします。BX*1は、BXの値（残りのバイト数）をオフセットとして使用し、SIやDIの末尾から逆算してロードするバイトを調整します。
     • CMPQ CX, DX: ロードしたバイトを比較します。
     • SETEQ AX: 比較結果が等しければAXを1に、そうでなければ0に設定します。
     • RET: 結果を返します。
   • small: 比較するバイト数が0から7の場合に実行されます。
     • CMPQ BX, $0: バイト数が0の場合、equalにジャンプします（常にtrue）。
     • このセクションには、メモリページ境界をまたぐ可能性のあるロードを安全に行うための複雑なロジックが含まれています。これは、SIやDIのアドレスがページ境界の末尾に近い場合に、不正なアクセスを防ぐために、ロードするバイト数を調整したり、部分的にロードしたりする処理です。
     • 最終的にequalラベルにジャンプし、SETEQ AXで結果を設定してRETします。

このアセンブリコードは、Goの文字列およびバイトスライス比較の性能を劇的に向上させるための、低レベルでの綿密な最適化を示しています。特に、データサイズに応じた比較戦略の切り替えと、SIMD命令の活用がその鍵となっています。

関連リンク

• Go Issue 3751: runtime: faster string/byte equality checks: https://github.com/golang/go/issues/3751
• Go CL 8056043: runtime: Implement faster equals for strings and bytes.: https://golang.org/cl/8056043

参考にした情報源リンク

• https://github.com/golang/go/commit/3d5daa23198f4b7ee71dd7647d5d061e1c883fce
• https://github.com/golang/go/issues/3751
• https://golang.org/cl/8056043
• SSE2命令セットに関する一般的な情報源 (例: Intel Intrinsics Guide, Wikipediaなど)
• Go言語のランタイムとアセンブリに関するドキュメント (Goの公式ドキュメントやブログ記事など)
• メモリのアライメントとページングに関する一般的なコンピュータアーキテクチャの知識