Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goランタイムにおけるx86アーキテクチャでのmemclr（メモリクリア）関数のパフォーマンスを大幅に改善するものです。具体的には、従来のREP STOSQ命令の使用から、明示的なSSE（Streaming SIMD Extensions）命令であるMOVOUを用いた書き込みに切り替えることで、特に小規模から中規模のメモリ領域のクリアにおいて顕著な速度向上を実現しています。ベンチマーク結果では、最大で約78%の性能向上が報告されています。

コミット

commit da7cf0ba5d5aed78f07c82508f0fa88e6dd69ea7
Author: Keith Randall <khr@golang.org>
Date:   Thu Feb 6 17:43:22 2014 -0800

    runtime: faster memclr on x86.
    
    Use explicit SSE writes instead of REP STOSQ.
    
    benchmark               old ns/op    new ns/op    delta
    BenchmarkMemclr5               22            5  -73.62%
    BenchmarkMemclr16              27            5  -78.49%
    BenchmarkMemclr64              28            6  -76.43%
    BenchmarkMemclr256             34            8  -74.94%
    BenchmarkMemclr4096           112           84  -24.73%
    BenchmarkMemclr65536         1902         1920   +0.95%
    
    LGTM=dvyukov
    R=golang-codereviews, dvyukov
    CC=golang-codereviews
    https://golang.org/cl/60090044
---
 src/cmd/8a/lex.c                |   1 +\
 src/cmd/8l/8.out.h              |   1 +\
 src/liblink/asm8.c              |   1 +\
 src/pkg/runtime/alg.c           |   5 ++
 src/pkg/runtime/asm_386.s       |  15 -----
 src/pkg/runtime/asm_amd64.s     |  15 -----
 src/pkg/runtime/export_test.go  |   4 ++
 src/pkg/runtime/memclr_386.s    | 125 ++++++++++++++++++++++++++++++++++++++++
 src/pkg/runtime/memclr_amd64.s  | 114 ++++++++++++++++++++++++++++++++++++
 src/pkg/runtime/memclr_arm.s    |   6 --
 src/pkg/runtime/memmove_test.go |  99 ++++++++++++++++++++++---------\n 11 files changed, 324 insertions(+), 62 deletions(-)

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

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

元コミット内容

runtime: faster memclr on x86.

Use explicit SSE writes instead of REP STOSQ.

benchmark               old ns/op    new ns/op    delta
BenchmarkMemclr5               22            5  -73.62%
BenchmarkMemclr16              27            5  -78.49%
BenchmarkMemclr64              28            6  -76.43%
BenchmarkMemclr256             34            8  -74.94%
BenchmarkMemclr4096           112           84  -24.73%
BenchmarkMemclr65536         1902         1920   +0.95%

LGTM=dvyukov
R=golang-codereviews, dvyukov
CC=golang-codereviews
https://golang.org/cl/60090044

変更の背景

Goランタイムにおいて、メモリをゼロクリアする操作（memclr）は、ガベージコレクションやスライス、マップの初期化など、様々な場面で頻繁に利用される基本的な操作です。この操作の効率は、Goプログラム全体のパフォーマンスに直接影響します。

従来のx86アーキテクチャにおけるmemclrの実装では、REP STOSQという命令が使用されていました。これは、指定された回数だけレジスタの値をメモリにストアする繰り返し命令であり、簡潔にメモリをクリアするのに便利です。しかし、現代のCPUアーキテクチャ、特にIntelやAMDのプロセッサでは、REP STOSQのようなマイクロコードで実装された繰り返し命令は、特定の条件下でパイプラインの効率を低下させたり、最適化の妨げになることが知られています。

特に、比較的小さなメモリ領域をクリアする場合、REP STOSQのオーバーヘッドが顕著になり、より低レベルで明示的なSIMD（Single Instruction, Multiple Data）命令、例えばSSE（Streaming SIMD Extensions）を用いた方が高速になる可能性があります。このコミットは、このパフォーマンスボトルネックを解消し、Goプログラムの実行速度を向上させることを目的としています。ベンチマーク結果が示すように、特に小規模なクリア操作で大幅な改善が見られました。

前提知識の解説

1. memclr (Memory Clear)

memclrは、指定されたメモリ領域の内容をすべてゼロ（または特定のバイト値）で埋める操作です。プログラミングにおいて、新しいメモリ領域を確保した際に、その内容が不定であることによるセキュリティリスクやバグを防ぐために、初期化としてゼロクリアが行われることがよくあります。Goランタイムでは、ガベージコレクタがオブジェクトを再利用する際や、新しいスライスやマップが作成される際に、メモリのゼロクリアが内部的に行われます。

2. REP STOSQ 命令

REP STOSQは、x86アセンブリ言語における文字列操作命令の一つです。

  • STOSQ (Store String Quadword): RAXレジスタ（64ビット）の内容をRDIレジスタが指すメモリ位置にストアし、RDIを8バイト（クアッドワードのサイズ）インクリメント（またはデクリメント、DFフラグによる）します。
  • REP (Repeat): RCXレジスタがゼロになるまで、続く命令を繰り返します。

したがって、REP STOSQはRCX回だけRAXの内容をメモリにストアし続けることで、指定されたメモリ領域をRAXの値で埋めることができます。メモリをゼロクリアする場合、RAXに0を設定してからREP STOSQを実行します。これは、ループを明示的に書くよりも簡潔で、かつCPUのマイクロコードによって最適化されることが期待される命令です。

3. SSE (Streaming SIMD Extensions)

