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

このコミットは、Go言語のランタイムにおけるaeshash関数の最適化に関するものです。具体的には、ハッシュ計算のパフォーマンスを向上させるために、アセンブリコードレベルでの変更が行われています。特に、ページ境界チェックの予測分岐の改善と、16バイト以上のデータがハッシュされる際の境界チェックの回避に焦点を当てています。

コミット

commit ee66972dce0afc5a0cf86be17d6e79cab418f701
Author: Keith Randall <khr@golang.org>
Date:   Wed May 15 09:40:14 2013 -0700

    runtime: Optimize aeshash a bit.  Use a better predicted branch
    for checking for page boundary.  Also avoid boundary check
    when >=16 bytes are hashed.
    
    benchmark                        old ns/op    new ns/op    delta
    BenchmarkHashStringSpeed                23           22   -0.43%
    BenchmarkHashBytesSpeed                 44           42   -3.61%
    BenchmarkHashStringArraySpeed           71           68   -4.05%
    
    R=iant, khr
    CC=gobot, golang-dev, google
    https://golang.org/cl/9123046

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

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

元コミット内容

Goランタイムのaeshash関数を少し最適化しました。ページ境界チェックのためにより予測しやすい分岐を使用し、また16バイト以上のデータがハッシュされる際には境界チェックを回避するようにしました。

ベンチマーク結果:

BenchmarkHashStringSpeed: 23 ns/op -> 22 ns/op (-0.43%)
BenchmarkHashBytesSpeed: 44 ns/op -> 42 ns/op (-3.61%)
BenchmarkHashStringArraySpeed: 71 ns/op -> 68 ns/op (-4.05%)

変更の背景

この変更の背景には、Go言語のランタイムにおけるハッシュ関数のパフォーマンス改善という明確な目的があります。特に、マップ（map）のようなデータ構造でキーのハッシュ計算が頻繁に行われるため、ハッシュ関数の効率は全体のアプリケーション性能に直結します。

aeshashは、AES命令セット（Advanced Encryption Standard Instruction Set）を利用して高速なハッシュ計算を行うための関数です。AES命令は、CPUが暗号化・復号化処理をハードウェアレベルで高速に実行するための命令であり、これをハッシュ計算に応用することで、ソフトウェアによる計算よりもはるかに高速な処理が可能になります。

このコミットでは、特に以下の2点に注目して最適化が行われています。

ページ境界チェックの最適化: メモリからデータを読み込む際、データがメモリページの境界をまたぐかどうかはパフォーマンスに影響を与える可能性があります。ページ境界をまたぐ読み込みは、CPUのキャッシュミスやTLB（Translation Lookaside Buffer）ミスを引き起こし、性能低下の原因となることがあります。このコミットでは、ページ境界チェックの分岐予測を改善することで、このオーバーヘッドを削減しようとしています。
16バイト以上のハッシュにおける境界チェックの回避: aeshashは通常、16バイト単位でデータを処理します。データサイズが16バイト以上の場合、ループ処理で効率的にハッシュ計算が行われます。このコミットでは、データサイズが16バイト以上であることが分かっている場合に、不要な境界チェックをスキップすることで、さらなる性能向上を図っています。

これらの最適化は、Goプログラムがマップ操作を多用する際に、より高速な実行を可能にすることを目的としています。

前提知識の解説

このコミットを理解するためには、以下の技術的な概念について基本的な知識が必要です。

1. Go言語のランタイム (Runtime)

Go言語のランタイムは、Goプログラムの実行を管理するシステムです。ガベージコレクション、スケジューリング、メモリ管理、そして今回関連するハッシュ関数のような低レベルの操作を担当します。ランタイムのコードは、Go言語自体で書かれている部分と、パフォーマンスが重要な部分（特にシステムコールやアセンブリ言語で書かれた部分）で構成されています。

2. ハッシュ関数 (Hash Function)

