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

このコミットは、Go言語のランタイムにおけるmemmove（Goの組み込み関数copy()が内部的に利用するメモリ移動処理）の実装を、x86およびx86-64アーキテクチャ向けに高速化することを目的としています。具体的には、アセンブリコードレベルで最適化を行い、特に小規模なメモリコピーにおいてパフォーマンスを大幅に改善しています。また、この変更に伴い、memmoveの正確性とパフォーマンスを検証するための新しいテストファイルが追加されています。

コミット

commit 6021449236c8ef46a6c78518470d0355b56943f3
Author: Keith Randall <khr@golang.org>
Date:   Fri May 17 12:53:49 2013 -0700

    runtime: faster x86 memmove (a.k.a. built-in copy())
    
    REP instructions have a high startup cost, so we handle small
    sizes with some straightline code.  The REP MOVSx instructions
    are really fast for large sizes.  The cutover is approximately
    1K.  We implement up to 128/256 because that is the maximum
    SSE register load (loading all data into registers before any
    stores lets us ignore copy direction).
    
    (on a Sandy Bridge E5-1650 @ 3.20GHz)
    benchmark               old ns/op    new ns/op    delta
    BenchmarkMemmove0               3            3   +0.86%
    BenchmarkMemmove1               5            5   +5.40%
    BenchmarkMemmove2              18            8  -56.84%
    BenchmarkMemmove3              18            7  -58.45%
    BenchmarkMemmove4              36            7  -78.63%
    BenchmarkMemmove5              36            8  -77.91%
    BenchmarkMemmove6              36            8  -77.76%
    BenchmarkMemmove7              36            8  -77.82%
    BenchmarkMemmove8              18            8  -56.33%
    BenchmarkMemmove9              18            7  -58.34%
    BenchmarkMemmove10             18            7  -58.34%
    BenchmarkMemmove11             18            7  -58.45%
    BenchmarkMemmove12             36            7  -78.51%
    BenchmarkMemmove13             36            7  -78.48%
    BenchmarkMemmove14             36            7  -78.56%
    BenchmarkMemmove15             36            7  -78.56%
    BenchmarkMemmove16             18            7  -58.24%
    BenchmarkMemmove32             18            8  -54.33%
    BenchmarkMemmove64             18            8  -53.37%
    BenchmarkMemmove128            20            9  -55.93%
    BenchmarkMemmove256            25           11  -55.16%
    BenchmarkMemmove512            33           33   -1.19%
    BenchmarkMemmove1024           43           44   +2.06%
    BenchmarkMemmove2048           61           61   +0.16%
    BenchmarkMemmove4096           95           95   +0.00%
    
    R=golang-dev, bradfitz, remyoudompheng, khr, iant, dominik.honnef
    CC=golang-dev
    https://golang.org/cl/9038048

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

https://github.com/golang/go/commit/6021449236c8ef46a6c78518470d0355b56943f3

元コミット内容

Go言語のランタイムにおけるx86およびx86-64アーキテクチャ向けのmemmove（Goの組み込み関数copy()が内部的に利用）の実装を高速化する。 REP命令は起動コストが高いため、小規模なデータサイズに対しては直線的な（ストレートライン）コードで処理する。REP MOVSx命令は大規模なデータサイズに対して非常に高速である。この切り替えの閾値は約1KBである。最大128バイト（x86）または256バイト（x86-64）までのコピーを実装しているのは、これがSSEレジスタにロードできる最大量であり、全てのデータをレジスタにロードしてからストアすることで、コピー方向（順方向か逆方向か）を考慮する必要がなくなるためである。

ベンチマーク結果（Sandy Bridge E5-1650 @ 3.20GHz上）では、特に小規模なコピーにおいて大幅な性能改善が見られる。例えば、2バイトから256バイトの範囲で50%以上の高速化が達成されている。

変更の背景

Go言語のランタイムにおいて、メモリコピー操作は非常に頻繁に行われる基本的な処理です。Goの組み込み関数であるcopy()は、内部的にこのmemmove関数を呼び出しています。したがって、memmoveの性能は、Goプログラム全体のパフォーマンスに直接的な影響を与えます。

従来のmemmove実装では、Intel/AMDプロセッサが提供するREP MOVSx（Repeat String Operation）命令が主に利用されていました。この命令は、大量のデータを効率的にコピーするために設計されており、非常に高速です。しかし、コミットメッセージにもあるように、REP命令には「高い起動コスト（high startup cost）」という特性があります。これは、コピーするデータサイズが小さい場合、REP命令のセットアップにかかるオーバーヘッドが、実際のデータコピーにかかる時間よりも大きくなってしまい、結果として非効率になることを意味します。