SSEは、Intelが開発したSIMD命令セットの拡張機能です。SIMDは「Single Instruction, Multiple Data」の略で、一つの命令で複数のデータ要素に対して同じ操作を同時に実行できる能力を指します。

  • XMMレジスタ: SSE命令は、128ビット幅のXMMレジスタ（XMM0からXMM7、またはXMM0からXMM15）を使用します。これらのレジスタは、単精度浮動小数点数、倍精度浮動小数点数、または整数データを格納できます。
  • MOVOU 命令: MOVOU (Move Unaligned Oword) は、XMMレジスタの内容をメモリにストアする命令です。この命令は、メモリのアライメント（境界）を気にせずに128ビット（16バイト）のデータを転送できます。メモリクリアの文脈では、XMMレジスタにゼロを設定し、そのゼロをMOVOUでメモリに書き込むことで、16バイト単位でメモリをゼロクリアできます。
  • PXOR 命令: PXOR (Packed XOR) は、2つのXMMレジスタの内容をビット単位でXOR演算し、結果をデスティネーションレジスタに格納する命令です。PXOR X0, X0のように同じレジスタに対してXOR演算を行うと、そのレジスタの内容はすべてゼロになります。これは、XMMレジスタを効率的にゼロクリアする一般的な手法です。

4. CPUのマイクロアーキテクチャと性能

現代のCPUは非常に複雑なパイプラインとキャッシュシステムを持っています。

  • REP STOSQのようなマイクロコード化された命令は、CPU内部で複数のマイクロオペレーションに分解されて実行されます。これは、命令のデコードや実行のオーバーヘッドを引き起こす可能性があります。
  • 一方、SSE命令のような明示的なSIMD命令は、より直接的にハードウェアリソースを利用し、複数のデータ要素を並列に処理できるため、特定のタスク（メモリクリアなど）において高いスループットを発揮することがあります。
  • メモリのアライメントも性能に影響します。MOVOUはアライメントを気にしませんが、アライメントされたアクセス（MOVAPSなど）の方が高速な場合もあります。しかし、memclrの対象となるメモリは必ずしもアライメントされているとは限らないため、MOVOUが選択されるのは妥当です。

技術的詳細

このコミットの核心は、Goランタイムのmemclr実装において、x86アーキテクチャ（386およびamd64）でREP STOSQ命令の使用を廃止し、代わりにSSE命令であるMOVOUとPXORを組み合わせたアプローチを採用した点にあります。

REP STOSQの限界

REP STOSQは、その簡潔さから古くからメモリ操作に用いられてきましたが、現代のCPUではその性能特性が必ずしも最適ではありません。

  • マイクロコードの複雑性: REP STOSQは単一の命令に見えますが、CPU内部では複数のマイクロオペレーションに展開されます。この展開プロセスや、繰り返し処理の制御ロジックが、特に短いループやデータサイズの場合にオーバーヘッドとなることがあります。
  • パイプラインの停滞: CPUのパイプラインは、命令を連続的に処理することで高いスループットを実現します。しかし、REP STOSQのような長い実行時間の命令は、パイプラインをブロックし、後続の命令の実行を遅らせる可能性があります。
  • キャッシュ効率: REP STOSQは、キャッシュラインを効率的に利用しない場合があります。特に、書き込みパターンがキャッシュのプリフェッチ機構と合致しない場合、性能が低下することがあります。

SSE命令による最適化

新しい実装では、以下の手順でメモリクリアを行います。

  1. XMMレジスタのゼロクリア: PXOR X0, X0命令を使用して、XMM0レジスタをゼロで埋めます。XMMレジスタは128ビット幅なので、これにより16バイトのゼロデータが用意されます。
  2. 16バイト単位での書き込み: MOVOU X0, 0(DI)のような命令を繰り返し使用し、XMM0レジスタのゼロデータをメモリに16バイト単位で書き込みます。DIレジスタは書き込み先のメモリポインタを保持します。
  3. サイズの分岐処理: memclrの対象となるメモリサイズは様々であるため、新しい実装では、サイズに応じて異なる処理パスが用意されています。
    • 非常に小さいサイズ（1〜16バイト）の場合：バイト単位、ワード単位、ダブルワード単位、クアッドワード単位の通常のストア命令（MOVB, MOVW, MOVL, MOVQ）を組み合わせて処理します。これは、SSE命令のセットアップオーバーヘッドを避けるためです。
    • 中程度のサイズ（17〜256バイト）の場合：MOVOU命令を複数回使用し、16バイト単位で効率的にクリアします。例えば、32バイトをクリアするにはMOVOU X0, (DI)とMOVOU X0, -16(DI)(BX*1)のように2つのMOVOU命令を使用します。
    • 大きなサイズ（256バイト以上）の場合：clr_loopというループに入り、一度に256バイト（16バイト * 16回）をMOVOU命令で書き込みます。ループの最後に残ったバイトは、clr_tailセクションで処理されます。

ベンチマーク結果の分析

コミットメッセージに含まれるベンチマーク結果は、この変更の有効性を示しています。

benchmarkold ns/opnew ns/opdelta
BenchmarkMemclr5225-73.62%
BenchmarkMemclr16275-78.49%
BenchmarkMemclr64286-76.43%
BenchmarkMemclr256348-74.94%
BenchmarkMemclr409611284-24.73%
BenchmarkMemclr6553619021920+0.95%
  • 小規模なクリア（5〜256バイト）: 73%〜78%という劇的な性能向上が見られます。これは、REP STOSQのオーバーヘッドが大きかった小規模なクリアにおいて、SSE命令の効率が最大限に発揮されたことを示しています。SSE命令のセットアップコストは存在するものの、一度セットアップすれば16バイト単位で高速に処理できるため、この範囲で大きなメリットがあります。
  • 中規模なクリア（4096バイト）: 約25%の性能向上が見られます。このサイズでは、REP STOSQもそれなりに効率的ですが、SSE命令による並列処理が依然として優位性を示しています。
  • 大規模なクリア（65536バイト）: 性能はほぼ横ばい（わずかに悪化）です。これは、非常に大きなメモリ領域のクリアにおいては、REP STOSQがCPUの内部最適化（例えば、キャッシュライン全体を一度にクリアするような最適化）によって非常に効率的になるためと考えられます。また、このサイズになると、メモリ帯域幅がボトルネックになり、CPUの命令実行速度の差が相対的に小さくなる可能性もあります。コミットメッセージには「TODO: for really big clears, use MOVNTDQ.」とあり、これはさらに大きなクリアに対してはキャッシュを汚染しないノンテンポラルストア命令（MOVNTDQ）の使用を検討していることを示唆しており、大規模なクリアにおけるさらなる最適化の余地があることを示しています。