ハッシュ関数は、任意の長さの入力データ（キー）を受け取り、固定長の出力データ（ハッシュ値）を生成する関数です。Go言語のマップ（map）では、キーの高速な検索、挿入、削除のためにハッシュ関数が内部的に使用されます。良いハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、衝突（異なる入力が同じハッシュ値を生成すること）を最小限に抑える特性を持ちます。

3. AES命令セット (Advanced Encryption Standard Instruction Set)

AES-NI（AES New Instructions）は、IntelおよびAMDのプロセッサに搭載されている命令セットで、AES暗号化・復号化処理をハードウェアレベルで高速化します。これらの命令は、暗号化だけでなく、高速なハッシュ計算など、他のデータ処理にも応用されることがあります。aeshash関数は、このAES命令を利用してハッシュ計算を高速化しています。

4. アセンブリ言語 (Assembly Language)

アセンブリ言語は、CPUが直接実行できる機械語に非常に近い低レベルのプログラミング言語です。Go言語のランタイムの一部、特にパフォーマンスが非常に重要な部分（例: コンテキストスイッチ、メモリ操作、今回のようなハッシュ関数）は、C言語やアセンブリ言語で書かれています。これにより、ハードウェアの特性を最大限に活用し、最高のパフォーマンスを引き出すことが可能になります。

5. メモリページとページ境界 (Memory Pages and Page Boundaries)

現代のオペレーティングシステムは、メモリを固定サイズの「ページ」に分割して管理します。一般的なページサイズは4KBです。メモリページは、仮想メモリと物理メモリのマッピングの単位となります。「ページ境界」とは、このメモリページの区切りのことです。例えば、アドレスが0x1000、0x2000、0x3000...といったアドレスはページ境界になります。 CPUがメモリからデータを読み込む際、データが単一のページ内に収まっているか、それとも複数のページにまたがっているかによって、処理の効率が変わることがあります。ページ境界をまたぐアクセスは、追加のTLBルックアップやキャッシュラインのフェッチが必要になる場合があり、パフォーマンスに影響を与える可能性があります。

6. 分岐予測 (Branch Prediction)

CPUは、プログラムの実行速度を向上させるために、次に実行される命令を予測します。特に条件分岐（if文やループの終了条件など）では、どちらのパスに進むかを予測し、そのパスの命令を事前にフェッチして実行準備をします。この予測が当たれば高速に処理が進みますが、外れると予測した命令を破棄し、正しいパスの命令を改めてフェッチし直すため、ペナルティ（性能低下）が発生します。このコミットでは、「より予測しやすい分岐」を使用することで、この分岐予測ミスによるペナルティを減らそうとしています。

7. `MOVOU`命令

MOVOU (Move Unaligned Oword) は、x86/x64アーキテクチャのSSE（Streaming SIMD Extensions）命令の一つで、128ビット（16バイト）のデータをメモリとXMMレジスタ間で転送します。この命令は、データが16バイト境界にアラインされているかどうかに関わらず使用できます。アラインされていないデータへのアクセスは、アラインされたアクセスよりも遅くなる可能性がありますが、MOVOUはこれを許容します。このコミットでは、この命令を使ってデータを読み込んでいます。

技術的詳細

このコミットの技術的詳細は、主にsrc/pkg/runtime/asm_386.sとsrc/pkg/runtime/asm_amd64.sという2つのアセンブリファイルにおけるruntime·aeshashbody関数の変更に集約されます。これらのファイルは、それぞれ32ビット（x86）と64ビット（x64）アーキテクチャ向けのアセンブリコードを含んでいます。

変更の核心は以下の2点です。