この問題に対処するため、本コミットでは、小規模なメモリコピーに対してはREP命令を使用せず、代わりに「直線的なコード（straightline code）」、つまり、特定のサイズに最適化された一連のロード（MOV）およびストア（MOV）命令を直接記述することで、オーバーヘッドを削減し、パフォーマンスを向上させることを目指しました。これにより、Goプログラムが頻繁に行う小規模なメモリコピー操作が高速化され、全体的な実行速度の向上が期待されます。

前提知識の解説

1. memmove関数

memmoveは、C言語の標準ライブラリ関数の一つで、メモリブロックをコピーするために使用されます。memcpyと似ていますが、memmoveはコピー元とコピー先のメモリ領域が重なっている場合でも正しく動作することが保証されています。Go言語の組み込み関数copy()は、このmemmoveと同様のセマンティクスを持ち、内部的にはランタイムのmemmove実装を呼び出します。

2. x86/x86-64アセンブリ言語

このコミットで変更されているファイルは.s拡張子を持つアセンブリ言語のソースファイルです。Go言語のランタイムは、パフォーマンスが重要な部分やハードウェアに密接に関わる部分でアセンブリ言語を使用することがあります。

• _386.s: 32ビットx86アーキテクチャ向けのアセンブリコード。
• _amd64.s: 64ビットx86-64アーキテクチャ向けのアセンブリコード。

3. REP MOVSx命令

Intel/AMDプロセッサには、文字列操作を高速化するための特別な命令群があります。MOVSx（Move String）命令は、メモリからメモリへデータを移動させます。

• MOVSB: 1バイト単位で移動。
• MOVSW: 2バイト（ワード）単位で移動。
• MOVSL: 4バイト（ダブルワード）単位で移動。
• MOVSQ: 8バイト（クアッドワード）単位で移動（x86-64のみ）。

これらの命令の前にREPプレフィックスを付けると、CX（またはRCX）レジスタに指定された回数だけMOVSx命令を繰り返します。これにより、ループ処理をCPU内部で効率的に実行でき、ソフトウェアによるループよりも高速になります。しかし、REP命令自体をセットアップするための内部的なオーバーヘッドが存在します。

4. SSE/SSE2 (Streaming SIMD Extensions)

SSEは、Intelが開発したSIMD（Single Instruction, Multiple Data）命令セットの拡張機能です。複数のデータを単一の命令で並行処理することで、浮動小数点演算やメディア処理などのパフォーマンスを向上させます。

• SSE2: SSEの拡張版で、整数演算にも対応し、128ビットのXMMレジスタ（X0からX15）を導入しました。これらのレジスタは、16バイト（128ビット）のデータを一度にロード・ストアするのに使用できます。
• MOVOU (Move Unaligned Oword): SSE命令の一つで、メモリからXMMレジスタへ、またはXMMレジスタからメモリへ、128ビット（16バイト）のデータを移動させます。アラインメントされていないメモリにも対応しています。

memmoveのようなメモリコピーでは、これらのSIMD命令を利用して一度に大量のデータを処理することで、効率を大幅に向上させることができます。特に、コピー元とコピー先が重なっていない場合、データをレジスタに一括でロードし、その後一括でストアすることで、コピー方向を気にすることなく処理を進めることが可能になります。

5. Goのcopy()組み込み関数

Go言語には、スライス間で要素をコピーするための組み込み関数copy(dst, src []Type)があります。この関数は、srcスライスからdstスライスへ要素をコピーし、コピーされた要素の数を返します。内部的には、Goランタイムのmemmove実装が呼び出されます。したがって、memmoveの最適化は、Goプログラムでcopy()を使用する際のパフォーマンスに直接貢献します。

技術的詳細

このコミットの主要な技術的アプローチは、メモリコピーのサイズに応じて異なる最適化戦略を適用する「ハイブリッドアプローチ」です。

1. 小規模コピーの最適化（ストレートラインコード）:

   • REP命令の起動コストを回避するため、非常に小さいサイズ（1バイトから128バイト/256バイト）のコピーに対しては、アセンブリ言語で直接、バイト、ワード、ダブルワード、クアッドワード、またはSSEレジスタ（XMMレジスタ）を使ったロード/ストア命令のシーケンスを記述しています。
   • 例えば、move_1or2、move_3or4、move_5through8、move_9through16といったラベルにジャンプし、それぞれのサイズに特化した効率的なコピー処理を行います。
   • SSE2が利用可能な環境では、MOVOU命令（Move Unaligned Oword）を使用して、16バイト単位でデータをXMMレジスタにロードし、その後ストアします。これにより、一度に大量のデータを処理できるため、ループのオーバーヘッドを削減し、キャッシュ効率も向上させます。特に、コピー方向（順方向か逆方向か）を考慮する必要がなくなるという利点があります。これは、全てのデータをレジスタに読み込んでから書き出すため、メモリの重なりによる問題が発生しないためです。