この変更は、Goランタイムの基盤となるメモリ操作の効率を向上させ、特にガベージコレクションの頻度が高いアプリケーションや、多数の小さなオブジェクトを扱うアプリケーションにおいて、全体的なパフォーマンス改善に貢献します。

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

このコミットにおける主要なコード変更は、Goランタイムのx86およびamd64アーキテクチャ向けのアセンブリファイルに集中しています。

  1. src/pkg/runtime/asm_386.s および src/pkg/runtime/asm_amd64.s からの runtime·memclr の削除:

    • これらのファイルから、従来のREP STOSL (386) および REP STOSQ (amd64) を使用したruntime·memclrの実装が削除されました。

  2. src/pkg/runtime/memclr_386.s の新規追加と実装:

    • 32ビットx86アーキテクチャ向けの新しいruntime·memclr実装が追加されました。
    • このファイルには、SSE2命令（PXOR, MOVOU）を用いたメモリクリアロジックが含まれています。
    • 様々なサイズ（1バイトから256バイト以上）に対応するための分岐処理が詳細に記述されています。

  3. src/pkg/runtime/memclr_amd64.s の新規追加と実装:

    • 64ビットx86アーキテクチャ向けの新しいruntime·memclr実装が追加されました。
    • こちらもSSE2命令（PXOR, MOVOU）を用いたメモリクリアロジックが中心です。
    • 386版と同様に、様々なサイズに対応するための分岐処理が記述されています。

  4. src/cmd/8a/lex.c, src/cmd/8l/8.out.h, src/liblink/asm8.c の変更:

    • アセンブラとリンカの定義にPXOR命令が追加されました。これは、GoのアセンブラがPXOR命令を認識し、正しくアセンブルできるようにするために必要です。

  5. src/pkg/runtime/alg.c の変更:

    • テスト用のラッパー関数runtime·memclrBytesが追加されました。これは、Goのテストコードからアセンブリで実装されたmemclrを呼び出すためのGo言語側のインターフェースです。

  6. src/pkg/runtime/export_test.go の変更:

    • memclrBytes関数がテストパッケージからアクセスできるようにエクスポートされました。

  7. src/pkg/runtime/memmove_test.go の変更:

    • memclrの新しいベンチマーク（BenchmarkMemclrX）と、memclrの正確性を検証するための新しいテストケース（TestMemclr）が追加されました。これにより、変更が正しく機能し、性能が向上したことを確認できます。

これらの変更により、memclrの低レベルな実装が、より現代的なCPUの特性に合わせた最適化されたアセンブリコードに置き換えられました。

コアとなるコードの解説

ここでは、src/pkg/runtime/memclr_amd64.s の主要な部分を例に、新しいmemclrの実装を解説します。memclr_386.sも同様のロジックですが、レジスタサイズや命令が32ビット用に調整されています。

// void runtime·memclr(void*, uintptr)
TEXT runtime·memclr(SB), NOSPLIT, $0-16
	MOVQ	ptr+0(FP), DI  // 第一引数: クリア対象のメモリポインタをDIレジスタにロード
	MOVQ	n+8(FP), BX    // 第二引数: クリアするバイト数をBXレジスタにロード
	XORQ	AX, AX         // AXレジスタをゼロクリア (バイト単位のクリア用)

	// MOVOU seems always faster than REP STOSQ.
clr_tail:
	TESTQ	BX, BX         // BX (残りバイト数) がゼロかチェック
	JEQ	clr_0          // ゼロなら終了

	// サイズに応じた分岐処理
	CMPQ	BX, $2
	JBE	clr_1or2       // 1または2バイトの場合
	CMPQ	BX, $4
	JBE	clr_3or4       // 3または4バイトの場合
	CMPQ	BX, $8
	JBE	clr_5through8  // 5から8バイトの場合
	CMPQ	BX, $16
	JBE	clr_9through16 // 9から16バイトの場合

	PXOR	X0, X0         // XMM0レジスタをゼロクリア (16バイトのゼロデータを作成)

	CMPQ	BX, $32
	JBE	clr_17through32 // 17から32バイトの場合
	CMPQ	BX, $64
	JBE	clr_33through64 // 33から64バイトの場合
	CMPQ	BX, $128
	JBE	clr_65through128 // 65から128バイトの場合
	CMPQ	BX, $256
	JBE	clr_129through256 // 129から256バイトの場合

	// TODO: use branch table and BSR to make this just a single dispatch
	// TODO: for really big clears, use MOVNTDQ.

clr_loop: // 256バイト以上の大きなクリアのためのループ
	MOVOU	X0, 0(DI)    // XMM0 (16バイトのゼロ) をメモリに書き込み
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, 64(DI)
	MOVOU	X0, 80(DI)
	MOVOU	X0, 96(DI)
	MOVOU	X0, 112(DI)
	MOVOU	X0, 128(DI)
	MOVOU	X0, 144(DI)
	MOVOU	X0, 160(DI)
	MOVOU	X0, 176(DI)
	MOVOU	X0, 192(DI)
	MOVOU	X0, 208(DI)
	MOVOU	X0, 224(DI)
	MOVOU	X0, 240(DI) // 合計16回のMOVOUで256バイトをクリア
	SUBQ	$256, BX     // 残りバイト数を256減らす
	ADDQ	$256, DI     // メモリポインタを256進める
	CMPQ	BX, $256     // 残りバイト数が256以上ならループを続ける
	JAE	clr_loop
	JMP	clr_tail     // 残りが256バイト未満になったら、残りの処理のためにclr_tailへジャンプ