16バイト未満のデータ処理の分岐ロジック変更: 元のコードでは、aesloopend（16バイト単位のループが終了した後）からpartial（部分的なブロックの処理）へのジャンプの前に、TESTL CX, CX (32bit) または TESTQ CX, CX (64bit) を使って残りのバイト数が0かどうかをチェックし、0の場合はfinalizeにジャンプしていました。新しいコードでは、aesloopの直前にCMPL CX, $16 (32bit) または CMPQ CX, $16 (64bit) を追加し、残りのバイト数が16未満の場合にaessmallという新しいラベルにジャンプするように変更されています。これにより、16バイト未満のデータに対する処理パスが明確に分離され、メインのaesloop内で不要なチェックが減ります。
ページ境界チェックの最適化と境界チェックの回避: 元のコードでは、highpartialへの分岐条件としてTESTL $16, AX (32bit) または TESTQ $16, AX (64bit) を使用していました。これは、アドレスの下位4ビット（16の倍数かどうか）をチェックすることで、ページ境界をまたぐ可能性を判断しようとしていました。新しいコードでは、この部分がCMPB AX, $0xf0 (32bit/64bit共通) に変更されています。これは、アドレスの下位バイトが0xf0（240）より大きいかどうかをチェックしています。この変更の意図は、より「予測しやすい分岐」を提供することにあります。通常、メモリアクセスはアラインされていることが多く、ページ境界をまたぐケースは比較的少ないため、この新しい比較がCPUの分岐予測器にとってより効率的であると判断された可能性があります。さらに、コメントで「16 bytes loaded at this address won't cross a page boundary, so we can load it directly.」とあるように、アドレスが特定の条件を満たす場合（つまり、ページ境界をまたがないことが確実な場合）には、直接MOVOU (AX), X1で16バイトを読み込むことで、複雑な境界チェックロジックを回避しています。また、aesloopendの直後にMOVOU -16(AX)(CX*1), X1という命令が追加され、その後にJMP partialが続くようになりました。これは、残りのバイトが1〜16バイトの場合に、前のロードとオーバーラップする可能性があるものの、常に16バイトを読み込み、その後で部分的な処理を行うというアプローチです。これにより、ループの終了条件と部分処理の開始がよりシンプルになり、効率が向上します。

これらの変更により、特に短い文字列やバイト列のハッシュ計算において、CPUのパイプラインがより効率的に動作し、分岐予測ミスによるペナルティが減少することで、全体的なパフォーマンスが向上しています。

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

変更は主にsrc/pkg/runtime/asm_386.sとsrc/pkg/runtime/asm_amd64.sのruntime·aeshashbody関数にあります。

`src/pkg/runtime/asm_386.s` (32-bit)

--- a/src/pkg/runtime/asm_386.s
+++ b/src/pkg/runtime/asm_386.s
@@ -755,31 +755,39 @@ TEXT runtime·aeshashbody(SB),7,$0
  	PINSRD	$1, CX, X0	// size to next 32 bits of xmm0
  	MOVO	runtime·aeskeysched+0(SB), X2
  	MOVO	runtime·aeskeysched+16(SB), X3
+	CMPL	CX, $16
+	JB	aessmall
  aesloop:
  	CMPL	CX, $16
-	JB	aesloopend
+	JBE	aesloopend
  	MOVOU	(AX), X1
  	AESENC	X2, X0
  	AESENC	X1, X0
  	SUBL	$16, CX
  	ADDL	$16, AX
  	JMP	aesloop
+// 1-16 bytes remaining
 aesloopend:
+	// This load may overlap with the previous load above.
+	// We'll hash some bytes twice, but that's ok.
+	MOVOU	-16(AX)(CX*1), X1
+	JMP	partial
+// 0-15 bytes
+aessmall:
  	TESTL	CX, CX
-	JE	finalize	// no partial block
+	JE	finalize	// 0 bytes
 
-	TESTL	$16, AX
-	JNE	highpartial
+	CMPB	AX, $0xf0
+	JA	highpartial
 
-	// address ends in 0xxxx.  16 bytes loaded
-	// at this address won't cross a page boundary, so
-	// we can load it directly.
+	// 16 bytes loaded at this address won't cross
+	// a page boundary, so we can load it directly.
  	MOVOU	(AX), X1
  	ADDL	CX, CX
  	PAND	masks(SB)(CX*8), X1
  	JMP	partial
  highpartial:
-	// address ends in 1xxxx.  Might be up against
+	// address ends in 1111xxxx.  Might be up against
  	// a page boundary, so load ending at last byte.
  	// Then shift bytes down using pshufb.
  	MOVOU	-16(AX)(CX*1), X1