2. 大規模コピーの最適化（REP MOVSx命令）:

   • コピーサイズが約1KB（1024バイト）を超える場合、REP MOVSx命令の効率が最大化されます。このサイズでは、REP命令の起動コストは全体の処理時間に比べて無視できるほど小さくなります。
   • したがって、この閾値を超えた場合は、引き続きREP MOVSL（32ビット）またはREP MOVSQ（64ビット）命令を使用して高速なブロックコピーを行います。

3. 切り替えの閾値:

   • コミットメッセージによると、ストレートラインコードとREP命令の切り替えの閾値は「約1KB」とされています。これは、ベンチマーク結果からも裏付けられており、BenchmarkMemmove512までは改善が見られるものの、BenchmarkMemmove1024以降は改善がほとんど見られないか、わずかに悪化していることから、このあたりで切り替えていることがわかります。

4. ベンチマーク結果の分析:

   • コミットメッセージに記載されているベンチマーク結果は、この最適化の効果を明確に示しています。
   • BenchmarkMemmove2からBenchmarkMemmove256までの範囲で、旧バージョンと比較して50%から78%という大幅な性能改善が達成されています。これは、小規模なコピーに対するストレートラインコードとSSE命令の導入が成功したことを示しています。
   • BenchmarkMemmove0とBenchmarkMemmove1のような非常に小さいサイズでは、改善幅は小さいですが、これは既に非常に高速であるため、これ以上の最適化が難しいことを示唆しています。
   • BenchmarkMemmove512以降の大きなサイズでは、性能改善がほとんど見られません。これは、これらのサイズでは既にREP MOVSx命令が効率的に機能しており、今回の最適化の対象外であるか、あるいはその効果が相対的に小さいためと考えられます。

このハイブリッドアプローチにより、Goのcopy()関数は、あらゆるサイズのメモリコピーにおいて、より効率的に動作するようになりました。

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

このコミットでは、以下の3つのファイルが変更されています。

1. src/pkg/runtime/memmove_386.s: 32ビットx86アーキテクチャ向けのmemmoveアセンブリ実装。

   • 小規模なコピーを処理するための新しい分岐ロジック（tailラベルとそれに続くCMPL/JBE命令群）が追加されました。
   • move_1or2、move_3or4、move_5through8、move_9through16、move_17through32、move_33through64、move_65through128といった新しいラベルと、それぞれのサイズに特化したストレートラインコピーコードが追加されました。
   • 特に、SSE2が利用可能な場合にMOVOU命令を使用するセクションが追加されています。
   • 既存のREP MOVSLの後に、残りのバイトを処理するためのREP MOVSBの呼び出しが削除され、代わりに新しいtailロジックにジャンプするように変更されました。

2. src/pkg/runtime/memmove_amd64.s: 64ビットx86-64アーキテクチャ向けのmemmoveアセンブリ実装。

   • memmove_386.sと同様に、小規模なコピーを処理するための新しい分岐ロジック（tailラベルとそれに続くCMPQ/JBE命令群）が追加されました。
   • move_1or2からmove_129through256までの新しいラベルと、それぞれのサイズに特化したストレートラインコピーコードが追加されました。
   • MOVOU命令を使用したSSE最適化が、より大きなサイズ（最大256バイト）まで拡張されています。
   • 既存のREP MOVSQの後に、残りのバイトを処理するためのREP MOVSBの呼び出しが削除され、代わりに新しいtailロジックにジャンプするように変更されました。

3. src/pkg/runtime/memmove_test.go: memmove関数の正確性とパフォーマンスを検証するための新しいGoテストファイル。

   • TestMemmove: さまざまなサイズとオフセットでcopy()関数をテストし、コピーが正しく行われることを検証します。特に、コピー元とコピー先が重ならないケースを網羅しています。
   • TestMemmoveAlias: コピー元とコピー先が重なる（エイリアシング）ケースでcopy()関数をテストし、memmoveのセマンティクスが正しく実装されていることを検証します。
   • bmMemmove: ベンチマークヘルパー関数。
   • BenchmarkMemmoveX: 0バイトから4096バイトまでの様々なサイズのメモリコピーのパフォーマンスを測定するためのベンチマーク関数群。コミットメッセージに記載されているベンチマーク結果は、これらの関数によって生成されたものです。

コアとなるコードの解説