// 小さいサイズのクリア処理 (末尾から書き込むことで、アライメントを考慮しつつ効率的に処理)
clr_1or2:
	MOVB	AX, (DI)         // 1バイト目をクリア
	MOVB	AX, -1(DI)(BX*1) // 残りのバイトをクリア (BXは残りバイト数)
clr_0:
	RET                      // 関数終了
clr_3or4:
	MOVW	AX, (DI)
	MOVW	AX, -2(DI)(BX*1)
	RET
clr_5through8:
	MOVL	AX, (DI)
	MOVL	AX, -4(DI)(BX*1)
	RET
clr_9through16:
	MOVQ	AX, (DI)
	MOVQ	AX, -8(DI)(BX*1)
	RET

// SSE命令を使った中程度のサイズのクリア処理 (末尾から書き込むことで、アライメントを考慮しつつ効率的に処理)
clr_17through32:
	MOVOU	X0, (DI)
	MOVOU	X0, -16(DI)(BX*1) // 16バイトをクリアし、残りを末尾からクリア
	RET
clr_33through64:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET
clr_65through128:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, -64(DI)(BX*1)
	MOVOU	X0, -48(DI)(BX*1)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET
clr_129through256:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, 64(DI)
	MOVOU	X0, 80(DI)
	MOVOU	X0, 96(DI)
	MOVOU	X0, 112(DI)
	MOVOU	X0, -128(DI)(BX*1)
	MOVOU	X0, -112(DI)(BX*1)
	MOVOU	X0, -96(DI)(BX*1)
	MOVOU	X0, -80(DI)(BX*1)
	MOVOU	X0, -64(DI)(BX*1)
	MOVOU	X0, -48(DI)(BX*1)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET

解説のポイント

  1. 引数の取得: ptr+0(FP)とn+8(FP)は、それぞれ関数に渡されたポインタとバイト数をスタックフレームから取得しています。
  2. XORQ AX, AX: これは、後でバイト単位のクリアが必要になった場合に備えて、AXレジスタをゼロに初期化しています。
  3. clr_tailと分岐: 関数はまずclr_tailラベルにジャンプします。これは、残りのバイト数を処理するための共通のエントリポイントです。BX（バイト数）がゼロであれば即座に終了します。
  4. サイズに応じた最適化:
    • 小サイズ（1〜16バイト）: CMPQ BX, $XとJBE（Jump Below or Equal）命令を使って、バイト数に応じて適切な処理パスに分岐します。これらのパスでは、MOVB（バイト）、MOVW（ワード）、MOVL（ダブルワード）、MOVQ（クアッドワード）といった通常のストア命令を組み合わせてメモリをクリアします。これは、SSE命令のセットアップコストを避けるためです。特に注目すべきは、MOVB AX, -1(DI)(BX*1)のように、末尾から書き込むことで、アライメントを考慮しつつ効率的に処理している点です。
    • SSE2のチェックと初期化: PXOR X0, X0は、XMM0レジスタをゼロで埋めます。これは、16バイトのゼロデータを効率的に作成するSIMD命令です。386版ではruntime·cpuid_edx(SB)をチェックしてSSE2が利用可能かを確認していますが、amd64ではSSE2が必須であるため、このチェックは省略されています。
    • 中サイズ（17〜256バイト）: MOVOU命令を複数回使用して、16バイト単位でメモリをクリアします。ここでも、末尾からの書き込みを組み合わせることで、アライメントを気にせず効率的に処理しています。
    • 大サイズ（256バイト以上）: clr_loopに入り、一度に256バイト（16バイト * 16回）をMOVOU命令で書き込みます。ループの最後に残ったバイトは、再度clr_tailにジャンプして処理されます。
  5. MOVOU命令の利用: MOVOUはアライメントされていないメモリへのアクセスを許可する命令であり、memclrの対象となるメモリが常に16バイト境界にアライメントされているとは限らないため、この命令が選択されています。

このアセンブリコードは、Goランタイムが特定のハードウェア特性（この場合はx86のSSE命令）を最大限に活用し、一般的な操作のパフォーマンスを最適化するために、いかに低レベルなチューニングを行っているかを示す好例です。

関連リンク

  • Go CL (Code Review) へのリンク: https://golang.org/cl/60090044

参考にした情報源リンク

  • Intel 64 and IA-32 Architectures Software Developer's Manuals:
    • Volume 2A: Instruction Set Reference, A-M (MOVOU, PXOR, REP STOSQなどの命令の詳細)
    • Volume 2B: Instruction Set Reference, N-Z
    • Volume 3A: System Programming Guide, Part 1 (CPUのマイクロアーキテクチャ、パイプライン、キャッシュに関する情報)
  • Agner Fog's optimization manuals:
    • "Optimizing software in C++" や "Assembly optimization manual" など、x86アセンブリのパフォーマンスに関する詳細な情報が提供されています。特に、REP STOS命令の性能特性や、SIMD命令の効率的な利用方法について言及されています。
    • https://www.agner.org/optimize/
  • Stack Overflow / 技術ブログ:
    • REP STOSQとSSE命令のパフォーマンス比較に関する議論やベンチマーク結果を扱った記事。
    • 例: "Why is REP STOS faster than a loop of MOV instructions?" (ただし、このコミットでは逆の結論が出ている点に注意)
    • 例: "Optimizing memset with SSE/AVX"

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

このコミットは、Goランタイムにおけるx86アーキテクチャでのmemclr（メモリクリア）関数のパフォーマンスを大幅に改善するものです。具体的には、従来のREP STOSQ命令の使用から、明示的なSSE（Streaming SIMD Extensions）命令であるMOVOUを用いた書き込みに切り替えることで、特に小規模から中規模のメモリ領域のクリアにおいて顕著な速度向上を実現しています。ベンチマーク結果では、最大で約78%の性能向上が報告されています。