`src/pkg/runtime/asm_amd64.s` (64-bit)

--- a/src/pkg/runtime/asm_amd64.s
+++ b/src/pkg/runtime/asm_amd64.s
@@ -772,31 +772,39 @@ TEXT runtime·aeshashbody(SB),7,$0
  	PINSRQ	$1, CX, X0	// size to high 64 bits of xmm0
  	MOVO	runtime·aeskeysched+0(SB), X2
  	MOVO	runtime·aeskeysched+16(SB), X3
+	CMPQ	CX, $16
+	JB	aessmall
  aesloop:
  	CMPQ	CX, $16
-	JB	aesloopend
+	JBE	aesloopend
  	MOVOU	(AX), X1
  	AESENC	X2, X0
  	AESENC	X1, X0
  	SUBQ	$16, CX
  	ADDQ	$16, AX
  	JMP	aesloop
+// 1-16 bytes remaining
 aesloopend:
+	// This load may overlap with the previous load above.
+	// We'll hash some bytes twice, but that's ok.
+	MOVOU	-16(AX)(CX*1), X1
+	JMP	partial
+// 0-15 bytes
+aessmall:
  	TESTQ	CX, CX
-	JE	finalize	// no partial block
+	JE	finalize	// 0 bytes
 
-	TESTQ	$16, AX
-	JNE	highpartial
+	CMPB	AX, $0xf0
+	JA	highpartial
 
-	// address ends in 0xxxx.  16 bytes loaded
-	// at this address won't cross a page boundary, so
-	// we can load it directly.
+	// 16 bytes loaded at this address won't cross
+	// a page boundary, so we can load it directly.
  	MOVOU	(AX), X1
  	ADDQ	CX, CX
  	PAND	masks(SB)(CX*8), X1
  	JMP	partial
  highpartial:
-	// address ends in 1xxxx.  Might be up against
+	// address ends in 1111xxxx.  Might be up against
  	// a page boundary, so load ending at last byte.
  	// Then shift bytes down using pshufb.
  	MOVOU	-16(AX)(CX*1), X1

`src/pkg/runtime/mapspeed_test.go`

このファイルには、BenchmarkHashBytesSpeedという新しいベンチマーク関数が追加されています。これは、バイト列のハッシュ速度を測定するためのもので、様々なアラインメントを持つチャンク（17バイトの配列）を使用して、実際の使用シナリオに近い条件でハッシュ関数の性能を評価します。