src/pkg/runtime/memmove_386.s および src/pkg/runtime/memmove_amd64.s

これらのファイルは、Goのアセンブリ言語（Plan 9アセンブラ）で書かれています。基本的な構造は、コピー元（SIレジスタ）、コピー先（DIレジスタ）、コピーサイズ（BXレジスタ）を受け取り、メモリコピーを実行するというものです。

変更の核心は、tailラベルから始まる新しい分岐ロジックです。

tail:
	TESTL	BX, BX   // 32-bit: TESTL, 64-bit: TESTQ
	JEQ	move_0   // サイズが0なら即座に終了

	CMPL	BX, $2   // 32-bit: CMPL, 64-bit: CMPQ
	JBE	move_1or2 // サイズが2以下ならmove_1or2へ
	CMPL	BX, $4
	JBE	move_3or4 // サイズが4以下ならmove_3or4へ
	// ... (同様の分岐が続く)

このコードは、コピーサイズBXを段階的に比較し、適切なサイズのハンドリングルーチンにジャンプします。

• move_0: サイズが0の場合、何もせずにRET（リターン）します。
• move_1or2: 1バイトまたは2バイトのコピーを処理します。
  • MOVB (SI), AX / MOVB -1(SI)(BX*1), CX: コピー元からバイトをロード。BX*1はサイズに応じてオフセットを調整し、重なりを考慮したコピーを可能にします。
  • MOVB AX, (DI) / MOVB CX, -1(DI)(BX*1): コピー先へバイトをストア。
• move_3or4: 3バイトまたは4バイトのコピーを処理します。ワード（2バイト）単位のMOVW命令を使用します。
• move_5through8: 5バイトから8バイトのコピーを処理します。ダブルワード（4バイト）単位のMOVL命令を使用します。
• move_9through16: 9バイトから16バイトのコピーを処理します。複数のMOVL命令を使用します。
• move_17through32 (x86/x86-64), move_33through64, move_65through128 (x86/x86-64), move_129through256 (x86-64):
  • これらのルーチンでは、SSE2命令であるMOVOUが活用されます。
  • MOVOU (SI), X0: コピー元から16バイト（128ビット）をXMMレジスタX0にロードします。
  • MOVOU X0, (DI): X0の内容をコピー先へ16バイトストアします。
  • 複数のMOVOU命令を組み合わせることで、より大きなブロックを効率的にコピーします。例えば、move_65through128では8つのXMMレジスタ（X0-X7）を使用し、合計128バイトを一度に処理します。
  • 重要なのは、これらのルーチンでは全てのデータをレジスタにロードしてからストアするため、コピー元とコピー先が重なっていても、コピー方向を考慮する必要がない点です。これは、memmoveの重なり対応の要件を満たしつつ、パフォーマンスを向上させるための鍵となります。

既存のREP MOVSx命令を使用するパスでは、コピー後に残ったバイトを処理するために、以前はREP MOVSBにフォールバックしていましたが、今回の変更でその部分が削除され、代わりにtailラベルにジャンプするように変更されました。これにより、残りのバイトも新しい最適化されたストレートラインコードで処理されるようになります。

src/pkg/runtime/memmove_test.go

この新しいテストファイルは、memmoveの正確性と性能を保証するために非常に重要です。

• TestMemmoveとTestMemmoveAliasは、様々なサイズのデータ、様々なオフセット、そして重なり合うメモリ領域でのコピーが、期待通りに動作するかを検証します。これは、アセンブリコードの変更が正しい結果を生成することを保証するための機能テストです。
• BenchmarkMemmoveX関数群は、Goの標準ベンチマークフレームワーク（testingパッケージ）を使用して、異なるサイズのメモリコピー操作の実行時間を測定します。これにより、最適化の効果を定量的に評価し、回帰がないことを確認できます。b.SetBytes(int64(n))は、ベンチマーク結果に「bytes/op」の統計を追加するために使用され、コピーされたバイト数あたりの操作時間をより明確に示します。

これらのテストとベンチマークは、ランタイムの低レベルな変更が、Go言語のユーザーに提供されるcopy()関数の安定性とパフォーマンスに悪影響を与えないことを確認するための重要な安全網となります。

関連リンク

• Go CL 9038048: https://golang.org/cl/9038048

参考にした情報源リンク

• Intel 64 and IA-32 Architectures Software Developer's Manuals (特にVolume 2A: Instruction Set Reference, A-M): REP, MOVSx, MOVOU命令の詳細について。
• Go言語のtestingパッケージドキュメント: ベンチマークの書き方について。
• Go言語のソースコード（runtimeパッケージ）: memmoveの実装と関連するアセンブリコードの慣習について。