コミット

commit da7cf0ba5d5aed78f07c82508f0fa88e6dd69ea7
Author: Keith Randall <khr@golang.org>
Date:   Thu Feb 6 17:43:22 2014 -0800

    runtime: faster memclr on x86.
    
    Use explicit SSE writes instead of REP STOSQ.
    
    benchmark               old ns/op    new ns/op    delta
    BenchmarkMemclr5               22            5  -73.62%
    BenchmarkMemclr16              27            5  -78.49%
    BenchmarkMemclr64              28            6  -76.43%
    BenchmarkMemclr256             34            8  -74.94%
    BenchmarkMemclr4096           112           84  -24.73%
    BenchmarkMemclr65536         1902         1920   +0.95%
    
    LGTM=dvyukov
    R=golang-codereviews, dvyukov
    CC=golang-codereviews
    https://golang.org/cl/60090044
---
 src/cmd/8a/lex.c                |   1 +\
 src/cmd/8l/8.out.h              |   1 +\
 src/liblink/asm8.c              |   1 +\
 src/pkg/runtime/alg.c           |   5 ++
 src/pkg/runtime/asm_386.s       |  15 -----
 src/pkg/runtime/asm_amd64.s     |  15 -----
 src/pkg/runtime/export_test.go  |   4 ++
 src/pkg/runtime/memclr_386.s    | 125 ++++++++++++++++++++++++++++++++++++++++
 src/pkg/runtime/memclr_amd64.s  | 114 ++++++++++++++++++++++++++++++++++++
 src/pkg/runtime/memclr_arm.s    |   6 --
 src/pkg/runtime/memmove_test.go |  99 ++++++++++++++++++++++---------\n 11 files changed, 324 insertions(+), 62 deletions(-)

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

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

元コミット内容

runtime: faster memclr on x86.

Use explicit SSE writes instead of REP STOSQ.

benchmark               old ns/op    new ns/op    delta
BenchmarkMemclr5               22            5  -73.62%
BenchmarkMemclr16              27            5  -78.49%
BenchmarkMemclr64              28            6  -76.43%
BenchmarkMemclr256             34            8  -74.94%
BenchmarkMemclr4096           112           84  -24.73%
BenchmarkMemclr65536         1902         1920   +0.95%

LGTM=dvyukov
R=golang-codereviews, dvyukov
CC=golang-codereviews
https://golang.org/cl/60090044

変更の背景

Goランタイムにおいて、メモリをゼロクリアする操作（memclr）は、ガベージコレクションやスライス、マップの初期化など、様々な場面で頻繁に利用される基本的な操作です。この操作の効率は、Goプログラム全体のパフォーマンスに直接影響します。

従来のx86アーキテクチャにおけるmemclrの実装では、REP STOSQという命令が使用されていました。これは、指定された回数だけレジスタの値をメモリにストアする繰り返し命令であり、簡潔にメモリをクリアするのに便利です。しかし、現代のCPUアーキテクチャ、特にIntelやAMDのプロセッサでは、REP STOSQのようなマイクロコードで実装された繰り返し命令は、特定の条件下でパイプラインの効率を低下させたり、最適化の妨げになることが知られています。

特に、比較的小さなメモリ領域をクリアする場合、REP STOSQのオーバーヘッドが顕著になり、より低レベルで明示的なSIMD（Single Instruction, Multiple Data）命令、例えばSSE（Streaming SIMD Extensions）を用いた方が高速になる可能性があります。このコミットは、このパフォーマンスボトルネックを解消し、Goプログラムの実行速度を向上させることを目的としています。ベンチマーク結果が示すように、特に小規模なクリア操作で大幅な改善が見られました。

前提知識の解説

1. memclr (Memory Clear)

memclrは、指定されたメモリ領域の内容をすべてゼロ（または特定のバイト値）で埋める操作です。プログラミングにおいて、新しいメモリ領域を確保した際に、その内容が不定であることによるセキュリティリスクやバグを防ぐために、初期化としてゼロクリアが行われることがよくあります。Goランタイムでは、ガベージコレクタがオブジェクトを再利用する際や、新しいスライスやマップが作成される際に、メモリのゼロクリアが内部的に行われます。

2. REP STOSQ 命令

REP STOSQは、x86アセンブリ言語における文字列操作命令の一つです。

  • STOSQ (Store String Quadword): RAXレジスタ（64ビット）の内容をRDIレジスタが指すメモリ位置にストアし、RDIを8バイト（クアッドワードのサイズ）インクリメント（またはデクリメント、DFフラグによる）します。
  • REP (Repeat): RCXレジスタがゼロになるまで、続く命令を繰り返します。

したがって、REP STOSQはRCX回だけRAXの内容をメモリにストアし続けることで、指定されたメモリ領域をRAXの値で埋めることができます。メモリをゼロクリアする場合、RAXに0を設定してからREP STOSQを実行します。これは、ループを明示的に書くよりも簡潔で、かつCPUのマイクロコードによって最適化されることが期待される命令です。

3. SSE (Streaming SIMD Extensions)

SSEは、Intelが開発したSIMD命令セットの拡張機能です。SIMDは「Single Instruction, Multiple Data」の略で、一つの命令で複数のデータ要素に対して同じ操作を同時に実行できる能力を指します。

  • XMMレジスタ: SSE命令は、128ビット幅のXMMレジスタ（XMM0からXMM7、またはXMM0からXMM15）を使用します。これらのレジスタは、単精度浮動小数点数、倍精度浮動小数点数、または整数データを格納できます。
  • MOVOU 命令: MOVOU (Move Unaligned Oword) は、XMMレジスタの内容をメモリにストアする命令です。この命令は、メモリのアライメント（境界）を気にせずに128ビット（16バイト）のデータを転送できます。メモリクリアの文脈では、XMMレジスタにゼロを設定し、そのゼロをMOVOUでメモリに書き込むことで、16バイト単位でメモリをゼロクリアできます。
  • PXOR 命令: PXOR (Packed XOR) は、2つのXMMレジスタの内容をビット単位でXOR演算し、結果をデスティネーションレジスタに格納する命令です。PXOR X0, X0のように同じレジスタに対してXOR演算を行うと、そのレジスタの内容はすべてゼロになります。これは、XMMレジスタを効率的にゼロクリアする一般的な手法です。