--- a/src/pkg/runtime/mapspeed_test.go
+++ b/src/pkg/runtime/mapspeed_test.go
@@ -32,6 +32,33 @@ func BenchmarkHashStringSpeed(b *testing.B) {\n 	}\n }\n \n+type chunk [17]byte\n+\n+func BenchmarkHashBytesSpeed(b *testing.B) {\n+\t// a bunch of chunks, each with a different alignment mod 16\n+\tvar chunks [size]chunk\n+\t// initialize each to a different value\n+\tfor i := 0; i < size; i++ {\n+\t\tchunks[i][0] = byte(i)\n+\t}\n+\t// put into a map\n+\tm := make(map[chunk]int, size)\n+\tfor i, c := range chunks {\n+\t\tm[c] = i\n+\t}\n+\tidx := 0\n+\tb.ResetTimer()\n+\tfor i := 0; i < b.N; i++ {\n+\t\tif m[chunks[idx]] != idx {\n+\t\t\tb.Error(\"bad map entry for chunk\")\n+\t\t}\n+\t\tidx++\n+\t\tif idx == size {\n+\t\t\tidx = 0\n+\t\t}\n+\t}\n+}\n+\n func BenchmarkHashInt32Speed(b *testing.B) {\n 	ints := make([]int32, size)\n 	for i := 0; i < size; i++ {\

コアとなるコードの解説

アセンブリコードの変更点

CMPL/CMPQ CX, $16 と JB aessmall: これは、ハッシュ対象の残りのバイト数（CXレジスタに格納）が16バイト未満であるかを最初にチェックする新しい分岐です。もし16バイト未満であれば、aessmallという新しい処理パスにジャンプします。これにより、メインのaesloopが常に16バイト以上のデータを処理することを前提とできるようになり、ループ内の条件分岐を簡素化できます。
JBE aesloopend から JB aesloopend: aesloop内の条件分岐がCMPL/CMPQ CX, $16からJBE aesloopend（Jump Below or Equal）に変更されました。これは、残りのバイト数が16以下の場合にループを終了するという意味です。元のJB（Jump Below）は16未満の場合に終了だったので、16バイトちょうどの場合もループを終了するように変更されています。これは、aesloopendの新しいロジックと整合性を取るためです。
aesloopend の新しいロジック: aesloopendの直後に、MOVOU -16(AX)(CX*1), X1という命令が追加されました。これは、残りのバイト数（CX）に基づいて、現在のポインタ（AX）から16バイト手前の位置から16バイトのデータをX1レジスタに読み込むものです。コメントにあるように、「このロードは、前のロードとオーバーラップする可能性がある。一部のバイトは2回ハッシュされるが、問題ない。」とされています。これは、部分的なブロックを処理する際に、常に16バイトのデータを読み込むことで、コードパスを簡素化し、効率を上げるための戦略です。その後、JMP partialで部分処理の共通パスにジャンプします。
aessmall の導入とページ境界チェックの変更: aessmallは、残りのバイト数が0〜15バイトの場合の新しいエントリポイントです。
- TESTL/TESTQ CX, CX と JE finalize は、残りのバイトが0の場合に最終処理にジャンプするという、元のロジックを継承しています。
- 最も重要な変更は、ページ境界チェックのロジックです。元のTESTL/TESTQ $16, AX（アドレスの下位4ビットをチェック）が、CMPB AX, $0xf0（アドレスの下位バイトが0xf0より大きいかをチェック）に変更されました。この変更は、CPUの分岐予測器にとってより予測しやすいパターンを提供することを目的としています。
- コメントも変更され、highpartialへの分岐条件が「address ends in 1111xxxx. Might be up against a page boundary」とより具体的に記述されています。これは、アドレスの下位バイトが0xf0（バイナリで11110000）以上の場合、つまりアドレスがページの終わりに近い場合に、ページ境界をまたぐ可能性が高いと判断していることを示唆しています。
- MOVOU (AX), X1の前のコメントも「16 bytes loaded at this address won't cross a page boundary, so we can load it directly.」と変更され、特定の条件下で境界チェックを回避して直接ロードできることを明示しています。

ベンチマークの追加

src/pkg/runtime/mapspeed_test.goに追加されたBenchmarkHashBytesSpeedは、この最適化の効果を測定するために非常に重要です。このベンチマークは、異なるアラインメントを持つバイト列のハッシュ速度を測定することで、アセンブリコードの変更が実際のパフォーマンスにどのように影響するかを評価します。特に、17バイトのチャンクを使用することで、16バイトのブロック処理と残りの部分処理の両方がテストされるように設計されています。

これらの変更は、Goランタイムのハッシュ関数が、様々なサイズの入力データに対して、より効率的に、そしてCPUの特性を最大限に活用して動作するように調整されたことを示しています。

参考にした情報源リンク

Go言語のドキュメント (runtimeパッケージ): https://pkg.go.dev/runtime
x86アセンブリ言語の命令セットリファレンス (MOVOU, TEST, CMPなど):
- Intel® 64 and IA-32 Architectures Software Developer’s Manuals: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
AES-NI (Advanced Encryption Standard New Instructions) について:
- Wikipedia: https://ja.wikipedia.org/wiki/AES%E6%96%B0%E8%A6%8F%E5%91%BD%E4%BB%A4
CPUの分岐予測について:
- Wikipedia: https://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90%E4%BA%88%E6%B8%AC
メモリページとページングについて:
- Wikipedia: https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%B3%E3%82%B0
Go言語のマップの実装について (ハッシュ関数の利用):
- Goのソースコード (runtime/map.goなど)
- Goのブログ記事やカンファレンス発表（Goの内部実装に関するもの）

comemo