4. CPUのマイクロアーキテクチャと性能

現代のCPUは非常に複雑なパイプラインとキャッシュシステムを持っています。

  • REP STOSQのようなマイクロコード化された命令は、CPU内部で複数のマイクロオペレーションに分解されて実行されます。これは、命令のデコードや実行のオーバーヘッドを引き起こす可能性があります。
  • 一方、SSE命令のような明示的なSIMD命令は、より直接的にハードウェアリソースを利用し、複数のデータ要素を並列に処理できるため、特定のタスク（メモリクリアなど）において高いスループットを発揮することがあります。
  • メモリのアライメントも性能に影響します。MOVOUはアライメントを気にしませんが、アライメントされたアクセス（MOVAPSなど）の方が高速な場合もあります。しかし、memclrの対象となるメモリは必ずしもアライメントされているとは限らないため、MOVOUが選択されるのは妥当です。

技術的詳細

このコミットの核心は、Goランタイムのmemclr実装において、x86アーキテクチャ（386およびamd64）でREP STOSQ命令の使用を廃止し、代わりにSSE命令であるMOVOUとPXORを組み合わせたアプローチを採用した点にあります。

REP STOSQの限界

REP STOSQは、その簡潔さから古くからメモリ操作に用いられてきましたが、現代のCPUではその性能特性が必ずしも最適ではありません。

  • マイクロコードの複雑性: REP STOSQは単一の命令に見えますが、CPU内部では複数のマイクロオペレーションに展開されます。この展開プロセスや、繰り返し処理の制御ロジックが、特に短いループやデータサイズの場合にオーバーヘッドとなることがあります。
  • パイプラインの停滞: CPUのパイプラインは、命令を連続的に処理することで高いスループットを実現します。しかし、REP STOSQのような長い実行時間の命令は、パイプラインをブロックし、後続の命令の実行を遅らせる可能性があります。
  • キャッシュ効率: REP STOSQは、キャッシュラインを効率的に利用しない場合があります。特に、書き込みパターンがキャッシュのプリフェッチ機構と合致しない場合、性能が低下することがあります。

SSE命令による最適化

新しい実装では、以下の手順でメモリクリアを行います。

  1. XMMレジスタのゼロクリア: PXOR X0, X0命令を使用して、XMM0レジスタをゼロで埋めます。XMMレジスタは128ビット幅なので、これにより16バイトのゼロデータが用意されます。
  2. 16バイト単位での書き込み: MOVOU X0, 0(DI)のような命令を繰り返し使用し、XMM0レジスタのゼロデータをメモリに16バイト単位で書き込みます。DIレジスタは書き込み先のメモリポインタを保持します。
  3. サイズの分岐処理: memclrの対象となるメモリサイズは様々であるため、新しい実装では、サイズに応じて異なる処理パスが用意されています。
    • 非常に小さいサイズ（1〜16バイト）の場合：バイト単位、ワード単位、ダブルワード単位、クアッドワード単位の通常のストア命令（MOVB, MOVW, MOVL, MOVQ）を組み合わせて処理します。これは、SSE命令のセットアップオーバーヘッドを避けるためです。
    • 中程度のサイズ（17〜256バイト）の場合：MOVOU命令を複数回使用し、16バイト単位で効率的にクリアします。例えば、32バイトをクリアするにはMOVOU X0, (DI)とMOVOU X0, -16(DI)(BX*1)のように2つのMOVOU命令を使用します。
    • 大きなサイズ（256バイト以上）の場合：clr_loopというループに入り、一度に256バイト（16バイト * 16回）をMOVOU命令で書き込みます。ループの最後に残ったバイトは、clr_tailセクションで処理されます。

ベンチマーク結果の分析

コミットメッセージに含まれるベンチマーク結果は、この変更の有効性を示しています。

benchmarkold ns/opnew ns/opdelta
BenchmarkMemclr5225-73.62%
BenchmarkMemclr16275-78.49%
BenchmarkMemclr64286-76.43%
BenchmarkMemclr256348-74.94%
BenchmarkMemclr409611284-24.73%
BenchmarkMemclr6553619021920+0.95%
  • 小規模なクリア（5〜256バイト）: 73%〜78%という劇的な性能向上が見られます。これは、REP STOSQのオーバーヘッドが大きかった小規模なクリアにおいて、SSE命令の効率が最大限に発揮されたことを示しています。SSE命令のセットアップコストは存在するものの、一度セットアップすれば16バイト単位で高速に処理できるため、この範囲で大きなメリットがあります。
  • 中規模なクリア（4096バイト）: 約25%の性能向上が見られます。このサイズでは、REP STOSQもそれなりに効率的ですが、SSE命令による並列処理が依然として優位性を示しています。
  • 大規模なクリア（65536バイト）: 性能はほぼ横ばい（わずかに悪化）です。これは、非常に大きなメモリ領域のクリアにおいては、REP STOSQがCPUの内部最適化（例えば、キャッシュライン全体を一度にクリアするような最適化）によって非常に効率的になるためと考えられます。また、このサイズになると、メモリ帯域幅がボトルネックになり、CPUの命令実行速度の差が相対的に小さくなる可能性もあります。コミットメッセージには「TODO: for really big clears, use MOVNTDQ.」とあり、これはさらに大きなクリアに対してはキャッシュを汚染しないノンテンポラルストア命令（MOVNTDQ）の使用を検討していることを示唆しており、大規模なクリアにおけるさらなる最適化の余地があることを示しています。

この変更は、Goランタイムの基盤となるメモリ操作の効率を向上させ、特にガベージコレクションの頻度が高いアプリケーションや、多数の小さなオブジェクトを扱うアプリケーションにおいて、全体的なパフォーマンス改善に貢献します。

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

このコミットにおける主要なコード変更は、Goランタイムのx86およびamd64アーキテクチャ向けのアセンブリファイルに集中しています。

  1. src/pkg/runtime/asm_386.s および src/pkg/runtime/asm_amd64.s からの runtime·memclr の削除:

    • これらのファイルから、従来のREP STOSL (386) および REP STOSQ (amd64) を使用したruntime·memclrの実装が削除されました。

  2. src/pkg/runtime/memclr_386.s の新規追加と実装:

    • 32ビットx86アーキテクチャ向けの新しいruntime·memclr実装が追加されました。
    • このファイルには、SSE2命令（PXOR, MOVOU）を用いたメモリクリアロジックが含まれています。
    • 様々なサイズ（1バイトから256バイト以上）に対応するための分岐処理が詳細に記述されています。

  3. src/pkg/runtime/memclr_amd64.s の新規追加と実装:

    • 64ビットx86アーキテクチャ向けの新しいruntime·memclr実装が追加されました。
    • こちらもSSE2命令（PXOR, MOVOU）を用いたメモリクリアロジックが中心です。
    • 386版と同様に、様々なサイズに対応するための分岐処理が記述されています。

  4. src/cmd/8a/lex.c, src/cmd/8l/8.out.h, src/liblink/asm8.c の変更:

    • アセンブラとリンカの定義にPXOR命令が追加されました。これは、GoのアセンブラがPXOR命令を認識し、正しくアセンブルできるようにするために必要です。

  5. src/pkg/runtime/alg.c の変更:

    • テスト用のラッパー関数runtime·memclrBytesが追加されました。これは、Goのテストコードからアセンブリで実装されたmemclrを呼び出すためのGo言語側のインターフェースです。

  6. src/pkg/runtime/export_test.go の変更:

    • memclrBytes関数がテストパッケージからアクセスできるようにエクスポートされました。

  7. src/pkg/runtime/memmove_test.go の変更:

    • memclrの新しいベンチマーク（BenchmarkMemclrX）と、memclrの正確性を検証するための新しいテストケース（TestMemclr）が追加されました。これにより、変更が正しく機能し、性能が向上したことを確認できます。

これらの変更により、memclrの低レベルな実装が、より現代的なCPUの特性に合わせた最適化されたアセンブリコードに置き換えられました。

コアとなるコードの解説

ここでは、src/pkg/runtime/memclr_amd64.s の主要な部分を例に、新しいmemclrの実装を解説します。memclr_386.sも同様のロジックですが、レジスタサイズや命令が32ビット用に調整されています。

// void runtime·memclr(void*, uintptr)
TEXT runtime·memclr(SB), NOSPLIT, $0-16
	MOVQ	ptr+0(FP), DI  // 第一引数: クリア対象のメモリポインタをDIレジスタにロード
	MOVQ	n+8(FP), BX    // 第二引数: クリアするバイト数をBXレジスタにロード
	XORQ	AX, AX         // AXレジスタをゼロクリア (バイト単位のクリア用)

	// MOVOU seems always faster than REP STOSQ.
clr_tail:
	TESTQ	BX, BX         // BX (残りバイト数) がゼロかチェック
	JEQ	clr_0          // ゼロなら終了

	// サイズに応じた分岐処理
	CMPQ	BX, $2
	JBE	clr_1or2       // 1または2バイトの場合
	CMPQ	BX, $4
	JBE	clr_3or4       // 3または4バイトの場合
	CMPQ	BX, $8
	JBE	clr_5through8  // 5から8バイトの場合
	CMPQ	BX, $16
	JBE	clr_9through16 // 9から16バイトの場合

	PXOR	X0, X0         // XMM0レジスタをゼロクリア (16バイトのゼロデータを作成)

	CMPQ	BX, $32
	JBE	clr_17through32 // 17から32バイトの場合
	CMPQ	BX, $64
	JBE	clr_33through64 // 33から64バイトの場合
	CMPQ	BX, $128
	JBE	clr_65through128 // 65から128バイトの場合
	CMPQ	BX, $256
	JBE	clr_129through256 // 129から256バイトの場合

	// TODO: use branch table and BSR to make this just a single dispatch
	// TODO: for really big clears, use MOVNTDQ.

clr_loop: // 256バイト以上の大きなクリアのためのループ
	MOVOU	X0, 0(DI)    // XMM0 (16バイトのゼロ) をメモリに書き込み
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, 64(DI)
	MOVOU	X0, 80(DI)
	MOVOU	X0, 96(DI)
	MOVOU	X0, 112(DI)
	MOVOU	X0, 128(DI)
	MOVOU	X0, 144(DI)
	MOVOU	X0, 160(DI)
	MOVOU	X0, 176(DI)
	MOVOU	X0, 192(DI)
	MOVOU	X0, 208(DI)
	MOVOU	X0, 224(DI)
	MOVOU	X0, 240(DI) // 合計16回のMOVOUで256バイトをクリア
	SUBQ	$256, BX     // 残りバイト数を256減らす
	ADDQ	$256, DI     // メモリポインタを256進める
	CMPQ	BX, $256     // 残りバイト数が256以上ならループを続ける
	JAE	clr_loop
	JMP	clr_tail     // 残りが256バイト未満になったら、残りの処理のためにclr_tailへジャンプ

// 小さいサイズのクリア処理 (末尾から書き込むことで、アライメントを考慮しつつ効率的に処理)
clr_1or2:
	MOVB	AX, (DI)         // 1バイト目をクリア
	MOVB	AX, -1(DI)(BX*1) // 残りのバイトをクリア (BXは残りバイト数)
clr_0:
	RET                      // 関数終了
clr_3or4:
	MOVW	AX, (DI)
	MOVW	AX, -2(DI)(BX*1)
	RET
clr_5through8:
	MOVL	AX, (DI)
	MOVL	AX, -4(DI)(BX*1)
	RET
clr_9through16:
	MOVQ	AX, (DI)
	MOVQ	AX, -8(DI)(BX*1)
	RET

// SSE命令を使った中程度のサイズのクリア処理 (末尾から書き込むことで、アライメントを考慮しつつ効率的に処理)
clr_17through32:
	MOVOU	X0, (DI)
	MOVOU	X0, -16(DI)(BX*1) // 16バイトをクリアし、残りを末尾からクリア
	RET
clr_33through64:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET
clr_65through128:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, -64(DI)(BX*1)
	MOVOU	X0, -48(DI)(BX*1)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET
clr_129through256:
	MOVOU	X0, (DI)
	MOVOU	X0, 16(DI)
	MOVOU	X0, 32(DI)
	MOVOU	X0, 48(DI)
	MOVOU	X0, 64(DI)
	MOVOU	X0, 80(DI)
	MOVOU	X0, 96(DI)
	MOVOU	X0, 112(DI)
	MOVOU	X0, -128(DI)(BX*1)
	MOVOU	X0, -112(DI)(BX*1)
	MOVOU	X0, -96(DI)(BX*1)
	MOVOU	X0, -80(DI)(BX*1)
	MOVOU	X0, -64(DI)(BX*1)
	MOVOU	X0, -48(DI)(BX*1)
	MOVOU	X0, -32(DI)(BX*1)
	MOVOU	X0, -16(DI)(BX*1)
	RET

解説のポイント

  1. 引数の取得: ptr+0(FP)とn+8(FP)は、それぞれ関数に渡されたポインタとバイト数をスタックフレームから取得しています。
  2. XORQ AX, AX: これは、後でバイト単位のクリアが必要になった場合に備えて、AXレジスタをゼロに初期化しています。
  3. clr_tailと分岐: 関数はまずclr_tailラベルにジャンプします。これは、残りのバイト数を処理するための共通のエントリポイントです。BX（バイト数）がゼロであれば即座に終了します。
  4. サイズに応じた最適化:
    • 小サイズ（1〜16バイト）: CMPQ BX, $XとJBE（Jump Below or Equal）命令を使って、バイト数に応じて適切な処理パスに分岐します。これらのパスでは、MOVB（バイト）、MOVW（ワード）、MOVL（ダブルワード）、MOVQ（クアッドワード）といった通常のストア命令を組み合わせてメモリをクリアします。これは、SSE命令のセットアップコストを避けるためです。特に注目すべきは、MOVB AX, -1(DI)(BX*1)のように、末尾から書き込むことで、アライメントを考慮しつつ効率的に処理している点です。
    • SSE2のチェックと初期化: PXOR X0, X0は、XMM0レジスタをゼロで埋めます。これは、16バイトのゼロデータを効率的に作成するSIMD命令です。386版ではruntime·cpuid_edx(SB)をチェックしてSSE2が利用可能かを確認していますが、amd64ではSSE2が必須であるため、このチェックは省略されています。
    • 中サイズ（17〜256バイト）: MOVOU命令を複数回使用して、16バイト単位でメモリをクリアします。ここでも、末尾からの書き込みを組み合わせることで、アライメントを気にせず効率的に処理しています。
    • 大サイズ（256バイト以上）: clr_loopに入り、一度に256バイト（16バイト * 16回）をMOVOU命令で書き込みます。ループの最後に残ったバイトは、再度clr_tailにジャンプして処理されます。
  5. MOVOU命令の利用: MOVOUはアライメントされていないメモリへのアクセスを許可する命令であり、memclrの対象となるメモリが常に16バイト境界にアライメントされているとは限らないため、この命令が選択されています。

このアセンブリコードは、Goランタイムが特定のハードウェア特性（この場合はx86のSSE命令）を最大限に活用し、一般的な操作のパフォーマンスを最適化するために、いかに低レベルなチューニングを行っているかを示す好例です。

関連リンク

  • Go CL (Code Review) へのリンク: https://golang.org/cl/60090044

参考にした情報源リンク

  • Intel 64 and IA-32 Architectures Software Developer's Manuals:
    • Volume 2A: Instruction Set Reference, A-M (MOVOU, PXOR, REP STOSQなどの命令の詳細)
    • Volume 2B: Instruction Set Reference, N-Z
    • Volume 3A: System Programming Guide, Part 1 (CPUのマイクロアーキテクチャ、パイプライン、キャッシュに関する情報)
  • Agner Fog's optimization manuals:
    • "Optimizing software in C++" や "Assembly optimization manual" など、x86アセンブリのパフォーマンスに関する詳細な情報が提供されています。特に、REP STOS命令の性能特性や、SIMD命令の効率的な利用方法について言及されています。
    • https://www.agner.org/optimize/
  • Stack Overflow / 技術ブログ:
    • REP STOSQとSSE命令のパフォーマンス比較に関する議論やベンチマーク結果を扱った記事。
    • 例: "Why is REP STOS faster than a loop of MOV instructions?" (ただし、このコミットでは逆の結論が出ている点に注意)
    • 例: "Optimizing memset with SSE/AVX"
  • Web検索結果:
    • REP STOSQとSSE MOVOUのパフォーマンス比較に関する詳細な情報。特に、メモリブロックのサイズ、アライメント、CPUアーキテクチャによって最適な選択が異なることが強調されています。現代のCPUではREP命令も高度に最適化されており、大規模なメモリ操作では非常に効率的である一方、小規模から中規模の操作ではSIMD命令が優位に立つことが示されています。